近況報告みたいな
普通に実装してます。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を無くすパターンがつかめてきた気がする。