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

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

( Read more... )