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モジュールに興味があるかたは実装を読んでも良いと思います．