Это третья часть моей серии отчётов об ICFPC 2020. Остальные части ищите здесь:

1. предисловие;
2. день первый;
3. день второй (это то, что вы сейчас читаете);
4. день третий;
5. день четвёртый;
6. итоги и выводы.

18-е июля, суббота, T+19:00. Я возвращаюсь в строй

Просыпаюсь, готовлю завтрак и с тарелкой в руках сажусь читать командный чатик. ForNeVeR и portnov, живущие восточнее и потому проснувшиеся ещё четыре часа назад, вместе с pink-snow зафлудили весь лог обсуждением какой-то «вычислялки» для «космолиспа». Решительно непонятно, в каком она состоянии: вроде как у pink-snow всё есть, но при этом и Форневер, и Портнов пилят то же самое… Не выдержав, устраиваю статус-митинг, который наконец вносит ясность:

• pink-snow написал на Python «вычислялку» для galaxy.txt: программу, берующую на вход целый исходник на «космолиспе» и «выполняющий» её, аж пока не получит результат. В «вычислялке» нет мемоизации, так что работает она весьма неспешно. Никто не может понять код, и у всех чешутся руки переписать это на Haskell;
• собственно, ForNeVeR занят первым шагом по переписыванию: парсером из текста во входной тип reduce;
• mr146 экспериментирует на C# с модуляцией-демодуляцией, то есть преобразованием «космолиспа» в последовательность ноликов-единичек и обратно. Это нужно для того, чтобы реализовать send и пообщаться, наконец, с инопланетянами;
• portnov сделал два неудачных подхода к написанию «вычислялки» по аналогии с кодом на Python и теперь пребывает в некой прострации;
• unclechu дописал биндинги для HTTP и спит;
• остальные тоже спят.

Тем временем некоторые соперники получают аж 10 очков, пройдя некий «первый туториал», а организаторы выкладывают видеоуроки по разбору и вычислению «космолиспа». Первый урок, про разбор, к этому моменту мы освоили сами. Второй, про вычисление только левого поддерева, приходится впору — я вчера как раз подбирался к этой идее, а тут мне сразу дали итоговый ответ. А вот третий урок, про шаринг поддеревьев, я проигнорировал, потому что он показался мне скорее оптимизацией, чем строгой необходимостью.

Тут я делаю ошибку: вместо того, чтобы с чистой головой сесть и закодить ровно то, что описали организаторы, я всё ещё цепляюсь за уже написанный reduce. Уверен, начни я с «нуля» — у нас к обеду субботы была бы готовая «вычислялка». Но увы.

Как любит повторять Максим Дорофеев, между срочным и важным человек всегда выбирает… понятное. Так что я решил заняться починкой сабмишенов. Как я уже упоминал во флешбеке про сбор команды, я никого не ввёл в курс дела касательно отправки результатов — а именно, о том, что весь наш код собирается в Docker-контейнере без доступа к Интернету. unclechu, не знавший об этом, добавил к нам в проект Servant и, таким образом, сломал сабмишены. Не знал он и о том, что сабмишены должны при запуске проделывать определённые действия. На устранение всех этих оплошностей у меня ушло два часа. Организаторы всё не мержили мой пулл-реквест с обновлённым Dockerfile, так что я перешёл к следующей задаче: помогать ForNeVeR-у с «вычислялкой».

Тут я снова проделал то же самое, что и вчера с pink-snow: убедил ForNeVeR-а, что «вычислялка» должна быть циклом, опирающимся на reduce для упрощения выражений. Я по-прежнему сопротивлялся всяким попыткам добавить подстановку тел функций в саму reduce. Саботировав таким образом написание рабочей «вычислялки» (во второй раз!), я ушёл обедать, а ForNeVeR продолжил бороться с зависаниями на каком-то тривиальнейшем кусочке «космолиспа».

