Отчёт об ICFP Contest 2020
Сразу приведу ссылку на наш проект на GitHub, там к моменту публикации моего отчёта уже могут найтись и ссылки на отчёты других участников из нашей команды.
Недавно закончилось ежегодное соревнование, которое официально называется ICFP Programming Contest 2020, а по моим документам для простоты проходит просто как ICFPC-2020. Как и в прошлом году, я постарался прямо на ходу делать какие-то заметки по каждому дню соревнования, чтобы упростить себе работу по составлению итогового отчёта. И, как и в прошлом году, это сработало неплохо; из этих вот ежедневных фрагментов (и некоторой дополнительной информации, которую собрал уже позже) я и собрал нижеизложенный отчёт.
На этот раз соревнование фактически началось намного раньше официального старта: 1 июля аккаунт zaitsev85, по сюжету принадлежащий астроному Ивану Зайцеву из уральской обсерватории Пеговка, выложил на GitHub обращение к учёным и инженерам, в котором он просит помочь с расшифровкой таинственной радиопередачи, полученной из космоса (приложена в виде аудиофайла).
В течение последующих нескольких недель сообщество понемножку расшифровывало эту и новые поступающие передачи — как было выяснено, присылаемые космическим аппаратом с (возможно) живыми инопланетянами на борту!
Аудиосообщения тривиально преобразовывались в двухмерные пикселизованные изображения, которые рассказывали нам об инопланетной системе записи чисел и базовой арифметике. Сообщество с интересом взялось разгадывать смысл этих посланий: кто-то считал, что там зашифрованы химические символы, кто-то видел намёки на отрывки ДНК.
По задачам прошлых лет я помнил, что все эти разминки перед настоящим соревнованием, как правило, не имеют к нему прямого отношения, и поэтому принимать участие в этом исследовании вовсе не обязательно. Тем более, что оно носило какой-то скорее творческий, нежели прагматичный характер, как мне тогда показалось.
Поэтому я спокойно занимался своими делами, готовил инфраструктуру, и немножко участвовал в формировании команды (хотя тут больше меня, конечно, постарался Минору). В итоге наша команда состояла из следующих людей (приведу список аккаунтов на GitHub, честно перемешанный первым попавшимся сниппетом на PowerShell):
mr146 присоединился к нам совершенно неожиданно: это мой коллега, который (видимо) нашёл в моём блоге отчёты прошлых лет и изъявил желание поучаствовать. Хоть для чего-то эти старые отчёты пригодились!
Понемногу продвигалась и подготовка по другим фронтам: мы традиционно создали запароленную конференцию в XMPP, но, помимо неё, в духе времени включили и трансляцию этой конференции в закрытую группу в Telegram. Для этого пришлось наспех запатчить бота, который занимается проксированием сообщений, чтобы он научился заходить в запароленные конференции. Обнаружился такой недостаток, что он не умеет нормально транслировать изображения и другие медиасообщения из Telegram, что доставило некоторые неудобства. Надо будет всё-таки доработать эту его возможность.
Ближе к началу соревнования мы также собрались и проверили окружение у всех участников: каждый установил Haskell Stack (потому что в этом году была договорённость писать на Haskell), и проверил, что всё правильно собирается и работает.
Ещё одним существенным моментом было то, что как раз к началу соревнования я, наконец, ввёл в строй новый более мощный домашний компьютер. Поэтому, когда соревнование началось, я отложил проверенную инсталляцию Stack на старом компьютере, и решил всё-таки врубить всё на новом. Как оказалось — ну, всё-таки не зря, но и беспроблемным это решение не назовёшь.
2020-07-17, день 0
В моём часовом поясе соревнование началось довольно поздно (в 20:00+0700), поэтому моё участие в первый день было довольно ограниченным.
На момент старта были худо-бедно представлены описания примерно первых 15 сообщений, и выложены некоторые более новые сообщения, но уже без описаний, что они означают.
Как тогда казалось, смысл соревнования состоит, в написании интерпретатора для программ на инопланетном языке лямбда-счисления.
Меня сразу расстроило, что часть информации была опубликована до официального начала соревнования, и участники, которые участвовали в их расшифровке, получили преимущество в lightning round: они уже знают пусть не всё, но многое про инопланетян, и намного лучше ориентируются в документации.
Сразу начались проблемы с GHC (плох тот ICFPC, где не было выявлено каких-нибудь небывалых багов в GHC или в рантайме Хаскеля!): на свежей Windows 10 2004 компилятор как-то очень уж стремительно разваливается.
В итоге за первый день я практически ничего полезного не делал, а просто
знакомился с документацией и пытался развернуть локальное Haskell-окружение. Но,
насколько я помню, доделать всё, чтобы работало хорошо, у меня вышло только на
второй день. До этого я пытался заставить Stack использовать более свежую версию
компилятора, которую сам скачал из интернета, а оказалось, что достаточно просто
включить одну опцию в stack.yaml.
2020-07-18, день 1
За сегодня мы очень хорошо поработали, но кажется, что мы едва достаём до самого нижнего (на текущий момент) слоя задачи. В lightning round мы, как обычно, никак не выступили, и приступили уже к полноценной реализации того, что на текущий момент считается реальным заданием.
Раскрылось следующее: написание интерпретатора для языка (который из себя
представляет ничто иное, как лямбда-счисление с кодировкой Чёрча для некоторых
вещей типа логического типа и списков) — это лишь самое начало задачи. (Кстати,
основной интерпретатор мы пока так и не доделали хоть до какого-то
работоспособного состояния.) Настоящая задача — это запуск программы
galaxy.txt (название по имени файла, присвоенному организаторами), которая
написана на том же инопланетном лямбда-языке.
В языке есть побочные эффекты (в виде функции send, которая общается с
сервером организаторов), а также возможность работать с графическим интерфейсом
(туда мы передаём координаты пикселя, по которому «кликнул» пользователь, а
программа нам возвращает изображение нового состояния UI). Разобраться дальше у
нас пока не получилось, потому что не получилось запустить эту программу, так
что всё ещё непонятно, что делать дальше.
Есть какие-то подающие надежды эксперименты на Питоне (которых я стараюсь не касаться, ибо никакого интереса в работе с этим стеком не ощущаю) и полуработающий интерпретатор на Haskell — который был сегодня начат мной (на базе уже имеющихся наработок по упрощению выражений, которые очень пригодились), и подхвачен Портновым и Минору, которые доводят его до ума.
unclechu за прошедшее время успел перевести HTTP API на Servant (какая-то крутая библиотека для Haskell), но у нас открылись сложности с её использованием в тестовом окружении организаторов, поэтому в итоге ему пришлось всё переписывать обратно.
mr146 в это время занимается какими-то наработками на C# (модулятор и демодулятор, а также база для интерпретатора). Также, я решил написать GUI на C#, но не переписывать при этом эвалюатор и прочее, а просто сделать IPC с программой на Haskell через stdin/stdout.
2020-07-19, день 2
За ночь организаторы соревнования выложили свою реализацию эвалюатора, по образцу которой мы относительно быстро смогли починить свою. Сегодня, после некоторых споров, я реализовал UI на C# (Avalonia нас действительно спасла и почти без проблем завелась у всех участников); при этом бэкендом для неё стала программа на Haskell (я быстро прикрутил протокол на stdin/stdout на основе языка программирования инопланетян, что отдельно забавно). Цитата из чата с обсуждением протокола:
ForNeVeR
InteractResult 0 nil [[(0,1)]]
Можно вот это перевести в обычную алиенову форму?
Ну там ap ap vec
У меня просто для неё уже парсер есть
pink-snow
Это такой протокол взаимодействия будет у GUI?
ForNeVeR
Он уже такой есть
portnov
ой, ладно, пусть инопланетный протокол, скажите спасибо что не soap-xml
UI выглядел вот так (это скриншот с более позднего этапа, но основная часть визуализации уже была приблизительно такой):
Мы смогли поисследовать этот UI и порешать там всякие забавные задачи, но в
итоге уткнулись в то, что для непосредственного запуска игры нужно прикрутить
работу с сервером организаторов (то есть ту самую функцию send, которая у нас
ещё не работала). Это доставило несколько неудобств, но в итоге мы это сделали.
К этому моменту стало примерно понятно, что на самом деле весь этот galaxy.txt
и виртуальная машина для лямбда-языка вообще не имеет отношения к итоговой
задаче: исследование работы galaxy.txt и его посылок к серверу должно было
только лишь помочь нам составить представление о командах, которые управляют
настоящей игрой (теперь уже действительно настоящей).
Реальная задача заключалась в управлении космическим кораблём, решающим одну из боевых задач (нападение или оборона). Ботов, написанных разными участниками, запускают в контейнерах и сталкивают друг с другом, кто лучше всех выступил — тот и победил. В игре есть гравитация, создаваемая космическим телом непонятной формы (в визуализации выглядит квадратным, но внутри команды было мнение, что оно на самом деле круглое), а корабли оснащены двигателями, лазерными пушками и (как обнаружилось позже) возможностью создавать дочерние корабли.
Часть нашей команды пилит работающего бота на Питоне, а я с остальными активно занимаюсь доработкой инфраструктуры на Хаскеле.
mr146 успел за сегодня сделать возможность шагать вперёд и назад (по стеку состояний) в нашем GUI, чтобы можно было легко отменять шаги вычисления; также, была сделана возможность сохранять и загружать «игровые сессии».
2020-07-20, день 3
Необычен уже сам факт моего участия в этот день: обычно третий день соревнования — это уже понедельник следующей недели, и поэтому я в него шёл на работу. Но в этот раз решил взять отгул, потому что сделанной нами работы явно недостаточно для получения хоть каких-то баллов в финале.
Я продолжаю развлекаться доработкой нашего творения на Haskell, и даже научил его заходить в игру и делать какие-то действия. К сожалению, за всё время соревнования мне так и не удалось перейти к активной стадии разработки (когда нужно придумывать стратегии и принимать участие в сражениях): получается, что всё время я занимался, по сути, бесполезной работой, которая в зачёт команде практически не пошла.
Сегодня или вчера Портнову удалось добраться до списка тьюториалов в UI, он выглядел вот так:
К сожалению, толком поиграться с ними не получилось, потому что просто не хватило времени, да и практически всю информацию, которую оттуда можно получить, мы уже знали благодаря изучению поведения нашего бота на Питоне (я был близок к тому, чтобы забросить Хаскель и что-нибудь туда наконтрибьютить, но сдержался).
Тем временем остальные допинывали бота на Python, и мы даже достигли довольно неплохих результатов: 37 места на момент традиционной заморозки рейтинга (впрочем, по баллам у нас всё не так уж и хорошо: у команд в топе до 264 очков, а у нас всего 26). Всего команд, набравших больше нуля баллов, 62 штуки, так что мы где-то пониже середины рейтинга.
Уже после завершения соревнования организаторы опубликовали итоговую таблицу рейтинга (pre-final), в которой нас таки подвинули на 38 место из 95 команд (при этом ненулевой рейтинг — у 65 из них).
А ещё внутри нашей команды зародился очередной мем: как мне показалось, не все участники осознали, что в кодировке Чёрча список формируется из пар, и поэтому модуляция для списка должна работать абсолютно идентично модуляции для пар. Многие пытались разделять эти типы у себя в языках, и не всегда получалось канонично, что приводило к множественным ошибкам во время модуляции и демодуляции данных. Дискуссии про списки и пары периодически появлялись в чате, но понять друг друга участникам таких дискуссий было неимоверно сложно (не иначе, из-за перегруженности термина список, особенно между разными языками программирования).
Выводы
Само соревнование мне понравилось, но не полностью. Первая половина (про виртуальную машину) всё ещё вызывает восторг, я очень люблю такие штуки. А вот вторая часть (про управление кораблём с помощью непонятных команд, которые нужно или угадывать, или подсматривать в документации) уже такого интереса не вызвала.
Ну и очень расстроило начало, когда оказалось, что нужно было за две недели до начала уже начинать следить за информацией и разгадывать загадки организаторов. Такого до сих пор не было!
Основной проблемой для нашей команды стало, как обычно, резкое рассредоточение усилий. Значительное время было потрачено на разработку бота на Haskell, который так и не был опубликован. Это печально, но что ж поделаешь. Также, лично меня очень сильно демотивировала эта ситуация: видя, как развивается бот на Python, я не мог хорошо сосредоточиться на доработках Haskell. Ну и нормально расписаться для работы с Haskell получилось только к самому последнему дню соревнования.
Ещё стоит отметить, что на Python было несколько жалоб в связи с тем, что он не проверяет корректность программ во время компиляции (которая вообще, по существу, отсутствует), и поэтому даже в последние минуты мы умудрились отправить организаторам поломанную программу :(
На Питоне не понравилось писать не только мне, unclechu тоже сильно расстраивался по этому поводу.
Почитав отчёт товарища tonsky, я таки загорелся мыслью сделать каких-нибудь заготовок перед соревнованием: может быть, какой-нибудь общий визуализатор, который бы точно у всех заработал хорошо (потому что мы его заранее отладили), а, может, и что-нибудь ещё.
Помимо этого, очень интересно оказалось смотреть на то, как люди программируют на «родном» для них языке, и на «неродном»: скажем, unclechu отлично и быстро решает задачи на Хаскеле, но, столкнувшись с чем-то другим, бывает раздосадован и демотивирован. Или mr146 и я: быстро написали довольно немаленький кусок логики на .NET, но тот же самый я с большим трудом мог разобраться в коде на Хаскеле и доработать его.
Мне понравилась идея писать штуки на разных языках и объединять их через IPC, так что, может быть, будет полезно наделать каких-то заготовок на эту тему — может, какую-то IPC-библиотеку с шаблонами на разных языках, которыми мы пользуемся?
Помимо этого, меня не оставляет мысль использовать какой-то «научный» подход к обоснованию выбора технологий, которыми мы пользуемся. Может быть, в ближайшее время попробую поставить некоторые эксперименты на эту тему.