Unlambda — мозги навыворот

Давно тешил себя мыслью, что пойму функциональное программирование. Недавно выпустил эту мысль на волю.
Я несколько раз пытался писать на lisp/scheme и даже немного на clojure. Но это все не серьезно.
И вот я узнал о языке, который мне СОВЕРШЕННО НИКАК в жизни не пригодится и я СОВЕРШЕННО НИЧЕГО на нем не смогу написать.
Это самый бесполезный, непонятный, нечитабельный язык. Даже хуже brainfuck.

Итак, встречайте…

Unlambda

Это почти чистый функциональный язык. Я не владею терминами ФП, поэтому говорить о том, что он использует комбинаторную логику как вид лямбда-исчисления, я не стану. Также этот язык считается полным по Тьюрингу.

Все, с чем работает Unlambda — это функции. Каждая функция имеет ровно один аргумент. Помимо функций у языка есть еще всего один оператор: ` (обратная кавычка). Этот оператор означает «применить» («apply»). Встретив такой символ, интерпретатор должен выполнить идущую за ним функцию.

Имена функций состоят из одной буквы. Именованных функций мало. Мы рассмотрим всего три-четыре (самых основных и необходимых — язык оказывается еще каким-то странным образом развивается).

Самая простая и невписывающаяся в идеологию языка — это функция вывода символа на экран. Функция описывается точкой. Такая функция, когда её выполнят с помощью оператора-кавычки, выведет на экран идущий за ней символ, например .x напишет «x», а .* нарисует звездочку. Почему же не вписывается в идеологию? Да потому что эти самые «иксы» и «звездочки» — это не аргументы функции. Это просто хак, для того чтобы сделать для чисто функционального языка в вакууме, который что-то вычисляет, функцию вывода.

Итак, есть еще функция i. Она принимает один аргумент, и возвращает его же. Т.е. `ix в результате выполнения вернет x.
Не понимаете зачем это может понадобится? Хе-хе!

А вот еще функция k. Она принимает уже два аргумента и… Как это может быть? Да, я говорил что функции принимают по одному аргументу. В Unlambda применяют подход «карринга». Т.е. если функция K принимает в действительности один аргумент, затем возвращает функцию, которая запоминает этот аргумент, и принимает еще один. Так вот получается, что в итоге K принимает как бы два аргумента. Вызывать такую конструкцию (функций-то уже как бы две) надо так: ``kxy, т.е. вызвать k(x), и ту функцию которую он вернет (скажем kx) вызвать как kx(y). Так вот, функция ``kxy принимает два аргумента и возвращает первый (x). Тоже странно?

Ну и напоследок, функция s. У неё уже три аргумента. В итоге, функция ```sxyz применяет функцию x к z, затем y к z, и потом применяет полученные в итоге функции друг к другу. Т.е. эквивалент ```sxyz — это ``xz`xz:

# В только что придуманном мною псевдокоде функция S выглядит так
s(x,y,z):
  a = x(z);
  b = y(z);
  return a(b);

Все. Тоже непонятно? Давайте начнем с вывода звездочки на экран. А потом возьмем, да и напишем свой интерпретатор языка Unlambda.

Для вывода звездочки нужна примерно такая программа: `.*i. Буквально: выполни функцию печати звездочки с аргументом — функцией i. Функция i, конечно, не будет выполнятся (у нас же только одна кавычка, а значит и одно выполнение). Роль функции i — просто выступать в качестве необходимого аргумента для функции вывода. Заметим, что аргументы функции проверяются только во время её вызова (через кавычку). До тех пор — можно писать что угодно.

Интерпретатор

Реализация языка на самом деле простая. Но если вам не знаком язык Go, или вы не любите писать свои интерпретаторы, то можете пропустить эту главу.
Итак, есть функции, есть оператор. Давайте обобщим эти два понятия и назовем это «выражением». Т.е. выражение — это либо оператор «применить», либо функция. Для выражения «применить» надо помнить выражение, которое применяем и его аргумент (тоже выражение). Для выражения-функции надо помнить только функцию. Получаем структуру:

