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

Здесь мы будем разбирать по буквам некую программу (компилятор VM) на Хаскеле. На вход этому компилятору дается бинарный файл с инструкциями некоего процессора, где в этих инструкциях описываются некие вычисления. На выходе нашего компилятора получается текст программы, тоже на Хаскеле, которая производит те же самые вычисления, с большой скоростью. Возможно, это не компилятор, а декомпилятор, не знаю. Сравнение работы результирующих программ на Haskell/Java приводится в предыдущем посте.



Предупреждение: людям с формальным математическим мышлением читать запрещено! Вы уже и так всё знаете. Этот пост для людей, интересующихся еще чем-то сверх обычных C/C++/C#/Java, потому что в последние 5 лет им надоело писать одно и то же на этих чудесных языках.

Про исходное задание ICFP контеста еще раз, с техническими подробностями: нам дается бинарный файл, в котором программа (вычисляющая формулы) написанная в машинных инструкциях некоторого процессора. Формул сразу несколько, потому при вычислении формул используется специальный пул для возвращаемых значений. Есть пул для входных значений. И есть пул для хранения значений, требующихся во время расчета формул, и для значений, живущих от итерации к итерации (т.е. когда программа запускается много раз, она может использовать данные от прошлого запуска). Входной пул в терминах задачи называется набором входных портов, аналогично существуют выходные порты, всё остальное называют просто «память».

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

Реализовать этот черный ящик, чтобы он вычислял вообще быстро, и является нашей первой целью в ICFPC 2009, а остальное (рассчитать управляющие воздействия на спутник, чтобы он правильно летал в мире, который описывается этими формулами) — является самой главной целью контеста, которую мы рассматривать этом посте не будем, а может быть, в другом.

В этом бинарном файле первоначальные данные были расположены вперемешку с кодом следующим образом:

Смещение (дес)	Длина	Содержимое	Тип
O	8	данные(ячейка 0)	Double
8	4	опкод(ячейка 0)	UInt32
12	4	опкод(ячейка 1)	UInt32
16	8	данные(ячейка 1)	Double

потом тот же порядок повторяется для ячеек 2,3, затем 4,5 итд. В спецификации написано: для четных ячеек вначале идут данные, затем опкод, для нечетных наоборот. Зачем здесь есть данные, почему вообще существуют даннные, отличные от нуля? Очень просто, 1) в опкодах невозможно забить константу, используется переменная (ячейка памяти), которая никем не модифицируется 2) некоторые переменные инициализированы, и они тоже лежат в данных.

Для того чтобы скомпилировать таковой бинарник в красивый текст на любом языке, необходимо:

1) прочитать бинарник в буфер
2) отделить данные от опкодов
3) построить AST из опкодов (AST в здешних терминах — это дизассемблированный опкод разложеный в удобную для манипуляций форму, в оригинале это означает Abstract Syntax Tree, дерево абстрактное потому что содержит суть программы, а не ее текстовое или бинарное представление)
4) трансформировать AST в другой вид (более высокоуровневый)
5) вывести AST в текстовом виде на требуемом языке, а также вывести определение данных с их первоначальным значением.

Далее идет программа с комментариями для совершенно далеких от Хаскеля людей, поэтому некоторые моменты в объяснениях намеренно упрощены и даже слегка искажены (помечено отдельно), для легкости восприятия.

Подключение некоторых стандартных модулей:

import System.IO<br>
import Foreign.Marshal.Alloc<br>
import Foreign.Ptr<br>
import Data.Word<br>
import Foreign.Storable<br>
import Debug.Trace<br>
import Data.Bits<br>
import Data.List<br>
import Data.Maybe

Описание синонимов типов, для подробности последующих определений данных: говорится, что исходный адрес в составе команды имеет тип Int, равно как и адрес назначения.

type DestAddr = Int<br>
type SrcAddr = Int

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

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

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

data Op = <br>
-- это конструкторы использующиеся в дереве. В частности, листья дерева:<br>
 Const Double |<br>
 ReadExp SrcAddr |  -- read main memory<br>
 ReadVarExp SrcAddr | -- read temporary variable<br>
 ReadPortExp SrcAddr | -- read port<br>
               -- узлы дерева:<br>
          SqrtExp Op | SubExp Op Op | AddExp Op Op | MulExp Op Op | DivExp Op Op | -- math<br>
 IfExp CmdOp Op Op Op  | -- branch: compare 1st op with zero, choose from other ops.<br>
