実装して理解する遅延評価の仕組み 〜 thunkを絵に描いて理解しよう・JavaScriptでHaskellを実装！？

この記事では, Haskellに用いられる「遅延評価」の仕組みを, 図に描いて説明します. 更に, 遅延評価版のフィボナッチ数の無限列を, JavaScriptで実装します. 遅延評価とはどのように動くのか, 考えて行きましょう.

HaskellのコードとJavaScriptのコードの比較

Haskellでの

x = y
y = 10

と, JavaScriptの

var x = y;
var y = 10;

というコードを考えてください. Haskellのコードは, これだけでは何も起こりません. print xとすると, x = y = 10 となって 10 が表示されます. 一方, JavaScriptのコードは var x = y; を評価した瞬間, ｢ReferenceError: y is not defined｣というエラーが出ます.

更に,

main = let x = 10 in let x = x + 5 in print x

というコードは, x の評価が無限ループに陥って何も表示されません.
JavaScriptの

x = 10;
x = x + 5;
console.log(x);

とは, 全く違った風に動くのです.

他の言語に慣れている人にとっては, Haskellの評価は奇妙に思えると思います. それは, Haskellが遅延評価と呼ばれる評価戦略をとっているからです.

遅延評価と無限リスト, undefined

遅延評価の分かりやすい例として, 無限リストを考えてみます.

main = print [0..]

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,...

このプログラムは, 0 からの数をずーっと表示し続けます.
これは以下のようにも書けます.

main = putStrLn (show [0..])

show [0..]というのは, 「無限リスト」を評価して無限の長さの文字列になります.
では,

main = let x = show [0..] in print (head x)

'['

というのはどうでしょう？
x は無限の長さの文字列です.
これってすごくないですか？
let x = show [0..] とした瞬間に, show [0..] という無限の長さの文字列の何らかの情報が x に束縛されるのですが, この時点で評価はされないのです.
そして, print (head x) とした瞬間に, x の最初が必要になって評価するのです.

take という関数を思い出して下さい.

main = let x = [0..] in print (take 10 x)

[0,1,2,3,4,5,6,7,8,9]

このプログラムも, 遅延評価が役だっています.
let x = [0..] で無限長のリストを x に束縛し, そのリストから最初の10個が必要になって, それ「だけ」評価して, print します.

もう一つ, undefined を思い出しましょう.

main = undefined >> print "hello"

 *** Exception: Prelude.undefined

ヤバイやつですね.
評価したら例外が飛んでプログラムがストップします.

main = let x = undefined in print x

 *** Exception: Prelude.undefined

もちろん, これも.
でも, 次のプログラムは undefined が評価されません！

main = let x = [undefined, undefined, undefined] in print (length x)

3

さらに次も！

main = let x = undefined : x in print (null x)

False

さらに

main = let x = undefined : x in print (length (take 10 x))

10

本当に, 必要になるまで評価されないんですね！！！

let x = [0..] や, let x = show [0..] などは, よく考えたら不思議な式です.
どうやって無限長のデータを x に束縛することができ, 必要なときに評価することができるのでしょうか.
さらに, let x = undefined : x など, undefined は本当の本当に要素が必要になるまでは, 評価されません.
値が必要か, どれくらい必要かどうかって, どうやって判定するのでしょうか.

評価されていない様子を絵に描いてみよう

let x = 3 という式は, 我々の直感的な代入とは異なります.
x は, 評価したら 3 になる, 何かなのです.
この「何か」を, 四角で囲って描いて表してみることにします.
つまり,

じゃなくて,

です.

何らかの関数 f, g がある時,

let x = f g 10

というのは,

ではなくて,

です！
つまり, 括弧を書けそうなところには全て四角で囲うのです.

let x = (((f) (g)) (10))

この絵の表現を使って, Haskell の評価がどのように動いているのか確かめてみましょう.
次のコードを考えます.

main = let x = 1 : x in print (null x)

これを絵に描いてみると

