Haskellで50行以内のミニマルコンパイラ

こんなツイートが流れてきた：

A complete #compiler to x86 in one page for my lecture today. pic.twitter.com/PwFl4V5czy

— Joe Gibbs Politz (@joepolitz) 2018年4月11日

元となっているのは"An Incremental Approach to Compiler Construction"という論文とのこと。

面白そうだったので、許可をとってHaskellで再現してみた。(Thanks @joepolitz !)

Minimal Lisp Compiler inspired by Joe Gibbs Politz (@joepolitz) and http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf · GitHub

S式のパース

元のOCamlのコードでは文字列をS式にパースするライブラリを使っている。多分Haskellでも存在すると思うが、今回は簡単なパーサを自前で作る：

data Sexp = Atom String
          | List [Sexp]

parseSexp :: Parser Sexp
parseSexp = parseAtom <|> parseList

parseAtom :: Parser Sexp
parseAtom = ((many1 letter) <|> (many1 digit)) >>= return . Atom

parseList :: Parser Sexp
parseList = between (char '(') (char ')') $ sepBy parseSexp (many1 space) >>= return . List

stringToSexp :: String -> Sexp
stringToSexp s = case parse parseSexp "compiler" s of
  Left err   -> error $ "Parse failed at String->Sexp conversion: " ++ show err
  Right sexp -> sexp

今の所、アルファベット文字だけのAtomか数字だけのAtom、そしてそれらを()で囲ったListだけをパースする。

エラーハンドリングもめんどくさがってParsecがエラーを返してきたら直接errorを投げるようにしている。さらにこのエラーはどこでもキャッチされない。

言語仕様とS式からASTへ

今回コンパイルするソース言語は非常に簡単。

Expressionは整数か、一つのExpressionに対するIncかDecオペレータの適用、だけ。

以下の定義のとおり：

data Op = Inc
        | Dec

data Expr = ENum Integer
          | EOp Op Expr 

さきほど定義したパーサが返すS式をこのExpr型を使ったASTに変換する：

sexpToExpr :: Sexp -> Expr
sexpToExpr (Atom s)                 = ENum (read s :: Integer)
sexpToExpr (List [Atom "inc", arg]) = EOp Inc (sexpToExpr arg)
sexpToExpr (List [Atom "dec", arg]) = EOp Dec (sexpToExpr arg)
sexpToExpr _                        = error "Parse failed at Sexp->Expr conversion"

これも簡単。パターンマッチ便利。

ただ、今読み直してみると(inc a)とかだとreadがエラーを投げていて統一感がないな・・・

ASTからアセンブラ

Expr型のデータに表されるASTをアセンブラ命令の文字列に変換する。

使う命令が三つしかない上、そもそもASTが枝分かれとかしないのでものすごく簡単：

exprToInstrs :: Expr -> [String]
exprToInstrs  (ENum n)    = ["move eax, " ++ show n]
exprToInstrs  (EOp Inc e) = exprToInstrs e ++ ["add eax, 1"]
exprToInstrs  (EOp Dec e) = exprToInstrs e ++ ["sub eax, 1"]

組み合わせたらコンパイラ

あとは組み合わせて、すべてのプログラム共通のヘッダ部分・フッタ部分を付け加えるだけ：

compile :: String -> String
compile s = body `seq` header ++ body ++ footer
 where header = "section . text\nglobal our_code_starts_here\nour_code_starts_here:\n"
       body   = concat $ map (printf "  %s\n") $ exprToInstrs $ sexpToExpr $ stringToSexp s
       footer = "  ret\n"

面白いところがあるとすれば、パースエラーが起きた場合にはヘッダを出力したくないのでseqをつかってパース部分を先行評価している部分か。

あとはmain関数のIOモナド内で、ファイル名を受けとり、ファイルを読んでコンパイルし、標準出力に送る：

main :: IO ()
main = do args   <- getArgs
          source <- readFile $ head args
          putStrLn $ compile source

全部で50行以内。非常に簡単なソース言語とはいえ、おおまかな枠組みが「ひとめ」で展望できるような形で実装できたのは面白かった。

これからhttp://scheme2006.cs.uchicago.edu/11-ghuloum.pdfもちょこちょこ実装していきたい。