Часть 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 (\-> 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 не было на это времени.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 4

      0
      +1, но вот не нужно так нажимать на 'формальное' или 'математическое' мышление, к которому, якобы, склоняют функциональные языки. IMHO, сиё есть заблуждение. Математика не позволяет описывать динамические объкеты. Описывать их свойства позволяет, но сами объекты — нет. Собственно в Haskell мы с этим сталкиваемся, когда нужно устроить ввод/вывод. Кроме того, функциональным языкам уже лет 50 (они старше даже, чем Си), но при этом, люди, которых сложно обвинить в недостатке математического мышления: физики-теоретики, 'распознаватели' образов, математические моделисты и прочие — предпочитают всякие C и Java. Так что, это неправильно считать, что людям с математическим мышлением в Haskell всё ясно. Математика тоже допускает различные стили мышления.

      И ещё… Когда программа вот так на куски разбита довольно сложно следить за её общей структурой. Можно, конечно, всё в блокнотик скопировать последовательно, но лень же :)
        0
        Можете уточнить, с чем именно, не описываемым математикой, мы сталкваемся в Haskell при вводе-выводе?
        С задачами же распознавания образов все, по-моему, достаточно банально — там нужна высокая производительность.
        0
        В моем предыдущем посте была ссылка на исходный код как он есть. Про структуру программы — в следующий раз придумаю, как ее сверху вниз рассматривать, спасибо. Этот же пост задуман для людей, которым любопытно узнать как оно вообще, а есть ли жизнь на марсе?
          0
          Класс. А я убоялся связываться с VM на Haskell, написал на C++, логику стал писать на OCaml и в итоге ничего не успел за сутки, которые удалось выделить.
          Оптимизирующий компилятор из кода регистровой машины в Haskell — это пять. Ещё бы скормить AST LLVM и получилась бы самая быстрая реализация VM.

          И ещё: для чтения опкодов наверное удобнее было бы использовать Data.Binary вместо FFI.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое