<svg xmlns="http://www.w3.org/2000/svg"
	viewBox="0,0 5,5"
<path d="M0,0 L5,0 L5,2 L4,2 L4,1 L1,1
	L1,4 L4,4 L4,3 L5,3 L5,5 L0,5 Z" />
<path d="M2,2 L2,3 L3,3 L3,2 Z">
<animateMotion begin="mouseover" restart="whenNotActive"
	keyPoints="0; .5; .5; 1"
	keyTimes="0; .36; .64; 1"
	keySplines=".5 0 .5 1; 0 0 1 1; .5 0 .5 1"
	path="M0,0 L2,0 Z" />

Я понял. Надо просто переместить:

  • феминисток - в Саудовскую Аравию;
  • борцов с изменением климата - в Китай;
  • антивакцинаторов - в Африку;
  • коммунистов, социалистов и прочих леваков - в Россию;
  • мечтающих о возвращении Сталина - в лагеря;
  • борцов за признание Палестины - в Палестину.

А также:

  • обложить стопроцентным налогом на наследство приверженцев этой идеи;
  • посадить за расизм применяющих закон в зависимости от расы нарушителя;
  • отправить в газовую камеру тех, кому наплевать на базовые права человека;
  • снять замки и забрать ключи у борцов за открытые границы;
  • запретить распространять свои гены противникам ГМО;
  • поселить лобковых вшей на лобок защитникам прав животных.

Ну и так далее. Теоремой Геделя навеяло.

Большие новости!

Я доделал needed reduction на веревочках, почистил лямбду от уродской waiting construct, сделал closed reduction дефолтным алгоритмом и обновил браузерную демку. Там теперь есть бесконечная прокрутка для дебага. Зацените рюшечки:


Приятно иметь калькулятор в браузере, который одновременно печатает полную βη-нормальную форму для любого бестипового λK-терма и при этом считает 10 2 2 1 в цифрах Черча за долю секунды на моем Хромбуке.

Напомню, что 21024 примерно в (1017)4 раз больше, чем гиперобъем пространства-времени всей наблюдаемой вселенной с момента большого взрыва в планковских единицах измерения, в наши дни имеющий порядок (1060)4 планковских единиц.

I am currently working on implementing needed reduction for interaction nets. To do that, I first needed to refactor a lot of somewhat ugly fast-written code in inet-lib. At some point, I changed retrieving an element from an array to .pop() from .shift(), just because in JavaScript the former happens to be a cheaper operation than the latter.

Many commits later, I decided to play with the program a little bit and compare performance between .shift()ing and .pop()ing. Boom! The program appeared to be broken. Even worse, invariance of the queue that is represented by that array with respect to the order in which it is processed is the whole point of interaction nets, namely the property of strong confluence also known as the one-step diamond property. I thought I fucked up hard.

First, I took a look at git-blame(1) for the line of code that calls .pop(), and found the corresponding commit. Then, I marked its parent commit as good with git-bisect(1). After a few steps, git-bisect(1) found the first bad commit.

Evidently, the problem had something to do with indirection applied by non-deterministic extension of interaction nets. And it did not take more than a couple of minutes to figure out a simple one-liner fix.

Overall, it took less than half an hour from finding a bug to fixing it which I first thought would take hours if not days. To me, it looks like yet another evidence that the idea of git-bisect(1) is totally genius. So, thanks again, Linus!

P. S. Free advice: when making commits, it is always useful to keep in mind 1) a possible need to git-grep(1) some lines of code later, and 2) almost inevitable need to deal with bugs which is a lot easier when commits are suitable for git-bisect(1).

Parallel needed reduction for pure interaction nets

Reducing interaction nets without any specific strategy benefits from constant time per step. On the other hand, a canonical reduction step for weak reduction to interface normal form is linear by depth of terms. In this paper, we refine the weak interaction calculus to reveal the actual cost of its reduction. As a result, we obtain a notion of needed reduction that can be implemented in constant time per step without allowing any free ports and without sacrificing parallelism.