type Expression struct {
	f   *Expression
	x   *Expression
	fn  *Function
	exp int // тип выражения - APPLY или FUNC
}
// Создаем новое выражение "apply"
func NewApplyExp(f *Expression, x *Expression) (e *Expression) {
	e = new(Expression)
	e.f = f
	e.x = x
	e.exp = EXPRESSION_APPLY
	return
}
// Создаем новое выражение-функцию
func NewFuncExp(f *Function) (e *Expression) {
	e = new(Expression)
	e.fn = f
	e.exp = EXPRESSION_FUNC
	return
}
// Выполняем выражение. "Apply" вернет нам результат, а выражение-функция вернет саму функцию.
func (e *Expression) Eval() (f *Function) {
	switch e.exp {
	case EXPRESSION_FUNC:
		return e.fn
	case EXPRESSION_APPLY:
		return e.f.Eval().ApplyTo(e.x.Eval())
	}
	panic("Bad expression")
}

Например, конструкция `.xi будет представлена выражениями:

f1 = FUNC(.x)
f2 = FUNC(i)
e1 = APPLY(f1, f2)

Сами же функции выглядят тоже достаточно просто:

type Function struct {
	x    *Function // аргумент 1
	y    *Function // аргумент 2
	rune int       // символ который надо вывести. Только для функции-точки
	fn   int       // код функции: I/S/K/DOT
}

// Creates a new function with the given operator code
func NewFunc(code int) (f *Function) {
	f = new(Function)
	f.fn = code
	return
}

// Creates a new dot-function, that will print a given rune
func NewDotFunc(rune int) (f *Function) {
	f = new(Function)
	f.fn = FUNCTION_DOT
	f.rune = rune
	return
}

func (f *Function) ApplyTo(x *Function) (res *Function) {
        // Тут выполняется функция f с аргументом x
}

Чтобы реализовать карринг, добавим несколько вспомогательных функций. Так, функция K возвращает функцию K1, которая делает всю работу, а функция S возвращает S1, которая потом возвращает S2. Вот как это отразится на ApplyTo:

func (f *Function) ApplyTo(x *Function) (res *Function) {
	switch f.fn {

	// I-function just returns its operand
	case FUNCTION_I:
		return x

	// K-function returns its first operant, but takes two of them
	case FUNCTION_K:
		res = new(Function)
		res.x = x
		res.fn = FUNCTION_K1
		return res
	case FUNCTION_K1:
		return f.x

	// S-function takes 3 operands and applies 1st to the 3rd, and 2nd to the 3rd
	case FUNCTION_S:
		res = new(Function)
		res.x = x
		res.fn = FUNCTION_S1
		return res
	case FUNCTION_S1:
		res = new(Function)
		res.x = f.x
		res.y = x
		res.fn = FUNCTION_S2
		return res
	case FUNCTION_S2:
		return f.x.ApplyTo(x).ApplyTo(f.y.ApplyTo(x))

	// Dot-function prints a single rune
	case FUNCTION_DOT:
		print(string(f.rune))
		return x
	}
	panic("Bad function code")
}

Весь код интерпретатора (в нем не хватает еще парсера) можно найти здесь. Собираем, запускаем.

Изучаем подробнее

Теперь у нас есть на чем тестировать выражения. Пишем hello world:

`````.h.e.l.l.oi

Меня хватило только на hello. У функции .h аргументом является .e.l.l.oi. Выполнив эту функцию, на экране появляется буква h, и следом выполняется функция-хвостик. Она пишет «e», и возвращает .l.l.oi. Так длится до функции .oi, которая пишет «о», и возвращает i. Больше нет операторов выполнения (их было всего пять), программа останавливается.

Несмотря на примитивность, Unlambda — язык избыточный. В нем больше 20% функций — не нужны. А именно, функция «i». Потому что iX это то же самое, что и skkX: ```skkX = ``kX`kX = `kxkx = x

Я пока остановлюсь. Хотел рассказать, как работает программа, рисующая числа фиббоначи, но… Вообщем вот она:

```s``s``sii`ki
  `k.*``s``s`ks
 ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
  `k``s`ksk

На нашем интерпретаторе она работает, и рисует строчки из звездочек (кол-во звездочек = число). Как это происходит — я уже не понимаю.

Напоследок скажу, что с помощью S/K функций можно описывать числа как глубину рекурсии(Church Integers), булевы значения (аналогично) и делать конструкции типа if-then-else. Может быть когда нибудь я вам об этом тоже расскажу. Жаль, что я к тому времени уже утрачу рассудок, буду общаться с духами и возможно покину этот слишком материальный мир.

Реклама

One comment on “Unlambda — мозги навыворот

  1. Ation:

    Если нечем мозг занять — учи плюсы и метапрограммирование. Отладка и поиск ошибок прямо на этапе компиляции =)

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s