トップ 最新 追記

uDiary

海野秀之(うんのひでゆき)の外部記憶

Twitter (twilog) / RSS / アンテナ / ぶくま

2006|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|08|
2010|01|02|03|05|06|07|10|11|
2011|03|08|
2012|02|04|07|08|10|
2013|01|02|03|05|06|08|11|12|
2014|01|02|05|06|07|08|09|12|
2015|01|02|03|04|

2014-05-14 (Wed)

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


2014-05-21 (Wed)

[Haskell][Tiger] Tiger Book chapter 2

Modern Compiler Implementation in Haskell ということで。

https://github.com/unnohideyuki/Tiger-in-Haskell

2章の lexer は Alex で書いた。 前回のも含めて github に置いてみた。

つぎの parser は Happy だなという話なんですが、Monadic Parser とか説明をちらっと読んでもよくわかんなかったので、最初は単純に書こう。

3章は Parser だけ書いたら、次に進んで、4章以降は練習問題もやっていこうかな。


2014-05-23 (Fri)

[Haskell][Tiger] Tiger Book chap3: Parser

3章の課題である 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

2014-05-29 (Thu)

[Haskell][Tiger] Modern Compiler Implementation in Haskell 5章

この間はじめた、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 を使ってないところも気になる。


2006|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|08|
2010|01|02|03|05|06|07|10|11|
2011|03|08|
2012|02|04|07|08|10|
2013|01|02|03|05|06|08|11|12|
2014|01|02|05|06|07|08|09|12|
2015|01|02|03|04|
Categories 3imp | Card | Cutter | Dalvik | Euler | Football | GAE/J | Hand | Haskell | Re:View | Ruby | Scheme | TQD | Tiger | TigerBook読 | UikiTeXi | Verilog | Violin | Web | parconc | tDiary | お勉強 | エントロピー | ツン読 | | 将棋 | 政治について | | 模写してみよう | 確率論 | 設定など | 雑文 | 音声