Как из одной прикольной фигни сделать еще более прикольную фигню или функциональный язык на коленке

«Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою.»
К.Прутков

Однажды, бесцельно тратя рабочее время и деньги работодателя с помощью серфинга интернета, наткнулся я на описание языка Whenever и на некоторое время был очарован. Язык поражает своей безумной простотой. Принципы его таковы:

1) Строки кода программы обязательно будут исполнены когда-нибудь, однако порядок их исполнения вообще никак не связан с порядком, в котором они записаны.
2) Переменные? У нас нету даже контроля за порядком исполнения, нам не нужны никакие переменные.
3) Структуры данных? Да вы шутите!

То есть программа трактуется как набор (пул) строк на выполнение и интерпретатор выбирает оттуда строку наугад, выполняет ее команды и выкидывает из пула. И так пока в пуле ничего не останется. Надо признать, что автор сего безумия почти выдержал концепцию. Почти, потому что все же организовать порядок выполнения в программе можно, так же, как и завести переменные, используя возможность добавления строк в пул выполняемых.

Итак, в языке есть следующие конструкции:

Строка кода вида

line-number statement;

Выражения состоят из команд, перечисленных через запятую. Среди них:
Номер строки

line-number#number-of-times-to-add/remove

Например команда в строке 1

1 4,5#3,-6;

Добавит в пул выполнения 1 строку с номером 4, 3 строки с номером 5 и уберет из пула строку с номером 6.

Заметим, что программа с бесконечным циклом будет выглядеть лаконично и потому гениально

1 1;

Интерпретатор будет выбирать из пула первую строку (никакой другой там больше нет) и добавлять ее же обратно в пул. Между прочим, очень полезная конструкция, как будет видно далее.

Вывод на экран

Просто команда print, печатающая то, что в скобках, на экран.

Кроме этих команд есть следующие конструкции:

defer
Если выражение в скобках вернет «истина», то команда не будет выполнена, а строка вернется обратно в пул. Например

1 defer (2) 3;

Пока в пуле присутствует строка 2, команда на добавление в пул строки 3 выполнена не будет.

again
Если выражение в скобках вернет «истина», то команда будет выполнена, но строка вернется в пул. Например:

1 again (2) 3;

Строка 3 будет добавлена в пул всегда, но если в пуле есть строка 2, то строка 1 не будет удалена после этого из пула.

Замечу, что выражение (2) эквивалентно ( N(2) > 0 ), где N() — функция, возвращающая количество строк назвонного номера в пуле.

forget
Если выражение в скобках вернет «истина», то команда не будет выполнена и строка будет удалена из пула. Например:

1 forget(2) 3;

Автор языка выкинул это выражение из языка, но мне пришлось его вернуть, о чем ниже.

again, defer & forget можно комбинировать, но каждый из модификаторов должен встречаться в строке только один раз.

Собственно все, весь язык. На сайте с описанием языка приводятся две программы:

99 бутылок пива

1 defer (4 || N(1)<N(2) && N(2)<N(3)) print(N(1)+" bottles of beer on the wall, "+N(1)+" bottles of beer,");
2 defer (4 || N(1)==N(2)) print("Take one down and pass it around,");
3 defer (4 || N(2)==N(3)) print(N(1)+" bottles of beer on the wall.");
4 1#98,2#98,3#98;

и Числа Фиббоначи (вычисляет ряд Фиббоначи от 1 до 100го элемента… ну… если дождетесь):

1 again (1) defer (3 || N(1)<=N(2) || N(7)>99) 2#N(1),3,7;
2 again (2) defer (3 || N(2)<=N(1) || N(7)>99) 1#N(2),3,7;
3 defer (5) print(N(1)+N(2));
4 defer (5) print("1");
5 4,-3,7;
6 defer (4) 3;
7 7;
8 defer (N(7)<100) -1#N(1),-2#N(2),-7#100,-3;
9 defer (3 || 6) 1,3;

Если первая программа — чистое баловство, то вторая делает что-то осмысленное и это удивительно. Казалось бы — из такого баловства ничего путнего выйти не может по определению. Однако же — вот оно.

И вот мне захотелось что-то с этим всем сделать. Результат получился несколько неожиданый, но обо всем по порядку.

Сразу бросется в глаза, что в этих программах неудобно: чтобы вычислить ряд Фиббоначи не до сотого, а, допустим, до 20го элемента, в программе надо поменять текст в четырех местах. Это как-то напрягает. Сделаем так, чтобы программа могла принимать входные параметры. Например так:

1 again (1) defer (3 || N(1)<=N(2) || N(7)>( @1 - 1 )) 2#N(1),3,7;
2 again (2) defer (3 || N(2)<=N(1) || N(7)>( @1 - 1 )) 1#N(2),3,7;
3 defer (5) print(N(1)+N(2));
4 defer (5) print("1");
5 4,-3,7;
6 defer (4) 3;
7 7;
8 defer (N(7)<@1) -1#N(1),-2#N(2),-7#100,-3;
9 defer (3 || 6) 1,3;

Сохраним текст программы в файлик fib.src. Вызов программы будет выглядеть так:
java -cp Whenever.jar Whenever fib.src 20

