JITиё моё

Этот пост посвящаю хорошему человеку и хорошему программисту — Ярославу, недавно реализовавшему свой первый Brainfuck-интерпретатор.

Итак, все мы любим компиляторы и виртуальные машины. Некоторые из них считаются круче, потому что в них есть JIT. А что же такое этот JIT?

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

А как это работает внутри? Вот об этом и поговорим.

Brainэтосамое

Итак, напишем свой JIT компилятор для Самого Простого Языка. Сложнее языки я не потяну, да и лень, а еще проще… Ну проще просто не бывает.

Дано. Инструкции <, > = сдвинуть указатель влево-вправо; +, — = увеличить/уменшить на 1 значение по указателю, [ и ] — начало и конец цикла (в цикл входим если значение по указателю не равно нулю). Еще есть точка и запятая — для ввода и вывода символов.

Простой не-JIT интерпретатор пишется легко (хотя и погружает вас в мистический мир виртуальных машин и всего такого):

char m[9999],*n[99],*r=m,*p=m+5000,**s=n,d,c;main(){for(read(0,r,p)
;c=*r++;c-93?c-91?d?0:c-43&~2?c-44?c-46?p+=c&~2^60?0:c%4-1:write(1,
p,1):read(2,p,1):(*p-=c-44):d++||(*++s=r):d&&--d?0:*p?r=*s:--s);}

Ой. Я этот код украл в образовательных целях (http://esoteric.sange.fi/brainfuck/impl/interp/small.c). Ну, если совсем не понятно — вот код интерпретатора на самом брейнф-е:

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]

Это код из http://www.hevanet.com/cristofd/brainfuck/
Вроде бы это самый лаконичный.

Но, давайте делать JIT.

JIT

И вот оно разочарование. Нет никакой магии. Просто выделяем сегмент памяти (с правами rwx, чтобы код в нем можно было читать, писать и выполнять), пишем туда куски машинного кода, и делаем туда goto. Всё. Потом освобождаем память. Делать в настоящей жизни такое на каждый чих не нужно, наверное нужно оптимизировать только часто выполняемые участки кода, длинные циклы и все такое. Да, тут уже конечно без магии никуда. Но мы сейчас не об этом. Итак, простой JIT.

Сколько машинных инструкций вы помните наизусть? Вот и я ни одной. Поэтому предлагаю такой вот хак. Например для инструкции «+» (которая «(*p)++» в С) делать следующее:

bf_inc_start:
  (*p)++;
bf_inc_end:

Теперь, у нас есть адрес начала машинного кода и его конца. Можно делать memcpy(). Чтобы не писать все руками сделаем пару макросов:

#define JIT_BEGIN(name) bf_ ## name ## _begin
#define JIT_END(name) bf_ ## name ## _end
#define nop() asm ("nop");

#define JIT_CODE(name, code) \
	if (jit == 0) { \
		JIT_BEGIN(name): \
		code ; \
		JIT_END(name): \
		nop(); \
	} else { \
		memcpy(jitptr, &&JIT_BEGIN(name), \
				&&JIT_END(name) - &&JIT_BEGIN(name)); \
		jitptr += &&JIT_END(name) - &&JIT_BEGIN(name); \
	}

Эти макросы очень некрасивые, но работают. JIT_CODE либо интерпретирует код, либо копирует соответствующие машинные инструкции в область памяти для JIT. Кстати, без nop() вы рискуете узнать, что метки в конце блоков кода не ставят, напр.:

if (...) {
  ...
label: /* так нельзя */
}

Итак. Приступим к реализации нашего интерпрето-компилятора-с-JIT. Все будет в одной функции. Причин несколько. В основном — это любовь x86 к относительным адресам. Глобальные переменные окажутся недоступными если перенести наш машинный код в другое место, некоторые переходы тоже. Мы об этом еще сильно пожалеем когда доберемся до циклов. Вот весь код:

