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

Начало здесь.

Теперь разбираемся как мы будем декодировать весь файл, а не только одну инструкцию.

readMyFile = withBinaryFile "bin4.obf" ReadMode $ \h -> do<br>
        len <- hFileSize h<br>
        buf <- mallocBytes $ fromInteger len<br>
        hGetBuf h buf $ fromInteger len<br>
        return (len, buf)<br>


Это императивный кусок, потому что с файлами так в основном и работают. withBinaryFile открывает файл, выполняет указанную ей «пользовательскую» функцию, передав ей handle, и закрывает файл, и возвращает то, что вернула ей пользовательская функция. Вот, после знака $ мы описали «пользовательскую» функцию с одним параметром h (от handle). Эта функция получает размер файла, аллоцирует буфер, читает в буфер и возвращает сам буфер и его длину (в байтах). Заметим, что «пользовательская функция» здесь не имеет имени и начинается так:



\h -> function_body -- это такой синтаксис безымянных функций с одним параметром

Далее функция получения инструкции и слова данных из буфера. Сюда передается текущий указатель на буфер (уже сдвинутый на нужное число байтов), и передается индекс инструкции. Из спецификации помним про четный-нечетный индекс, и что опкод и слово данных лежат то так то эдак. То есть инструкция начинается то с нулевого байта, то с восьмого, а слово данных (плавающее), соответственно, то с четвертого, то с нулевого.

instruction :: Ptr a -> Int -> IO (Word32,Double)<br>
instruction ptr i = do<br>
        let (iaddr,daddr) = if i `mod` 2 /= O then (O,4) else (8,O)  -- смещения instruction/data<br>
        instr <- peek (plusPtr ptr iaddr) :: IO Word32  -- выборка инструкции<br>
        dta <- peek (plusPtr ptr daddr) :: IO Double                  -- выборка данных<br>
        return (instr, dta)<br>


Заметим, что операция «неравно» звучит по-математически: "/=".
Теперь пройдемся «циклом» по всему буферу, и вернем список пар (инструкция, данное):

ast = mapM (\i -> instruction (plusPtr buf $ i*12) i) [O..nframes-1]<br>


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

let q = map (\h -> h * 2) [1,2,3,4,5]

вернет [2,4,6,8,10], это классический пример. А у нас в рассматриваемой задаче на входе индексы (от нуля до конца), а на выходе список результатов вызова функции «instruction» с каждым индексом. Это иногда сложно понять сразу, но уже пора — python и ruby движутся в этом направлении, а с ними еще когорта языков (из тех, которые еще не там, понятное дело).

ast = mapM (\i -> instruction (plusPtr buf $ i*12) i) [O..nframes-1]<br>

Возвращаясь к нашей mapM, в переданной ей функции стоит вызов instruction, которому по-очереди скармливается 0, 1, итд, как второй аргумент, а как первый — передается буфер со смещениями по 12 байт дальше и дальше на каждую итерацию (1 опкод + 1 слово данных = 12 байт). plusPtr формирует новый указатель, отстоящий от указанного на указанное число байт.

Вот и весь цикл. В результате имеем список из «плоских» опкодов (плоских, потому что переведены один к одному по спецификации):

[(Add 0 77 66, 0.0), (Sub 1 0 102, 0.0), ...]

Что означает: сложить ячейки 77 и 66, результат поместить в 0. Затем вычесть содержимое ячейки 102 из содержимого ячейки 0, результат поместить в 1… итд. Таков наш код. А вот данные: в нулевой ячейке 0.0, в первой 0.0, итд…

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

Почему медленно? Потому что будет присутствовать операция записи в память некоторых результатов, которые используются только 1 раз, и которые, по правде, лучше хранить где-то в регистрах или даже на стеке (этими деталями займется компилятор C/Haskell/Java или чего угодно, во что мы представим наш AST, а «чем угодно» у нас нынче служит хаскель). И если мы нагенерим запись в поле структуры по каждому чиху, то никакой компилятор нам регистров оттуда не наизобретает, а только одни записи в память.

Поэтому мы разберем, на какие же категории делятся наши ячейки «памяти».

1) константы: только чтение, никогда запись
2) реальная память: чтение раньше записи, запись позже чтения
3) временные переменные: запись, затем несколько чтений
4) одноразовые переменные: запись, затем одно чтение. Пойдут в выражения со скобками.

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

Описываем поведение каждой инструкции — что она читает (потребляет).

