こんにちはphi16です。この記事はHaskell Advent Calendar 2016 の8日目の記事です。
Haskell(GHC)で色々プログラムを書いていると、たまにバグって次のようなエラーを見ることがあるとおもいます。
main: <<loop>>
これはGHCが式を評価していたら無限ループを発生させてしまうことを検出して投げる例外なのですが、勿論全ての無限ループを検出することはできません。
またHaskellでは次のような「無限ループ」は"合法"です :
a = 1 : a
というわけで、どんな無限ループなら「合法なのか」「検出できるのか」、また「どういう機構でこれを実現しているのか」という話を、GHCの実際の評価機構をJavaScriptで1作りながら適当にまとめてみようとおもいます。半分くらいは自分用メモかもしれないです。
情報源としてはSTG論文が主で、それを更に単純化したモデルを考えているため現行のGHCとはかなり異なる処理をしています。ご了承ください。
これを読むことでHaskellコードからCPUの歓声が聞こえるようになるといいなとおもいます。
値の表現
Haskellは遅延評価を行うため、「値」そのものの表現が自明な形では定まりません。遅延評価というのは「実行(評価)することで値が初めて得られるような仕組み」なので、これが表現できれば良さそうです。
今回考える処理系では、値一般のことを「実行コードcodeをメンバに持つオブジェクト」とみなすことにしましょう。全ての基礎となる評価関数は次のように実装されます :
function Eval(x,env){
x.code(x,env);
};
このように実行関数x.codeにはその値自身xと環境envが渡されてきます。このような処理を想定したオブジェクトのことを「クロージャ」と呼ぶことにします。
その名の通りといえば何ですが、実際これはクロージャを表現してくれます。関数に必要なのは「引数名」「関数本体」と言ったところですが、それに加えて「自由変数名」「自由変数の参照先」も管理することになります。
var Closure = function(free,args,code,ref){ // ([String],[String],(X,Env) → (),[Closure])
return {free:free,args:args,code:code,ref:ref};
};
引数などは関数適用のときにargsに対応する名前で環境envに自動で登録されるものとしましょう。とすると例えばconst関数は次のように実装できそうです :
// this doesn't work
var Const = Closure([],["x"],function(x,env){
return Closure(["x"],["y"],function(x,env){
return env["x"];
},[env["x"]]);
},[]);
後で正しく書き直すことになりますが、雰囲気は伝わるでしょうか。Haskellで書いたconst関数 : \x → \y → xには自由変数の情報は含まれていませんが、構文解析の段階でもその情報を加えることはできるでしょう。今回は自分で明示していくことになります。
なおクロージャの一種(引数が無いもの)としてサンク(未評価の値)という概念があります。これこそが遅延評価の特徴となっており、後で細かくみることになります。
Haskellの値といえばデータコンストラクタがありますが、これも一種のクロージャとして構成します。List a = Nil | Cons a (List a)とした時、NilとConsは次のように表現されます :
var Nil = Closure([],[],function(x,env){
ReturnCon(0)();
},[]);
var Cons = Closure([],["x","y"],function(x,env){
ReturnCon(1)(env["x"],env["y"]);
},[]);
実はデータコンストラクタを評価するのはcase式の中だけだと決まっているので2、Nil/Consを実行することになるときはこのコードは必ずパターンマッチに使われるはずです。ReturnCon(n)で「n番目のコンストラクタのマッチングに対応する継続を拾ってくる」ということができ、実際にデータコンストラクタに対応する分岐が実行されることとなります。タグ付けて値を返して分岐を選ぶよりも効率的なわけです。
また、Intなどの生値をこの実行形式ではそのまま扱うことができます。正確には全ての生値を単一のデータコンストラクタで包むことで遅延評価をしつつ生レベルの処理を実行できるというものです。
var Raw = function(n){
var cl = Closure([],[],function(x,env){
ReturnRaw(x.value);
},[]);
cl.value = n;
return cl;
};
今回はこのRaw関数によって生値を包み、その値へのcase式が発生したときにReturnRaw関数に生値を渡してあげる、ということにします。ReturnRawはReturnConと大差ないです。JavaScriptの任意の値はRawで包むことでこの枠組で扱えるようになるわけですが3、とりあえずは整数値を入れることを考えています。
・・・とまぁ、だいぶ一般的な言語処理系とは異なる値の扱い・処理をしているようです。値に意味が付随するというのがちょっとおもしろい点でしょうか？caseのマッチングの仕組みがなんとも合理的な感じで個人的に好きです。
未だに「動作」はさせていないので分からない点は多いと思います。実際の動作例を見ることで理解できることもあるとおもうのでとりあえず読んでいくと良い気がします。
関数適用
遅延評価でなければ「引数を評価し」「それを関数に渡す」のが基本ですが、今回は「引数のクロージャを自由変数に結びつけ」「関数を実行する」という流れになります。この評価機構は複数引数を同時に適用できるようになっているのですが、過剰引数(const id 1 2など)を適切に扱うために一度「引数スタックargs」に退避してからenvに書き込みをすることになります。
var args = [];
function exec(code,def){
def.code = code;
return def;
}
function retrive(env,x){
if(typeof env[x] === "undefined")return x;
else return env[x];
}
var Apply = function(x,env){
for(var i=x.arg.length-1;i>-1;i--){
args.push(retrive(env,x.arg[i]));
}
Enter(x.func);
};
function app(f,xs){
return exec(Apply,{func:f,arg:xs});
}
先に言ったように、基本的に値は「意味を表すコード」と「データを表すオブジェクト自身」で表現します。exec関数はそれらを合成して値を構成する便利関数です。またappはApplyをコードとして持つような値を作るための便利関数です。
Applyを実行する(つまり関数適用をEvalする)とき、その引数をスタックに積んでEnterによって「関数を実行」します。
Enterされた関数は自由変数と引数の情報を拾い集め、関数本体を評価しにいきます :
function Enter(f){
var env = {};
for(var i=0;i<f.free.length;i++){
env[f.free[i]] = f.ref[i];
}
f.args.forEach(function(name){
env[name] = args.pop();
});
Eval(f,env);
}
これで先程書いた「自動でenvに登録する」を達成しますね。さて、このApplyによって「ちゃんと動く」id関数を作ることができます :
var Id = Closure([],["x"],function(x,env){
Eval(app(env["x"],[]),env);
},[]);
env["x"]をEvalするのではなくapp(env["x"],[])をEvalしているのはちゃんと「(サンクとしての)クロージャを実行する」という処理(Enter)を走らせるためです4。
ちなみにconstは引数をもう一つ取ればいいだけですね。
var Const = Closure([],["x","y"],function(x,env){
Eval(app(env["x"],[]),env);
},[]);
リターンスタック
基礎は大体できあがったので、次に生値をリターンする部分をつくります。
var returns = [];
function ReturnRaw(n){
var ret = returns.pop();
ret(ret.env)[0](n);
};
function evaluate(expr){
returns.push(function(env){return [function(n){
console.log(n);
}];});
Eval(expr,{});
}
式の評価はcase式でのみ発生すると言いました。これはcase式でのみリターンスタックに積む処理が発生するということです。ReturnRaw関数では確かにそのリターン先を取り出して引数に渡して実行、を行っていますね。
また、evaluate関数ではとりあえず最初に「値を表示するための謎の継続」を積んでおくことで評価を模倣しています。実際Evalした結果は自動的にリターンスタック上の関数を呼ぶので、これでconsole.log(n);は実行されるはずです5。
というわけで、早速実行してみましょう。と言ってもid/constくらいしかないですけど。
evaluate(app(Id,[Raw(1)])); // => 1
evaluate(app(Const,[Raw(2),Raw(3)])); // => 2
evaluate(app(Const,[Id,Raw(4),Raw(5)])); // => 5
ちなみに、ここで関数の引数として渡せるものはかなり限られています。元々クロージャくらいしか想定していないのです。これでは関数適用のネストすらできないので、これを回避するためにlet-in式を作ることになります。
let-in式、case式
もう評価機構自体は殆ど出来ているので複雑なことはあんまりないです。
var Let = function(x,env){
for(var i=0;i<x.defines.length;i+=2){
var name = x.defines[i];
var value = x.defines[i+1];
env[name] = value;
}
for(var i=0;i<x.defines.length;i+=2){
var name = x.defines[i];
env[name].ref = [];
env[name].free.forEach(function(n){
env[name].ref.push(env[n]);
});
}
Eval(x.expr,env);
};
function letIn(xs,e){ // ([String,Closure],Closure)
return exec(Let,{defines:xs,expr:e});
}
letInについては細かく解説しません。
function ReturnCon(n){
var ret = returns.pop();
return ret(ret.env)[n];
};
var Case = function(x,env){
x.cases.env = env;
returns.push(x.cases);
Eval(x.expr,env);
};
function caseOf(expr,cases){ // (Closure,Env -> [Argument -> Closure])
return exec(Case,{expr:expr,cases:cases});
};
ReturnConではReturnRawと同様に適切な継続(今回はn番目のコンストラクタに対応する継続)を拾ってきます。Caseはリターンスタックに積むだけですね6。
いろいろ実行してみよう
case式ができるようになったおかげでだいぶ幅が広まりました。特にRawの中身を取り出すことができるようになりました。ということで :
var Add = Closure([],["x","y"],function(x,env){
Eval(caseOf(app(env["x"],[]),function(env){return [function(x){
env["#x"] = x;
Eval(caseOf(app(env["y"],[]),function(env){return [function(y){
env["#y"] = y;
Eval(Raw(env["#x"] + env["#y"]),env);
}];}),env);
}];}),env);
},[]);
evaluate(app(Add,[Raw(6),Raw(7)])); // => 13
生値の加算ができるようになりました7！
ついでに調子に乗ってみます。
var Length = Closure([],["xs"],function(x,env){
Eval(caseOf(app(env["xs"],[]),function(env){return [function(){
Eval(Raw(0),env);
},function(a,as){
Eval(letIn([
"n",Closure([],[],function(x,env){Eval(app(Length,[as]),env);},[])
],Closure(["n"],[],function(x,env){Eval(app(Add,[Raw(1),env["n"]]),env)},[])),env);
}]}),env);
},[]);
evaluate(letIn([
"a",Closure([],[],function(x,env){Eval(app(Nil,[]),env);},[]),
"b",Closure(["a"],[],function(x,env){Eval(app(Cons,[Raw(10),env["a"]]),env);},[]),
"c",Closure(["b"],[],function(x,env){Eval(app(Cons,[Raw(9),env["b"]]),env);},[]),
"d",Closure(["c"],[],function(x,env){Eval(app(Cons,[Raw(8),env["c"]]),env);},[])
],Closure(["d"],[],function(x,env){Eval(app(Length,[env["d"]]),env);},[]))); // => 3
読みにくいですけどlet {a = Nil; b = Cons 10 a; c = Cons 9 b; d = Cons 8 c} in length d、要はlength (Cons 8 (Cons 9 (Cons 10 Nil)))です。うまくうごいてくれるはずです。
折角なので評価経過をゆっくり見てみようかと思います。重要なのはEval/Enter/ReturnCon/ReturnRawなので、それらの呼び出しを確認してみます。適当に手動で見やすくしています8(あと無駄な部分を消したりしてます)。
"Eval" let {a=Nil[], b=Cons[10,a], c=Cons[9,b], d=Cons[8,c]} in Length[d]
"Eval" Length[Cons[8,Cons[9,Cons[10,Nil[]]]]] {}
"Enter" Length {}
"Eval" Length {xs -> Cons[8,Cons[9,Cons[10,Nil[]]]]}
"Eval" case xs of {Nil -> ..., Cons a as -> ...} {xs -> ...} [+Return]
"Eval" Cons[8,Cons[9,Cons[10,Nil[]]]] {xs -> ...}
"Enter" Cons {xs -> ...}
"Eval" Cons {xs -> ..., x -> 8, y -> Cons[9,Cons[10,Nil]]}
"ReturnCon" 1 (Cons) [-Return]
"Eval" Add[1,Length[y]] {xs -> ..., x -> 8, y -> ...}
"Enter" Add {xs -> ..., x -> 8, y -> ...}
"Eval" Add {xs -> ..., x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]}
"Eval" case x of {x -> ...} {xs -> ..., x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]} [+Return]
"Eval" 1 {xs -> ..., x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]}
"ReturnRaw" 1 [-Return]
"Eval" case y of {y -> ...} {xs -> ..., x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]} [+Return]
"Eval" Length[Cons[9,Cons[10,Nil[]]]] {xs -> ..., x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]}
"Enter" Length {xs -> ..., x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]}
"Eval" Length {xs -> Cons[9,Cons[10,Nil]]}
...
"Eval" Length {xs -> Nil[]}
"Eval" case xs of {Nil -> ..., Cons a as -> ...} {xs -> Nil[]} [+Return]
"Eval" Nil[] {xs -> Nil[]}
"Enter" Nil {xs -> Nil[]}
"Eval" Nil {}
"ReturnCon" 0 (Nil) [-Return]
"Eval" 0 {xs -> Nil[]}
"ReturnRaw" 0 [-Return]
"Eval" 1 {x -> 1, y -> Length[Nil[]]}
"ReturnRaw" 1 [-Return]
"Eval" 2 {x -> 1, y -> Length[Cons[10,Nil[]]]}
"ReturnRaw" 2 [-Return]
"Eval" 3 {x -> 1, y -> Length[Cons[9,Cons[10,Nil[]]]]}
"ReturnRaw" 3 [-Return]
// => 3
再帰呼び出しによってリターンが積まれていき、最後に一気に戻っていくのがわかるとおもいます。
グラフ簡約
今のところ遅延評価としてはうまく動作するのですがグラフ簡約はしてくれないです。
例えば :
evaluate(letIn([
"a",Closure([],[],function(x,env){Eval(app(Add,[Raw(1),Raw(1)]),env);},[]),
"b",Closure(["a"],[],function(x,env){Eval(app(Add,[env["a"],env["a"]]),env);},[]),
"c",Closure(["b"],[],function(x,env){Eval(app(Add,[env["b"],env["b"]]),env);},[])
],Closure(["c"],[],function(x,env){Eval(app(env["c"],[]),env);})));
要はlet {a = 1 + 1; b = a + a; c = b + b} in cで8なのですが、この間aは4回評価されてしまいます9。これではグラフ簡約になってないので、色々修正する必要があるのです。
実際に必要な仕組みは「クロージャの更新」です。aを評価した結果ReturnRaw 2が発生するはずですが、これを察知してaの指すクロージャをRaw(2)そのものにすり替えてしまう、ということを行うのです。更新できるクロージャと更新できないクロージャ(idとか)がありますが、これは明示的にソースに記述することにします10。
function updatable(closure){
closure.updatable = true;
return closure;
}
var updates = [];
function Enter(f){
var env = {};
for(var i=0;i<f.free.length;i++){
env[f.free[i]] = f.ref[i];
}
f.args.forEach(function(name){
env[name] = args.pop();
});
if(f.updatable){
// f.args.length should be 0
updates.push({args:args,returns:returns,target:f});
args = [], returns = [];
}
Eval(f,env);
}
updatableなクロージャへのEnterが発生したとき、引数スタックとリターンスタックをすべて退避してしまいます。そうすると、このクロージャが最後にリターンするときにちょうどスタックが空になっているはずです。というわけでReturnRaw、ReturnConを対応させます。
function ReturnRaw(n){
if(returns.length==0){
var u = updates.pop();
args = u.args, returns = u.returns;
var repl = Raw(n);
u.target.free = repl.free;
u.target.args = repl.args;
u.target.code = repl.code;
u.target.ref = repl.ref;
u.target.value = repl.value;
delete u.target.updatable;
}
var ret = returns.pop();
ret(ret.env)[0](n);
}
function ReturnCon(n){
if(returns.length==0){
var u = updates.pop();
args = u.args, returns = u.returns;
return function(){
var args = [];
for(var i=0;i<arguments.length;i++)args.push(arguments[i]);
var names = [];
for(var i=0;i<args.length;i++){
names.push("Var"+i);
}
var repl = Closure(names,[],function(x,env){
var vars = names.map((n)=>env[n]);
ReturnCon(n).apply(null,vars);
},args);
u.target.free = repl.free;
u.target.args = repl.args;
u.target.code = repl.code;
u.target.ref = repl.ref;
delete u.target.updatable;
var ret = returns.pop();
ret(ret.env)[n].apply(null,args);
}
}else{
var ret = returns.pop();
return ret(ret.env)[n];
}
}
更新する対象はupdates[0]に保持されており、またそれを何に更新するかというのもReturnRawでは引数のnが持っています。というわけで実際にRaw(n)の処理内容をコピーし11、最後にupdatableのフラグを消せば更新完了なのです。ReturnConでも大体同じです12。
というわけで次のコードは実際にaを1度しか評価しないようになってくれます。やったね！
evaluate(letIn([
"a",updatable(Closure([ ],[],function(x,env){Eval(app(Add,[Raw(1),Raw(1)]),env);},[])),
"b",updatable(Closure(["a"],[],function(x,env){Eval(app(Add,[env["a"],env["a"]]),env);},[])),
"c",updatable(Closure(["b"],[],function(x,env){Eval(app(Add,[env["b"],env["b"]]),env);},[]))
],Closure([],[],function(x,env){Eval(app(env["c"],[]),env);})));
本題
とりあえず今まで評価機構を作ってきたわけですが、元々の考えたい内容は「無限再帰停止機構」のはなしでした。
無限再帰検出の仕組みは実は非常に簡単です : クロージャを更新している間にそのクロージャを評価したら無限再帰。
何故なら更新可能なクロージャは引数を取れないことになっている為envの内容は全く変化せず13、結果そのクロージャへの評価はまた必ず更新を生むので、またさらなるクロージャの評価を生むからですね。参照透明性からこれは無限再帰にしかならないことがわかります。
「現在クロージャの評価中であること」は一般のクロージャでは取得できませんが、更新中なら明らかです。(更新開始したら更新終了するはずです。)
さらに言えばクロージャを更新する際には完全に前のクロージャの情報を消してしまうわけで、「クロージャの更新を開始したらそのクロージャに対して何をしても良い」ということが従います。もしもそれで問題となるケースがあれば無限再帰のみだからです14。そしてこの機構は"Black hole"と呼ばれているようです。
function updatable(closure){
closure.updatable = true;
var code = closure.code;
closure.code = function(x,env){
// make a black hole!
x.code = function(x,env){
throw new Error("<<loop>>");
};
code(x,env);
};
return closure;
}
updatableにする際にクロージャの内部コードにちょっと手を加えます。これで評価が発生したときに「自身の実行コードを例外を投げる関数に変えてから」今まで通りの評価をする、ということが実現できます。
var A = updatable(Closure([],[],function(x,env){
Eval(app(Add,[Raw(1),A]),env);
},[]));
evaluate(A); // => Uncaught Error: <<loop>>
a = 1 + aとしてaを評価すると、確かに例外を吐いてくれるようになりました！
でも、勿論b = 1 : bは特に問題は起きないですね！ (下のコードはlength (take 10 b)です) (Takeの定義でズルをしていますけど許してください)
var Take = Closure([],["n","xs"],function(x,env){
Eval(caseOf(app(env["n"],[]),function(env){return [function(n){
if(n==0){
Eval(app(Nil,[]),env);
}else{
Eval(caseOf(app(env["xs"],[]),function(env){return [function(){
Eval(app(Nil,[]),env);
},function(a,as){
Eval(letIn([
"ys",Closure([],[],function(x,env){Eval(app(Take,[Raw(n-1),as]),env);},[])
],Closure(["ys"],[],function(x,env){Eval(app(Cons,[a,env["ys"]]),env);},[])),env);
}];}),env);
}
}];}),env);
},[]);
var B = updatable(Closure([],[],function(x,env){
Eval(app(Cons,[Raw(1),B]),env);
},[]));
evaluate(letIn([
"b",updatable(Closure([],[],function(x,env){Eval(app(Take,[Raw(10),B]),env);},[])),
"c",updatable(Closure(["b"],[],function(x,env){Eval(app(Length,[env["b"]]),env);},[]))
],Closure(["c"],[],function(x,env){Eval(app(env["c"],[]),env);},[]))); // => 10
この差がどこから来るかというと、a = 1 + aについてはaを更新する際には1の評価のあとaを評価しないと更新が完了しない(Addの中でcase式を呼んでしまう)、ということとb = 1 : bではbの更新は最初のConsが来た時点でもう完了する(ReturnCon)、という部分ですね。
というわけで、無限再帰停止機構について1から作り上げて再現できるようになりました！おめでとうございます！
まとめ
最初の質問に対する答えとしては :
- クロージャの評価中にそのクロージャ自身を巻き込むようなことがなければ合法で
- 合法でないものは全て検出できる
- その検出機構は"Black hole"で実現されている
ということになります。
これでf x = 1 + f xでは検出できないことや、a = seq a 1では検出されることがわかるとおもいます15。
長かった・・・
感想
Haskell AdCなのにHaskellコードはおろか型の話16すら書いてないので書いてて申し訳ない感じでしたが、あまり表に出てこない内部機構についてちょっと細かくかけたかなーと思います。
このSTG機械は勿論関数型言語の実装に参考になる点が多いとおもいますが、普通に読んでいても楽しいしHaskellの内部に詳しくなった気になれるので暇があれば覗いてみると良いとおもいます(そのなかでBlack holeがおもしろかったのでこの記事を書いた)。
尚今回はJSで実装しましたが、できるだけクロージャを使わないようにしているのでC言語などに落とすのもそんなに難しくないはずです(envはこのままだと困りそう)(元論文にはこの先のアセンブリレベルの話も載っていますのでそちらを参照)。いつかGHCの吐くバイナリを読めるようになってみたいですね。
おわりです。明日は@todays-mitsuiさんの記事です。
-
GCがあり、型が無く、値の更新ができるというそこそこ実際の評価環境に近い言語なので (あと個人的な趣味) ↩
-
STG言語の中では。Haskellでも全ての基本的な評価はcase式に置き換えられますけど。 ↩
-
と考えるとIO Monadの中ではいくらでも自由なことができる、というのはまぁ自明なんですね。不思議さがちょっと減ったでしょうか。 ↩
-
STG言語では「クロージャを直接返す」ことはできず、必ず適用演算が挟まるようになっています。今回は0引数ということです。 ↩
-
この挙動を見るとわかるとおもいますが、この評価器は全てを末尾呼び出し・継続渡しスタイルで実行しています。アセンブリにも落としやすそう。 ↩
-
ところでSTG論文の方は素直に
case xs ofとか書いていたんですけど構文的にダメじゃないですかね・・・？(case xs {} of？) ↩ -
ここではさらっと
envに生値を突っ込んでいますが、実際にはこれが生値なのかクロージャなのかの区別を示すタグをいれるようです ↩ -
と言っても普通に出力したら謎オブジェクトしか吐いてくれないので自分で中身を想像して書いてるんですけど・・・ ↩
-
function(x,env){}の中でconsole.logとかすればわかるとおもいます ↩ -
STG言語ではクロージャの表記に
\u(updatable)と\n(not updatable)を用意しています。どっちにするべきかの解析は結構大変らしいですね。 ↩ -
JSなので直接
u.target = repl;してもダメなんですよね ↩ -
STG論文内に書いてあったStandard Constructorがこの
replになるんですかね。最後のrefsを入れ替えたら確かに他のコンストラクタにも使えそうです。 ↩ -
これがあるから関数の場合には適用できない(出来たら困る)。 ↩
-
無限再帰は結局値の意味としては
undefinedなので何しても良いみたいなところがある ↩ -
左辺の
f xと右辺のf xは違うクロージャを指すから、またaの更新中にaを評価することになるから。 ↩ -
まぁ実行時の話で型なんて出しても非効率的って感じだし意味わかんないですよね～～～～ ↩