Arantium Maestum

プログラミング、囲碁、読書の話題

めざそう言語処理系の沼　〜shift/resetへの旅 〜　その１５ 末尾呼び出し最適化

OCaml めざそう言語処理系の沼 言語処理系

関数型言語の多くはループを再帰で、あるいは再帰を使った高等関数（mapやfold / reduceなど）で表現することが多い。

命令型プログラミングで使われるforやwhileループだと「ループごとに現在の変数環境で何かが変わっている必要がある」、つまり「状態に対して破壊的変更が行われる」ということが必要になるからだ。

再帰を使う場合、「ループごとの変更」が現在の変数環境内での破壊的変更ではなく、別の変数環境を用意してしまうことで表現される。

その変数環境は非常に局所的にその一回の関数呼び出しだけに使われるので、その「変更」がプログラムの他の部分に漏れるリスクが減る（純粋関数型だったらリスクは０だ）。

しかし、再帰一回ごとに新しい変数環境を用意すると、どんどん変数環境が積み上がってしまい非常にメモリ効率が悪いのではないか？

実際C言語やPythonなどで再帰するとどうしてもこの問題にぶつかる。Pythonなどではメモリが足りなくなるのを避けるため、デフォルトでコールスタックが1000までいったらRecursionErrorになる。

関数型言語の多くはこの問題を避けるために言語機能として「末尾呼び出し最適化」を実装している。

余談だがPythonの言語開発者であるGuido van Rossumが「なぜPythonに末尾呼び出し最適化を実装しないのか」というブログ記事を書いていた。全面的に賛成するわけではないが、個人的にはトレードオフの中での選択としては全然アリだと思っている：

neopythonic.blogspot.com

今回はどうすればこの最適化を実装できるかを考えたい。

今回は簡単な再帰的コードを書いて前回作ったステップ実行インタプリタを使って分析してみたい。

調べるコード

整数のリストを足し合わせるaddall関数を定義してみる：

(letrec [addall [acc xs]
  (if (nil? xs)
    acc
    (addall
      (+ (car xs) acc)
      (cdr xs)))]
  (addall 0 (list 1 2 3)))

末尾再帰形にするためにアキュミュレータを使っている。

この再帰関数addallは：

  • 足し合わせたいリストのxsが空リストかどうかを調べ
  • 空リストの場合はそのままaccを結果として返す
  • 空リストで無い場合はaddallを再帰呼び出し
  • 第一引数はxsの先頭の整数とaccを足した結果
  • 第二引数はxsの残り

となっている。

このaddall関数と0というアキュミュレータの初期値を使って(list 1 2 3)を足し合わせていく。

ステップ実行

インタプリタに上記のプログラムを与えてみる：

>>> (letrec [addall [acc xs]
  (if (nil? xs)
    acc
    (addall
      (+ (car xs) acc)
      (cdr xs)))]
  (addall 0 (list 1 2 3)))

Evaluating expression (letfn [(addall [acc xs] (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs))))] (addall 0 (list 1 2 3)))
Cont Head:
Cont Full:
Environment:

Evaluating expression (addall 0 (list 1 2 3))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)}]

全体の式を評価して、まず再帰関数addallを作成して変数環境に入れた上で(addall 0 (list 1 2 3)を評価するステップに移っている。

1回目のaddall呼び出し

（変数環境Environmentがどんどん横に長くなっていくので読みやすいように改行をいれてある）

（中略）

Applying continuation on value (1 2 3)
Cont Head:  CALL [] [0 Fn(addall)]
Cont Full:  CALL ENV
Environment:    
[{addall Fn(addall)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

2回目のaddall呼び出し

（中略）

Applying continuation on value (2 3)
Cont Head:  CALL [] [1 Fn(addall)]
Cont Full:  CALL ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

ほぼ同一の変数環境と、それに対応するENV継続が積み上がっているのがわかる。変数環境の方はaddall関数のクロージャで、ENV継続は「この式の評価が終了したら変数環境を一つ外す」ということを表すものだ。

3回目のaddall呼び出し

（中略）

Applying continuation on value (3)
Cont Head:  CALL [] [3 Fn(addall)]
Cont Full:  CALL ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

4回目のaddall呼び出し

（中略）

Applying continuation on value nil
Cont Head:  CALL [] [6 Fn(addall)]
Cont Full:  CALL ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

3回目、4回目とどんどんスタックが増えていく。さらに変数環境が増えているだけではなく、継続の方もENVが続いて乗せられている。

addall評価終了後

再帰関数のif (nil?)が真になり、式の評価が終了してその値が継続に渡される：

（中略）

Evaluating expression acc
Cont Head:  ENV
Cont Full:  ENV ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)}]

Applying continuation on value 6
Cont Head:
Cont Full:
Environment:

Applying continuation on value 6
Cont Head:
Cont Full:
Environment:

Done
6

同じ値がずっと「変数環境を巻き戻す」ENV継続に渡され続けて、すべての変数環境がスタックから外されて終了している。

これ自体は必ずしも最適化できるポイントではない。

(let [x 1]
  (let [y 2]
    (let [z 3]
      (+ x y z))))

といった式が評価される時にも

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV ENV ENV
Environment:    
[{z 3}] | 
[{y 2}] | 
[{x 1}] |

というような形になっているし、かといってこれら変数環境を(+ x y z)という式を評価する前に取り除くことはできない。

末尾呼び出しのどこに最適化の可能性があるかというと、関数呼び出しの時に追加される変数環境が関数のクロージャであることがポイントである。

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

よく見ると評価される式(if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))に出てくるすべての変数は、一番上の変数環境に含まれている。これは偶然ではなく、関数がレキシカル・スコープであることからの必然だ。とすれば、この式自体の評価に、以前の変数環境はまったく影響しない。

とすれば、関数呼び出しが行われ、関数とすべての引数の評価が終わり、関数に引数を適用する段階に移る瞬間：

Applying continuation on value nil
Cont Head:  CALL [] [6 Fn(addall)]
Cont Full:  CALL ENV ENV ENV ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}] | 
[{addall Fn(addall)}]

この時に、CALLの前にあるENV継続とそれに対応する変数環境は関数適用中にはなんら評価結果に影響せず、評価が終わった後は素通りされる存在だということで、つまりこの時点でもう役割を終えている。（関数呼び出しが行われた瞬間はまだ関数や引数の評価に使われる可能性があるのでまだ役割がある）

Applying continuation on value nil
Cont Head:  CALL [] [6 Fn(addall)]
Cont Full:  CALL ENV ENV ENV ENV

のように、

  • CALL継続に値が渡されようとしている
  • CALL継続にはもう未評価の式が残っていない（CALL [] ...という状態）
  • 継続全体を見るとCALLの後にENVが一つ以上続いている

という状況であれば、直接続いているENVとそれに対応する変数環境をすべて取り外してから関数適用してやればいい。

と、これがつまり末尾呼び出し最適化だ。

末尾呼び出し最適化でのステップ実行

末尾呼び出し最適化が実装されているとこのような結果になる：

>>> (letrec [addall [acc xs]
  (if (nil? xs)
    acc
    (addall
      (+ (car xs) acc)
      (cdr xs)))]
  (addall 0 (list 1 2 3)))

Evaluating expression (letfn [(addall [acc xs] (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs))))] (addall 0 (list 1 2 3)))
Cont Head:
Cont Full:
Environment:

Evaluating expression (addall 0 (list 1 2 3))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)}]
（中略）

Applying continuation on value (1 2 3)
Cont Head:  CALL [] [0 Fn(addall)]
Cont Full:  CALL ENV
Environment:    [{addall Fn(addall)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}
（中略）

Applying continuation on value (2 3)
Cont Head:  CALL [] [1 Fn(addall)]
Cont Full:  CALL ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 0} {xs (1 2 3)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}]

関数呼び出し時に、変数環境が積み上がるのではなく代替されている。{acc 0} {xs (1 2 3)が{acc 1} {xs (2 3)}に変わっているだけ。

（中略）

Applying continuation on value (3)
Cont Head:  CALL [] [3 Fn(addall)]
Cont Full:  CALL ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 1} {xs (2 3)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}]
（中略）

Applying continuation on value nil
Cont Head:  CALL [] [6 Fn(addall)]
Cont Full:  CALL ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 3} {xs (3)}]

Evaluating expression (if (nil? xs) acc (addall (+ (car xs) acc) (cdr xs)))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}]

3回目、4回目もまったく同じく、変数環境は積み上がらず代替される。

（中略）

Evaluating expression acc
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}]

Applying continuation on value 6
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {acc 6} {xs nil}]

Applying continuation on value 6
Cont Head:
Cont Full:
Environment:

Applying continuation on value 6
Cont Head:
Cont Full:
Environment:

Done
6

関数呼び出しの式が評価された後、巻き戻す変数環境も最低限（関数のクロージャのみ）となっている。

実装

というわけで、この最適化を実装してみる。

今回のコード差分：

