Javaで ラムダ計算機を実装してみました。

PG Java

ラムダ計算入門
この PDFを参考に、Javaでのラムダ計算を実装してみました。ついでに JavaCCを使って以下のような文を解釈できるようにしました。

(λx.x(y z));
λs.λz.s(s(sz));

実際には、以下のようなコードで入力の解析と簡約化を行います。

import static ch.jpn.taoe.lambda.Parser.*;
import ch.jpn.taoe.lambda.*;

public class Sample {
    public static void main(String[] args) {
        Parser parser = new Parser();
        String input = "((λx. x) (λx. x)) ((λx. x) (λx. x))";
        Expression exp = parser.parse(new LambdaParser(new StringReader(input)));
        System.out.println(exp); // ((λx.x)(λx.x))((λx.x)(λx.x))

        Set<Expression> repeated = actual.repeat(); // 簡約化
        Expression exp = repeated.toArray(new Expression[0])[0];
        System.out.println(exp); // λx.x
    }
}

ch.jpn.taoe.lambda.variableパッケージには、これを使った チャーチ数の計算や IF分の実装を行ったユーティリティもあります。


ソースは以下のURLからsvnでチェックアウトできます。
http://taoe.jpn.ch:8080/svn/trunk/lambda/