Лямбды против присваиваний

[thedeemon]

ICFPC еще торт, скажу я вам! В этом году нам предложили поиграть в пакмэна, где вместо колобка был Лямбдамэн (куда ж без Вадлера), а привидения выглядели как знаки присваивания, квинтессенция императивщины. Лямбдамэн и его враги управлялись программами, исполняющимися двумя различными виртуальными машинами. У привидений-присавиваний была императивная машина с регистрами, данными в виде массива и программами, его мутирующими и вызывающими прерывания для выполнения сайд-эффектов. У Лямбдамэна был вариант SECD-машины, где (за исключением одной ненужной операции) все довольно чисто и функционально. Программа - это функция, принимающая свое прошлое состояние и состояние мира на вход, и возвращающая выбранное ей направление движения вместе с обновленным своим состоянием.
Помимо описания виртуальных машин организаторы выложили и референсную реализацию (мегабайты непролазного джаваскрипта, полученного компиляцией хаскеля).


В первый день я долго изучал спецификацию ВМ Лямбдамэна, писал небольшие программки на ее "ассемблере", и сразу было видно, что это не масштабируется, нужна генерация кода. Долго не мог решить, на чем мне писать. Последние две недели я тут пописывал один компилятор на Идрисе, и накушался его незрелости (от банальных ошибок в базовых библиотеках до генерации некорректного Си, который GCC не ест, или ест, но результат просто падает), так что Идрис точно отпадал. Окамл расчехлять не хотелось, Хаскель - вариант, но непонятно было что именно на нем делать. Было ощущение, что полноценный компилятор мне писать не надо, хватит и какого-то DSL'я для построения выражений и генерации из них "ассемблера". Еще было ясно, что я не хочу возиться с нагромождениями car/cdr/cadadr (это тоже не масштабируется), нужны типы (как минимум структуры с именованными полями и списки). Тут я понял, что проще всего мне будет такой DSL сделать на D. Там очень удобная перегрузка операторов и замечательная вещь opDispatch - аналог method_missing из Ruby и подобных. Описываем базовый класс:

class Val {
    abstract void gen(Writer w);
    abstract Val getMemb(string s);
    Val opDispatch(string s)() { return getMemb(s); };

    Val opBinary(string op)(Val v) {
        Op o;
        switch(op) {
            case "+": o = Op.ADD; break;
            case "-": o = Op.SUB; break;
            case "*": o = Op.MUL; break;
            case "/": o = Op.DIV; break;
            default: assert(0, "Val no has "~ op);
        }
        return new GenVal((Writer w) {
            gen(w);
            v.gen(w);
            w.put(CMD(o));
        });
    }
}

И разные виды значений наследуем от него. Теперь для любого v унаследованного от Val типа можно написать v.smth и это приведет к вызову v.getMemb("smth"), который уже разные типы могут разруливать по-своему. Например, значения-списки будут реагировать на "hd", "tl", "empty", а значения-структуры могут находить по имени нужное поле и генерить код доступа к нему (те самые car car cdr cdr). Всякая арифметика вроде v1 + v2 автоматически превращается в вызов v1.opBinary!("+")(v2), можно в одном месте сразу разные операции описать одним кодом.

В итоге постепенно нарисовался встроенный DSL, и можно было писать так:

Type Int = new TInt;
Type Pos = new TTuple("x" in Int, "y" in Int);
Type G = new TTuple("vit" in Int, "pos" in Pos, "dir" in Int);
Type Map = new TList(new TList(Int));
Type Me = new TTuple("vit" in Int, "pos" in Pos, "dir" in Int, "lives" in Int, "score" in Int);
Type W = new TTuple("map" in Map, "me" in Me, "gs" in new TList(G), "fruit" in Int);
// ^ вот такую структуру получает на вход программа лямбдамэна

//копировать движения первого привидения:
auto args = new Args("my" in Int, "w" in W);
cons(0.num, args.w.gs.hd.dir).gen(w);

// можно описывать функции
w.defun("nth", ["n" in Int, "xs" in new TList(Int)], (w, args) { 
    if0(args.n, 
               args.xs.hd, 
               call("nth", args.n - 1.num, args.xs.tl)).gen(w);
});

w.defun("addVec", ["a" in Pos, "b" in Pos], (w,as) {            
    cons(as.a.x + as.b.x, as.a.y + as.b.y).gen(w);
});

Шумновато, но жить можно.

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

При описании функции сразу задаются имена и типы параметров. Чтобы какое-то сложное выражение вычислить один раз и результат потом использовать многократно по имени, нужен аналог let x = A in B, который естественно разворачивать в (\x -> B) A. Получилось так:

w.let(["x" in Int], 21.num, (w,as) {
    (as.x + as.x).gen(w);
})

Серия let-ов, где следующие значения зависят от предыдущих, грозит превратиться в нагромождение вложенных вызовов тут. В этом месте я понял, что так дальше не пойдет, все эти множественные скобочки, точки, запятые и служебные переменные превратятся в неподдерживаемую кашу. Тогда (в конце второго дня уже) я принял решение сделать таки синтаксис и парсинг из него. Тем более, что есть такая замечательная библиотека как Pegged. В отличие от парсер-комбинаторов, использующих синтаксис языка-хоста, и генераторов парсеров, которые надо запускать отдельно, Pegged получает очень чистое описание грамматики в виде строки и прямо во время компиляции генерит Packrat парсер (который сразу можно во время компиляции же и использовать, но это мне не понадобилось). Вызов Pegged с полным описанием грамматики у меня получился такой:

mixin(grammar(`
Program:
    Prog < (TypeDef / FunDef)+
    TypeDef < "type" Name "=" (TupleDef / ListDef)
    TupleDef < "(" ArgDef ("," ArgDef)* ")"
    ArgDef < Name ":" TypeExpr
    ListDef < "[" TypeExpr "]"
    TypeExpr <- "Int" / Name / ListDef / "*"
    Name <~ [A-Za-z][A-Za-z0-9]*
    FunDef < :Comment* "def" Name TupleDef FunDef* Expr "end"
    Expr < :Comment* (LetExpr / Single (BinOp Single)*)
    Single < "(" Expr ")" / IfExpr / If0Expr / Const / FunCall / VarExpr  / ConsExpr / ListExpr
    BinOp <- "+" / "-" / "*" / "/" / "==" / "!=" / "<=" / ">=" / "<" / ">" 
    LetExpr < "let" Name ":" TypeExpr "=" Expr "in" Expr
    Const <~ "-"? [0-9]+
    VarExpr <- Name ("." Name)*
    ConsExpr < "@(" Expr ("," Expr)+ ")"
    ListExpr < "[" Expr? ("," Expr)* "]"
    FunCall < Name "(" Expr ("," Expr)* ")"
    IfExpr < "if" Expr "then" Expr "else" Expr
    If0Expr < "if0" Expr "then" Expr "else" Expr
    Comment <- "/*" (!"*" .)* "*/"
`));

Теперь достаточно вызвать Program(строка_с_исходником) и получаешь готовое ParseTree, правда, stringly-typed. Функция компиляции у меня проходила рекурсивно по этому ParseTree и превращала отдельные его части в значения типа Val, а иные конструкции - в вызовы соответствующих функций из имевшегося ранее DSL'я (defun, let, call, if0 и т.д.). Синтаксис для нового языка у меня получился какой-то странной смесью Руби, Окамла и Хаскеля. Вот так выглядит программа на нем. В частности, аналоги процитированного выше:

type Pos = (x : Int, y : Int)
...
type W = (map : Map, me : Me, gs : [G], fruit : Int)

def nth(n : Int, xs : [*])
  if0 n then xs.hd else nth(n-1, xs.tl)
end

def addVec(a : Pos, b : Pos)
  @(a.x + b.x, a.y + b.y)
end

На этом языке уже в последний день я стал наконец лепить алгоритм для моего Лямбдамэна. На этапе инициализации он сканирует карту и подсчитывает число соседей-не-стен (0-4) для каждой клетки, составляя такую карту. Затем проходит по ней и разбивает всю карту на комнаты, сопоставляя каждой проходимой клетке номер комнаты, которой она принадлежит. Клетки-перекрестки (с числом проходимых соседей больше 2) становятся отдельными комнатами, клетки-коридоры (с числом проходимых соседей 1-2) объединяются в комнаты-коридоры. Параллельно составлению такой карты строится список с информацией о комнатах: размер, имеющиеся в ней богатства (суммарные очки, которые можно набрать, пройдя по ней), список айдишников комнат-соседей. Карта комнат и их список становятся основной частью состояния Лямбдамэна, передаваемого между ходами. Функция принятия решения во время игры находит по карте в какой комнате мы находимся, дальше по графу комнат (для каждой комнаты известен список соседей же) идет breadth-first на несколько шагов, суммируя для каждого пути бенефиты и выкидывая те пути, что проходят через комнату, занятую привидением. Из полученного списка возможных путей выбирается лучший (по очкам), из него извлекается номер следующей комнаты куда идти, она отыскивается от текущей позиции и так выбирается направление движения. В целом, довольно банальный алгоритм вышел, на более продвинутый не хватило времени.