-- плоские операции (из спецификации+дополнительные)<br>
 Add DestAddr SrcAddr SrcAddr |<br>
 Sub DestAddr SrcAddr SrcAddr |<br>
 Mul DestAddr SrcAddr SrcAddr |<br>
 Div DestAddr SrcAddr SrcAddr |<br>
 Output SrcAddr SrcAddr |         -- copy from memory to out port.<br>
 If CmdOp SrcAddr DestAddr SrcAddr SrcAddr |  --  compare mem with 0,choose,store <br>
 Input DestAddr SrcAddr |   -- read src port into memory<br>
 Sqrt DestAddr SrcAddr |<br>
 Copy DestAddr SrcAddr |<br>
-- низкоуровневые плоские операции, от которых мы избавляемся практически сразу<br>
 Cmpz CmdOp SrcAddr |   -- first part of "If"<br>
 Phi DestAddr SrcAddr SrcAddr |    -- second part of "If"<br>
 Noop DestAddr   <br>
                                deriving Show


Видим, что варианты у нас перечисляются через символ "|", традиционно означающий «или». Также наличествует «deriving Show», означающее, что если мы захотим перевести какое-то значение данного типа к строке, то получим строку на хаскеле, приблизительно близкую к оригиналу. Данная конструкция означает буквально следующее: «компилятор, сделай указанный тип принадлежащим к классу Show, а метод класса Show, который переводит из значения в строку, сгенерируй сам таким, какой умеешь.»

Теперь о том, что у нас будет про дерево. Предположим, в результирующем коде будет сгенерено выражение:
o32 = (i2 * 37) + (m75 * (m76 * t4))
Оно означает: в выходной порт поместить значение входного порта умноженное на 37 плюс произведение двух ячеек памяти и одной временной переменной. Выражение справа от скобок записывается в терминах нашего AST следующим образом:

     AddExp (MulExp (ReadPortExp 2) (ConstExp 37)) ...<br>
         ... (MulExp (ReadExp 75) (MulExp (ReadExp 76) (ReadVarExp 4)))   -- lisp? ;)

Если посчитать скобки, должно сходиться 8). Что у нас в листьях дерева? Константы, входные порты, память и временные переменные. Как мы отличаем одно от другого? Ведь по спецификации у нас есть только входные порты и память? Откуда же берутся константы, например?

Очень просто. Если у нас в ячейку никто не пишет, а все только читают из нее, то это константа. Имеет смысл вынести ее из «памяти» и забить ее константой в результирующем коде. Аналогичным образом отделяются временные пременные от постоянных переменных, а так же переменные, которых вообще не должно быть, то есть они должны быть преобразованы прямо в выражения со скобками (см несколько ниже).

Продолжаем. Ниже описан кусок AST для условных операций (сравнение с нулем, из спецификации). Сравнений пять штук, по результатам сравнения идет выбор из одного или из другого адреса памяти.

data CmdOp = Ltz | Lez | Eqz | Gez | Gtz deriving Enum

Представляет интерес конструкция «deriving Enum». Она автоматически относит данный тип к классу Enum, а типы этого класса имеют метод, позволяющий перевести экземпляр типа в целое, и наоборот. Будет использоваться в следующем абзаце.

Теперь зададим, что тип CmdOp принадлежит к классу Show. Данный класс используется для перевода значений какого-либо типа к строковому типу, как было упомянуто выше в «deriving Show». В нашем случае мы не хотим, чтобы компилятор сам генерировал конвертирующие методы по умолчанию, а реализуем свой метод (функцию).

instance Show CmdOp where<br>
show cmdOp = ["<0","<=0","==0",">=0",">0"] !! fromEnum cmdOp

Собственно функция — это show, она берет параметром cmdOp, возвращает строку, одну из списка. Выражение справа от знака равенства означает: перевести из значения в целое (fromEnum, вспоминаем deriving Enum), затем это целое использовать как индекс (функция "!!") для выборки из списка (список в квадратных скобках). Коротко и ясно, зато O(N), ну и что. O(N) здесь означает что для получения пятого элемента списка потребуется 5 итераций (потому что здесь использован список, а не массив), а для N-ного, следовательно, N итераций, что долго. Существует простая возможность ускорить, написав case или использовав массив, но я экономил строки программы 8-)