IngvarJackal тем временем занимался демодулятором на Python. Это была, кажется, уже вторая реализация этого алгоритма. Впрочем, мы не видели в этом проблемы: нам казалось, что в условиях повышенной неопределённости будет даже лучше, если несколько под-команд будут одновременно исследовать задачу на удобных им языках. Я даже предположить не мог, насколько хорошо отобьётся эта наша ставка.

Всё это время я каждые полчаса делал тестовый сабмишен, чтобы знать, когда организаторы деплойнут новый образ с Servant. Сабмишены фейлились. Прошло три часа, а они всё фейлятся. И тут…

T+24:00, Z-48:00. Lightning division заканчивается

Да-да, мы снова не успели ничего сделать в первые 24 часа. И в этот раз мне даже не стыдно, потому что задача действительно дикая.

Как раз в это время проснулся unclechu, и мы с ним принялись выяснять, что же не так с сабмишенами. Оказалось, что деплой уже давно выполнен, и я, по всей видимости, не добавил в образ какие-то библиотеки: Servant-то там есть, а вот десятка невесть откуда взявшихся вспомогательных пакетов — нет. Провозившись с этим ещё полчаса и так и не поняв, как stack смог поставить Servant, но не поставить его зависимостей, я предложил вернуться на http-conduit; благо, нам нужны были только два эндпоинта. unclechu, честь ему и хвала, воспринял это предложение стоически и взялся переделывать.

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

И тут, в Z-47:30, организаторы наконец объясняют, как выиграть контест. Инопланетяне летят устраивать у нас на орбите звёздные войны. Мы обязаны выиграть. Для этого командам нужно писать ботов, управляющих космическими кораблями. Лучший бот сразится с пришельцами, прибытие которых ожидается к концу контеста, в час Z: 20-го июля в 13:00 UTC. Ну наконец-то хоть какая-то определённость!

Судя по новому документу организаторов, нам всё же нужно вычислить galaxy, и там будут нетривиальные картинки:

В связи с этим ForNeVeR передаёт работу над «вычислялкой» мне, а сам отправляется писать на C# GUI, в котором мы могли бы исследовать рисунки galaxy. Ко мне тут же присоединяется Портнов, и мы снова начинаем возиться. Высказываются идеи добавить мемоизацию, чтобы не пересчитывать одинаковые поддеревья. Проскакивает идея добавить в AST частично применённые функции. Мы ходим кругами, пробуя то да сё.

mr146, посмотрев на наши мучения, берётся писать ещё одну (третью) версию «вычислялки» на случай, если мы не преуспеем c Haskell: будет, хотя бы, что прикрутить к GUI. Задач получше для него не находится, поэтому никто не возражает.

Z-44:00. Мы вспоминаем про IngvarJackal-а

Дела с «вычислялкой» на Haskell заходят в тупик, и я решаю глянуть на Python-код, который, вроде, работает. В процессе расспросов о том, как его вообще запустить, обнаруживается, что на Python есть рабочие модулятор и кусочек демодулятора, а IngvarJackal сидит без дела. У меня появляется первая правильная идея за весь день, и я быстренько организую ветку, из которой можно слать сабмишены на Python. IngvarJackal уходит мучить сервер организаторов тестами в надежде выяснить что-нибудь про HTTP API, пока мы доводим до ума «вычислялки» и GUI.

portnov показывает картинки из профилировщика, согласно которым дерево постоянно растёт, а не редуцируется. Я возвращаюсь к разборкам с «вычислялкой». Выясняется, что коллективными усилиями мы ушатали её в хлам: она виснет даже на простейшем кусочке «космолиспа»:

:1 = ap ap vec 2 5
:0 = ap ap cons :1 nil

ForNeVeR, сделав часть GUI, удаляется спать, а portnov пытается добиться какой-то ясности касательно наших дальнейших действий. Прошло уже 29 часов с начала контеста, а у нас до сих пор один балл и нет понимания того, как заработать ещё. Что это за туториалы, пройденные остальными командами? Как до них добраться и как их проходить? Как это связано с HTTP API и galaxy?