Собственно, даже на этот времени не хватило, т.к. когда он был уже практически завершен программа начала падать на некоторых ходах и работать на других. Время было на исходе, и такая падучая программа была засабмичена чисто статистики ради. Потом уже баг был найден: в одном месте в функцию getCell(pos : Pos, map : Map) параметры передавались в перепутанном порядке, а в компиляторе у меня была сделана лишь проверка на число аргументов, но не на типы (типы использовались лишь для генерации кода, проверка соответствия не делалась). После исправления этого бага и еще одной глупости получился вариант, который ведет себя более-менее разумно, хоть и все равно съедается привидениями после обхода почти всего уровня. А на составление программ для привидений у меня времени не хватило совсем, как видите.

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

А, да, репа с исходниками тут.

Comments

[swizard.livejournal.com]

А у тебя этот "смесь Руби, Окамла и Хаскеля" только в GCC компилировался, или его можно было на хосте как-то запускать? Если нет, то как ты его отлаживал, там же алгоритмы нетривиальные достаточно?

[thedeemon.livejournal.com]

Только компилировался. Для отладки лишь волшебный print(x,y) - выводит x и возвращает y.

[gliv.livejournal.com]

Отличное описание! Спасибо.

[pbl.livejournal.com]

ICFPC еще более торт, чем когда-либо! (До 2009 не считаю, ибо не привлекался.)

Вот еще роскошь со статической типизацией и выведением типов: https://github.com/RafaelBocquet/icfp-contest-2014/blob/master/LM/lambdaman_source.hl

Или даже так: https://github.com/ychin/icfp_2014_CannonBrawl/blob/master/code/lambdaman_ai.hs

По моей оценке это сберегло бы мне миллионы невинноубиенных синапсов. А во втором случае это еще и eDSL, так что не надо парсер малевать.

"...анализировать программы привидений, моделировать их поведение" - не, мало циклов. Возмем карту 256x256, 256 гостов, выполняющих 1024 инструкции, и 8 операций на доступ к 256 байтам рама, это ~2,000,000 инструкций в GCC. На один тик. По оценке снизу. При лимите в 3,000,000.

[jsn.livejournal.com]

Ну в позапрошлом, что ли, году тоже была задача на path finding и прочие A*, что ж опять-то. Я вот не смог себе заставить снова это писать (поэтому brohm писал).

LambdaMan CPU: это ж SECD-machine, сразу было видно. Я за первые сутки написал для него на scheme компилятор scheme c tail call elimination, шахматами и поэтессами (но без макросов, впрочем). Records потом легко делаются на схеме (но мы, впрочем, не стали морочиться).

В ghost CPU был лимит в 1000 инструкций на ход, но память и регистры (кроме PC) сохраняются между ходами. Написал для него path finding с поддержкой resume computation на каждом следующем ходу (на макроассемблере в виде DSL на ruby).

[thedeemon.livejournal.com]

Круто!
А как был сделан pathfinding у гостов в условиях такой маленькой памяти?

[jsn.livejournal.com]

Ну он недалеко трейсит. Сначала он трейсит до ближайшей развилки, потом от нее трейсит в каждом из трех направлений до ближайшей развилки. Для каждого трейса запоминает best distance seen до пакмана.

Edit: у меня при этом память команд кончилась сильно раньше, чем память данных.

[azamat kalimoulline (from livejournal.com)]

Я тоже сначала хотел сделать с resume computation, но потом забил на это дело. Решил сделать тупее, но быстрее соображающего.

[azamat kalimoulline (from livejournal.com)]

Мы запоминали тупиковые клетки и расширяли их список, а далее просто по уменьшению расстояния до цели. Или по увеличению в случае убегания.

[eiennohito.livejournal.com]

А я участвовал вместе с командой японцев.
Первой мыслью было тоже взять язык, который хорошо поддерживает DSL и играться с ними, но потом я вспомнил, что в Скале были хорошие макросы и решил просто брать AST скалы и генерить по нему GCC код. Правда кодогенерацию писал не я (по большей части).
На второй день я читал тайпчеканые деревья из компилятора скалы и использовал информацию о типах на всю катушку.
Кроме этого я ещё реализовал страшное извращение над железом GCC: массивы с O(log n) на чтение и запись. Имея такие массивы и паттерн матчинг можно было бы написать симулятор процессора для гостов, но мы забили на эту идею.

https://github.com/eiennohito/icfpc2014

[thedeemon.livejournal.com]

Классно! xeno_by будет рад. :)

[xeno-by.livejournal.com]

Выглядит прикольно :) Несколько вопросов по коду:

1) В файле Annotations.scala определяется пачка функций liftXXX. Почему бы их не выразить в виде инстансов Liftable? Тогда во многих местах их вызов можно было бы опустить. upd. Ага, заметил лифтаблы. А почему тогда вы пишете ${liftExpr(expr)} вместо просто $expr?

