Unlambda

Unlambda — минимальный функциональный язык программирования, придуманный Дэвидом Мэдором (David Madore). Он основан на комбинаторной логике, варианте Лямбда-исчисления, который опускает оператор lambda. Язык полагается в основном на две встроенные функции (s и k) и оператор аппликации (`). Уже это делает язык полным по Тьюрингу, но в нём также есть несколько функций ввода/вывода для возможности взаимодействия с пользователем, функция для ленивых вычислений и короткие эквиваленты некоторых функций.

Будучи эзотерическим языком программирования, Unlambda предназначена для демонстрации очень чистого функционального языка, а не для практического использования. Главная особенность — отсутствие обычных операторов и типов данных — функции от одного аргумента являются единственным типом данных. Несмотря на это, данные могут быть воспроизведены при помощи соответствующих функций, как в лямбда-исчислении. Функции нескольких аргументов могут быть представлены при помощи карринга.

Unlambda основана на принципе исключения абстракций (abstraction elimination) или исключения всех сохранённых переменных, включая функции. Как в чисто функциональном языке, в Unlambda функции не только являются объектами первого рода (first-class object), но и единственными объектами первого рода.

Hello World!

Пример программы Hello world выглядит так:

`r```````````.H.e.l.l.o. .w.o.r.l.di

Запись .x указывает на функцию, которая принимает один аргумент и возвращает его неизменным, также в качестве побочного эффекта печатая символ «x» при вызове. i представляет вариант тождественного отображения, у которой нет побочных эффектов и которая используется как фиктивный аргумент. Программа `.di применяет функцию .d, печатающую символ «d», к аргументу i, возвращая i и печатая «d» как побочный эффект. Аналогично ``.l.di сначала применяет .l к .d, печатая «l» и возвращая .d, которая потом применяется к i как в предыдущем примере. Функция r — синтаксический сахар к функции, печатающей символ новой строки.

s и k

Другие важные элементы Unlambda включают в себя функции k и s, двух и трёх аргументов соответственно (передаваемых при помощи карринга). k производит функции-константы: результат `kx — функция, при вызове возвращающая x. Так значением ``kxy будет x для любых x и y.

s — обобщённый оператор вычисления (evaluation operator). ```sxyz вычисляется в ``xz`yz при любых x, y и z. Примечательно, что s и k достаточно для произведения любых вычислений (подробнее см. SKI-исчисление). В качестве краткого примера можно привести, что функция отображения i может быть выражена как ``skk, так как ```skkx возвращает x при любом x.

Управляющая конструкция

Единственной управляющей конструкцией Unlambda является продолжение, обозначаемое символом c. Когда выражение вида `cx вычисляется, образуется специальный объект «продолжение», представляющий состояние интерпретатора в данный момент. Тогда вычисляется x и результат вычисления передается продолжению как аргумент. Но если продолжение применяется к y, тогда выполнение x сразу же прерывается и значением выражения `cx является y.

Ленивые вычисления

Хотя вычисления в Unlambda обычно «энергичные» (дословный перевод англоязычного термина eager evaluation; то есть значение аргумента вычисляется перед передачей в функцию), есть возможность ленивых вычислений, обозначаемая оператором d. Обычно для вычисления выражения вида `xy, Unlambda сначала вычисляет x, затем y и после этого применяет x к y. Если же значением x будет d, тогда y не вычисляется. Значение выражения `dy — специальный объект отложенного вычисления, который, когда применяется к аргументу z, вычисляет y и тогда применяет полученное значение к z. Стоит заметить, что при отсутствии побочных эффектов это то же самое, что `iy. Разница в том, что `y выполняет любые побочные эффекты в y незамедлительно, тогда, как `dy откладывает их, пока результат не будет применён к другому аргументу.

v

Функция v принимает аргумент, игнорирует его и возвращает v. Она может быть применена к любому количеству аргументов. В v нет необходимости, поскольку она может быть выражена как ```sii``s`kk``sii (то есть $s \left(i,i,s\left(k\left(k\right),s\left(i,i\right)\right)\right)$), но присутствует для удобства (а также для ускорения работы интерпретатора).

Ввод / вывод

Ввод в Unlambda обеспечивается операторами @ и ?u. Когда @ применяется к функции x, символ считывается со ввода и сохраняется как «текущий символ» (current character), затем x применяется к i. Если нет больше символов на вводе, то «текущий символ» остаётся неопределённым. Когда функция ?u применяется к x, результатом будет вычисление `xi, если текущим символом является u, иначе вычислится `xv.

Также есть функция печати текущего символа — |. При вычислении `|x функция x применяется к .u, если u текущий символ, иначе к v, если текущий символ неопределён.

Выход

И в заключение имеется оператор выхода — e. Когда e применяется к x, исполнение программы прерывается, и x возвращается как результат программы (большинство существующих интерпретаторов его игнорируют).

См. также

• Аппликативный подход к программированию

Ссылки

• Домашняя страничка Unlambda