となります.
演算子は良い感じにセクションとして見て下さい.

null の定義はこうでした.

null       :: [a] -> Bool
null []    =  True
null (_:_) =  False

JavaScriptのnullとは違って, 空リストかどうか判定する関数ですね.
つまり, function (list) { return list.length === 0; } のことです (大体).
これを用いると,

   print (null x)
 = print (null (1 : x))
 = print False

となることが分かりますね.
これを絵で確認してみましょう.
「評価する」ことは, 絵の上では四角を外すことになります.
二項演算子は, 演算子から四角を外します.

何ステップも経て箱を外し, ようやく False と表示することができました (まぁ厳密にはちょっと違うますが許してください(๑´◕﹏◕`))
最後から二行目に注目して下さい.
「1」が, 四角で囲われたままです！
つまり, null 関数は最初の要素が何であるかを評価しないのです.
もちろん null 関数は最初以外「も」必要がありません.
だからこそ, このコードはきちんと評価が止まるんです.
結局, データ構成子 (:) だけ, 評価出来ればいいんですね.

ここで書いたような図には, 幾つかのルールに基づいています.

• let x = hoge とした時, hoge 全体が四角で囲われる; x = [ hoge ]. すぐには評価されない.
• 四角は外側から外す. 勝手に内側の四角を外してはいけない.
• f x という関数適用の四角を外した後は, f の方が先に評価される. その後, x は評価されないまま f に適用される; [ [ f ] [ x ] ] -> [ f ] [ x ] -> f [ x ]. [ [ [ f ] [ g ] ] [ x ] ] -> [ [ f ] [ g ] ] [ x ] -> ([ f ] [ g ]) [ x ] -> (f [ g ]) [ x ].
• パターンマッチはデータ構成子で行われる. データ構成子が評価された時点で, パターンマッチで分岐し, 変数には評価されていないデータが束縛される; [ [ T ] [ a ] ] -> [ T ] [ a ] -> T [ a ].

undefined を含むコードが, この絵の上でどう評価されるか考えてみましょう.

main = undefined >> print "hello"

このコードを実行すると, "hello"と表示すること無くundefined の例外が飛ぶんでしたね.
これを図に描くと次のようになります.

undefined の箱を開けると, 例外が飛んでその他のコードを評価すること無く, プログラムは終了します.
図に描くと, >&gt の第一引数を評価した瞬間終了し, print "hello" が評価されないというのがよく分かります.

逆に, undefined の箱を外さなければ, 例外は飛ぶこと無くプログラムはきちんと動作します.

main = let x = undefined : x
           in print (null x)

図に描くと, こうなります.

上の絵を見て分かるように, null x では undefined は評価されないんですね (undefinedを囲っている四角が外れない).
だから例外が飛ばなかったんですね.

四角 = thunk

上の図で四角に書いたものは, thunk と呼ばれるものです.
後で評価する, ブラックボックスのようなものです.
それを評価したら何が出てくるかは, 評価しなければ分かりません.
絵の上では, thunk を評価すると, どんどん箱が取れていくのです.

しかし, 箱はどこまでもとるわけではありません.
もし全ての箱を取らなければいけないならば, null (undefined : x) の引数を全て評価しようとして, 無限ループになってしまうはずです.
null の分岐は, データ構成子 (:) のパターンマッチで行われます.
この動作から推測するに, データ構成子の箱がとれた時に, 取り敢えずはそこで評価が止まるのです.

JavaScriptで書いてみる

以上のことを踏まえて, JavaScriptで遅延評価を実装してみます.
まずは, 基本的なデータです.
thunk は, 値を保持しておいて後で評価するような箱です.

function Thunk (value) {
  this.value = value;
}

使い方は

> x = new Thunk(10);
Thunk
> x.value;
10

ではなくて,

> x = new Thunk(function () { return 10; });
Thunk
> x.value;
function () { return 10; }
> x.value();
10

です.
こうすることで, Haskell の

x = y
y = 20

は,

> x = new Thunk(function () { return y; });
Thunk
> y = new Thunk(function () { return 20; });
Thunk
> x.value();
Thunk
> x.value().value();
20

のように書けます.
value を何度も評価することで, 値を得ることができます.

λの wrapper と, thunk を二つ取って関数適用したものを作る App を書きます.

function Lambda (fn) {
  this.fn = fn;
}

function App (fn, arg) {
  this.fn = fn;
  this.arg = arg;
}

次に, thunk を評価する関数です.
thunk である限りは箱を外し続けます.

function Evaluate (val) {
  while (val instanceof Thunk) {
    val = val.value();
    if (val instanceof App) {
      val = (PeelLambda(Evaluate(val.fn)))(val.arg);
    }
  }
  return val;
}

function PeelLambda (lam) {
  if (!(lam instanceof Lambda)) {
    throw "type error: apply a non-lambda to a value"
  }
  return lam.fn;
}

ここで,

      val = (PeelLambda(Evaluate(val.fn)))(Evaluate(val.arg));

ではないことに注意して下さい.
値は評価せずに, thunk のまま関数に適用するのです！！！

二つの thunk から関数適用の thunk を作るものを準備しておきます.
先ほどの App は, 直接使うと全体を thunk で包まないので, 代わりにこちらの Apply を使うことにします.

function Apply (fn) {
  return function (arg) {
    return new Thunk(function () {
      return new App(fn, arg);
    });
  };
}

さあ, 準備は整いました.
Thunk, Apply, Lambda を実際に使って実装してみましょう.
目指すは, fib = 0 : 1 : zipWith (+) fib (tail fib) をJavaScript で実装することです！
これが実装できたら, 遅延評価の実装もホンマモンでしょう？

JavaScript のあらゆる値は, thunk で包まれます.

> twenty = new Thunk(function () { return 20; });
Thunk
> twenty.value;
function () { return 20; }
> Evaluate(twenty);
20
> x = new Thunk(function () { return y; });
Thunk
> y = new Thunk(function () { return 20; });
Thunk
> Evaluate(x);
20

関数は new Lambda を使って, 次のように書きます.

var add = new Lambda(function (x) {
  return new Lambda(function (y) {
    return new Thunk(function () {
      return Evaluate(x) + Evaluate(y);
    });
  });
});

var sub = new Lambda(function (x) {
  return new Lambda(function (y) {
    return new Thunk(function () {
      return Evaluate(x) - Evaluate(y);
    });
  });
});

これを用いて 1 + 2 を計算してみます.

> one = new Thunk(function () { return 1; });
Thunk
> two = new Thunk(function () { return 2; });
Thunk
> onetwo = new Thunk(function () { return Apply(Apply(add)(one))(two); });
Thunk
> Evaluate(onetwo);
3

はい, 1 + 2 = 3 ということが分かりました.
関数適用するあらゆる所に Apply を使います.
なぜカーリー化がデフォルトなのか, これでお分かりだと思います.
カーリー化してた方が統一的に扱えるでしょう？

リストを実装すると, こんな感じです.

function Cons (car, cdr) {
  this.car = car;
  this.cdr = cdr;
}
function Nil () {
}

// []
var nil = new Thunk(function () {
  return new Nil();
});

// (:)
var cons = new Lambda(function (x) {
  return new Lambda(function (xs) {
    return new Thunk(function () {
      return new Cons(x, xs);
    });
  });
});

JavaScript のデータとして new Nil, new Cons を使うことはできるのですが, これは nil, cons を通して使わなくてはなりません.
何故なら, 適当に new Cons... とか書くと, thunk で包むのを忘れるからです.

Evaluate 関数で, リストを処理した時にどうなるか, 考えてみます.

> zero = new Thunk(function () { return 0; });
Thunk
> // let x = 0 : x
> x = new Thunk(function () { return new Cons(zero, x); });
Thunk

評価します.

> Evaluate(x);
Cons

無限ループになりません！
これは, Cons というデータ構成子で Evaluate が止まるからです.

実装を進めましょう.
map関数, take関数は次のようになります.

// map _ [] = []
// map f (x:xs) = f x : map f xs
var map = new Lambda(function (f) {
  return new Lambda(function (list) {
    return new Thunk(function () {
      var xxs = Evaluate(list);
      if (xxs instanceof Cons) {
        var x = xxs.car;
        var xs = xxs.cdr;
        return Apply(Apply(cons)(Apply(f)(x)))
                                (Apply(Apply(map)(f))(xs));
      } else {
        return nil;
      }
    });
  });
});

// take _ [] = []
// take n _ | n <= 0 = []
// take n (x:xs) = x : take (n - 1) xs
var take = new Lambda(function (n) {
  return new Lambda(function (list) {
    return new Thunk(function () {
      var xxs = Evaluate(list);
      if (xxs instanceof Cons) {
        var nval = Evaluate(n);
        if (nval <= 0) {
          return nil;
        } else {
          var x = xxs.car;
          var xs = xxs.cdr;
          return Apply(Apply(cons)(x))
                                  (Apply(Apply(take)(Apply(Apply(sub)(n))(one)))(xs));
        }
      } else {
        return nil;
      }
    });
  });
});

Apply がいっぱいですね.
関数適用するあらゆる所に, Apply を使わなければいけません.
さらに, 条件分岐する所で Evaluate を使っていることに注意して下さい.

() と, monad 的な関数を用意しておきます.

function Unit () {
}

// ()
var unit = new Thunk(function () {
  return new Unit();
});

// print = \x -> log x; return ()
var print = new Lambda(function (x) {
  return new Thunk(function () {
    console.log(Evaluate(x));
    return Apply(return_)(unit);
  });
});

// return
var return_ = new Lambda(function (x) {
  return new Thunk(function () {
    return x;
  });
});

// (>>)
var then = new Lambda(function (fn1) {
  return new Lambda(function (fn2) {
    return new Thunk(function () {
      Evaluate(fn1);
      Evaluate(fn2);
    });
  });
});

まぁぶっちゃけ, ここのコードはあまり monad 的じゃなくて, 取り敢えず動きそうなコードです.
きちんとしたコードは自分で書いてみて下さい.
あと, ここでの print 関数は Haskell で言う print 関数と動作が異なるので, 注意して下さい.

map 関数を真似して, mapM_ を書いてみます.

// mapM_ _ [] = return ()
// mapM_ f (x:xs) = f x >> mapM_ f xs
var mapM_ = new Lambda(function (f) {
  return new Lambda(function (list) {
    return new Thunk(function () {
      var xxs = Evaluate(list);
      if (xxs instanceof Cons) {
        var x = xxs.car;
        var xs = xxs.cdr;
        return Apply(Apply(then)(Apply(f)(x)))
                                (Apply(Apply(mapM_)(f))(xs));
      } else {
        return Apply(return_)(unit);
      }
    });
  });
});

以上の用意で, Haskell の

inf = 0 : map (+1) inf

は次のようになります.

var zero = new Thunk(function () {
  return 0;
});

var one = new Thunk(function () {
  return 1;
});

// inf = 0 : map (+1) inf
var inf = new Thunk(function () {
  return Apply(Apply(cons)(zero))
                          (Apply(Apply(map)(Apply(add)(one)))(inf));
});

実行すると次のようになります.

> twenty = new Thunk(function () { return 20; });
Thunk
> // mapM_ print (take 20 inf);
> Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twenty))(inf)));
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

うまく動いているように見えます∩(＞◡＜*)∩
ideone での実行結果を置いておきます: http://ideone.com/KXT74d .

そろそろフィボナッチ数を書きたくなって来ましたよね.
ウズウズしていると思います.

fib = 0 : 1 : zipWith (+) fib (tail fib)

これを実装するには, zipWith と tail 関数が必要です.
zipWith は二つのリストを関数で貼りあわせて新しいリストを作る関数です.
tail は, リストの頭以外を返す関数 function tail(list) { return list.slice(1); }(大体こんな感じ; ホントは空リストならエラーが飛ぶ) ですね.

// zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
// zipWith _ _ _ = []
var zipWith = new Lambda(function (f) {
  return new Lambda(function (listx) {
    return new Lambda(function (listy) {
      return new Thunk(function () {
        var xxs = Evaluate(listx);
        if (xxs instanceof Cons) {
          var yys = Evaluate(listy);
          if (yys instanceof Cons) {
            return Apply(Apply(cons)(Apply(Apply(f)(xxs.car))(yys.car)))
                                    (Apply(Apply(Apply(zipWith)(f))(xxs.cdr))(yys.cdr));
          }
        } else {
          return nil;
        }
      });
    });
  });
});

// tail [] = error "tail: empty list"
// tail (_:xs) = xs
var tail = new Lambda(function (list) {
  return new Thunk(function () {
    var xxs = Evaluate(list);
    if (xxs instanceof Cons) {
      return xxs.cdr;
    } else {
      throw "tail: empty list";
    }
  });
});

フィボナッチ数の無限列は, 次のように実装できます.

// fib = 0 : 1 : zipWith (+) fib (tail fib)
var fib = new Thunk(function () {
  return Apply(Apply(cons)(zero))
                          (Apply(Apply(cons)(one))
                                            (Apply(Apply(Apply(zipWith)(add))(fib))(Apply(tail)(fib))));
});

var twenty = new Thunk(function () {
  return 20;
});

Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twenty))(fib)));

実行すると

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181

となります. (ideone: http://ideone.com/6HJhqA )
バンザイです！ JavaScript でフィボナッチ数の無限リストを実装することができました∩(＞◡＜*)∩♡

束の間の喜び, フィボナッチ数が再帰爆発していることに気が付こう

しかしながら, 上の実装には問題があります.
フィボナッチ数の計算が, 再帰爆発を起こしています.
試しに add 関数で足し算が実行される回数をカウントしてみましょう.

i = 0;
var add = new Lambda(function (x) {
  return new Lambda(function (y) {
    return new Thunk(function () {
      i++;
      return Evaluate(x) + Evaluate(y);
    });
  });
});

> i = 0;
0
> Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twenty))(fib)));
0
1
1
...
2584
4181
> i;
17690

やべぇ...
フィボナッチ数20個ですので, 大体足し算は20回すればいいはずです.
適当に

> i = 0;
0
> twentyfive = new Thunk(function () { return 25; });
Thunk
> Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twentyfive))(fib)));
0
1
...
6765
10946
17711
28657
46368
> i;
196392

もーーんーーのーーすーーごーーくっ時間がかかります...

何が悪いんでしょうか.

先ほどの fib から最初の3つを評価するまでの様子を, 図に描いてみました.
mapM_ print fib したと考えて下さい.

最初から三行で, 「0」「1」が表示されます.
その後, 3つ目の「1」の表示のために, fib を定義まで戻ってまた thunk を開くことを2回しています.
そうです, fib を呼ぶたびに, 定義まで戻っているからダメなんです.
この後に, fib の4つ目を計算するために定義まで戻っていては, せっかく3つ目が分かっているのに勿体ないです.

fib の箱を幾つか外したら, そこまでの処理は何度もしなくていいのではないでしょうか.
すぐ前の結果を呼ぶようにして, 3つまでの値を評価したのが次の図です.

こちらの方がすぐに3つの要素が取り出せますね.
それだけでなく, 「(+) 0 1」が実行され, fib !! 2 が数字に決定していますので, これ以降のステップで fib を呼ぶ時は「0 : 1 : 1 : zipWith ...」となります.
3つ目を計算するための足し算(+)が不要になるのです.

問題が分かった所で, 実装を変更します.
評価したところまでキャッシュするために, Evaluate 関数だけ変更します.

function Evaluate (val) {
  while (val instanceof Thunk) {
    var v = val;
    if (v.evaluated) {
      val = val.value;
    } else {
      val = val.value();
    }
    if (val instanceof App) {
      val = (PeelLambda(Evaluate(val.fn)))(val.arg);
    }
    v.evaluated = true;
    v.value = val;
  }
  return val;
}

実行します.

> i = 0;
0
> Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twenty))(fib)));
0
1
1
...
4181
> i;
18

ｷﾀ━━━━✧*。ヾ(๑＞◡＜๑)ﾉﾞ✧*。━━━━!!

> i = 0;
0
> hundred = new Thunk(function () { return 100; });
Thunk
> Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(hundred))(fib)));
0
1
1
2
3
5
8

.....

31940434634990100000
51680708854858330000
83621143489848430000
135301852344706760000
218922995834555200000
> i;
98

さっきは滅茶苦茶時間がかかってたのに, 今度は100個も余裕で求められるようになりました！(ideone: http://ideone.com/ILSuJW )
足し算の回数も, 合ってます！ (fib から100個求めるのに, 最初の二つは足し算をしないでも分かっているので, 100 - 2 = 98 なのですが, 「80」と出た人は, 理由を考えてみて下さい.)
たった Evaluate だけの変更で, うまく動くようになるのは, とっても嬉しいなって.
下の方の桁がうまく求められてないのは, JavaScriptの数値の扱いのせいなので, 仕方ないですね.

Evaluate 関数が, 何処まで処理するかは, とても重要です.
何度も言っていますが, データ構成子が現れたら, そこでストップします.
もう一つ, 今まで言ってなかったのが, λです.
ほら, while (val instanceof Thunk) {... というコードですので, new Lambda に対しては処理しません.
これはとても重要な観察で, WHNF というのですが, この記事が更に長くなりそうなので名前を出すだけにとどめます.

遅延評価はどう動いているか, お分かりいただけたかと思います.
キーワードは, thunk です.
図をいっぱい描いてどういうふうに thunk の箱が外れていくか, 考えてみて下さい.

JavaScript == Haskell

もう一回, fib のコードを見てみます.

var fib = new Thunk(function () {
  return Apply(Apply(cons)(zero))
                          (Apply(Apply(cons)(one))
                                            (Apply(Apply(Apply(zipWith)(add))(fib))(Apply(tail)(fib))));
});

Haskellのコードはこうでした.

fib = 0 : 1 : zipWith (+) fib (tail fib)

つまり,

fib = ((:) (0)) (((:) (1)) (((zipWith (+)) (fib)) (tail (fib))))

であり, 更に関数適用に全て($)を用いると

fib = ($) (($) (:) 0)
           (($) (($) (:) 1)
                 (($) (($) (($) zipWith (+)) fib) (($) tail fib)))

となります.
あれ... これってJavaScript のコードと($)の位置とApplyの位置が, そのままじゃないですか！

と言うことは...

$ = Apply

まさかの...

var fib = new Thunk(function () {
  return ($)(($)(cons)(zero))
                      (($)(($)(cons)(one))
                                    (($)(($)(($)(zipWith)(add))(fib))(($)(tail)(fib))));
});

うおお... これは... Haskell のコードです！！！

add = (+)
cons = (:)
zero = 0
one = 1
fib = ($)(($)(cons)(zero))
                    (($)(($)(cons)(one))
                                  (($)(($)(($)(zipWith)(add))(fib))(($)(tail)(fib))));

うわああああああああ...
JavaScript と Haskell は一緒だったのだ... +。:.ﾟ٩(๑>◡<๑)۶:.｡+ﾟ

まとめ

thunk のイメージを捉えられたでしょうか.
絵を描いて見ることが重要です.
私も, いっぱい箱を描きました.
詳しいことは, Haskell Wiki の Thunk - HaskellWiki, Lazy evaluation - HaskellWiki, Weak head normal form - HaskellWiki, そして Haskell/Laziness - Wikibooks, open books for an open world あたりを読んで勉強して下さい.
そして何よりも, 遅延評価しない言語で遅延評価を実装してみるのが一番理解を深めます.
お好きな言語で, 遅延評価を実装してみて下さい.

裏話

このブログ記事を書いたきっかけは, fay(https://github.com/faylang/fay)でした.
Haskell のコードを JavaScript のコードに変換するプログラムです.
これがどう実装しているのか, 最初は見当も付きませんでした.
私はまず, fib を Haskell で実装, fay で変換し, その出力コードを読みほどいてみたのです.
そして, thunk をどう実装すればいいか, それをどう評価すればいいかが分かったのです.

thunk, WHNF について調べ, 徐々に理解してきた私は, fay の出力コードを参考にしながら JavaScript で書いてみました.
高階関数ばかりでデバッグしにくい状況で, 初めて mapM_ print (take 20 fib) がうまく動いた時は, 心が震えました.
その感動に, 再帰爆発していることに気が付きませんでした.

数日して, フィボナッチ数を100個求めたいと思ったのです.
その時, 初めて再帰爆発していることに気が付きました.
fay で出力したコードでは, すぐにフィボナッチ数100個を評価出来ました.

最初は原因すら分かりませんでした.
コードは thunk ばっかりで, 非常にデバッグしにくいものでした.
キャッシュしていないせいだと分かったのは, fay の出力コードを読み直した時でした.
これは, 再帰爆発に気がついた数日後, そしてこの記事を書いた前日でした.

コード全体

コピペして実行したい人のために全体のコード置いておきますね♡-(╹ヮ＜✿)
以下のコードの実行結果はこちらです: http://ideone.com/5FmJha .
というより, 自分で実装しやがれ下さい♡-(╹ヮ<★)

function Thunk (value) {
  this.value = value;
}

function Lambda (fn) {
  this.fn = fn;
}

function App (fn, arg) {
  this.fn = fn;
  this.arg = arg;
}

function Evaluate (val) {
  while (val instanceof Thunk) {
    var v = val;
    if (v.evaluated) {
      val = val.value;
    } else {
      val = val.value();
    }
    if (val instanceof App) {
      val = (PeelLambda(Evaluate(val.fn)))(val.arg);
    }
    v.evaluated = true;
    v.value = val;
  }
  return val;
}

function PeelLambda (lam) {
  if (!(lam instanceof Lambda)) {
    throw "type error: apply a non-lambda to a value"
  }
  return lam.fn;
}

function Apply (fn) {
  return function (arg) {
    return new Thunk(function () {
      return new App(fn, arg);
    });
  };
}

// add = (+)
var add = new Lambda(function (x) {
  return new Lambda(function (y) {
    return new Thunk(function () {
      return Evaluate(x) + Evaluate(y);
    });
  });
});

// sub = (-)
var sub = new Lambda(function (x) {
  return new Lambda(function (y) {
    return new Thunk(function () {
      return Evaluate(x) - Evaluate(y);
    });
  });
});

function Cons (car, cdr) {
  this.car = car;
  this.cdr = cdr;
}

function Nil () {
}

// []
var nil = new Thunk(function () {
  return new Nil();
});

// (:)
var cons = new Lambda(function (x) {
  return new Lambda(function (xs) {
    return new Thunk(function () {
      return new Cons(x, xs);
    });
  });
});

// head [] = error "head: empty list"
// head (x:_) = x
var head = new Lambda(function (list) {
  return new Thunk(function () {
    var xxs = Evaluate(list);
    if (xxs instanceof Cons) {
      return xxs.car;
    } else {
      throw "head: empty list";
    }
  });
});

// tail [] = error "tail: empty list"
// tail (_:xs) = xs
var tail = new Lambda(function (list) {
  return new Thunk(function () {
    var xxs = Evaluate(list);
    if (xxs instanceof Cons) {
      return xxs.cdr;
    } else {
      throw "tail: empty list";
    }
  });
});

// map _ [] = []
// map f (x:xs) = f x : map f xs
var map = new Lambda(function (f) {
  return new Lambda(function (list) {
    return new Thunk(function () {
      var xxs = Evaluate(list);
      if (xxs instanceof Cons) {
        var x = xxs.car;
        var xs = xxs.cdr;
        return Apply(Apply(cons)(Apply(f)(x)))
                                (Apply(Apply(map)(f))(xs));
      } else {
        return nil;
      }
    });
  });
});

// take _ [] = []
// take n _ | n <= 0 = []
// take n (x:xs) = x : take (n - 1) xs
var take = new Lambda(function (n) {
  return new Lambda(function (list) {
    return new Thunk(function () {
      var xxs = Evaluate(list);
      if (xxs instanceof Cons) {
        var nval = Evaluate(n);
        if (nval <= 0) {
          return nil;
        } else {
          var x = xxs.car;
          var xs = xxs.cdr;
          return Apply(Apply(cons)(x))
                                  (Apply(Apply(take)(Apply(Apply(sub)(n))(one)))(xs));
        }
      } else {
        return nil;
      }
    });
  });
});

function Unit () {
}

// unit = ()
var unit = new Thunk(function () {
  return new Unit();
});

// print = \x -> log x; return ()
//   (not so monadic...)
var print = new Lambda(function (x) {
  return new Thunk(function () {
    console.log(Evaluate(x));
    return Apply(return_)(unit);
  });
});

// return
var return_ = new Lambda(function (x) {
  return new Thunk(function () {
    return x;
  });
});

// (>>)
var then = new Lambda(function (fn1) {
  return new Lambda(function (fn2) {
    return new Thunk(function () {
      Evaluate(fn1);
      Evaluate(fn2);
    });
  });
});

// mapM_ _ [] = return ()
// mapM_ f (x:xs) = f x >> mapM_ f xs
var mapM_ = new Lambda(function (f) {
  return new Lambda(function (list) {
    return new Thunk(function () {
      var xxs = Evaluate(list);
      if (xxs instanceof Cons) {
        var x = xxs.car;
        var xs = xxs.cdr;
        return Apply(Apply(then)(Apply(f)(x)))
                                (Apply(Apply(mapM_)(f))(xs));
      } else {
        return Apply(return_)(unit);
      }
    });
  });
});

// zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
// zipWith _ _ _ = []
var zipWith = new Lambda(function (f) {
  return new Lambda(function (listx) {
    return new Lambda(function (listy) {
      return new Thunk(function () {
        var xxs = Evaluate(listx);
        if (xxs instanceof Cons) {
          var yys = Evaluate(listy);
          if (yys instanceof Cons) {
            return Apply(Apply(cons)(Apply(Apply(f)(xxs.car))(yys.car)))
                                    (Apply(Apply(Apply(zipWith)(f))(xxs.cdr))(yys.cdr));
          }
        } else {
          return nil;
        }
      });
    });
  });
});

var zero = new Thunk(function () {
  return 0;
});

var one = new Thunk(function () {
  return 1;
});

var twenty = new Thunk(function () {
  return 20;
});

var hundred = new Thunk(function () {
  return 100;
});

// inf = 0 : map (+1) inf
var inf = new Thunk(function () {
  return Apply(Apply(cons)(zero))
                          (Apply(Apply(map)(Apply(add)(one)))(inf));
});

// fib = 0 : 1 : zipWith (+) fib (tail fib)
var fib = new Thunk(function () {
  return Apply(Apply(cons)(zero))
                          (Apply(Apply(cons)(one))
                                            (Apply(Apply(Apply(zipWith)(add))(fib))(Apply(tail)(fib))));
});

// main = mapM_ print (take 100 fib)
var main = new Thunk(function () { 
  return Apply(Apply(mapM_)(print))(Apply(Apply(take)(hundred))(fib)); 
});

Evaluate(main);