consumesData (Add _ r1 r2) = [r1,r2]<br>
consumesData (Sub _ r1 r2) = [r1,r2]<br>
consumesData (Mul _ r1 r2) = [r1,r2]<br>
consumesData (Div _ r1 r2) = [r1,r2]<br>
consumesData (Output r1 r2) = [r2]<br>
consumesData (If _ condr1 _ r1 r2) = [condr1,r1,r2]<br>
consumesData (Sqrt _ r2) = [r2]<br>
consumesData (Copy _ r2) = [r2]<br>
consumesData _ = []<br>


Подчеркивание в последнем случае означает «все остальные», а в первых случаях оно означает, что нам не интересно, что там в этом месте конструктора за аргумент. Как видно, здесь снова используется pattern matching.

Аналогично описываем поведение каждой операции касаемо того, что она пишет (производит):

producesData (Add addr _ _) = [addr]<br>
producesData (Sub addr _ _) = [addr]<br>
producesData (Mul addr _ _) = [addr]<br>
producesData (Div addr _ _ )= [addr]<br>
producesData (If _ _ addr _ _) = [addr]<br>
producesData (Input addr _) = [addr]<br>
producesData (Copy addr _) = [addr]<br>
producesData (Sqrt addr _ )= [addr]<br>
producesData _ = []<br>


Описываем, что каждая инструкция делает по отношению к портам — какие порты она читает.

readsPort (Input _ port) = [port]<br>
readsPort _ = []<br>


И запись — какие порты она пишет:

writesPort (Output r1 _) = [r1]<br>
writesPort _ = []<br>


Далее, для более короткой записи (причуда автора)

cmap = concatMap<br>


Что делает concatMap? Она делает то же что и map, только еще после этого делает concat. Concat «склеивает список на один уровень». Маленький пример:

concat ["hello","africa"] = "helloafrica"<br>
concat [[1,2,3,4],[5,6,7,8]] = [1,2,3,4,5,6,7,8]<br>
concat [[]] = []<br>
<br>
map (\i -> [1..i]) [1..5] = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]<br>
concatMap (\i -> [1..i]) [1..5] = [1,1,2,1,2,3,1,2,3,4,1,2,3,4,5]<br>


Теперь самый страшный и большой кусок:

produceCode ast dta =<br>
let <br>
   inports = cmap readsPort ast  :: [Int]<br>
   outports = cmap writesPort ast :: [Int]<br>


применить readsPort/writesPort к каждому опкоду, и сложить (concat) все списки в один список. Таким образом, мы получили списки входных и выходных портов вообще.

   -- consumes,produces,outputs to port [(memory/port ref,op address)] lookup tables<br>
   consumes = cmap (\(d,a)-> consumesData d `zip` [a,a..] ) (ast `zip` [O..]) :: [(Int,Int)]<br>
   produces = cmap (\(d,a)-> producesData d `zip` [a,a..] ) (ast `zip` [O..])<br>
   outputsPort  = cmap (\(d,a)-> writesPort d `zip` [a,a..] ) (ast `zip` [O..])<br>


здесь мы построили несколько lookup tables (справочников?), к которым можно задавать следующие вопросы:

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

В хаскеле примитивный справочник (lookup table) — это список пар (ключ, значение). У нас вот есть функции, которые ищут все значения по данному ключу и возвращают список. Вот они:

   -- op address that reads/writes given mem/port<br>
   reads m = map snd $ filter ((m==).fst) consumes :: [Int]<br>
   writes m = map snd $ filter ((m==).fst) (produces) :: [Int]<br>
   outputs m = map snd $ filter ((m==).fst) outputsPort :: [Int]<br>


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

     reads m = map snd $ filter ((m==).fst) consumes^M<br>


означает буквально: взять вторые элементы, отфильтровав сначала всех у кого первый элемент равен указанному m из справочника consumes (вычислен раньше). Как это работает?

функция filter на вход берет «пользовательскую функцию» ((m==).fst) и список. Пользовательской функции скармливается на вход каждый элемент из списка, и она возвращает True или False. Из этого списка, в зависимости от результата, в результирующий список попадают или не попадают элементы. Остается меньший список, стало быть. Этот список является вторым аргументом функции map (как было рассказано раньше про оператор '$'). Дальше map применяет функцию snd к каждому элементу списка и формирует список результатов.

Нерассмотренными осталось несколько вещей. Функции snd/fst возвращают второй или первый элемент пары соответственно, то есть они занимаются декомпозицией пары, а если говорить простым языком, выкусывают второй или первый элемент:

fst (1,2) = 1
snd (1,2) = 2
fst ("Hello", 2+2) = "Hello"
snd ("Hello", 2+2) = 4

И теперь один из интересных моментов в хаскеле — композиция функций. Рассмотрим примерчик:

f x = sin (cos (sqrt (x))), его можно записать по-хаскельски короче:
f x = sin $ cos $ sqrt x

Теперь пошевелить мозгом и увидеть, что «x» всегда проходит через мясорубку функций: сначала sqrt, потом cos, потом через sin. Наверняка можно бы было построить график функции f x, а раз можно построить график, то наверняка последовательности применений этих трех функций соответствует какая-то одна единственная функция, которая дает тот же результат, только математики не дали ей еще названия!!! Да простят меня люди с формальным мышлением.

Теперь, предположим, у нас есть функция на хаскеле, которая строит график любой переданной функции, например

plot :: (Double -> Double) -> Double -> Double -> IO() (читаем IO () как void, а всё определение типа звучит как: функция plot берет на вход функцию от Double возвращающую Double, а также еще берет два аргумента Double (интервал на котором строить), и возвращает void)
plot sin 0 6.28 -- построить график функции sin на интервали от 0 до 6.28
plot cos 0 3.14 -- то же, на другом интервале, другой функцией.

Тут мы видим, что функцию sin или cos мы передаем как таковую, аргумент в нее передавать будут в процессе постройки графика, те кто его строят. Как же нам передать целую мясорубку функций, которой не придумали имя, но мы знаем как оно складывается?

Возникает насущная необходимость описать такую мясорубку. Следовательно:

fun1 = sin -- это мясорубка из 1 функции
fun2 = sin . cos . sqrt -- это мясорубка из трех функций, а точка - это операция композиции функций

Теперь про неполное применение. Вот у нас есть функция, которая берет два аргумента, например возведение в степень:
pow 2 3 = 8 -- два в третьей степени
теперь опишем функцию pow2:
pow2 = pow 2

Оказывается, мы передали всего один аргумент из двух требуемых, но нас никто не остановил и не поругал! Какой же тип у функции pow2? Очень просто, она хочет еще один аргумент Double, и добавит его, и вызовет функцию pow с этим аргументом, а двойка там уже стоит!

pow2 4 = 16
Оказывается, нотация для описания хаскельских типов тоже не с потолка взята: следите за руками:

pow :: Double -> Double -> Double -- берет double, и еще double, возвращает double
pow2 :: Double -> Double -- берет один double, возвращает double

а так как pow2 получилось указанием одного аргумента к функции pow, то мы можем заключить, что добавление одного аргумента к pow порождает новую функцию!

pow :: Double -> (Double -> Double) -- вот я тут добавил скобок.

Стало быть, можно как угодно справа добавлять скобок, а смысл будет тот же. Из этого также следует, что:

pow 2 3 = (pow 2) 3, то есть вначале сгенерим функцию, а потом добавим в нее недостающий аргумент (применим функцию к тройке).

Вернемся к нашим баранам.

     reads m = map snd $ filter ((m==).fst) consumes<br>


в filter стоит функция: (m==). fst. Здесь мы наблюдаем точку (композиция) и частичное применение: m==. Вот это вот m== — это функция, которая получает на вход 1 аргумент, подставляет его справа от знака равно, и вуаля! Функция m== возвращает результат сравнения своего аргумента с m. Если m равно 5, то ((m==) 5) вернет True.

Теперь читаем всё справа налево: у нас есть мясорубка, то что в нее входит, сначала скармливается функции fst (которая, как известно, из пары извлекает первый элемент), потом это значение скармливается m==, которая берет число, сравнивает его с m и возвращает Boolean. Таким образом, в мясорубку входит пара (a,b), а выходит Boolean, равно ли а вот этому m.

Теперь нам надлежит выбрать все упоминания ячеек, которые пишутся или читаются, для того чтобы было от чего отталкиваться:

   -- all memory references (including temporaries etc - from plain program)<br>
   alldata =  nub $ sort $ cmap consumesData ast ++ (map recast $ cmap producesData ast) :: [Int]<br>


Здесь (читаем справа налево) «cmap producesDataAst ast» возвращает список всех записываемых ячеек в виде плоского списка их адресов, аналогично происходит с consumesData, потом оба списка просто склеиваются (++), потом сортируются, и потом из них удаляются дупликаты (nub). В принципе, nub не требуется отсортированный список, но я этого раньше не знал:

nub [1,2,1] = [1,2]
nub [2,1,2] = [2,1]


   -- constants<br>
            constants = filter (\m -> O == (length $ writes m))  alldata :: [Int]<br>


A тут произошло следующее: мы выбрали из alldata все адреса, в которые никто никогда не пишет. А раз из них только читают, то это наверняка константы. Вот мы списочек и составили.

   -- all persistent (optimized memory)<br>
            persistents = filter (\m -> (head $ reads m) <= (head $ writes m)) (alldata \\ constants) :: [Int]<br>


А тут мы выбрали все переменные, которые должны сохраняться от раза к разу между итерациями. Для этого мы взяли alldata, вычли из него константы (операция \\ — разность списков), и нашли кто первый читает и кто первый пишет. Если читают раньше того места где пишут, значит полагают, что там что-то есть! Осталось с прошлого раза! Вот, таким образом и составили список тех мест, которые реально являются памятью нашего черного ящика, доступной для чтения-записи.

   -- temporaries which are reused parts of expressions<br>
            lets = filter (\m -> 1 < (length $ reads m))  (alldata \\ constants) \\ persistents :: [Int]<br>


Теперь мы из оставшихся (потому что вычли из alldata всё, что знаем до сих пор), нашли те ячейки, которые читаются больше одного раза. Так как это не перманентные данные (мы их исключили), то это наверняка временные переменные, которые сначала вычисляются, а потом несколько раз пользуются. Временные переменные используются в пределах одной итерации, а вне нее они не нужны.

   -- expressions to inline (variables that are used 1 time)<br>
            onerefs = filter (\m -> (length $ reads m) ==1 && (length $ writes m) == 1) <br>
((alldata \\ constants) \\ persistents) :: [Int]<br>


А тут мы вычислили переменные, которые один раз пишутся и потом 1 раз читаются. Для них мы не будем вообще ничего заводить, и из них сформируются выражения со скобками. Этот класс переменных понадобился авторам черного ящика, потому что у них такой низкоуровневый язык, а в нашем высокоуровневом результате они будут жить в регистрах процессора, но об этом позаботится компилятор без нашего ведома.

Сейчас мы должны будем из плоских операций (в которых упоминаются только адреса которые читаются пишутся в процессе работы операции), перейти к древовидным опкодам, то есть к тем, которые у нас с суффиксом Exp — они содержат в себе ссылки на себе подобных, образуя дерево. Для этого мы опишем функцию, которая нам будет генерировать по адресу целый древовидный Op. Она будет рекурсивной. Потому что если мы даем ей адрес, по которому лежит константа, то делать особо много не надо. А если мы даем ей адрес, в который записывается результат сложений двух каких-то других ячеек, то нужно сгенерировать Op, который складывает два других Op-а, а уж они там могут быть константами, или вдруг там результатами умножений…

   -- geherates reference to the expression identified by given address,<br>
   -- this excludes address where to store it, only value is obtained<br>
   ref :: DestAddr -> Op<br>
   ref a <br>
        | elem a constants = Const (dta!!a)<br>
        | elem a onerefs = geneval a<br>
        | elem a lets = ReadVarExp a<br>
        | elem a persistents = ReadExp a<br>
        | otherwise = trace "oops1" $ undefined<br>


Тут мы имеем функцию ref, в которой есть некоторые пред-условия, накладывающиеся на входной параметр, синтаксис таких условий — это вертикальная черта, потом условие, а потом знак равенства, а за ним — тело функции, выполяющееся в случае истинности условия. Это как бы большой if… elseif… elseif… else… endif. Последний else у нас описан через trace «oops» $ undefined — выведет ошибку (trace) и остановит программу (undefined).

Смотрим, если входной адрес принадлежит к константам, то генерируем доступ к константе (просто Op, обозначающий константу). Какую именно константу — определяет параметр конструктора Const — это просто значение памяти по указанному адресу. dta — это список, содержащий все ячейки памяти последовательно, а dfa!!a — это доступ к a-тому элементу списка.

Если входной адрес принадлежит к onerefs (память 1 раз пишется, затем 1 раз читается), то нужно образовать просто узел дерева с двумя другими опами (операция со скобками). Вызывается geneval (описан ниже), который сгенерирует из простого Op-а (сложение двух ячеек памяти и помещение результата в третью) сложный (сложить два других Op-а, вернуть результат _вообще_)

Аналогично для чтения временных переменных (которые один раз пишутся, много читаются), и для чтения входных портов.

