Tuesday, August 2, 2011

3. О том, как на Хаскеле компилировать Паскаль в.

На Хаскеле писать компиляторы и трансляторы - милое дело, потому что один из самых больших проектов на Хаскеле - это компилятор Хаскеля (ghc).

Сначала надо написать парсер языка. Паскаль - язык старый и могучий, поэтому там всё в жестких рамках. Если написано "Uses", то наверное потом идет список юнитов. Если написано "procedure" - то потом наверняка есть скобка и список параметров, а если параметров нету, то точка с запятой, и наверное еще модификаторы. Вот вспоминаем паскаль (замечаем раздел "interface", "implementation"):

unit unit1;

interface

type s0 = record
a : Integer;
b : Integer;
end;

procedure doit;

implementation

var v2: q;

procedure doit;
begin
writeln('doit ok!');
end;

begin
v2.m := 5;
v2.l := v2.m * 2;
writeln('Zorroz ftw!',v2.l);
end.

Это всё засовывается в типы данных (описание юнита / модуля), описанных следующим образом:

data Unit = Unit {
unitName :: String
,unitInterfaceDecls :: [Declaration]
,unitImplDecls :: [Declaration]
,unitInitCode :: CodeBlock
} deriving (Show,Read,Eq)

На хаскеле есть (кроме всего прочего) parsec, который, хоть на него и жалуются что он медленный, для наших задач самое то. Парсер на нем выглядит так:

unit = do
simple_string "UNIT" "UNIT keyword"
iden <- identif
ws -- whitespace
char ';'
ws
simple_string "INTERFACE" "interface keyword"
ws
decls <- many $ try declaration
ws
simple_string "IMPLEMENTATION" "implementation keyword"
ws
unitBody <- many $ try declarationBody
emptyDecl <- optionMaybe ( try $ do ws; simple_string "END" "END(of unit)"; ws; char '.'; ws; eof )
initCode <- case emptyDecl of
Just _ -> return $ CodeBlock []
Nothing -> do
cb <- codeblock;
ws; char '.'; ws; eof
return cb
return $ CompiledUnit $ Unit iden decls unitBody initCode

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

Я на парсеке, как уже и сказал, не специалист, наверное можно и еще красивее, но по-моему и так тоже ничего. Надо как-то еще шаманить, чтобы оно правильно ошибки сообщало, а то у меня ругается не там где ошибка, но это я к гуру пойду, там меня научат.

Вот, и в конце-концов, оно у нас докомпилирует кучу Declaration, включая объявления (FunHeadDecl) и описания (FunDecl) процедур:

data Declaration =
UsesDecl [String] |
FunHeadDecl FunctionHeadDecl |
FunDecl FunctionHeadDecl (Maybe ScopeBlock) |
LabelDecl [String] |
VarDecl [(String,(Maybe TypeRef),(Maybe Expr))] | -- constants here as well
TypeDecl [(String, TypeRef)]
deriving (Show,Read,Eq)

После этого у меня есть куча файлов и на каждый файл вот такая куча деклараций. Мне нужно пройтись по типам и составить в голове что за типы в программе. Типы мы описываем таким образом:

data TypeRef = TypeRefByName String |
TypeRefUnitScope | -- Graph.PutPixel (type of Graph)
TypeRefVoid | -- procedure return
TypeRefNative String | -- tree transformation
TypeRefFixedString Expr | -- fixed string size
TypeRefPointer TypeRef |
TypeRefAnyPointer |
TypeRefNameValue String TypeRef | -- in record assignment
TypeRefSoftPointer String | -- pointers which are forward references
TypeRefRecord [(String,TypeRef)] |
-- TypeRefUnion [(Expr, [(String,TypeRef)])] | -- case record of
TypeRefArray Expr TypeRef | -- expr = range expr
TypeRefSet (Either Expr TypeRef) |
TypeRefProcedure [Argument] (Maybe TypeRef) Bool

Тут вот всякие типы, включая даже такие странные как TypeRefUnitScope,потому что в процессе вычисления типа выражений таких как "System.ExitProc", символ System - это название модуля, и тип этого символа - натурально, TypeRefUnitScope. Другие типы понятны сами по себе. Нужно заметить, что Expr - это любое выражение, включая диапазон в определении массива (1..10), или определение инициализации для записи: (Name: 'Vasya', Age: 35). Сам Expr там тоже имеет свое описание, не будем о нем.

Как мы все эти типы проходим? Очень просто - у нас есть Scope, и мы можем пройтись по декларациям и типы-то добавить! Сверху вниз, с нюансами: какие типы у нас приватные, а какие в интерфейсе описаны, и сохраняя юнит, в котором они были описаны.

Вот, а потом так же проходим переменные, и даже инициализированные переменные, и смотрим чтобы их значения были совместимыми с их типом.

А потом идем по процедурам....

Чтобы в обход дерева не передавать "обработчик для произвольного генератора языка", я просто возвращаю ленивый список событий: начало модуля, начало процедуры... и в каждом событии уже правильно насетапленный scope со всеми доступными символами. Я подсмотрел это в одной из реализаций SAX Parser. Обычный SAX Parser требует обработчик событий - что в Java, что в C#, и наверное везде. Кроме Хаскеля, тут автор рассудил здраво и просто вернул список событий (ленивый список, то есть, когда он его вернул, он еще ничего не отпарсил, верно?).

Вот, JS генератор получает этот список событий, и начинает генерировать JS код. Для этого была использована либа HJavaScript для построения AST (abstract syntax tree) жабоскриптовой программы, но она оказалась неподходящей, вследствие 1) чересчурной затипизированности, т.к. она предполагала что будет писаться статический код руками 2) неполноты: в ней не было многих конструкций, наверное автор был такой же раздолбай.. Поэтому из нее используется в основном конструкция "сгенерить кусок программы в виде произвольной строки". Бессмысленно и беспощадно. И это плохо, потому что я не могу использовать сгенерированный текст JS программы и свободно его модифицировать (преобразовывать AST), что потребовалось в дальнейшем.

Во время обработки указанных событий (начало функции), на JS генерится заголовок функции, а потом идут один за одним операторы паскаля, которые конвертятся в соответствующие джавоскриптовые. Они содержат выражения, которые тоже проверяются по типам (правая часть присвоения сводится ли к левой части в смысле типа?). В программе проверяется почти всё, кроме L-values (то есть того, что в указанное выражение, например, имя переменной, можно что-то записать, а в константу нельзя), т.к. это уже занадто, потому что транслироваться будет по-любому работающая программа.

Вот это и происходило на Хакатоне, и транслятор паскаля транслировал до того, что результирующий JS код стал успешно проверяться такими зверями как google-traceur, и грузиться в бровзеры.

Отдельная задача - сделать реализацию ключевого слова VAR в списке параметров, что означает "in/out variable", например:

function P1(var i: Integer): real; begin i := 5; p1 := 3.1415; end;
procedure P2(var r: SomeRecord); begin r.name := 'vasya'; end;

у нас это сделано следующим образом:

function P1(i) {
_rt_retval = 0.0;
i = 5;
_rt_retval = 3.1415;
return [_rt_retval, i]
}

let w = (_tmp = P1(v), (v = _tmp[1]), tmp[0])

то же и с p2.

Но это еще не конец! Конец наступает тогда, когда мы запустим Battle Tetris с его многозадачностью.

No comments:

Post a Comment