JavaScriptの練習用につくった。
式を書き込んでボタンを押し、その下の要素をクリックすると計算が進む。
変数名の後ろに名前の衝突を避けるための数字が
(簡単のため必要以上に) つくことがある。
ソースコードとJavaScriptの紹介。
1行目。
var pair = function(x, y) {this.car = x; this.cdr = y;};
thisが何を指すのか分かりにくいが、
のいずれかによってthisの指すものは変わる。
2行目。
var cons = function(x, y) {return new pair(x, y);};
newがついているのでpairはコンストラクタだ。
3--35行目は、2行目のconsとともにLispでよく使われる関数と
定数nilを真似たもの。
conspのpは述語 (predicate) のこと。
readは文字列をパースしてコンスの木構造をつくる。
readが失敗したときはnullを返す。
成功してもnilを返すことがあるので、nilとnullは同一視できない。
var acons = function(x, y, z) {return cons(cons(x, y), z);};
var nil = cons(null, null);
var consp = function(x) {return x && x.car && x.cdr;};
var reverse = function(xs) {
var ys = nil;
while (consp(xs)) {
ys = cons(xs.car, ys);
xs = xs.cdr;
}
return ys;
};
var read = function(str) {
var tokens = str.match(/\(|\)|[^ \f\n\r\t\v\(\)]+/g);
if (!tokens) return null;
var xs = nil;
var xss = nil;
while (tokens.length > 0) {
var t = tokens.shift();
if (t == "(") {
xss = cons(xs, xss);
xs = nil;
} else if (t == ")") {
if (xss == nil) return null;
xs = cons(reverse(xs), xss.car);
xss = xss.cdr;
} else {
xs = cons(t, xs);
}
}
if (xss != nil) return null;
if (xs.cdr != nil) return null;
return xs.car;
};
37--53行目。parseの定義。
readが返す木構造を解析してλ式の定義に合う構文木をつくる。
λ式の構文はvariable, application, abstractionの3種類ある。
それらをswitchやifで場合分けする書き方とポリモーフィズムを使う書き方がある。
Arcで書いたときのやつはifで分けていた。
それと、λ式の定義のチェックを事前には行わず
不正な部分式を見つけ次第その場でnilに置き換えていた。
今回はparseの中で構文のチェックとポリモーフィズムの下準備をしている。
var parse = function(x) {
if (x != nil) {
if (!consp(x)) return new variable(x);
if (consp(x.cdr)) {
if (x.cdr.cdr == nil) {
var fn = parse(x.car);
var arg = parse(x.cdr.car);
if (fn && arg) return new application(fn, arg);
} else if (consp(x.cdr.cdr) && x.cdr.cdr.cdr == nil && x.car == "fn") {
var param = parse(x.cdr.car);
var body = parse(x.cdr.cdr.car);
if (param && body && param.type == "var")
return new abstraction(param, body);
}
}
}
};
returnせずに関数から抜けるとundefinedが返される。
この後にvariable, application, abstractionの定義が続く。
55--71行目。variableの定義。
var variable = function(x) {this.name = x;};
variable.prototype.type = "var";
variable.prototype.id = 0;
variable.prototype.substitute = function(al) {
while (consp(al)) {
var z = al.car.car;
if (this.name == z.name && this.id == z.id) {
return al.car.cdr;
}
al = al.cdr;
}
return this;
};
variable.prototype.beta = function() {return this;};
variable.prototype.print = function() {
return this.id ? this.name.concat("(", this.id, ")") : this.name;
};
コンストラクタのprototypeのプロパティは各インスタンスに継承される。
具体的には、variable.prototypeに以下のプロパティ
を定義したので、variableの各インスタンスもこれらのプロパティを持つ。
ただし各自でコピーを取るのではなく同一のオブジェクトを共有する形になる。
immutableなオブジェクトの共有は全く問題ないが、
mutableなものは共有すると困ることもある。
たとえばidを0以外の値にしたいとき。
idはλ式中の変数をリネームするとき既存の変数名との衝突を防ぐ。
var rename_id = 0;
var rename = function(v) {
var w = new variable(v.name);
rename_id += 1;
w.id = rename_id;
return w;
};
(73--79行目)
ここで77行目が破壊的代入に見えるかもしれないが、
実はprototypeのプロパティは破壊されない。
wに新たにプロパティ (w.id) を追加しているだけである。
81--98行目。applicationの定義。
applicationとは「関数適用」のこと。
var application = function(x, y) {this.fn = x; this.arg = y;};
application.prototype.type = "app";
application.prototype.substitute = function(al) {
return new application(this.fn.substitute(al), this.arg.substitute(al));
};
application.prototype.beta = function() {
if (this.fn.type == "abs") {
return this.fn.body.substitute(acons(this.fn.param, this.arg, nil));
}
var x = this.fn.beta();
if (x != this.fn) return new application(x, this.arg);
x = this.arg.beta();
if (x != this.arg) return new application(this.fn, x);
return this;
};
application.prototype.print = function() {
return "(" + this.fn.print() + " " + this.arg.print() + ")";
};
こちらでもsubstitute, beta, printが定義されていることに注意。
そして、variableなのかapplicationなのかabstractionなのか
分からないオブジェクトのsubstitute, beta, printメソッドを呼び出している。
そういうのをポリモーフィズムという。
100--113行目。abstractionの定義。
ここにもsubstitute, beta, printがある。
var abstraction = function(x, y) {this.param = x; this.body = y;};
abstraction.prototype.type = "abs";
abstraction.prototype.substitute = function(al) {
var v = rename(this.param);
return new abstraction(v, this.body.substitute(acons(this.param, v, al)));
};
abstraction.prototype.beta = function() {
var x = this.body.beta();
if (x != this.body) return new abstraction(this.param, x);
return this;
};
abstraction.prototype.print = function() {
return "(fn " + this.param.print() + " " + this.body.print() + ")";
};
余談だがメソッド呼び出しと関数呼び出しの違いが分かりにくい件について。
x.foo == fのとき
x.foo()はメソッド呼び出しf()は関数呼び出し(x.foo)()はメソッド呼び出し(y = x.foo)()は関数呼び出し(y.foo = x.foo)()は関数呼び出しなど。(合ってるかな……)
115--138行目。ユーザインターフェースというかイベントハンドラ。
ボタンを押したときにinitが呼ばれる。
それはHTMLのソースにそう書いたのだから当たり前だ。
しかしボタンの下のdiv要素をクリックしたときの動作は
HTMLのほうには書いてない。
JavaScriptの実行時に設定している。
それ以外にも、実行時に文字を書いたり消したり色々なことができるが、
それはJavaScriptの仕様ではなく、DOMというAPIの仕様である。
var init = function() {
var stdin = document.getElementById("stdin");
var stdout = document.getElementById("stdout");
var x = read(stdin.value);
if (!x) {
alert("parse error");
return;
}
x = parse(x);
if (!x) {
alert("parse error");
return;
}
rename_id = 0;
stdout.innerHTML = x.print();
stdout.onclick = function() {iter(x, stdout);};
};
var iter = function(x, o) {
var y = x.beta();
if (x != y) {
o.innerHTML += "<br>" + y.print();
o.onclick = function() {iter(y, o);};
}
};