2) Как я понимаю, единственная задача аннотации @gccCode - добавить в компаньон поле ast, правильно? Если это так, то тогда можно было бы наверное не заморачиваться с c.typecheck в макро аннотации, а перенести логику разбора типизированного скаловского аста в деф макрос. Ну то есть аннотация бы всегда эмиттила `val ast: ... = yourDefMacro(...)`, и тогда в yourDefMacro приходил бы уже тайпчекнутый код. Просто c c.typecheck в аннотациях есть ряд проблем, поэтому я всегда чувствую себя нервно, когда его кто-то юзает :)

3) Увидел throw new MacroException. Почему бы не c.abort? Или c.error, чтобы репортить несколько ошибок сразу?

4) Какие у вас в целом проблемы были с макросами? Что особенно выводило из себя?

5) Вместо tupleLast можно было бы наверное заюзать shapeless. Я не до конца уверен, но по-моему в нем прямо для туплов определен статически типизированный метод last наряду с другими collection-like методами.

[eiennohito.livejournal.com]

1) Я сначала не использовал MacroBundles и попытался использовать как раз Liftable, определив их в другом object по примеру в http://docs.scala-lang.org/overviews/quasiquotes/lifting.html , однако оно не захотело компилироваться, так как context.universe и scala.reflect.universe были разные. Поэтому я грязно кастанул одно к другому (с мыслью авсоь получится, так как чистота кода в целях особо не стояла) и оно некоторое время работало на функциях. Потом я всё собрал в MacroBundle и стало гораздо лучше, но всё переписывать было лениво и я обошёлся минимальным вариантом.

2) Основная идея была в том, чтобы делать класс "модулем" компиляции, собирать оттуда все функции, но выдавать только нужные, а именно точку входа + все использованные, что и делал линкер. Аннотации в этом случае делали минимум проблем для народа, который писал AI, а он писал на скале первый раз в жизни по большей части :)
Я просто не знал, можно ли из функции достать тайпчекнутый ast другой функции, если да, то всё было бы очень просто и я бы так и сделал. Если в scala.meta AST будут достпны в рантайме, то такие игрушки будет писать гораздо легче

3) Можно было :) Но даже этот эксепшн у народа, который писал ИИ не выпал ни разу вроде бы

4) Для первого более-менее серьёзного использования макросов в скале проблем было меньше, чем я ожидал. Таки прототип этой штуки мне удался за примерно 6 часов (включая чтение документации) и это я считаю успехом со стороны вашей API и всех окололежащих штук типа квазиквотаций.
Только описание использования Toolbox (в REPL) в документации квазиквотаций не работает, опять же из-за проблем с universe. Вариант, что в документации scala.reflect работает.

5) tupleLast не рекомендовался к использованию с момента как я стал использовать деревья с типами, так как там в можно было достать размер тапла из его типа и не было никаких проблем с доступом к последнему элементу стандартными средствами. А когда я писал эту штуку, я пользовался ещё не тайпчекнутыми деревьями.

[xeno-by.livejournal.com]

Не знаю, куда пропал последний камент, который был ответом на мой камент, поэтому отвечаю тут:

2) Тайпчекнутый AST другой функции получить пока что нельзя, но можно этот AST себе скопировать локально (в качестве аргумента для деф макроса) и потом его разобрать.

4) Рад слышать! А что не так с примерами из документации по квазицитатам?

[thedeemon.livejournal.com]

ЖЖ его заскринил по дефолту, я открыл сейчас.

[eiennohito.livejournal.com]

2) Ну наверное для компилятора -- решения этой задачи макрос-аннотация был лучшим решением, так как требует меньше манипуляций со стороны пользователей. Все равно код состоит из кучи хаков.

4) Если в консоли, как написано на http://docs.scala-lang.org/overviews/quasiquotes/setup.html набрать
val universe = reflect.runtime.universe; import universe._
import reflect.runtime.currentMirror
import tools.reflect.ToolBox
val toolbox = currentMirror.mkToolBox()

то результатом будет
scala> toolbox.typecheck(q"val x = 5")
:15: error: type mismatch;
found : universe.ValDef
required: toolbox.u.Tree
toolbox.typecheck(q"val x = 5")

[xeno-by.livejournal.com]

Спасибо! Я починил баг в документации.

[azamat kalimoulline (from livejournal.com)]

"Было ощущение, что полноценный компилятор мне писать не надо, хватит и какого-то DSL'я для построения выражений и генерации из них "ассемблера""

Ну так это почти компилятор. Учитывая, что бэкендом лежит вполне полноценная SECD машина.