DumLambda

ラムダ式のコンパイラ。
型推論、パターンマッチ、ガーベジコレクションなど、論文や書籍で学ん だことを実装してみた。
ソース言語はコアのラムダ式にデータ型定義とパターンマッチなどを加え ただけのプリミティブなもの。
型推論は Functional ProgrammingのChapter 7、 パターンマッチ、抽象機械はZINCのChapter 5とChapter 3、 ガーベジコレクションは Modern compiler implementation in ML :basic techniquesの Chapter 13をそれぞれ参考にした。

今後の予定

実行例

fun fact 1 = 1
  | fact n = n * (fact (n - 1));
fun sum [] = 0
  | sum (x::xs) = x + (sum xs);

datatype 'a Tree = Leaf of 'a | Node of 'a Tree * 'a Tree;

fun foldTree f1 f2 tr = case tr of
    Leaf n => f1 n
  | Node(left,right) => f2(foldTree f1 f2 left , foldTree f1 f2 right);

fun makeTree p = case p of
    (0,n) => Leaf n
  | (i,n) => Node(makeTree (i-1,n),makeTree (i-1,n * 2));

(foldTree (fn x=>x) (fn (l,r)=>l + r) (makeTree (fact 3, sum [1,2,3])));

プログラムファイルを指定するバッチモードと、 標準入力からプログラムを受け取るインタラクティブモードがあります。

インタラクティブモードで実行する場合は引数を指定しないか、 "-p"オプションにつづいてひとつ以上のファイル名を引数に指定します。
DumLambdaは、引数で指定されたファイルをまず読み込んで実行し、 その後でプロンプトを表示して標準入力からの入力を受け付けます。

インタラクティブモード実行

bash$ dumlambda -p prelude.dml val fst = fn : V_g.V_f.(_f * _g) -> _f : : val @ = fn : V_ff.(_ff list * _ff list) -> _ff list >

バッチモードで実行する場合は次のようにひとつ以上のファイルを引数にします。

バッチモード実行

bash$ dumlambda test.dml val fact = fn : int -> int val sum = fn : int list -> int datatype 'a Tree = Leaf of 'a | Node of ('a Tree * 'a Tree) val foldTree = fn : V_bc.V_bm._bc -> _bm -> (_bm * _bm) -> _bm -> _bc Tree -> _bm val makeTree = fn : (int * int) -> int Tree val it = 4374 : int

ソース

monotype record計算を導入したバージョン(dumlambda-record)、 polymorphic recordを導入したバージョン(dumlambda-polyrec)を含めたソー スはこちらです。
DumLambda-all-0.5.tar.gz

コンパイル方法

./install

ドキュメント