ICFPC 2014

В этот понедельник закончился ICFPC — соревнование по программированию, проводящееся ежегодно в преддверии международной конференции ICFP. Последние пару лет я с упоением читал отчёты _adept_’а, да и других людей, повествующих о чудных задачах и трёхдневных гонках за титул победителя. В прошлом году пообещал даже одному чуваку вместе поиграть в ICFPC 2013, но он отправил меня учить OCaml, и на этом всё закончилось (вина моя).

После того несостоявшегося опыта я ничего больше не предпринимал, поэтому когда увидел заметку упомянутого _adept_ касательного того, что конкурс уже на носу, просто сделал себе мысленную закладку не пропустить потом отчётики. Когда контест начался, я интересу ради прочёл первые пару абзацев задания, понял, что оно интересное, и забил — все равно потом в отчётах сто раз перескажут.

А на следующий день в codingteam@conference.jabber.ru раздалось:

<ForNeVeR> Посаны! Хочет кто в icfpc поучаствовать? У нас ещё джва дня, но нас осталось всего джва человека, а работы куча ._.

<ForNeVeR> Задание вот: http://icfpcontest.org/specification.html И вот: http://icfpcontest.org/spec-extra.html

<ForNeVeR> Minoru: ?

<ForNeVeR> У нас там компилятор лиспа уже написан на хаскеле :3

От такого приглашения я отказаться просто не мог ☺

Здесь нужно сделать небольшую паузу и рассказать-таки, в чём же состояло задание.

Организаторы придумали историю о какой-то игровой компании, которая пыталась делать аркады, но зафейлилась и была вытеснена с рынка. Тем не менее, её инженеры успели-таки разработать игру, «очень похожую» на Pac-Man. Призраки в этом клоне выполнялись на каком-то простеньком процессоре, а собственно Пакманом (который в клоне носил гордое имя Lambdaman) рулила лисп-машина.

Для молниеносного тура (первый день соревнований) нужно было написать программу для лисп-машины. Полное же задание (для основного тура, длящегося дополнительные два дня) подразумевало также написание программ для процессора.

Команда состояла из трёх человек: portnov, ForNeVeR и rexim. Последний смог поучаствовать только в молниеносном туре, поэтому на второй день ребят осталось всего двое. Когда ForNeVeR позвал меня помогать, они уже написали на Haskell компилятор из Scheme в код лисп-машины и вовсю пилили волновой алгоритм, так что я занялся призраками. ForNeVeR сказал, что им нужен компилятор для процессора, на котором выполняются программы призраков, и это задало ход моих мыслей до самого конца контеста.

К восьми вечера того же дня я уже начал формировать представление о том, как конструкции языка будут транслироваться в ассемблер, и закоммитил соответствующую заметочку в репозиторий. Спустя три часа язык морфировал в Python с декларациями переменных. Тогда же начал рождаться AST будущего компилятора. Нужно сказать, что раньше я компиляторов с нуля не писал, так что теперь я получал тонны фана, но продуктивность была близка к нулю. Особенно мне мешало стремление сделать AST типобезопасным: воплотить идею в жизнь почему-то не получалось, но и отказатся от неё я себя заставить не мог.

Так ничего толком и не добившись, я закоммитил все свои наработки и отправился спать. Уже засыпая, я наконец-то понял, как именно нужно было дизайнить AST и, проснувшись на следующий день ближе к обеду, сел и всё переписал. Спустя ещё два часа у меня был готов парсер всего, кроме вызовов функций, и вот тут-то я застрял.

Над этой задачей я пусто бился полтора часа, пока наконец не попросил помощи у ребят. portnov почитал код, сделал пару правок, но в итоге я сам методом тыка выяснил (но не понял!), что мне нужно использовать sepEndBy вместо sepBy.

После этого нужно было бы сразу приняться за кодогенерацию, но с ней случилась та же беда, что и с AST: я начал что-то воротить, программа всё не компилировалась, и в итоге к вечеру я попросту сдался, решив, что завтра проснусь вовремя и на свежую голову наконец-то что-то выдам. В этот момент я уже осознавал, что компилятор к концу контеста готов не будет, и нужно менять цель. Поэтому в понедельник утром (последний день соревнования) я занимался уже не кодогенерацией, а написанием призрака вручную.

Здесь меня снова подвела зацикленность на ранних идеях: я решил, что мне непременно нужно начать с призрака, двигающегося случайным образом, и я сразу бросился воплощать в жизнь именно эту идею, не подумав как следует над альтернативами. А ведь как минимум одна другая команда додумалась до идеи, к которой мог бы придти и я: они реализовали D*, воспользовавшись тем, что память между запусками программы управления призраком не обнуляется¹

Писать на языке ассемблера было довольно весело, но немного неудобно: никакого ассемблера на самом деле не было, и писал я фактически байт-код. Вместо меток для условных переходов нужно было писать адрес в теле программы, так что результат я ассемблировал вручную: сначала написал код с комментариями и метками, а потом чистил и расчитывал сдвиги (в чём мне сильно помог vim).

Таким макаром я с первого раза написал вполне корректную программу, которая, тем не менее, не могла даже заставить призрака покинуть комнатушку в центре дефолтной карты:

Над чем я и бился следующие полчаса. Дальше я просто процитирую лог нашего командного чатика:

<Minoru> заметил, что вызываю первое прерывание вместо нулевого

<Minoru> пофиксил, проверил — вроде шагает действительно рандомно теперь

<Minoru> даже из комнатки посреди карты вышел, умница такой!

<Minoru> переключаюсь в окно с mcabber, чтобы сказать ForNeVeR, что я готов сабмиттить

<Minoru> смотрю на часы

<Minoru> 15:59:58

<Minoru> 15:59:59

<Minoru> 16:00:00

<Minoru> T_T

16:00 MSK — это конец основного раунда. Так что моё решение в командный сабмишшен не попало, хотя в репозиторий я его таки закоммитил.

Такие вот дела. Получил море фана, в следующем году обязательно снова к кому-то присоединюсь (надеюсь, что ForNeVeR, portnov и rexim снова позовут писать код с ними). Только стратегию нужно будет поменять: сначала всё-всё-всё продумаю, а потом уже сяду писать первые строчки кода. Потому что чисто теоретически я мог и про D* подумать, и AST быстро написать (такой же, как написали NCPLUG). Нужно было лишь немного помозговать, а не бросаться сразу писать код.

Update 14.09.2014: Заняли в общем зачёте 99-е место (в молниеносном туре не участвовали вовсе). В будущем страничку результатов переместят, так что я сделал копию на память.