近況報告みたいな

Haskell Hackathon

普通に実装してます。http://svn.soutaro.com/has/trunkにあります。

http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4-05w/text/eopl014.htmlあたりを見て適当に実装して、遅延評価ができるようになった。

f x y = x
print f 100 (1/0)

とかやっても、ちゃんと100って出るとか。

x = 1 : map (\n -> n+1) xs
print take 5 x

とかやると、[1,2,3,4,5]って出るとか。そんな感じ。あ、printっていうのは、式を表示するための構文です。出力のための関数を定義したくないので（セマンティクスがおかしくなる）、トップレベルに変なの入れることにした。めんどくさくなったので、サンクはOCamlのクロージャをそのまま使ってる。あ、遅延評価はしてるけど、call-by-needにはなってない（毎回サンクが評価されてしまう）。

ここまでで面白かったのは、パターンマッチングとか再帰の定義とか。

パターンマッチングは、

case [1,2,3] of 
     [x,y,z] -> ...

とかやると、x,y,zに1,2,3がそれぞれ入る機能。これも、まあパターンと値を普通に分解していって、変数があったら値を登録した環境を作るようにする、みたいな感じ。eval.mlのbind_patternがその辺。

最初、はまったのは、

let rec bind_pattern env pat v =
  match (pat, Values.thaw v) with
      (Ast.VarPat x, v) -> Values.Env.add x { Values.result = Some v } env
    | (Ast.LitPat(Ast.IntLit i), Values.IntValue j) when i = j -> env
    | (Ast.LitPat(Ast.CharLit c), Values.CharValue d) when c = d -> env
    | (Ast.ConstrPat(constr_name, pats), Values.ConstrValue(constr_name', values))
        when constr_name = constr_name' && List.length pats = List.length values
           -> List.fold_left2 bind_pattern env pats values
    | (Ast.TuplePat pats, Values.TupleValue vals) -> List.fold_left2 bind_pattern env pats vals
    | _ -> raise (MatchError(pat, v))

みたいに書いていたところで、これで何がまずいかというと、問答無用で値のサンクを評価してしまっているところ。変数に対しては、問答無用でバインドしないといけないので、そのときはサンクを評価してはいけない（パターンへのバインドは関数適用のときにも使うので、一番上の例見たいのがdivision by zeroになってしまう）。パターンが変数(VarPat)の場合は、一番最初に特別扱いしてあげないといけない。

あと、上のプログラムにも書いてあるけど、Consとかはそれようの値は定義してなくて、Cons(1,Nil)とか普通にヴァリアントに分解するようになってたりする。TrueとかFalseとかも。これはこれで楽しい。自然数も、

data Int = Zero | Succ Int

とかして定義してしまえば、ラムダ計算にさらに近づくことになるけど、まあそこまでやっても、という感じ。

再帰的な定義は、最初、関数的に書きたいと思ってEOPLの再帰関数の実装 - sumiiの日記とかを見てやってたんだけど、コメントを見ればわかるんだけど、この方法は実は制限が大きい（右辺がラムダ式になっていないといけない）。これだと、無限リスト(x = 1:x)みたいのが作れなくて悲しいので、途中で副作用を使うようにした。

一方、できてないのは、トップレベルだと相互再帰が書けないとか(letの中なら大丈夫、なはず)、whereがないとか、let { fact 0 = 1; fact n = ... } in ...みたいな、let bindingの中に複数書きたいとか、その辺。めんどくさい。

まじめにインタプリタ作るのは初めてなので、いろいろと躓くけど、面白い。正直、ランタイムの振る舞いにはそこまで興味が持てないので、あんまりまじめにはやってないけど。そろそろ型システムを書く。

あと、パーサ書くのに慣れてきた。ちょっと前まで24 shift/reduce conflictsとか言われると途方にくれてたんだけど、なんとなくshift/reduce conflictを無くすパターンがつかめてきた気がする。