Сама функция geneval описана далее, в ней используется pattern matching. Из полученного адреса мы выбираем плоский Op (из списка ast), и преобразуем его в древовидный. Любопытно, что эта функция вызывает ref, описанную выше, таким образом функции взаимно-рекурсивны.

   -- turns plain code in tree code, converting memory refs to ops via "ref"<br>
            geneval a = e $ ast !! a<br>
   e (Add addr r1 r2) = AddExp (ref r1) (ref r2)<br>
   e (Sub addr r1 r2) = SubExp (ref r1) (ref r2)<br>
   e (Mul addr r1 r2) = MulExp (ref r1) (ref r2)<br>
   e (Div addr r1 r2) = DivExp (ref r1) (ref r2)<br>
   e (If cmdop cmdr addr r1 r2) = IfExp cmdop (ref cmdr) (ref r1) (ref r2)<br>
   e (Input addr r1) = ReadPortExp r1<br>
   e (Sqrt addr r1) = SqrtExp (ref r1)<br>
   e (Copy addr r1) = ref r1<br>
   e x = trace (show x) $ undefined<br>


Op копирования (Copy) просто означает взять результат по оригинальному адресу. Команды Add/Sub/Mul/Div — дословные преобразования из плоских в древовидные. Input преобразовывается в чтение из порта. Чтение из временных переменных или из постоянных переменных конвертируется выше, в ref.

Следом пишем генерацию

   retval = "module Vm where\ndata VMState = VMState { " ++<br>
(intercalate "," $ <br>
map (("m"++).show) persistents ++<br>
map (("o"++).show) outports<br>
    ) ++ "::Double } \n"++<br>


Это сгенерировалась часть с описанием самой структуры. Тут, очевидно, (++) — оператор склеивания списков (строк), intercalate — это склеивание нескольких списков, перемежая их указанным (читаем: вставляем разделяющую запятую), а в структуру мы включим все персистентные поля с префиксом m (memory) и все выходные порты с префиксом o — output ports. В конце дадим им тип Double и перевод строки не забудем.

Можно дать им не тип Double, а тип !Double, тогда это будет структура не с ленивыми полями, а с неленивыми. Исследование показывает (см предыдущий пост), что при вычислении всех выходных портов разница по скорости составляет больше 20 раз, с ленивыми, понятно, медленнее. Ну, дело читателя подставить или не подставить strictness annotation (воскл знак). Почему я сказал «всех выходных портов»? Потому что с ленивыми вычислениями можно получить значение этой структуры после N-й итерации, и спросить только один требуемый порт, например. Начнет разворачиваться большой фронт работ, и после некоторой паузы придет вычисленное значение (например, когда мы напишем

putStrLn $ "o10=" ++ (show $ o10 vmlast)


то произойдет следующее: на консоли напишется «o10=», а потом будет пауза, а потом выведется значение. Если следом написать снова тот же putStrLn, то задержки уже не будет, т.к. значение вычислено. Если спросить потом написать o11, то задержка будет снова, но, вероятно, не такая большая, так как скорее всего o10 и o11 имеют какую-то общую часть вычислений, которая целиком уже посчиталась для o10, и для o11 считаться уже не будет.

       "initState = VMState {"++<br>
(intercalate "," $ <br>
map (\a -> "m"++(show a) ++"="++(show $ dta !! (recast a))) persistents ++<br>
map ((++"=O").("o"++).show) outports<br>
    )  ++"} \n"++<br>


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

"nextState x ("++(intercalate "," $ map (("i"++).show) inports)++")=\n let\n"++<br>
cmap (\a->"    t"++show a++"=("++(ast2haskell "x" $ geneval a)++") :: Double\n") lets  ++<br>
" in x {\n"++ <br>
  intercalate ",\n" (<br>
map (\a->"    m"++show a++"="++(ast2haskell "x" $ geneval a)) persistents ++<br>
map (\a->"    o"++show a++"="++(ast2haskell "x" $ geneval $ head $ outputs a)) outports )<br>
++"}\n";<br>


Тут генерируется самая объемная часть. Для начала, формируется кортеж входных параметров в виде, подобном этому: (i10,i11,i60000), затем идет «let», в которую вписываются все временные (неперманентные) переменные, с префиксом «t». Затем идет формирование новой структуры, в которой прописываются выражения для каждого ее члена: x {m20=expr1,m25=expr2...,o10=exprN}. Выражения в инциализациях t и m ссылаются на «tNN», «iNN» и «mNN x» — последнее означает значение памяти из предыдущей итерации.

in retval -- вернули строку с целой хаскельской программой.


Окончание следует