void bf(const char *s, int jit) {
	volatile char mem[8];
	volatile char volatile *p = mem;
	volatile void  *loops[128]; /* who needs more than 128 nested loops in BF?! */
	volatile void **sp = loops;
	volatile void *jitend;
	void *code;
	void *jitptr;
	int (*in)(void) = &getchar;
	int (*out)(int)  = &putchar;
	int i;

	int sz = 4096;

	memset(mem, 0, sizeof(mem));

	if (jit) {
		code = mmap (0, sz, PROT_READ | PROT_WRITE | PROT_EXEC,  
				MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
		jitptr = code;
	}
	for (;;) {
		switch (*s++) {
			case '<':
				JIT_CODE(left, p--);
				break;
			case '>':
				JIT_CODE(right, p++);
				break;
			case '+':
				JIT_CODE(inc, (*p)++);
				break;
			case '-':
				JIT_CODE(dec, (*p)--);
				break;
			case ',':
				JIT_CODE(in, (*p) = in());
				break;
			case '.':
				JIT_CODE(out, out((int) *p));
				break;
			case '[':
				if (jit) {
					*sp++ = jitptr;
					JIT_CODE(enter, { if (*p == 0) { void *endloop = 0x0123456789abcdef; goto *endloop; }});
				} else {

				}
				break;
			case ']':
				if (jit) {
					void *start = *(--sp);
					void *patchhi, *patchlo;
					uint32_t patternhi = 0x01234567;
					uint32_t patternlo = 0x89abcdef;
					patchhi = xmemmem(start, jitptr - start, &patternhi, sizeof(patternhi));
					patchlo = xmemmem(start, jitptr - start, &patternlo, sizeof(patternlo));
					JIT_CODE(exit, { asm volatile("jmp *%0" :: "r" (start)); })
					(* ((uint32_t *) patchhi)) = (uint32_t) ((uintptr_t) jitptr >> 32);
					(* ((uint32_t *) patchlo)) = (uint32_t) ((uintptr_t) jitptr & 0xffffffff);
				} else {

				}
				break;
			case '\0':
				if (!jit) {
					return;
				}
				JIT_CODE(ret, asm volatile("jmp *%0" :: "r" (&&end)));
				goto do_jit;
		}
	}
do_jit:
	if (jit) {
		unsigned char *p;
		memcpy(jitptr, &&JIT_BEGIN(ret), &&JIT_END(ret) - &&JIT_BEGIN(ret));
		jitptr += &&JIT_END(ret) - &&JIT_BEGIN(ret);

		for (p = code; p < jitptr; p++) {
			printf("%02x ", *p);
		}
		printf("\n");
		goto *code;
	}
end:
	if (jit) {
		munmap(code, sz);
	}
	printf("POINTER=%ld\n", p - mem);
	for (i = 0; i < sizeof(mem); i++) {
		printf("%02x ", (unsigned char) mem[i]);
	}
	printf("\n");
	return;
}

Переменная «jit» определяет режим — интерпретатор или компилятор JIT. Все переменные связанные с состоянием BF-машины делаем volatile, чтобы оптимизатору неповадно было.
С помощью mmap/munmap работаем с областью памяти для JIT.

Как в любом интерпретаторе BF в цикле читаем инструкции. Для каждой их них либо формируем машинные инструкции, либо интерпретируем (макрос JIT_CODE).

» заслуживает отдельной обработки, т.к. он возвращает нас назад в нашу функцию из JIT-области.

После всех операций и компиляции, если мы в JIT-режиме — дописываем «ret» и делаем goto в скомпилированную область. Если не рухнем — то все удачно.

В конце работы просто показываем чё наш язык наделал — состояние памяти и указателя.

А что же с циклами? На открывающую скобку запоминаем текущий адрес в JIT-области, нам сюда еще возвращаться. Код JIT такой — если под указателем сейчас 0 — прыгнуть в конец цикла. А где конец цикла? Пока не знаем. Заменяем этот адрес на метку — 0x0123456789abcdef (у меня 64-битная система). Когда встречаем закрывающую скобку — берем адрес открывающей из стека, делаем туда jmp. И патчим нашу метку фактическим адресом конца цикла.

Кстати, у меня сломался memmem из glibc — пришлось писать свой. Я так понимаю эта функция вообще тяжелой судьбы (см. маны)?

Вот и всё. Запускаем:

bf("+++", 0) - интерпретируем. Получаем [3, 0, ....] в памяти
bf("+++", 1) - то же, но с JIT. 
bf("+[,.]", 1) - программа "cat" с JIT.
bf("+++[,.]", 1) - считывает три буквы
На hello world - падает 🙂

Вообщем, так JIT писать нельзя. Работает только с gcc без оптимизаций, на 32-битной системе немного проще и стабильнее (как переделать под 32 бита — домашнее задание). Хотя идея конечно вначале казалась забавной — использовать машинный код одного компилятора для другого да еще и убить двух зайцев. Авантюра не удалась.

Выводы

Можно делать JIT по-человечески. Есть библиотечка GNU lightning (http://www.gnu.org/software/lightning/) для генерации JIT-кода, она дает более-менее универсальный набор инструкций, и не глючит. Еще можно смотреть в сторону LLVM. Но, конечно, свой велосипед ближе к телу.

Реклама

Регулярные выражения и выражения благодарности Робу Пайку.

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

А что если написать свой движок регулярных выражений?

Итак, вспомним, что регулярные выражения — это по сути конечный автомат. Когда мы встречаем какой-то символ — автомат переходит в новое состояние (если это возможно). Например, для выражения ab(cd|ef)g получится такой автомат:

RegEx State Automata

Я не буду вдаваться в подробности о детерминированных и недетерминированных автоматах. Просто будем помнить, что само выражение описывает всевозможные состояния и связи между ними, а входная строка буква за буквой переключает состояния автомата. Здесь, например, в состоянии 2 если на вход поступит буква ‘d’ — перейдем в состояние 3, если буква ‘c’ — в состояние 4. Иногда нельзя будет сказать в какое состояние переходить не заглядывая наперёд строки.

Самый простой движок регулярных выражений

Существует великолепная книжка Роба Пайка и (кажется) Брайна Кернигана — The Practice Of Programming (TPOP). Там приводится код простейшего движка для регулярных выражений. Кому лень читать всю книгу — тут описан основной подход и приводятся те самые легендарные 30 строк кода.

Движок способен распознавать начало/конец строки и задавать wildcard — маску для множества одинаковых символов.
Гениальность этой реализации в рекурсивном подходе. Код получается очень лаконичный, а разница в скорости почти не заметна.

Извлекаем больше пользы

Я решил использовать этот код за основу, но получить чуть больше, а именно:

  • Узнавать где начинается соответствие и сколько символов строки попадает под выражение
  • Добавить специальные группы символом — ну хотя бы \d для цифр и \s для пробелов
  • Добавить квантификаторы (ну или как это назвать?) для нахождения 0 и больше вхождений («*»), 1 и больше («+»), 0 или 1 («?») и жадного оператора для 0 и больше («-» — как в Lua)

Попробуем вложиться строчек эдак в 100.

Начинать будем так же — нам нужная единственная главная функция и функция, определяющая соответствие начала строки выражению — regex_match и regex_match_here соответственно:

int regex_match(const char *regex, char *s, int *len) {
	char *p = s;

	/* force match from the beginning of the string */
	if (regex[0] == '^') {
		return (regex_match_here(regex + 1, s, len) ? 0 : -1);
	}

	/* iterate the string to find matching position */
	do {
		*len = 0;
		if (regex_match_here(regex, p, len)) {
			return p - s;
		}
	} while (*p++ != '\0');

	return -1;
}

int regex_match_here(const char *regex, char *s, int *len) {
	// TODO
}

С regex_match все ясно, если «^» — проверяем начало строки, иначе — пляшем слева направо пока не найдем соответствие.

Самое главное находится в regex_match_here:

static int regex_match_here(const char *regex, char *s, int *len) {
	int c = regex[0];

	if (regex[0] == '\0') { /* end of regex = full match */
		return 1;
	} else if (regex[0] == '$' && regex[1] == '\0') { /* check end of string */
		return (*s == '\0');
	} else if (regex[0] == '\\' && regex[1] != '\0') { /* check escaped symbol */
		c = regex[1];
		if (c != '^' && c != '$' && c != '\\' && c != '+' && c != '*' && c != '-' && c != '?') {
			c = c | 0x100;
		}
		regex = regex + 1;
	}
	/* check for special operators *,+,?,- */
	if (regex[1] == '*' || regex[1] == '+' || regex[1] == '-' || regex[1] == '?') {
		return regex_match_quantity(regex[1], c, regex+2, s, len);
	} else if (*s != '\0' && regex_match_group(*s, c)) {
		*len = *len + 1;
		return regex_match_here(regex+1, s+1, len);
	}
	return 0;
}

Здесь проверяем состояние нашего неявного автомата:

  • если выражение закончилось (достигнуто конечное состояние) — вернуть 1, соответствие найдено
  • если в регулярном выражении дошли до последнего символа, и это — «$» (т.е. конец строки) — вернуть 1 если строка тоже закончилась.
  • если нашли «\» — экранирующий символ, но мы имеем дело с особой группой символов. Вообще, в обычном синтаксисе «\» играет две роли — для «\.», «\^», «\$», ‘\?’, ‘\*’, ‘\+’, ‘\-‘ он означает использовать просто символы «.», «^» и т.д. вместо из мета-значений («любой символ», «начало строки», «конец строки», …). Для остальных («\d», «\s», …) он означает использовать мета-значение («любая цифра», «любой пробельный символ», …). Договоримся, что значение выше 256 будут означать мета-символ, т.е. (‘d’|0x100) — это «любая цифра», а ‘d’ — буква ‘d’. Ах да, с точной («.») все будет наоборот. Ну и синтаксис.
  • итак, символ или группу мы считали. Теперь проверяем операторы «+», «*», «?» и «-«. Для них — особая функция проверки regex_match_quantity, а в остальных случаях — просто проверяем попадает ли следующий символ строки в группу и идёт дальше (рекурсивно).

Функция проверки попадания символа в группу простая и легко расширяемая:

static int regex_match_group(int c, int group) {
	if ((group & 0xff) == '.') group ^= 0x100;
	if (group < 0x100) { /* a single char */
		return c == group;
	}
	/* a meta char, like \d, ... */
	switch (group & 0xff) {
		case 'd': return isdigit(c);
		case 's': return isspace(c);
		case 'D': return !isdigit(c);
		case 'S': return !isspace(c);
		case '.': return 1;
	}
	return 0;
}

В этой функции мы смотрим — для простых символов кроме точки — просто сравниваем. Для остальных — проверяем группы. С точкой — все наоборот. Я использую функции из ctypes.h, но для простых групп можно и без них обойтись.

Ну и самый кошмарный код в функции regex_match_quantity:

static int regex_match_quantity(int quant, int c, const char *regex, char *s, int *len) {
	if (quant == '?') {
		if (regex_match_group(*s, c)) {
			*len = *len + 1;
			s = s + 1;
		}
		return regex_match_here(regex, s, len);
	}

	if (quant == '+' || quant == '*') { /* match as much as possible */
		char *p;
		for (p = s; *p != '\0' && regex_match_group(*p, c); p++) {
			*len = *len + 1;
		}
		if (quant == '+' && p == s) {
			return 0;
		}
		do {
			if (regex_match_here(regex, p, len)) {
				return 1;
			}
			*len = *len - 1;
		} while (p-- > s);
	} else if (quant == '-') { /* match as little as possible */
		do {
			if (regex_match_here(regex, s, len)) {
				return 1;
			}
			*len = *len + 1;
		} while (*s != '\0' && regex_match_group(*s++, c));
	}
	return 0;
}

Ну для «?» всегда возвращаем 1, но если символ действительно входит в группу — увеличиваем длину совпадающего региона на 1.

Для жадных операторов «+» и «*», которые захватывают как можно больше символов строки — так и поступаем. Проверяем сколько вообще символов строки может попасть в заданную группу, а затем возвращаемся назад пока не найдем соответствие остатка строки остатку регулярного выражения. Для «+» хотя бы один символ строки должен попасть в группу.

Для нежадного оператора «-» просто идёт слева направо пока не совпадет остаток строки с остатком выражения.

Вот и все. У меня получилось 98 строк. Ни одной зависимости. Из libc — только ctype.h, т.е. при особом умении соберется даже каким-нибудь ущербным SmallC. Также никаких особых плюшек С я не использовал, код должен быть переносим и на другие языки, на тот же Forth.

Весь код — как всегда на bitbucket.
Там же и горстка тестов чтобы быть уверенным что все работает как надо.

Вместо выводов

Спасибо Робу Пайку за элегантный и полезный код. Я понимаю, что для серьезных задач такие микро-регекспы не годятся, но для чего-нибудь простенького в embedded — вполне. Тем более лично я считаю, что не стоит делать и регулярных выражений тьюирнг-полный мега-язык, уж лучше бы был способ комбинирования простых регулярных выражений с примесью некоторой простой логики типа условний-циклов.

Здесь кстати тоже стоит отметить работу Роба Пайка о структурных регулярных выражениях. И его текстовый редактор Sam красочный пример их простоты и мощности. Спасибо, Роб.

P.S. Отдельно спасибо, Роб, за язык Go 🙂

О самодельном printf для идиотов, перегрузке функций в C и макросах

Я не люблю отладку и отладчики. Ну вот привычнее мне как-то вести логи и по ним уже разбираться где что не так.
В обычной жизни для этого использую либо printf, либо самодельные обертки над ним.

Но иногда приходится работать с AVR и прочей мелочевкой, там на полноценный printf как-то жаба давит память тратить.
Да и в целом хочется минимализма. И вот к чему я пришел. Читать далее

Стив Возняк. Где мои 16 лет. Велосипеды.

Я так понимаю, каждый уважающий себя айтишник должен придумать свой собственный процессор. Ну вы только посмотрите что творится вокруг DCPU-16. Ну Нотч, ну игра, ну процессор. А что такого особенного в этом DCPU16? По-моему самый обычный вымышленный 16-разрядный процессор. Нет, это конечно хорошо что народ начал писать эмуляторы, компиляторы, на verilog там что-то делают, да, толчок дали хороший. Но это все — маркетинг, и лучше бы для других процессоров делали то же самое. А то — для AVR эмулятора под linux нет толкового, так чтобы расширять можно было легко и просто. Для PIC кажется тоже. Для STM8 очень классных и модных — вообще ничего нет, даже ассемблера! Но все пишут и пишут для практически непригодного DCPU-16. На этом фоне эмулятор Cortex на AVR выглядит намного круче, хотя шума о нем меньше.

Ну ладно, разворчался я что-то. Читать далее

Процессор J1 — куда уж проще

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

Я давний фанат этого процессора. Я писал о нем на хабре, дважды, и хочется написать еще.

Для тех, кто не слышал никогда о J1 — это простенький процессор,
ориентированный на язык Форт. Для любителей подробностей — официальный сайт J1 CPU.

Так вот, я с гордостью могу сказать, что я маялся бездельем и тем временем написал эмулятор + компилятор почти-Форта для J1. Здесь я расскажу что это и зачем. Читать далее

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. Может быть когда нибудь я вам об этом тоже расскажу. Жаль, что я к тому времени уже утрачу рассудок, буду общаться с духами и возможно покину этот слишком материальный мир.