Проводим статус-митинг и выясняем, что:

• unclechu уже выпилил Servant и добавил новые функции для двух нужных нам эндпоинтов, а теперь планирует реализовать модулятор/демодулятор на Хаскеле;
• IngvarJackal чинит (де)модулятор на питоне, обкладывая его тестами, и готовится делать сабмишены для выяснения API;
• mr146 пишет «вычислялку» на C#, но готов бросить, как только мы доведём до ума код на Haskell;
• portnov пытается привести в чувство хаскелевскую «вычислялку»;
• остальные спят.

Таким образом получается, что у нас, якобы-Haskell-команды, действительно рабочий код есть только на Python, да и писали его вовсе не «старожилы», а «новички». Иронично!

Z-41:30. Codingteam на первом месте

Akon32 обращает наше внимание на лидерборд, и мы наблюдаем невероятное:

Один из тестовых сабмишенов IngvarJackal-а оказался настолько удачным, что «обыгрывал» соперников несмотря на то, что никакой игровой логики в нём не было: сабмишен выполнял все необходимые инициализации и бездействовал. Практически пустой скрипт на Python выводит Haskell-команду на первое место лидерборда.

Марш смерти

Тем временем мы с portnov пришли к выводу, что пора объединять «вычислялку» с reduce, потому что ни один из нас не может понять, как эти две функции между собой меняют дерево. Промежуточные результаты показали небольшое улучшение: «вычислялка» перестала виснуть на наших простых примерах, но по-прежнему отказывалась что-либо вычислять в galaxy.txt.

Я стал подозревать, что дело в рекурсии, и попытался закодировать простенький цикл вроде этого кода на Haskell:

fn0 = fn1 13
fn1 = \x -> if x == 0 then 42 else fn1 (x - 1)

Тут со мной случилось то, что Тонский назвал «принудительным ликбезом по лябмда-исчислению»: чтобы в fn1 использовать x дважды (в условии и в else-ветке), пришлось напрячь мозг и сообразить, как с помощью двойного применения S-комбинатора «вывернуть» выражение, чтобы оно принимало x как аргумент. Получился вот такой вот код на «космолиспе»:

:0 = ap :1 13
:1 = ap ap s ap ap s if0 ap t 42 ap ap b :1 dec

Он, естественно, не работал, и я потратил ещё чуток времени, добавляя в «вычислялку» на Python поддержку if0 и dec. Код же на Haskell успешно редуцировал выражение к «42», только если в :1 передавался ноль, единица или двойка. Если тройка и больше — вычисление шло вразнос, S-комбинатор в левой ветке не заменялся, и всё заканчивалось каким-то покорёженным выражением.

Мне понадобилось всего полчаса, чтобы сообразить, что, кодируя if0, я бездумно переписал правила из сообщений инопланетян, и эта функция не была определена для значений помимо нуля и единицы. Вот так вот всегда: тестируя руками, мечтаешь о юнит-тестах; написав юнит-тесты, мечтаешь о свойствах на QuickCheck…

Тем временем организаторы смилостивились над нами и выложили псевдокод интерпретатора «космолиспа». mr146 успешно реализовал его на С#, и мне следовало бы уже остановиться, но сонный мозг уже не способен был принимать решения. Пообщавшись с проснувшимся unclechu, я пришёл к выводу, что пора впиливать мемоизацию, а для этого нужно взять монаду State и держать в ней Map, где ключом будет Data.Unique.Unique, соответствующий выражению, а значение (само выражение) мы будем постепенно редуцировать. К счастью, тут меня начал рубить сон, и я принял второе и последнее верное решение за день — лечь спать.

Как поступят мои соратники, проснувшись и обнаружив, что «вычислялка» на Хаскеле всё ещё не готова, зато есть две других? Сможем ли мы наконец понять, как заработать баллы? Об этом читайте в следующем посте :)