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

[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

[jsn.livejournal.com]

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

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

[azamat kalimoulline (from livejournal.com)]

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