Comparing v0.14...v0.15 · zehnpaard/kontlang · GitHub

Executeモジュールでtcoヘルパ関数を定義：

let rec tco env = function
| (Cont.Env::cont)::cont' -> tco (Env.pop env) @@ cont::cont'
| cont -> env, cont

継続と変数環境を受け取り、継続の先頭がENVなら継続・変数環境どちらもtailをとって再帰。継続の先頭がENVでなければ停止。

これをExecute.apply_contの関数呼び出しのところで使う：

let apply_cont env cont v = match cont with
...
| (Cont.Call([], vs) :: cont')::cont'' -> (match List.rev (v::vs) with
...
  | Val.Fn(s, ss, fvalsr, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then
      let env', cont''' = tco env @@ cont'::cont'' in (* ここ *)
      let env'' = Env.extend_list (!fvalsr @ (List.combine ss vs')) env' in
      Eval(env'', Cont.add Cont.Env cont''', e)
    else failwith @@ Printf.sprintf "Function %s called with incorrect number of args: expected %d received %d" s paramcount argcount

先ほどの３行とこの(* ここ *)とマークしてある1行を新たに追加し、それに続く2行では変数名を変更する。それだけで末尾呼び出し最適化が実装できてしまった。

ここまで簡単なのは、継続が代数的データ型で表現されていて普通のデータと同じように形を調べたり変えたりできるようになっているからこそである。

末尾型ではない再帰

addall関数を再帰で書く場合、一番簡単なのはこのような書き方だ：

(letrec [addall [xs]
  (if (nil? xs)
    0
    (+ (car xs) (addall (cdr xs))))]
  (addall (list 1 2 3)))

アキュミューレタは使わずに先頭の数字と、残りに対する再帰結果を足し合わせる。

これだと再帰結果に対して「先頭の数字と足し合わせる」という継続が残っているので末尾再帰ではない。

これをステップ評価してみると：

>>> (letrec [addall [xs]
  (if (nil? xs)
    0
    (+ (car xs) (addall (cdr xs))))]
  (addall (list 1 2 3)))

Evaluating expression (letfn [(addall [xs] (if (nil? xs) 0 (+ (car xs) (addall (cdr xs)))))] (addall (list 1 2 3)))
Cont Head:
Cont Full:
Environment:

Evaluating expression (addall (list 1 2 3))
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{addall Fn(addall)}]
（中略）

Applying continuation on value (1 2 3)
Cont Head:  CALL [] [Fn(addall)]
Cont Full:  CALL ENV
Environment:
[{addall Fn(addall)}]

Evaluating expression (if (nil? xs) 0 (+ (car xs) (addall (cdr xs))))
Cont Head:  ENV
Cont Full:  ENV
Environment:
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]
（中略）

Applying continuation on value (2 3)
Cont Head:  CALL [] [Fn(addall)]
Cont Full:  CALL CALL ENV
Environment:
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]

Evaluating expression (if (nil? xs) 0 (+ (car xs) (addall (cdr xs))))
Cont Head:  ENV
Cont Full:  ENV CALL ENV
Environment:
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (2 3)}] |
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]
（中略）

Applying continuation on value (3)
Cont Head:  CALL [] [Fn(addall)]
Cont Full:  CALL CALL ENV CALL ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]

Evaluating expression (if (nil? xs) 0 (+ (car xs) (addall (cdr xs))))
Cont Head:  ENV
Cont Full:  ENV CALL ENV CALL ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]
（中略）

Applying continuation on value nil
Cont Head:  CALL [] [Fn(addall)]
Cont Full:  CALL CALL ENV CALL ENV CALL ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]

Evaluating expression (if (nil? xs) 0 (+ (car xs) (addall (cdr xs))))
Cont Head:  ENV
Cont Full:  ENV CALL ENV CALL ENV CALL ENV
Environment:    
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs nil}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (2 3)}] | 
[{addall Fn(addall)} {nil? Op(nil?)} {+ Op(+)} {car Op(car)} {cdr Op(cdr)} {xs (1 2 3)}]

と、このように末尾呼び出し最適化を実装していても変数環境が積み上がってしまう。理由も明白で、クロージャを表すENV継続の間に関数呼び出しを表すCALL継続が挟まれているからである。

「関数呼び出し時に、呼び出し元で直近の継続が変数環境の巻き返しENV以外だと、末尾再帰の形にならず最適化されない」ことがわかる。末尾再帰じゃないから当たり前ではあるが、継続の形としても確認できた。

次回

次回はついにshiftとresetを実装する。