Лямбдами же чё хочешь можно закодировать:
хоть ДНК для Endo, хоть управление для Hohmann Transfer,
хоть стратегию для робота в лабиринте… дело такое
Народная мудрость
Dreaming of the Crash
Строго говоря, этот пост я начал писать 26 июня 2014 года. К тому времени уже были известны имена организаторов и мне хотелось сделать обзорчик их работ, а заодно и накидать черновик будущего отчёта...С той поры прошёл уже год с лишним, в течение которого было несколько безуспешных подходов к этому снаряду. Наверное, пора уже дожать, пока меня не догнала сингулярность...
Начнём с организаторов. Nicolas `zenzike` Wu — один из оргов-сопредседателей — имеет среди своих публикаций следующий замечательный труд: Pure and Lazy Lambda Mining: An Experience Report. В соавторах этой работы фигурирует также еще один орг — José Pedro `dreixel` Magalhães. Сама публикация, понятно, посвящена добыванию лямб роботом в ICFPC-2012. Полагаю, все в курсе.
Другой сопредседатель — Duncan `dcoutts` Coutts — довольно-таки известный персонаж в мире haskell.
Об остальных оргах известно меньше, но, например, Martin `mariusz` Lester пишет о себе, что "was part of the team ... that won the ICFP Programming Contest in 2011"...
Чего ждать от всех этих оксфордских джентльменов в плане задания к контесту было совершенно непонятно. Оставалось надеяться, что с всё будет по крайней мере неплохо организовано.
В качестве базовых ингредиентов взял ghc-7.8, Emacs и haskell-mode. Добавил туда stylish-haskell, structured-haskell-mode, flycheck-hdevtools и немножко HaRe. Но где-то что-то не рассчитал — а может старые книги врут с составом, — спалил к чёртовой матери макбук и уехал в отпуск лазить по скалам...
Cornfield Chase
По мере того, как счётчик приближался к приобретшим вдруг "сакральный смысл" датам 25-28 июля, я стал поковыривать свой хаскельный сетап. Честно говоря, это каждый раз напоминает алхимию и поиски философского камня.
Помимо выкладывания фоточки (надеюсь, в будущем обойдётся без обязательного инстаграмма...) орги еще намекнули, что нам потребуется "много фруктов", а также опубликовали это:
Выглядело чертовски похоже на биндинг некоторого лямбда-выражения с пропусками вместо подтермов и переменных. Правда не совсем понятно было, что за "%" слева от "=". К чему 3072? И при чём тут фрукты?
Последние несколько дней перед стартом мы с Лёхой по-полной проникались атмосферой контеста, разгадывали хинты оргов, обсуждали современный c++, прошлогодние SMT-солверы, алгоритмическую разрешимость евклидовой геометрии и философские основания нашего участия в ICFPC.
Dust
Уже который год орги ICFPC не оставляют Philip Wadler в покое. Вот и в этот раз в официальном твиттере был опубликован такой вот Lambda-Man:
% = \...o.....
Первым делом я её отправляю на принтер — незначительная деталь, которая непременно сыграет свою роль в дальнейшем повествовании, — и углубляюсь в чтение. Следующий час проходит за изучением 30-страничного документа и сумбурной перепиской по скайпу.
На первый взгляд задание подозрительно напоминает тот самый Lambda Mining 2012-го года, о котором с ностальгией пишет в своей работе г-н Wu. Снова нужно управлять какой-то хреновиной в двумерном лабиринте, чего-то собирать, от чего-то уворачиваться.
С LambdaMan'ом ситуация интереснее. Задание содержит подробную многостраничную спецификацию его "микропроцессора" GCC (General Computing Processor), построенного на 4 регистрах: S(tack), E(nvironment), C(control) и D(ump). Микропроцессор имеет частоту 3.072Mhz и исполняет одну инструкцию за такт. Программе доступно 10^6 CONS-ячеек памяти. Одна "минута" машинного времени на инициализацию, одна "секунда" — на ход. К счастью, орги дали не только референсную реализацию GCC, но и симулятор Игровой Механики на js.
К счастью, потому что сама игровая механика весьма нетривиальна. Понятие машинного такта, связанные с ним хитрые правила совершения ходов и набора очков, изменение скорости перемещения юнитов и море всяких прочих мелких технических деталей, включая "секретные параметры" и "неиспользуемые прерывания" (technical debt?). Даже возможность при определённых обстоятельствах разминуться с призраком в узком коридоре (Как в том любимом анекдоте Никулина: "...и не встретились. Не судьба!"). И совершенно неясно, сделано ли это всё оргами из чистой любви к искусству или имеет какой-нибудь практический смысл.
Лёха первым понимает, что речь идёт о PacMan'е, а я — что о SECD-машине.
Правда с SECD-машиной я в последний раз сталкивался году этак в 2007-ом, когда только начинал изучать FP. А PacMan — это вообще из детства. Т.ч. толку от такого знания было мало.
Тем не менее вырисовывается план действий. Нам предстоит научиться программировать на ассемблере SECD-машины им. тов. Лэндина. Мы даже собираемся что-нибудь засабмитить в лайтнинг. А после этого, предстоит, очевидно, разработка компилятора.
План был хорош, но при попытке его воплощения в жизнь сразу полезли некоторые трудности. Во-первых, выяснилось, что референсная реализация не понимает ассемблер с метками и комментариями. Т.ч. нам требуется Макропроцессор. Во-вторых, Лёха наотрез отказывается параллелить задачи и доверить мне разработку Компилятора ("я тоже хочу повозиться с компилятором") или Стратегии (чем мотивировал — не помню). В итоге решили, что я запилю по-быстрому Макропроцессор, а там видно будет.
Макропроцессор я пилил аж 5 с лишним часов... Вместо того, чтобы сделать всё по-простому на awk, я сразу запилил под это дело целый проект на haskell'е. Идея была в том, чтобы выдавать нормальные сообщения об ошибках (строка, позиция) в исходнике. В конечном итоге это сработало, но поначалу я тупанул и вооружился attoparsec'ом. Только для того, чтобы через 2 часа, уже выписав грамматику со всеми комментариями и метками, выяснить, что из него нельзя достать текущую позицию токена. Пришлось всё срочно переписывать на parsec'е... Ну и была еще пара фейлов помельче.
В общем в 12-ом часу ночи новенький сияющий Макропроцессор был интегрирован в master-ветку репозитория. Жаль, что ошалевший к тому времени от отсутствия комментариев и меток Лёха не был способен оценить мою гордость. Впрочем, Макропроцессор этот выдержал test-of-time и был использован во всех наших решениях, как в течение контеста, так и по его окончании.
Пока я развлекался с Макропроцессором, Лёха "тихо ненавидел html и javascript". Он потихоньку экспериментировал с ассемблером SECD-машины и копался в потрохах референсных симуляторов (скомпилированных ghcjs, ага...)
Пятницу мы провели, очевидно, совершенно бездарно.
Day One
В пятницу в четыре часа дня счётчик на странице контеста пересекает 0 снизу вверх и через несколько секунд там появляется Спецификация Проблемы. Сейчас она, как и всякие дополнительные материалы доступна в официальном репозитории.
- AP> опять eating pills and evading ghosts?
Дальнейшее чтение показывает, что ностальгируют орги не только по 2012-ому, но и по 80-ым (полностью поддерживаю). Особенно по компьютерным играм (ой, да ладно?).
Можно было даже реализовать подмножество какого-нибудь стандартного лиспа, типа clojure или EmacsLisp (Лёха заморочился-таки с racket'ом). Это позволило бы отлаживать какие-то элементы Стратегии вообще не имея компилятора. Но я от этой идеи отказался, потому что распараллелить работы по созданию Компилятора и Стратегии мне было не с кем, а искусственно завязываться на определённый синтаксис не хотелось.
Stay
Суббота начинается с того, что Лёха долго выясняет, как проехать ко мне на работу и где правильно парковать машину, а потом не приезжает. Какой-то у него там форс-мажор. Меня это не слишком расстраивает, потому что план на день совершенно понятен. С лайтнингом мы были, очевидно, в пролёте, поэтому предстоит делать компилятор для SECD-машины. А где SECD-машина, там, естественно, Lisp. Не, ну была одна безумная идея с хаскелем... Впрочем, не будем забегать вперёд.
Message from Home
К 12 на связи появляется Лёха, который доехал-таки к себе на работу. Поначалу он продолжает заниматься ассемблерными разработками. С появлением макропроцессора дела у него идут получше и он всё чаще присылает мне какие-то адские простыни с комментариями в духе "смотри, какой читаемый код!" Вроде такой:
Совершенно очевидно... эээ... что здесь демонстрируется владение такими концепциями как замыкания (LDF), различные механизмы вызова функций (AP/RAP+DUM), мутабельные переменные (ST) итп.
; Мне нужна одна локальная переменная t, поэтому создаю окружение из одной переменной
DUM 1
LDC 0
LDF init
RAP 1
STOP
init:
; Здесь мы получаем замыкание с локальными переменными в родительском стеке
DUM 2 ; x, y
LDC 1 ; x = 1
LDC 2 ; y = 2
LDF getsum
RAP 2
; В этом месте нам вернули в качестве параметра функцию sum z, у которой также захвачены переменные x и y
ST 0 0 ; t := sum 1 2
LDC 10
LD 0 0
AP 1 ; sum 10
RTN
; get_sum x y
getsum:
; В этой функции 2 локальных переменных: x,y
LD 0 0
LD 0 1
CONS
DBUG
; Теперь захватываем родительский контекст и возвращаем наружу адрес функции sum z
LDF sum
RTN
sum:
; Функция sum принимает 1 параметр z, извлекает из родительского стека x и y, возвращает x+y+z
LD 1 0
LD 1 1
LD 0 0
CONS
CONS
DBUG
LD 1 0
LD 1 1
LD 0 0
ADD
ADD
RTN
The Wormhole
Меня это к тому времени не очень впечатляет, так как к половине второго я уже умею компилировать арифметические выражения.
echo "(defun add (x y) (+ x y))" | dist/build/lmc/lmc compile
LD 0 0
LD 0 1
ADD
RTN
Петля положительной обратной связи затягивается, я только успеваю добавлять новые фичи в lmc: определение (defun) и вызов (apply) функций, булевские переменные и операторы... Они, как правило, сразу работают. Но не все.
TLDR, некоторые баги в этом механизме смогли продержаться еще как минимум сутки :-)
Mountains
Первым камнем преткновения стал... if. Мало того, что для правильной генерации меток, пришлось протащить через весь "чистый" (ну не переписывать же в самом деле из-за этого всё на монады?) код состояние — счётчик меток, — так еще и пришлось ввести понятие "блока" кода. Дело в том, что специальная форма (if b t f) моделируется, по сути, как
И если раньше compile(b)
SEL t_xxx, f_xxx
...
t_xxx:
compile(t)
JOIN
f_xxx:
compile(f)
JOIN
compile возвращал один блок просто как список инструкций (с символьными метками) и такие списки просто конкатенировались в программу, то теперь стало нужно куда-то приткнуть список инструкций, начинающийся с метки t_xxx. Если бы я к тому моменту знал, что в списке инструкций есть jmp (замаскированный под TSEL), то можно было бы влепить этот блок перед compile(b) и перепрыгнуть его. Но я поленился внимательно прочитать про хвостово-рекурсивные расширения SECD-машины и мне пришлось изменить compile так, чтобы он мог возвращать два блока: основной и дополнительный. Дополнительные блоки лепились в конце программы (а точнее — в конце top-level выражения).
В метро по дороге домой до меня доходит, что на базе TSEL легко организовать
А по приезду домой я еще замутил поддержку Afraid of Time
Тем не менее, за 15 минут до окончания лайтнинга я "почти умею" считать элементы ряда Фибоначчи. Ну, или, точнее вот так:
Остаток дня занимаюсь добавлением поддержки таплов ((defun main () (apply fib 4))
(defun fib (n) (if (<= n 1) 1 (+ (apply fib (- n 1)) (apply fib (- n 2)))))
tuple/nth), списков (list/car/cdr) и всяких мелочей, вроде отладочной печати. Заодно читаю, наконец, про pascal extensions и закрываю для себя другие белые пятна Спека.
jmp, которого так не хватало весь день.
let-выражений — давно подозревал, что для этого будет достаточно defun/apply, — и прикрутил магический оператор rap для интерфейса процессор-сопроцессор. Это позволяло исполнять программы не только в симуляторе GCC, но и в симуляторе Игровой Механики, т.е. подступиться к созданию Стратегии.
Во-первых, нужно было понять, каков будет порядок редукции. Я пошёл по пути наименьшего сопротивления и остановился на строгой семантике — аргументы вычисляются слева направо перед вызовом функции. Это хорошо ложилось на SECD-машину. Впрочем, ввиду отсутствия сайд-эффектов — а внедрять "pascal extensions" я не собирался, — это было не слишком важно.
Во-вторых, и тут свободы никакой не было, нужна была поддержка булевских и арифметических выражений, таплов и списков. Орги заботливо предусмотрели в спеке, чтобы все эти примитивы использовались в Игровой Механике. Как, кстати, и замыкания, что я долго обходил с помощью магического оператора
А дальше — полная свобода. Например, поддерживать или не поддерживать каррирование и частичное применение функций? Я согласился с предложением Лёхи "забить сразу", т.к. не придумал лучшей реализации, чем такая (на примере функции
Ну, а дальше пошло-поехало. Вместо паттерн-матчинга — распаковка с помощью
Надеюсь, происхождение названия языка теперь понятно. Ладно, вот пример.
Фрагмент
A Place Among the Stars
К этому моменту основные черты языка Poor LambdaMan Lisp уже утряслись и хочется по ним быстренько пройтись. Должен сказать, что изобретение своего лиспа оказалось довольно увлекательным занятием. По крайней мере более увлекательным, чем последующее программирование на нём...
(rap), не понимая толком, что он делает.
__eq из компилятора ghclm, см. ниже):
__eq_curry:
LD 1 0
LD 0 0
CEQ
RTN
__eq:
LDF __eq_curry
RTN
let и nth/car/cdr. Никаких лямбда-функций. Вообще никаких вложенных функций: только top-level, только хардкор. Соответственно, и замыкания не нужны. О системе типов я вообще молчу, потому что даже соответствие числа формальных и фактических аргументов при вызове функции не проверяется...
превращается в элегантное
fold (f env) x0 xs
where f env ...
т.к. контекст (car (fold f (tuple x0 env) xs)
...
(defun f (acc y)
(let ((x (nth 0 acc))
(env (nth 1 acc))
...
)
env приходится протаскивать через аккумулятор fold'а. Особенно это доставляет, если нужно добавить еще одно поле в AIState.
У меня в воскресенье такой задачкой была реализация Running Out
Если хотите утром сразу включиться в работу, то надо с вечера себе оставить какую-нибудь маленькую приятную задачку.
fold'а. Конечно, fold можно просто сделать функцией и дело с концом. Но т.к. lmc не поддерживает хвостовую рекурсию, то такая реализация мне не нравится. Вместо этого я решаю сделать fold специальной формой. Она заводит себе на стэке DUMMY-контекст для значения аккумулятора и далее использует pascal extension ST для его обновления и TSEL для реализации цикла. Дёшево и сердито.
Вторая Тривиальная Стратегия исполняет заданную программу команд:
I'm Going Home
После появления fold'а, я реализую Первую Тривиальную Стратегию LambdaMan'а, которая заставляет его двигаться строго курсом 0:
Практического смысла в этой стратегии, понятное дело, никакого нет. Зато есть очень важный символический смысл. Она есть доказательство того, что теперь можно писать код не только под симулятор GCC, но и в связке с Игровой Механикой.
(rap)
(defun init (world undoc f)
(tuple 0 f))
(defun step (state world)
(tuple state 0))
Я привожу эту Стратегию целиком, потому что она стала основой для всех будущих построений. Особое внимание следует обратить на (rap)
(defun init (world undoc f)
(tuple
(list
(list 1 1 1 1 1 1 2 2 1 1 0 0 1 1)
(list)
f))
(defun step (state world)
(let
((moves (nth 0 state))
(rmoves (nth 1 state)))
(tuple
(list
(cdr moves)
(list (car moves) rmoves))
(car moves))))
rmoves, в котором сохраняется информация, необходимая для возврата в исходную точку.
Параметр Coward
Идея отступления лежит в основе моей единственной эвристики по работе с призраками. Заключается она в том, чтобы при виде призрака в клетке, куда собирается наступить LambdaMan, развернуться и трусливо бежать (кроме тех случаев, когда ГГ обдолбался powerpile'ом, конечно).
rmoves в AIState как раз и является заготовкой под эту логику. Позже в нём будет сохраняться непосредственно список команд, т.ч. для режима паники будет достаточно поменять в нужный момент списки moves и rmoves местами. Et voilà!
Естественно, начать пришлось со всяких примитивов:
Наконец, в 9 вечера случился первый прорыв в области Стратегии. Для каждой точки карты я научился вычислять список всех возможных направлений движения из неё. Представлялось это "двумерным массивом" ([вырожденным] бинарным деревом [вырожденных] бинарных деревьев) списков. Теперь, зная пару координат Detach
На этом тривиальные конструкции закончились и нужно было строить более содержательную Стратегию. Однако строить было не из чего. Поэтому воскресенье я посвятил разработке Стандартной Библиотеки.
length, reverse, splitAt итп. В процессе полезли всякие грабли в компиляторе, которые приходилось тут же исправлять. К вечеру я добрался уже до таких абстракций, как двоичные деревья, которые заменяли мне массивы за неименением последних. Правда деревья были несбалансированными, а на практике так даже и всегда вырожденными в списки. Но я себе честно поставил TODO это исправить, если потребуется...
(j,i) можно было получить список всех возможных направлений движения из данной точки карты (maze) с помощью:
К 11 я уже умел находить на карте все "интересные" точки: пересечения, тупики и стартовую позицию LambdaMan'а. А к двум часа ночи для каждой пары смежных точек у меня была "программа перехода" между ними. Идея была в том, чтобы принимать решения только в узлах графа, вершинами которого являются "интересные" точки, а рёбрами — "программы перехода". В промежуточных точках, не являющихся интересными, нужно было просто исполнять программу, не забывая поглядывать под ноги, чтобы не наступить на призрака.
(apply ij i j maze)
Через систему прерываний призраки могут задавать своё новое направление движения и получать информацию об окружающей обстановке: содержимое ячеек карты, положение LambdaMan'а, положение второго LambdaMan'а (подразумевался multiplayer?), свой порядковый номер, стартовые и текущие координаты любого из призраков, их текущее состояние и направление движения.
Призраки имеют ряд ограничений. В частности, они могут менять направление движения только на перекрёстках, поворотах и в тупиках. При этом на 180 они могут разворачиваться только в тупиках. Некорректно выбранные направления движения игнорируются. Итп.
На этих фактах, например, основана приведённая в reference materials программа призрака fickle.ghc:
Наиболее state-of-the-art призрачные решения, встречающиеся в отчётах команд, не только реализуют алгоритмы преследования (и уклонения от) LambdaMan'а разной степени нетривиальности, но и эффективно противодействуют тенденции "кластеризации" призраков в одном коридоре, что важно и для задачи преследования, и для задачи уклонения. Встречаются также попытки охраны powerpiles и "межпризрачного взаимодействия".
Некоторые решения стараются по-максимуму использовать выделенные 1024 такта на ход, намеренно генерят невалидные направления движения или вообще ошибки исполнения программы призраков. Связано это с тем, что недокументированный параметр программы LambdaMan'а, оказывается, представляет собой список закодированных программ призраков. Были даже команды (например THIRTEEN), которые реализовали эмулятор призрачного "микропроцессора" для SECD-машины. Однако, насколько мне известно, никто из этого ничего полезного не выжал.
S.T.A.Y.
Следует, наверное, пару слов сказать о призраках. Хотя, если често, по причинам, которые станут полностью ясны позднее, мне про призраков сказать особо нечего. Все мои знания почёрпнуты из чтения спека и отчётов других команд.
По сути, здесь реализована "условно-рандомная" стратегия-бродилка, которая всё время пытается пойти по тому направлению, по которому призрак ходил реже всего. Понятно, что с такими призраками каши не сваришь.
; Keep track of how long we have spent travelling in each direction.
; Try to go in the direction we've travelled in least.
; Count of time spent going in direction 0 is in memory address 0, and so on.
mov a,255 ; A is the min value.
mov b,0 ; B is the corresponding direction.
mov c,255 ; C is the candidate direction for the new min.
; Start of loop.
inc c ; Pick new direction.
jgt 7,[c],a ; Jump if count of direction C is above best so far.
; We have a new min.
mov a,[c] ; Save new min.
mov b,c ; Save direction.
jlt 3,c,3 ; Jump target. Loop back if we have not tried all 4 directions.
mov a,b ; Actually set desired direction.
int 0
int 3 ; Get our ghost index in A.
int 6 ; Get out current direction in B.
inc [b] ; Increment corresponding count.
hlt ; Stop.
У меня уже ни с чем сил бодаться нет, но — чёрт возьми! — неужто столько работы пойдёт коту под хвост?
И я иду пилить Стратегию дальше. Для начала нужно хоть как-нибудь научиться обходить граф в отсутствие призраков. По построению графа это гарантировало бы сбор всех pile'ов.
Where We're Going
Утро понедельника начинается с Лёхиного телефонного звонка. Зевая рассказываю ему о своих успехах и планах. Лёха бодается с вычислением функции Беллмана. Ну-ну...
First Step
В качестве простейшей реализации алгоритма обхода выбран следующий. С каждым маршрутом ассоциируется число — количество раз, которое этот маршрут был выбран LambdaMan'ом в качестве текущей программы. При попадании в один из узлов графа LambdaMan выбирает тот маршрут, по которому ходил реже всего. Т.к. граф маршрутов у меня ориентированный, то это приводит к тому, что LambdaMan зачастую проходит некоторый коридор сначала в одну сторону, а потом сразу же в обратную. "Эффективность? Не, не слышали!..". Тем не менее, такой алгоритм набирает 1040 очков на World Classics и удостаивается комментария "WOW!!!" в git'е.
Наблюдать за его тупейшим поведением очень забавно. Например, как он пощёлкивая клювом проходит мимо коридора с фруктом и ничтоже сумняшеся поворачивает в коридор навстречу призраку...
Flying Drone
Таким образом за 3.5 часа до окончания контеста свет в конце тоннеля забрезжил и у меня появилась, наконец, первая содержательная Стратегия. Первый работающий девайс, способный, если ему сильно не мешать, обойти всю карту и собрать все pile'ы и powerpile'ы.
Времени до окончания контеста остаётся мало и понятно, что никаких принципиально новых решений не появится. Но тем не менее я уже набрал приличный момент в разработке Стратегии. Хочется потратить оставшееся время эффективно и выжать максимум из существующего решения.
Atmospheric Entry
К этому моменту Компилятор и Стандартная Библиотека практически не путаются под ногами. Баги повыпилены, структуры данных — позапилены. Конечно, Poor LambdaMan Lisp по-прежнему доставляет, но тут уже ничего поделать нельзя.
No Need to Come Back
Следующим изменением становится добавление счётчика посещений не только маршрутам, но и узлам.
Теперь LambdaMan сортирует маршруты сначала по весу узла, а потом — по весу маршрута. Эта простенькая модификация была отлажена за какой-то час и давала 2170 очков на World Classics. Недурно.
Этого, конечно, совершенно недостаточно для настоящих Ghost Busters, но на World Classics сей нехитрый приём даёт 8700 очков, что близко ко вчерашнему максимуму лидеров на этой карте. Круто...
Кстати, уже после окончания контеста я еще улучшил это решение, заменив сортировку рёбер по числу посещений на сортировку по общему количеству оставшихся ништяков в коридоре. На World Classics эта дало 10200 очков.
Imperfect Lock
Далее нужно научиться что-то делать с призраками. Идея у меня была готова еще в воскресенье и за час до окончания контеста я успеваю её воплотить. Ну, вы знаете уже: режим паники, программа отступления, — вот это вот всё. Это даёт примерно 50%-ные шансы спастись при встрече с призраком на узкой дорожке.
Тут нас ждёт неожиданная развязка сюжета с распечаткой задания. Дело в том, что весь понедельник у меня не было интернета (пользуясь случаем передаю привет провайдеру). Поэтому получив 8700 очков на World Classics практически за час до окончания контеста, я расслабился и стал неторопясь готовить submission... по распечатанному пятничному рецепту, т.е. по правилам lightning round'а...
Я уже готов был диктовать sha1-сумму своего решения Лёхе по телефону, чтобы он засабмитил за меня хотя бы хэш (чему тот был бы явно не рад, т.к. в этот момент в панике пытался тоже что-нибудь засабмитить), но тут случилось чудо — интернет дали. В итоге я спокойно и без нервотрёпки залил своё решение и поехал на работу.
Где с удивлением узнал, что в финальном раунде нужно было сабмиттить не только стратегию LambdaMan'а, но и призраков. Понятное дело, что в моём решении никакими призраками и не пахло, не было даже стандартного fickle.ghc. Однако решение не забанили на этом основании. Видимо, запускали конкурентов без кода моих призраков вообще (что эквивалентно тупейшим призракам, долбящим строго вниз). Результат понятен.
Забавно при этом, что Лёха не успел выложить своё решение до дедлайна, но успел выложить хэш. В итоге орги связались с ним и приняли его решение.
No Time for Caution
Почему я вдруг говорю о вчерашнем максимуме?
На первый взгляд такая задача может показаться гораздо более сложной, чем исходная, но чем больше я о ней думал, тем больше понимал, что попробовать стоит.
Согласно AOS и GHC Wiki есть как минимум три "точки расширения" в GHC, пригодных для нашей цели. Во-первых, это API, позволяющий использовать GHC как библиотеку. Во-вторых, возможность реализовать свой кодогенератор для компиляции из Cmm. В-третьих, возможность реализовать свой Core-to-Core Pass плагин.
Меня больше всего заинтересовал последний вариант, т.к. из всех представлений хаскельной программы именно GHC Core проще всего транслировать в код SECD-машины. Опять же, плагин для Core-to-Core преобразования элементарно подключается к GHC ключом командной строки.
Так появился на свет проект ghclm. Плагин к GHC, реализующий тождественное Core-to-Core преобразование с небольшим сайд-эффектом в виде .gcc-файла.
Не могу сказать, что познал все тонкости System FС / GHC Core, но кучу базовых тестов по работе с числами, таплами, списками, рекурсией итп плагин честно проходит в связке с официальным GCC-симулятором, запущенным под node.js. Также, в качестве proof-of-concept я замутил рандомную стратегию-бродилку, которая компилируется и исполняется в официальной Игровой Механике. 27 часов на всё про всё, включая тесты. Совсем неплохо.
Конечно, ghclm поддерживает только тот набор типов данных, которые присутствовали в спецификации задачи: числа, 2-таплы, списки. Никаких тебе алгебраических типов данных, массивов, даже строк. Такой себе Poor LambdaMan's Haskell.
Также имеются шероховатости и в самой процедуре трансляции.
Во-первых, как и в компиляторе lmc, не поддерживается хвостовая рекурсия и другие pascal extensions. На практике не такая уж большая проблема, но можно было бы генерить несколько более эффективный код.
Во-вторых, нет поддержки дебажного вывода (DBUG). Вот это действительно неудобно.
В-третьих, есть несколько моментов, связанных со спецификой самого GHC Core. Например, для форсирования thunk'а в этом языке используется конструкция
Еще один пример. В GHC Core все лямбда-выражения имеют только один формальный параметр, а LambdaMan'овская SECD-машина поддерживает вызов функций от нескольких переменных (AP/RAP n). Я не стал заморачиваться, поэтому вызов многоместной функции превращается в цепочку из нескольких последовательных вызовов. А можно было бы сэкономить несколько машинных тактов и CONS-ячеек в Env'е. Зато автоматически поддерживается каррирование функций, чего так не хватало в lmc.
В общем, проблемы есть. Это уж не говоря про то, что прототип остался прототипом и иногда тривиальные изменения в исходном коде стратегии приводят к тому, что мозги компилятора взрываются в панике или плагин генерирует некорректный код.
С другой стороны, плюсы разработки стратегии LambdaMan'а на почти полноценном хаскеле легко перевешивают любые неудобства. Вплоть до того, что можно использовать часть функций из Prelude и даже других библиотек. Т.ч. если бы я догадался до этого варианта в пятницу, то стоило бы попробовать.
Кстати, команда, которая провернула аналогичную афёру с OCaml'ом — gagallium, — получила judges prize :-)
What Happens Now?
Настало время рассказать об еще одной замечательной идее, которая нашла своё воплощение лишь после завершения контеста. Идея состояла в том, чтобы делать не компилятор Lisp'а, а компилятор Haskell'а... Да, ровно так: компилятор подмножества языка хаскелл для SECD-машины.
Моя же разновидность хаскеля предполагала строгую семантику, так-то толку генерить такие case'ы не было. Но до столь тонких оптимизаций руки не дошли.
case thunk of thunk1 {
__DEFAULT -> ...
}
Да, к сожалению, из-за небольшого форс-мажора у нас случился split-brain, поэтому команд две, а не одна.
Мы не смогли воспользоваться естественным разбиением Проблемы на подзадачи: Компилятор, Стандартная Библиотека, Стратегия, Призраки, — каждый делал всё. На выходе получилось два работающих компилятора, две стандартные библиотеки, две независимые стратегии и ни одного призрака.
Натупили мы напару тоже немало. Взять хотя бы то, что Лёха реализовал подмножество racket'а, но не сообразил, что можно отлаживать Стратегию (или хотя бы Стандартную Библиотеку) на racket'е же. Это как, вообще?! Ха-ха-ха! Я уж молчу про то, что компилятор лиспа в SECD-машину на лиспе гуглится ровно за секунду... Мда.
Отчёты участников в этот раз довольно унылые, честно говоря (или я что-то пропустил?). У _adept_'а, вон, вообще не задался :-) Т.ч. упомяну только отчёт обладателя first prize — Supermassive Black Hom-set и отчёт обладателя judges prize — gagallium.
Зато отжигают организаторы.
Да и вообще, ICFPC держит марку. Огромная благодарность оргам за возможность полноценной offline-работы, отсутствие особых требований к железу и отличную Проблему.
Ну, тренд понятен... Ждём теперь тетрис для НАМ, sokoban для КАМ, minesweeper для МП итд :-)
Do Not Go Gentle Into That Good Night
Финальные результаты можно посмотреть в официальном репозитории. Наши с Лёхой команды называются IKS и SKY (искать ближе к концу списка...). Лёха еще и на 100 с лишним очков обойти меня ухитрился.
The Imitation Game
Да-да, high-assurance cryptography, вот это вот всё. Так что дружно ботаем Cryptol и Co, пока еще есть немного времени.
Анонс в любом случае многообещающий...
