uDiary

◆ [Haskell][Tiger] Modern Compiler Implementation in Haskell?

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 も書けるようになるんだ（ったらいいな）。