2008-02-02
■ [Haskell Hackathon]

これからしばらくHaskell Hackathonに向けた予習について書いていこうと思います.当日,東京での参加が不可能なことがわかったので,あらかじめ書いておいたほうが良いだろうと思うので.
ちなみにソースコードはhttp://svn.soutaro.com/has/trunkにあります.適宜チェックアウトしてみてください.まだまだ開発中なので,最新版は変更がどんどん加わると思いますが.
■ [Haskell Hackathon]どこまでやるか決める

最初に,Haskellのどこまでの機能を実装するのか決めてしまいたいと思います.後日,進み具合によって変更することはあるかもしれませんが,目標は決めておきたい.
現時点で,Haskellの興味深い機能を適当に挙げると次のようになります.便宜上,字句解析器・構文解析器・評価器・型システムに分けました.
それぞれ上からの順で実装していけば良いと思います.オフサイドルールは飛ばしても問題ありませんね.パターンマッチは別に興味深くは無いのですが,私が実装したことがありませんでした.遅延評価も飛ばせますが,遅延評価が無いとMonadic IOがなんだかちょっと寂しいことになってしまいます.型クラスを実装しないとその下には進めません.
あと,コンパイラを書くのは面倒なので,全て再帰的なevalで評価器は書きます.また,型推論なんかもパフォーマンスは無視で,関数的に書いていこうと思います.あまりに遅かったらまた考えますが.
あとプログラミング言語はOCamlを使います.ocaml3.10とfindlib,ExtLibが導入されている環境を前提でソースコードを書いていきます.私のコードをビルドしたい方はインストールしておいてください.
■ [Haskell Hackathon]全体の構造を考える

普通に…
モジュール名 | ファイル名 | 説明 |
---|---|---|
Main | main.ml | エントリポイントを書きます |
Ast | ast.ml | 抽象構文木(Abstract Syntax Tree)の定義と操作を書きます |
Lexer | lexer.mll | 字句解析器を書きます |
Parser | parser.mly | 構文解析器を書きます |
Values | values.ml | 値の定義と操作を書きます |
Prelude | prelude.ml | 組み込みの値の定義を書きます |
Eval | eval.ml | 評価器(evaluator)の定義を書きます |
Debug | debug.ml | デバッグプリンタの定義を書きます |
ビルドの方法は
$ ocamlbuild -ocamlc "ocamlfind ocamlc -package extlib" -lib extlib main.byte
みたいな感じです.これはMakefileに書いてあります.
■ [Haskell Hackathon]構文を考える

構文を決めます.Astの定義を見てみましょう.
$ svn cat -r 5 http://svn.soutaro.com/has/trunk/ast.ml
- r 5ってどんなだったか覚えていませんが,最初はこんな感じで定義していました.
type id = string type literal = String of string | Char of char | Int of int type expr = Var of id | Lit of literal | App of expr * expr | Abs of id * expr | Let of let_binding * expr (* Binary operators *) | Plus of expr * expr | Minus of expr * expr | Mul of expr * expr | Div of expr * expr and let_binding = id * expr type decl = Val of id * expr | Print of expr
literalは即値(literals)の型.文字列と整数と文字があります.文字列はリストがあれば必要ありませんが,とりあえず入れておきます.
exprが式の型です.変数(Var),リテラル(Lit),関数適用(App),関数抽象(Abs),Let式(Let)などがあります.残りは普通の二項演算子.
letbindingはlet x = e in exprの太字の部分のことを言います.これも,本当は関数が来たり,パターンが来たりするのですが,現時点ではこのままにしておきます.
最後のdeclはトップレベルの定義です.プログラム全体はdeclのリストになります.Valが,Haskellで
fact = ¥n -> if n = 0 then 1 else n * fact (n-1)
とか書くやつに相当します.値の定義です.Printは,ここで特別に入れた構文で,引数の式を評価した結果を出力します.Haskellには本当はこんな構文はありませんが,普通の関数として文字列を出力するやつを入れるのは,純粋関数型言語的にいかがなものかと思い,構文を新たに導入することにしました.Monadic IOまで実装したら,Printは消えます.
他にPretty Printerの定義があります.OCamlのFormatモジュールに興味があるかたは実装を読んでも良いと思います.