めざそう言語処理系の沼 〜shift/resetへの旅 〜 その15 末尾呼び出し最適化
関数型言語の多くはループを再帰で、あるいは再帰を使った高等関数(map
やfold
/ reduce
など)で表現することが多い。
命令型プログラミングで使われるfor
やwhile
ループだと「ループごとに現在の変数環境で何かが変わっている必要がある」、つまり「状態に対して破壊的変更が行われる」ということが必要になるからだ。
再帰を使う場合、「ループごとの変更」が現在の変数環境内での破壊的変更ではなく、別の変数環境を用意してしまうことで表現される。
その変数環境は非常に局所的にその一回の関数呼び出しだけに使われるので、その「変更」がプログラムの他の部分に漏れるリスクが減る(純粋関数型だったらリスクは0だ)。
しかし、再帰一回ごとに新しい変数環境を用意すると、どんどん変数環境が積み上がってしまい非常にメモリ効率が悪いのではないか?
実際C言語やPythonなどで再帰するとどうしてもこの問題にぶつかる。Pythonなどではメモリが足りなくなるのを避けるため、デフォルトでコールスタックが1000までいったらRecursionError
になる。
関数型言語の多くはこの問題を避けるために言語機能として「末尾呼び出し最適化」を実装している。
余談だがPythonの言語開発者であるGuido van Rossumが「なぜPythonに末尾呼び出し最適化を実装しないのか」というブログ記事を書いていた。全面的に賛成するわけではないが、個人的にはトレードオフの中での選択としては全然アリだと思っている:
今回はどうすればこの最適化を実装できるかを考えたい。
今回は簡単な再帰的コードを書いて前回作ったステップ実行インタプリタを使って分析してみたい。
調べるコード
整数のリストを足し合わせる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
先ほどの3行とこの(* ここ *)
とマークしてある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
を実装する。