soutaroのHaskellにっき

2008-02-02

[] 2008-02-02 - soutaroのHaskellにっき を含むブックマーク

これからしばらくHaskell Hackathonに向けた予習について書いていこうと思います.当日,東京での参加が不可能なことがわかったので,あらかじめ書いておいたほうが良いだろうと思うので.

ちなみにソースコードはhttp://svn.soutaro.com/has/trunkにあります.適宜チェックアウトしてみてください.まだまだ開発中なので,最新版は変更がどんどん加わると思いますが.

[]どこまでやるか決める どこまでやるか決める - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - どこまでやるか決める - soutaroのHaskellにっき

最初に,Haskellのどこまでの機能を実装するのか決めてしまいたいと思います.後日,進み具合によって変更することはあるかもしれませんが,目標は決めておきたい.

現時点で,Haskellの興味深い機能を適当に挙げると次のようになります.便宜上,字句解析器・構文解析器・評価器・型システムに分けました.

  1. 字句解析器
    1. オフサイドルール
  2. 構文解析器
  3. 評価器1
    1. パターンマッチ
    2. 遅延評価
  4. 型システム
    1. 型推論
    2. 型クラス
  5. 評価器2
    1. 型クラス
    2. Monadic IO

それぞれ上からの順で実装していけば良いと思います.オフサイドルールは飛ばしても問題ありませんね.パターンマッチは別に興味深くは無いのですが,私が実装したことがありませんでした.遅延評価も飛ばせますが,遅延評価が無いとMonadic IOがなんだかちょっと寂しいことになってしまいます.型クラスを実装しないとその下には進めません.

あと,コンパイラを書くのは面倒なので,全て再帰的なevalで評価器は書きます.また,型推論なんかもパフォーマンスは無視で,関数的に書いていこうと思います.あまりに遅かったらまた考えますが.

あとプログラミング言語はOCamlを使います.ocaml3.10とfindlib,ExtLibが導入されている環境を前提でソースコードを書いていきます.私のコードをビルドしたい方はインストールしておいてください.

[]全体の構造を考える 全体の構造を考える - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - 全体の構造を考える - soutaroのHaskellにっき

普通に…

モジュール名ファイル名説明
Mainmain.mlエントリポイントを書きます
Astast.ml抽象構文木(Abstract Syntax Tree)の定義と操作を書きます
Lexerlexer.mll字句解析器を書きます
Parserparser.mly構文解析器を書きます
Valuesvalues.ml値の定義と操作を書きます
Preludeprelude.ml組み込みの値の定義を書きます
Evaleval.ml評価器(evaluator)の定義を書きます
Debugdebug.mlデバッグプリンタの定義を書きます

ビルドの方法は

$ ocamlbuild -ocamlc "ocamlfind ocamlc -package extlib" -lib extlib main.byte

みたいな感じです.これはMakefileに書いてあります.

[]構文を考える 構文を考える - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - 構文を考える - soutaroのHaskellにっき

構文を決めます.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

idが識別子の型です.ここでは単純にstringです.

literalは即値(literals)の型.文字列と整数と文字があります.文字列はリストがあれば必要ありませんが,とりあえず入れておきます.

exprが式の型です.変数(Var),リテラル(Lit),関数適用(App),関数抽象(Abs),Let式(Let)などがあります.残りは普通の二項演算子

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