Часть 3/3. Компилятор идеальной VM для ICFPC 2009, на Haskell, с популяризаторскими комментариями

Окончание. Предыдущие части: 1 и 2

Что еще осталось? Мы пропустили место, в котором два смежных опкода превращаются в один. Что мы имели? По спецификации проходили следующие операции:

flag = m20 > 0
if (flag) m222 = m3 else m222 = m4


Исследуя бинарные файлы на предмет того, как эти конструкции используются, мы поняли, что они ходят парой Cmp, затем Phi. Наверняка, потому что так скомпилировались организаторами из каких-то их исходных формул ихним каким-то компилятором. Ну, раз так, то мы их немножко склеим в одну операцию:

-- convert 2-op conditional operator to 1-op<br>
removePhi [] = []<br>
removePhi ((Cmpz cond condr1):(Phi addr r1 r2):xs) = <br>
            Noop addr : If cond condr1 addr r1 r2 : removePhi xs<br>
removePhi (x:xs) = x:removePhi xs<br>


Тут работа со списком ведется следующим образом: на вход функции подается список опкодов, на выходе имеем список, в котором эта парочка [Cmp,Phi] заменена на [Noop,If]. Noop вставляется для того, чтобы оставить адреса всех команд неизменными (т.е. чтобы их количество и положение не изменилось, т.к их положение в памяти является одним из их операндов).

Вот, мы определяем, что для пустого списка и делать ничего не надо. Для списка, начинающегося с двух наших искомых команд, мы заменям их на две новые команды, а дальше процессим оставшуюся часть списка. А если список начинается со всего остального (что соответствует третьей строке, здесь остальному дается имя «x»), то мы оставляем это остальное без изменений, и процессим остальную часть списка «xs».

Теперь главная часть программы. Точка входа в Хаскеле — функция main

main = do<br>
        (len,buf) <- readMyFile<br>


Это мы прочитали файл (см выше)

        let nframes = fromInteger $ len `div` 12   -- посчитали количество опкодов и размер памяти.<br>
        -- opcode/data memory in tuples<br>
        ids <- mapM (\i -> instruction (plusPtr buf $ i*12) i) [0..nframes-1]<br>


Здесь замапили каждое i (от 0 до nframes-1] на результат — пару (instructon,data), которая получилась от добавления к указателю (buf) соответствующего смещения (i*12), и интерпретации команды по этому адресу (вызов instruction с указателем где оно лежит и с указанием номера инструкции, для чет-нечет выборки).

-- code AST<br>
let code = removePhi $ map disasm $ zip (map fst ids) [O..]<br>


Теперь мы (читаем справа), взяли из списка пар (ids) все (map) первые (fst) элементы (только инструкции), сделали из них пары (zip) с числами от нуля до стольки, сколько надо ([0..]), потом для все эти пары (инструкция, адрес) пропустили (map) через disasm, получили список Op-ов, после чего удалили из них Phi, сделав вместо нее If (с помощью removePhi).

        -- print code<br>
        putStrLn $ produceCode code (map snd ids)<br>


Далее, имея code и data (через map snd ids — взять вторые половинки из пар "(инструкция,data)", вызвали produceCode с двумя параметрами и напечатали результат (putStrLn).

free buf


А эта строка точно не нуждается в комментарии.

Заключение.

Этот «компилятор» написан на уровне начинающего хаскелиста, понятное дело. Но даже на этом уровене мне стало заметно отличие его от Java, на которой я пишу каждый день на работе.

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

Во-вторых, распределение времени. Большой кусок времени я потратил на исследование работы с Ptr — потому что я выбрал именно этот способ преобразования 8 bytes в Double, и этим раньше не занимался. Затем, около двух третей времени пошло на написание именно декодирования файла, создание AST и базовой его сериализации в Haskell-код (линейный). И лишь треть времения я потратил собственно на алгоритм перевода плоских опкодов в древовидный AST, и алгоритм получался сам собой.

Короче, я испытал чувство глубокого удовлетворения. Жаль, на IFCPC не было на это времени.