Далее идет функция, переводящая Op в язык, в который мы компилируем. Мы компилируем в хаскель, и поэтому требуется следующее введение:

Наш черный ящик на входе имеет входные порты, и свое предыдущее состояние, а на выходе имеет свое состояние и выходные порты. А скомпилированный в Хаскель бинарный файл будет содержать в себе одну функцию, которая на входе и на выходе будет иметь те же данные. Возвращать выходные порты будем как часть структуры. Таким образом, откомпилированный файл будет содержать в себе:

1) описание данных:

data VMState = VMState { m13, m55, m77, o11 :: Double }  -- выходные порты и persistent mem

2) главную функцию (подробно разбирается далее):

nextState :: VMState -> (Double,Double,Double...) -> VMState<br>
getNextState x (i2,i3,i16000...) =                                                                                       (1)<br>
   let t1 = i2+i3 + m55 x;<br>
        t2 = if (i-16000 > O) then t1*(i16000+1) else O<br>
   in VMState { m13 = t1+t2*2, m55 = 2*i3..... o10 = (i2+22)*576000.0 }

3) функцию, возврающую состояние черного ящика в момент времени 0 — то есть те данные, которые мы будем кормить ему итерация за итерацией:

initState = VMState { m13=O, m55=123.456, ...o90 = O}

Рассмотрим по пунктам каждую строку. Первая объявляет «структуру» данных. Ее отличие от структур C/Java в том, что ее поля нельзя менять, возможно только получить новую структуру с некоторыми (или одним, или всеми) измененными значениями текущей структуры. Пишется это так:

     let newStruct = oldStruct { field5 = 7, field10 = O }

После чего, при желании, старые данные можно выкинуть.
Для чтения одного поля из структуры используется синтаксис:

     let myFieldValue = field5 newStruct

Почему так странно? Потому что при объявлении структуры автоматически объявляются все функции для доступа к ее полям. В частности, неявно появляется функция (например):

field5 :: VMState -> Double 

Это значит, что функция получает на вход значение VMState (в нашем примере наверху мы передали целиком newStruct), а возвращает численное значение с плавающей точкой.
Попутно мы поняли, как выглядят сигнатуры методов (название метода :: тип). Смотрим на главную функцию

nextState :: VMState -> (Double,Double,Double...) -> VMState

В хаскеле троеточий нет, это я их добавил для иллюстрации того, что мы объявим кортеж из стольких double, сколько нам нужно будет. Функция берет 2 параметра, первый это VMState, второй состоит из нескольких значений (в нашем случае это значения всех портов), и возвращает эта функция новое значение VMState.

Главная функция идеальной VM имеет синтаксис, подобный нижеследующему:

fun arg1 arg2 = <br>
  let bind1 = expr1; bind2 = expr2<br>
  in exprResult<br>
  where bind3 a1 a2 a3 = expr3<br>
             bind4 a5 a6 = expr4

То есть, мы можем определить некоторые повторно используемые выражения в разделе «let», а потом их свободно использовать в результирующем выражении (которое в «in»). Также мы можем определить такие же выражения в разделе «where», только там обычно описывают не переменные, а функции, локальные (по видимости) к объемлющей функции (fun). Функции можно также описывать в разделе let, но это менее удобно. Добавлю, что из where не видно значений из раздела «let».

Далее, отмечу, что конструкция «if» в хаскеле является выражением. Конструкции «for» в самом языке нету, она есть в отдельном модуле и является обычной функцией. Равно как и «while» и подобные.

В свете вышесказанного продолжим рассмотрение компилятора бинарных файлов.

Нижеследующая функция переводит элемент AST (имеющий тип Op), в строковое представление на языке результата (на Хаскеле). Первым параметром идет строка, содержащая имя параметра с исходным состоянием (потому что мы будем генерировать операции чтения из него), в формуле (1) это будет «x». На самом деле я мог захардкодить это имя, потому что оно встречается всего один раз.

