海野秀之（うんのひでゆき）の外部記憶
Twitter (twilog) / RSS / アンテナ / ぶくま
Haskell で、Haskell コンパイラを書いてみたいなぁと思うものの、手も足もでない日々、っていうか、 なんにもできてない日々続行中だったのですが、ふと、読みかけの本があったのを思い出した。 "Modern Compiler Implementation in ML" である。
もう、ML 覚える気まったくないんだけど、この本は好きなので、再挑戦しよう。 ただし、Haskell でかく。
たとえば、Program 1.5 Representation of straight-line programs は、ML ではこうなのだが、
type id = string
datatype binop = Plus | Minus | Times | Div
datatype stm = CompoundStm of stm * stm
| AssignStm of id * exp
| PrintStm of exp list
and exp = IdExp of Id
| NumExp of int
| OpExp of exp * binop * exp
| EseqExp of stm * exp
わりとあっさり Haskell でも書ける：
-- Tigerbook PROGRAM 1.5
-- Representation of straight-line programs.
type Id = String
data Binop = Plus | Minus | Times | Div
data Stm = CompoundStm Stm Stm
| AssignStm Id Exp
| PrintStm [Exp]
data Exp = IdExp Id
| NumExp Int
| OpExp Binop Exp Exp
| EseqExp Stm Exp
わーい。パターンマッチのない言語で書くのは苦しそうだけど、Haskell だったらよゆーだ。
maxargs も書いてみた：
-- maxargs
maxargs :: Stm -> Int
maxargs stm =
case stm of
CompoundStm stm1 stm2 -> max (maxargs stm1) (maxargs stm2)
AssignStm _ e -> maxargs_exp e
PrintStm es -> max (length es) (maxargs_es es)
where
maxargs_es :: [Exp] -> Int
maxargs_es [] = 0
maxargs_es (e:es) = max (maxargs_exp e) (maxargs_es es)
maxargs_exp :: Exp -> Int
maxargs_exp e =
case e of
EseqExp stm _ -> maxargs stm
_ -> 0
*Main> maxargs prog 2
ふむ。
よーし、この調子で Tigerbook も読めて、Haskell も書けるようになるんだ（ったらいいな）。
Modern Compiler Implementation in Haskell ということで。
https://github.com/unnohideyuki/Tiger-in-Haskell
２章の lexer は Alex で書いた。 前回のも含めて github に置いてみた。
つぎの parser は Happy だなという話なんですが、Monadic Parser とか説明をちらっと読んでもよくわかんなかったので、最初は単純に書こう。
３章は Parser だけ書いたら、次に進んで、４章以降は練習問題もやっていこうかな。
３章の課題である Tiger Language Parser を書いた： https://github.com/unnohideyuki/Tiger-in-Haskell/tree/master/chap3
ほとんど文法をそのまま Happy で書いただけなんだけど、shift/reduce conflict の解消については以下を参考にさせてもらった。 https://github.com/sunchao/tiger/blob/master/tiger.grm
Happy と Alex の連携については、これが、たぶん一番ナイーブな方法だと思う。
http://www.cs.princeton.edu/~appel/modern/testcases/ にあるものでは、test49.tig のみが Parse Error に：
$ ./parsetest < ../testcases/test49.tig parsetest: Parse Error at token nil at line 5, col 25
この間はじめた、Modern Compiler Implementation in Haskell という遊びは、 けっこう面白くて良いです。きちんと読みたかった Tiger Book も読めて、Haskell を書く量を確保する意味でもいい感じ。
いま、5 章の Type Checking のところをやっているんですが、 どうも再帰的な型定義のところがあやしい。
testcases にある test5.tig は以下のようなコードなのですが、
/* define valid recursive types */
let
/* define a list */
type intlist = {hd: int, tl: intlist}
/* define a tree */
type tree ={key: int, children: treelist}
type treelist = {hd: tree, tl: treelist}
var lis:intlist := intlist { hd=0, tl= nil }
in
lis
end
これを、今日書きたての type checker にかけると、こんな感じ：
$ ./driver.exe < ../testcases/test5.tig
ExpTy {ty = RECORD [("hd",INT),("tl",NAME "intlist" (Just (RECORD [("hd",INT),("tl",NAME "intlist" Nothing)] 40016)))] 40016}
レコード型のフィールド部分に Nothing が残っちゃっています。
最初は tl=nil のところで型チェックでコケていました：
$ ./driver.exe < ../testcases/test5.tig
driver.exe: Pos {line = 10, column = 36}undefined type (1): intlist
そこで、苦し紛れに trdec (A.TypeDec tdecs) を 3 pass にしてみたけど、やっぱりダメよねと。
明日、ちゃんと考えよう。
以下のコードも参考にさせてもらおうかな： https://github.com/steshaw/tiger-ml
せっかく無理やり実装した unique を使ってないところも気になる。