$ npm install -g @alexo/lambda
└── @alexo/lambda@0.1.6 

$ lambda -e 'S hello bye world'
hello world (bye world)
$ lambda -de 'x: (x: x) v1 x'
\read_{[ ]}(\print) = \lambda(w1, \apply(\apply(\lambda(w2, w2), \atom_{v1}), w1));
\apply(\apply(\lambda(w2, w2), \atom_{v1}), \atom_{v2}) = \read_{v2: [ ]}(\print);
\apply(\lambda(w2, w2), \atom_{v1}) = \lambda(\atom_{v2}, \read_{v2: [ ]}(\print));
\lambda(w2, w2) = \lambda(\atom_{v1}, \lambda(\atom_{v2}, \read_{v2: [ ]}(\print)));
\lambda(\atom_{v2}, \read_{v2: [ ]}(\print)) = \atom_{v1};
\atom_{v2} = \read_{v1 [ ]}(\read_{v2: [ ]}(\print));
\read_{v2: [ ]}(\print) = \atom_{v1 v2};
\print = \atom_{v1};
$ npm explore -g @alexo/lambda -- sh test.sh
SAMPLE             NORMAL          CLOSED         OPTIMAL        ABSTRACT
counter             54(7)           58(6)          145(4)             N/A
w2eta             125(20)         137(16)          208(7)           38(7)
22210ii               N/A       1740(182)        7918(70)         732(70)
3222ii                N/A       5896(545)      164474(43)        1183(43)
1022ii                N/A     23026(2085)     2490504(59)        4299(59)
4222ii                N/A 1442259(131124)             N/A      262402(64)
222210ii              N/A 6685119(655415)             N/A    2359813(201)
cfact4         8605(1028)      18606(887)      96676(691)      13985(691)
yfact4        92395(4833)     53519(1741)     659727(760)      16611(760)
cfact5      170958(16917)   895848(16170)  5906411(13462)   287527(13462)
yfact5      783031(43651)  1371216(22267)             N/A   291418(13550)

Только что опубликовали IEEE 1003.1-2008+TC1+TC2.

В список участников TC2 мое имя попало в связи с багами 735-737 против TC1:


Теперь грамматика языка Shell не содержит shift/reduce-конфликтов (можно засунуть ее в yacc(1) и убедиться, раньше было пять конфликтов), лишена двух лишних правил, а также корректно описывает произвольное количество команд в скриптах.

Token-passing Optimal Reduction with Embedded Read-back
Anton Salikhmetov

We introduce a new interaction net implementation of optimal reduction for the pure untyped lambda calculus. Unlike others, our implementation allows to reach normal form regardless of the interaction net reduction strategy using the approach of so-called token-passing nets and a non-deterministic extension for interaction nets. Another new feature is the read-back mechanism implemented without leaving the formalism of interaction nets.

In Andrea Corradini and Hans Zantema: Proceedings 9th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2016), Eindhoven, The Netherlands, April 8, 2016, Electronic Proceedings in Theoretical Computer Science 225, pp. 45–54.
Published: 10th September 2016.

The Tonnetz is a lattice diagram representing tonal space. It can be used to visualize harmonic relationships in music. Each node in the diagram corresponds to one of the twelve tones and is connected to six adjacent tones that are related to it by a major third, a minor third, or by a perfect fifth, depending on their relative position in the diagram.

I forked on GitHub the source code of TonnetzViz created by Ondřej Cífka and implemented the following features:

  • zero configuration without any menus;
  • Tonnetz-like keyboard layout;
  • Shepard tones using Web Audio;
  • plug and play Web MIDI support;
  • blue minor and red major triads;
  • Tonnetz bent to represent halftones;
  • Shift key to sustain notes;
  • and arrow keys to transpose.

Now the live version is available at


Most Popular Tags


RSS Atom

May 2017

1415 1617181920
Powered by Dreamwidth Studios