Blackhole : 無限再帰停止機構

こんにちはphi16です。この記事は[Haskell Advent Calendar 2016](http://qiita.com/advent-calendar/2016/haskell) の8日目の記事です。

Haskell(GHC)で色々プログラムを書いていると、たまにバグって次のようなエラーを見ることがあるとおもいます。

```
main: <<loop>>
```
これはGHCが式を評価していたら無限ループを発生させてしまうことを検出して投げる例外なのですが、勿論全ての無限ループを検出することはできません。
またHaskellでは次のような「無限ループ」は"合法"です :

```haskell
a = 1 : a
```

というわけで、どんな無限ループなら「合法なのか」「検出できるのか」、また「どういう機構でこれを実現しているのか」という話を、GHCの実際の評価機構を**JavaScriptで[^js]**作りながら適当にまとめてみようとおもいます。半分くらいは自分用メモかもしれないです。
情報源としては[STG論文](https://www.microsoft.com/en-us/research/publication/implementing-lazy-functional-languages-on-stock-hardware-the-spineless-tagless-g-machine/)が主で、それを更に単純化したモデルを考えているため現行のGHCとはかなり異なる処理をしています。ご了承ください。

[^js]: GCがあり、型が無く、値の更新ができるというそこそこ実際の評価環境に近い言語なので (あと個人的な趣味)

これを読むことでHaskellコードからCPUの歓声が聞こえるようになるといいなとおもいます。

# 値の表現
Haskellは遅延評価を行うため、「値」そのものの表現が自明な形では定まりません。遅延評価というのは「実行(評価)することで値が初めて得られるような仕組み」なので、これが表現できれば良さそうです。
今回考える処理系では、値一般のことを「実行コード`code`をメンバに持つオブジェクト」とみなすことにしましょう。全ての基礎となる評価関数は次のように実装されます :

```javascript
function Eval(x,env){
  x.code(x,env);
};
```

このように実行関数`x.code`にはその値自身`x`と環境`env`が渡されてきます。このような処理を想定したオブジェクトのことを「クロージャ」と呼ぶことにします。

その名の通りといえば何ですが、実際これはクロージャを表現してくれます。関数に必要なのは「引数名」「関数本体」と言ったところですが、それに加えて「自由変数名」「自由変数の参照先」も管理することになります。

```javascript
var Closure = function(free,args,code,ref){ // ([String],[String],(X,Env) → (),[Closure])
  return {free:free,args:args,code:code,ref:ref};
};
```

引数などは関数適用のときに`args`に対応する名前で環境`env`に自動で登録されるものとしましょう。とすると例えば`const`関数は次のように実装できそうです :

```javascript
// 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`は次のように表現されます :

```javascript
var Nil = Closure([],[],function(x,env){
  ReturnCon(0)();
},[]);
var Cons = Closure([],["x","y"],function(x,env){
  ReturnCon(1)(env["x"],env["y"]);
},[]);
```

実はデータコンストラクタを評価するのはcase式の中だけだと決まっているので[^stg]、Nil/Consを実行することになるときはこのコードは必ずパターンマッチに使われるはずです。`ReturnCon(n)`で「`n`番目のコンストラクタのマッチングに対応する継続を拾ってくる」ということができ、実際にデータコンストラクタに対応する分岐が実行されることとなります。タグ付けて値を返して分岐を選ぶよりも効率的なわけです。

[^stg]: STG言語の中では。Haskellでも全ての基本的な評価はcase式に置き換えられますけど。

また、`Int`などの生値をこの実行形式ではそのまま扱うことができます。正確には全ての生値を単一のデータコンストラクタで包むことで遅延評価をしつつ生レベルの処理を実行できるというものです。

```javascript
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`で包むことでこの枠組で扱えるようになるわけですが[^io]、とりあえずは整数値を入れることを考えています。

[^io]: と考えるとIO Monadの中ではいくらでも自由なことができる、というのはまぁ自明なんですね。不思議さがちょっと減ったでしょうか。


・・・とまぁ、だいぶ一般的な言語処理系とは異なる値の扱い・処理をしているようです。値に意味が付随するというのがちょっとおもしろい点でしょうか？caseのマッチングの仕組みがなんとも合理的な感じで個人的に好きです。
未だに「動作」はさせていないので分からない点は多いと思います。実際の動作例を見ることで理解できることもあるとおもうのでとりあえず読んでいくと良い気がします。

# 関数適用
遅延評価でなければ「引数を評価し」「それを関数に渡す」のが基本ですが、今回は「引数のクロージャを自由変数に結びつけ」「関数を実行する」という流れになります。この評価機構は複数引数を同時に適用できるようになっているのですが、過剰引数(`const id 1 2`など)を適切に扱うために一度「引数スタック`args`」に退避してから`env`に書き込みをすることになります。

```javascript
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`された関数は自由変数と引数の情報を拾い集め、関数本体を評価しにいきます :

```javascript
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`関数を作ることができます :

```javascript
var Id = Closure([],["x"],function(x,env){
  Eval(app(env["x"],[]),env);
},[]);
```

`env["x"]`を`Eval`するのではなく`app(env["x"],[])`を`Eval`しているのはちゃんと「(サンクとしての)クロージャを実行する」という処理(`Enter`)を走らせるためです[^enter]。

[^enter]: STG言語では「クロージャを直接返す」ことはできず、必ず適用演算が挟まるようになっています。今回は0引数ということです。

ちなみに`const`は引数をもう一つ取ればいいだけですね。

```javascript
var Const = Closure([],["x","y"],function(x,env){
  Eval(app(env["x"],[]),env);
},[]);
```

# リターンスタック
基礎は大体できあがったので、次に生値をリターンする部分をつくります。

```javascript
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);`は実行されるはずです[^cps]。
[^cps]: この挙動を見るとわかるとおもいますが、この評価器は全てを末尾呼び出し・継続渡しスタイルで実行しています。アセンブリにも落としやすそう。

というわけで、早速実行してみましょう。と言っても`id`/`const`くらいしかないですけど。

```javascript
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式
もう評価機構自体は殆ど出来ているので複雑なことはあんまりないです。

```javascript
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`については細かく解説しません。

```javascript
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`はリターンスタックに積むだけですね[^bug]。
[^bug]: ところでSTG論文の方は素直に`case xs of`とか書いていたんですけど構文的にダメじゃないですかね・・・？(`case xs {} of`？)

# いろいろ実行してみよう

case式ができるようになったおかげでだいぶ幅が広まりました。特に`Raw`の中身を取り出すことができるようになりました。ということで :

```javascript
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
```

生値の加算ができるようになりました[^real]！
[^real]: ここではさらっと`env`に生値を突っ込んでいますが、実際にはこれが生値なのかクロージャなのかの区別を示すタグをいれるようです

ついでに調子に乗ってみます。

```javascript
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`なので、それらの呼び出しを確認してみます。適当に手動で見やすくしています[^visu](あと無駄な部分を消したりしてます)。

```javascript
"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
```

[^visu]: と言っても普通に出力したら謎オブジェクトしか吐いてくれないので自分で中身を想像して書いてるんですけど・・・
再帰呼び出しによってリターンが積まれていき、最後に一気に戻っていくのがわかるとおもいます。

# グラフ簡約

今のところ遅延評価としてはうまく動作するのですがグラフ簡約はしてくれないです。
例えば :

```javascript
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回評価されてしまいます[^cons]。これではグラフ簡約になってないので、色々修正する必要があるのです。

[^cons]: `function(x,env){}`の中で`console.log`とかすればわかるとおもいます

実際に必要な仕組みは「クロージャの更新」です。`a`を評価した結果`ReturnRaw 2`が発生するはずですが、これを察知して`a`の指すクロージャを`Raw(2)`そのものにすり替えてしまう、ということを行うのです。更新できるクロージャと更新できないクロージャ(`id`とか)がありますが、これは明示的にソースに記述することにします[^update]。

```javascript
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`を対応させます。

```javascript
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)`の処理内容をコピーし[^copy]、最後に`updatable`のフラグを消せば更新完了なのです。`ReturnCon`でも大体同じです[^stcon]。

[^update]: STG言語ではクロージャの表記に`\u`(updatable)と`\n`(not updatable)を用意しています。どっちにするべきかの解析は結構大変らしいですね。
[^copy]: JSなので直接`u.target = repl;`してもダメなんですよね
[^stcon]: STG論文内に書いてあったStandard Constructorがこの`repl`になるんですかね。最後の`refs`を入れ替えたら確かに他のコンストラクタにも使えそうです。

というわけで次のコードは実際に`a`を1度しか評価しないようになってくれます。やったね！

```javascript
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`の内容は全く変化せず[^func]、結果そのクロージャへの評価はまた必ず更新を生むので、またさらなるクロージャの評価を生むからですね。参照透明性からこれは無限再帰にしかならないことがわかります。
「現在クロージャの評価中であること」は一般のクロージャでは取得できませんが、更新中なら明らかです。(更新開始したら更新終了するはずです。)
さらに言えばクロージャを更新する際には完全に前のクロージャの情報を消してしまうわけで、「クロージャの更新を開始したらそのクロージャに対して何をしても良い」ということが従います。もしもそれで問題となるケースがあれば無限再帰のみだからです[^bot]。そしてこの機構は**"Black hole"**と呼ばれているようです。

[^func]: これがあるから関数の場合には適用できない(出来たら困る)。
[^bot]: 無限再帰は結局値の意味としては`undefined`なので何しても良いみたいなところがある

```javascript
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にする際にクロージャの内部コードにちょっと手を加えます。これで評価が発生したときに「自身の実行コードを例外を投げる関数に変えてから」今まで通りの評価をする、ということが実現できます。

```javascript
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`の定義でズルをしていますけど許してください)

```javascript
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`では検出されることがわかるとおもいます[^ans]。
長かった・・・

[^ans]: 左辺の`f x`と右辺の`f x`は違うクロージャを指すから、また`a`の更新中に`a`を評価することになるから。

# 感想

Haskell AdCなのにHaskellコードはおろか型の話[^type]すら書いてないので書いてて申し訳ない感じでしたが、あまり表に出てこない内部機構についてちょっと細かくかけたかなーと思います。

[^type]: まぁ実行時の話で型なんて出しても非効率的って感じだし意味わかんないですよね～～～～

このSTG機械は勿論関数型言語の実装に参考になる点が多いとおもいますが、普通に読んでいても楽しいしHaskellの内部に詳しくなった気になれるので暇があれば覗いてみると良いとおもいます(そのなかでBlack holeがおもしろかったのでこの記事を書いた)。
尚今回はJSで実装しましたが、できるだけクロージャを使わないようにしているのでC言語などに落とすのもそんなに難しくないはずです(`env`はこのままだと困りそう)(元論文にはこの先のアセンブリレベルの話も載っていますのでそちらを参照)。いつかGHCの吐くバイナリを読めるようになってみたいですね。

おわりです。明日は@todays-mitsuiさんの記事です。

---