Уже хорошо. Чтобы закрепить успех, я написал программу поиска наибольшего общего делителя двух натуральных чисел, вот она:

1 defer(2) again(N(3) - (N(3)/N(4))*N(4) != 0) 6#N(3),-3#N(3),3#N(4),-4#N(4),4#(N(6) - (N(6)/N(3))*N(3)),-6#N(6);
2 3#( @1 - 1 ),4#( @2 - 1 ),-6;
3 3;
4 4;
5 defer(1) print("NOD of " + @1 + " and " + @2 + " is " + N(4)),-3#N(3),-4#N(4);
6 6;

При вызове программы требуется указать два числа, причем сперва большее, потом меньшее. Разберем эту программу;

Строки 3 и 4 используются как ячейки памяти для хранения двух чисел. Точнее как переменные используется число вхождений в пул соответственных строк. Строка 6 используется как промежуточная переменная тем же извращенным способом (язык не оставляет другого).
Строка 2 запускает весь процесс. Она добавляет в пул N строк 3 и M строк 4 и удалет из пула строку 6. После чего удаляется из пула навсегда.
Строка 1 собственно делает всю работу. Выполнение строки 1 откладывается до момента пока в пуле присутствует строка 2 (defer(2)). Кроме того строка НЕ выкидывается из пула до момента нахождения НОД (again). Выражение в скобках даст остаток от деления количества строк 3 на количество строк 4 (используется целочисленная математика). Собственно действия в строке 1 выполняются слева направо:

1. Добавляется в пул столько строк 6, сколько на данном шаге в пуле строк 3
2. Убираются из пула все строки 3
3. Добавляется столько строк, сколько в данным момент строк 4 (эти две команды можно схлопнуть в одну -3#(N(3) — N(4))
4. Убираем все строки 4
5. Добавляем строки 4 в количестве == остатку от деления бОльшего числа на меньшее. Опять же эти две команды можно схлопнуть в одну.
6. Убираем из пула все строки 6 (скрипач не нужен)

Строка 5 выводит на экран результат и чистит за собой, удаляя из пула все, что там осталось. Ее выполнение откладывается до тех пор, пока в пуле присутствует строка 1, а она будет находиться там до момента нахождения НОД. Замечу, что в оригинальной версии языка print не может комбинироваться с другими командами, там надо было бы писать

5 defer(1) print("NOD of " + @1 + " and " + @2 + " is " + N(4));
....
7 defer(5) -3#N(3),-4#N(4);

Ага, подумал я. А давай-ка сделаем так, чтобы при добавлении строки в пул ей можно было передавать параметры. Поскольку круглые скобки и запятые уже используются в синтаксисе и сильно все переписывать не хотелось, я задействовал квадратные скобки и знак процента % для разделителя параметров.

Здесь возникает одна тонкость. При добавлении строки в пул на самом деле должна создавться другая строка с новым номером, а не увеличиваться количество выполнений для уже существующей. (На самом деле для «чистоты» надо для строк с одинаковыми параметрами как раз увеличивать число выполнений, но я пока этого не реализовал).

Тут у меня неожиданно возникло еще одно измерение, еще одна переменная — текущий номер строки. Для того, чтобы можно было его использовать я ввел еще одно ключевое слово — self.

Ура! Можно что-нибудь теперь сделать полезное. Например, переписать тот же ряд Фиббоначи:

1 forget(self>@3) print("iter: " + self + " value: " + @1 ),1[@1+@2%@1%@3];

В программу передаются три параметра — 1, 0 и номер числа, до которого надо вычислять. По хорошему значимым является только третий параметр и программу можно переписать так, чтобы она принимала только его. Тогда, кстати, можно будет избавиться от self, но программа ужасно разрастется до целых двух строк, а это не очень красиво.

Замечания: мне пришлось 1) восстановить в правах forget и 2) сделать так, чтобы print выполнялся в ряду других команд (в оригинале мог быть только либо принт, либо другие команды).

А вот и НОД:

1 forget( @2 == 0 ) 1[@2%(@1 - (@1 / @2) * @2)],2[@2%(@1 - (@1 / @2) * @2)];
2 forget( @2 > 0 ) print("Nod is: " + @1 );

Опять же можно сделать, чтобы выполнение не зависело от того каким номером идет бОльший параметр, но мне лень.

И на закуску, проверка является ли число простым:

1 defer(5) forget( @2 == 0 || @2 == 1 ) 4[@1%(@2 - 1)],2[@1%(@2 - 1)],3[@1%(@2 - 1)];
2 defer(5) forget( @2 == 0 || @1 != (@1 / @2) * @2 || @1 == @2 || @2 == 1 ) print( "Number " + @1 + " is not prime");
3 defer(5) forget( @2 != 1 ) print( "Number " + @1 + " is prime");
4 defer(5) forget( @2 == 0 || @1 == (@1 / @2) * @2 ) 1[@1%@2];
5 1[@1%@1];

Здесь я использую еще один трюк: если параметр не указан, он становится равным нулю.

Вот такие пирожки с котятами. Что-то мне подсказывает, что можно попробовать решать комбинаторные задачки с помощью этой фигни. Но придумывать решения пока лень. Хотя…