ast2haskell :: String -> Op -> String<br>
ast2haskell x op = s op where <br>
s (Const d) = show d  -- константа показывается как есть.<br>
s (ReadExp r1) = "m"++(show r1)++" "++x<br>-- generate read access to memory<br>
s (ReadVarExp r1) = "t"++(show r1)<br>                         -- to temporary variable <br>
s (ReadPortExp r1) ="i"++(show r1)<br>                        --  to input port <br>
s (SqrtExp op') = "(sqrt "++s op'++")"<br>
s (AddExp op1 op2) = "("++s op1++"+"++s op2++")"<br>
s (SubExp op1 op2) = "("++s op1++"-"++s op2++")"<br>
s (MulExp op1 op2) = "("++s op1++"*"++s op2++")"<br>
s (DivExp op1 (Const x)) = "("++s op1++"/"++(show x)++")"<br>
s (DivExp op1 op2) = "(if "++s op2++" /= 0 then "++s op1++"/"++s op2++" else 0)"<br>
s (IfExp cond opc op1 op2) = "(if "++s opc++show cond++" then "++s op1++" else "++s op2++")"

Что мы здесь имеем? Знакомую нам конструкцию fun param = expr where ...., но только сразу идет вызов одной из локальных функций. Почему? Сейчас разберемся. Сначала только обратим внимание, что функция «s» (от «string») имеет несколько определений, по одному определению для каждого конструктора типа Op. В результате, понятное дело, вызовется только одна функция, и сразу же конкретный объект типа Op разобьется на свои компоненты, которым дадутся имена:

s :: Op -> String<br>
s (AddExp op1 op2) = "("++s op1++"+"++s op2++")"

Это реализация функции s для конструктора типа Op по имени AddExp, который имеет два параметра: две ветки AST, которые складываются. А сама функция s имеет один аргумент, поэтому там стоят скобки вокруг AddExp. Результатом работы этой функции будет строка, склеенная из кусочков (операция ++ соединяет два списка; строки тоже являются списками). Тут по бокам приклеиваются скобки, а между ними строковые представления обеих веток, между которыми вклеивается плюс. Строковое представление каждой ветки, стало быть, вычисляется рекурсивно, это обычная практика в таких задачах. И, наконец, функция show переводит число в строку, а также она используется для CmdOp (условие сравнения с нулем), который тоже относится к классу Show (описано выше).

Обратим внимание на следующее определение:

s (DivExp op1 (Const x)) = "("++s op1++"/"++(show x)++")"<br>
s (DivExp op1 op2) = "(if "++s op2++" /= 0 then "++s op1++"/"++s op2++" else 0)"

Оно замечательно тем, что обе функции работают над данными DivExp, но для выбора первой необходимо чтобы делителем в этом узле была константа! Для этого случая сгенерируется особенный, более простой код, потому что здесь не нужно делать проверку на 0.

Из этого следует, что определение того, какая функция вызывается, не идет по «типу конструктора», а происходит гораздо гибче: входное значение по очереди пытается «пролезть» в каждую реализацию функции с требуемым именем, и вызывается та функция, в которую оно пролезет. В указанном случае в первую функцию не пролезет DivExp, у которого второй параметр инициализирован чем-либо, отличным от Const. Это называется Pattern Matching (не путать с оным для строк).

Теперь о том, для чего вообще была сделана функция «s». Исключительно для удобства. Сравниваем 2 куска, с ней:

ast2haskell x op = s op where <br>
s (SubExp op1 op2) = "("++s op1++"-"++s op2++")"<br>
s (MulExp op1 op2) = "("++s op1++"*"++s op2++")"

и без нее:

ast2haskell x (SubExp op1 op2) = "("++ast2haskell x op1++"-"++ast2haskell x op2++")"
ast2haskell x (MulExp op1 op2) = "("++ast2haskell x op1++"*"++ast2haskell x op2++")"

Вывод: код с функцией «s» короче, и не нужно постоянно таскать этот «x», передавая его дальше.

Рассмотрим теперь новую тему — о том, как производится декодирование опкода в операцию, которая у нас представляется типом Op. Каждая операция изначально лежит по какому-то адресу в бинарном файле. Для большинства операций этот же адрес является адресом назначения для результата работы операции (результат сложения и прочих операций — всё кладется в «память» по этому адресу, для каждой операции своему). Именно поэтому мы передаем в функцию пару «опкод, его адрес», а на выходе имеем уже инициализированную операцию, в которой в дополнение к адресу назначения инициализированы дополнительные аргументы, для каждой операции свои.

В спецификации опкодов они декодируются каскадно, то есть если старшая часть опкода равна нулю, то смотрится следующий кусок, иначе это готовый опкод Старшая часть — четыре старших бита, то есть 4 бита вверх, начиная с 28-го бита (28, 29, 30, 31).

Для выкусывания битов из Word32 нами здесь определена функция (.%.), которая может использоваться как операция (инфиксная, то есть стоять между двумя операндами, как + или *). Синтаксис хаскеля позволяет определить функцию с именем из всяких символов, например "++++" Определяется это так:

(++++) a b = sqrt(a*a + b*b)

или иначе:

a ++++ b = sqrt(a*a + b*b)

а используется так:

let q = 3 ++++ 4<br>
let p = (++++) 3 4

Таким образом, получается очень удобно. Также, можно любую из «обычных» функций двух аргументов сделать инфиксной, см пример ниже с 'shiftL' (сдвиг влево). Для этих целей имя функции берется в обратные кавычки и ставится между операндами. Для инфиксных операторов действуют всякие приоритеты, но это не наша тема сейчас, а сама функция (.%.) будет определена ниже.

disasm :: (Word32, Int) -> Op<br>
disasm (opcode, addr) = disasm1 (opcode .%. (28, 4))  -- декодируется первый "каскад"<br>                                         -- заданный четырьмя старшими битами<br>
   where<br>
       r1 = recast $ opcode .%. (14,14)  -- а это выкусываем из опкода сразу<br>
       r2 = recast $ opcode .%. (O,14)  nbsp; -- два аргумента<br>
       r1' =    -- а это для красоты для второго каскада<br>
       disasm1 i = [disasm2 $ opcode .%. (24,4) , Add addr r1 r2,Sub addr r1 r2,Mul addr r1 r2, Div addr r1 r2,Output r1 r2,Phi addr r1 r2] !! recast i


Что происходит в disasm1? Снова определение списка (квадратные скобки) с выбором по индексу (операция "!!"). Функция recast описана ниже, она преобразует знаковые в беззнаковые, оттого, что мы связались с Word32, а не только с Int — а Хаскель не особо любит их мешать, это не C. Ну, а что же в рассматриваемом списке? В нулевом индексе нас посылают задекодировать второй каскад (код операции закодирован 4 битами начиная с 24 бита вверх). Дальше идут операции сложить, вычесть, и далее по спецификации. Операция Phi будет отдельно рассмотрена дальше.

disasm2 i = [Noop addr, Cmpz (decodeImm (opcode .%. (21,3))) r1',<br>
Sqrt addr r1',Copy addr r1',Input addr r1'] !! recast i<br>

Второй каскад, он же завершающий, состоит из того же мяса. В спецификации r1 для этих операций лежит в том же месте, что r2 для первого каскада, оттого там синоним r1', для красоты. Также идет выборка из списка по индексу. В первом (начиная с нуля) лежит сложное выражение — конструктор Cmpz, для которого аргумент вычисляется специальным декодированием из куска опкода (тип сравнения с нулем):

decodeImm i = [Ltz,Lez,Eqz,Gez,Gtz] !! recast i -- а могли бы написать ту же функцию и через enum (благо он определен для этого типа).

А вот и сами операции выкусывания битов — прямая трансляция из C.

        mask x n = x .&. ((1 `shiftL` n) - 1)  -- маскирование = отрезание n младших битов из x<br>
        (.%.) w32 (start,len) = (w32 `shiftR` start) `mask` len  -- сдвиг, затем маскирование<br>

А эта функция (recast) преобразует из signed в unsigned и наоборот, в зависимости от контекста. Она не очень эффективна, зато работает нормально в нашей задаче. Здесь типы явно не указаны, указан лишь их класс (Integral). Здесь хаскель замечательно подставит в каждом случае нужные типы (Int или Word32) и для каждого из них есть операции fromInteger/toInteger. Заметим, что типы выведутся в процессе компиляции, а не в runtime (это я на всякий случай напоминаю).

recast :: (Integral a, Integral b) => a -> b<br>
recast x = (fromInteger . toInteger) x  -- то же, что "fromInteger (toInteger x)", только заумнее

а еще можно написать так:

recast x = fromInteger $ toInteger x -- это совсем на заумно, а придумано специально<br>
   -- для тех, кто не любит скобки: выражение справа от<br>
   -- знака $ скармливается целиком как последний<br>
   --  аргумент (или как единственный) функции слева.<br>

а еще можно написать так:

recast = fromInteger . toInteger   -- совсем заумно, зато жуть как коротко.
  -- Ну, а затем проходит время, и такие конструкции
  -- читаются на ура


Конец 1 части (ограничение по размеру), вторая часть последует.