めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１９ shift/resetでつくるStateモナド

shiftとresetを使ってStateモナドを実装する。ちなみに今まで実装したモナドの中で随一のややこしさである。

Stateモナドはその名のとおり、計算に局所的な「状態」を持たせることができるモナドである。状態とは「値を参照したり書き換えたりできる何か」を指す。

詳細はHaskell Wikiを参照してほしい：

wiki.haskell.org

reify、get、put、run_state

今回reifyが複雑になっている：

(let [reify (macro [expr]
        (reset
          (let [result expr]
            (fn [state] (cons result state)))))]
  ...)

最終的にreifyが返すのは「初期状態」を受けとり「exprの評価結果と最終状態のタプル」を返す関数となる。例によってreifyはマクロなのでexprはresetの中でresultに束縛される時点までは評価されない。

Stateモナドにはreflectに直接当たる処理はなく、getとputの二つの関数がモナディックな処理を担う。

まず現在のStateの値をとってくる関数であるget：

(let [get (fn []
        (shift [k]
          (fn [state] ((k state) state))))]
  ...)

そしてStateの値を更新した上で評価結果はnilになるput：

(let [put (fn [val]
        (shift [k]
          (fn [state] ((k nil) val))))]
  ...)

これら二つの関数は形がけっこう似ている。どちらもshiftを使って限定継続をとり、reset内の式を(fn [state] ((k X) Y))という形の関数に置き換えてしまう。

Xは「この関数呼び出しの評価結果」で、Yは「この関数呼び出し以降のstateの値」である。

getの場合はXは現在のstate、Yも（状態を変更しないので）現在のstateで(fn [state] ((k state) state))となる。

putの場合はXはnil、Yはputの引数であるvalで、(fn [state] ((k nil) val))となって元々のstateは破棄されて新しい値に更新される。

reifyの中でgetやputが呼ばれるかどうかに関わらず、reifyの結果は(fn [state] ...)という関数であることがわかる。

その関数に対して初期状態値を適用してやるrun_state関数を定義する：

(let [run_state (fn [m state]
        (m state)))]
  ...)

Stateモナドな値と初期状態値をとって関数適用するだけ。

これらの関数があればStateモナドが使える。ここからはいくつか使用例を紹介する。

使用例１

getもputも使わず、reifyに直接値を渡す場合：

(run_state (reify 5) 0)

reifyの部分は、内部でshiftが呼ばれなかったのでそのまま(fn [state] (cons 5 state))という関数になり、run_stateで0をstate引数として渡されて、最終的な結果は(5 . 0)。

使用例２

getを使ってみる：

(run_state (reify (get)) 0)

今回はreifyの中にgetがあるのでshiftが実行され、

(reify (get))

は

(fn [state] ((k state) state))

に置き換えられる。

この時点での限定継続kを関数として表現すると(fn [v] (let [result v] (fn [state] (cons result state))))となるので、(reify (get))はこの：

(fn [state] ((k state) state))

からkを置き換えて：

(fn [state] ((let [result state] (fn [state'] (cons result state'))) state))

簡約して：

(fn [state] ((fn [state'] (cons state state')) state))

さらに簡約して

(fn [state] (cons state state))

となり、(run_state (reify (get)) 0)の結果は(0 . 0)となる。

使用例３

putを使ってみる：

(run_state (reify (put 5)) 0)

これも(reify (put 5))が

(fn [state] ((k nil) 5))

に置き換えられ、限定継続kはやはり(fn [v] (let [result v] (fn [state] (cons result state))))となるので

(fn [state] (((fn [v] (let [result v] (fn [state] (cons result state)))) nil) 5))
(fn [state] ((let [result nil] (fn [state] (cons result state))) 5))
(fn [state] ((fn [state] (cons nil state)) 5))
(fn [state] (cons nil 5))

となり、(run_state (reify (put 5)) 0)の結果は(nil . 5)になる。

使用例４

最後に「shift/resetプログラミング入門」の例題を実装してみる：

(run_state
  (reify
    (let* [(tick (fn [] (put (+ (get) 1))))
           (_ (tick))
           (_ (tick))
           (a (get))
           (_ (tick))]
       (- (get) a)))
  0)

• 「状態をインクリメントする」tick関数をgetとputを使って定義
• tickを複数回使って状態を更新
• 途中の状態の値を変数aに束縛
• 最終的な状態の値とaとの差を求める

という処理になっており、最終的な結果は(1 . 3)（求めた差と最終状態のタプル）となる。

このコードの全容：

(let [(reify (macro [expr]
        (reset
          (let [result expr]
            (fn [state] (cons result state))))))
      (get (fn []
        (shift [k]
          (fn [state] ((k state) state)))))
      (put (fn [val]
        (shift [k]
          (fn [state] ((k nil) val)))))
      (run_state (fn [m state]
        (m state)))]
  (run_state
    (reify
      (let* [(tick (fn [] (put (+ (get) 1))))
             (_ (tick))
             (_ (tick))
             (a (get))
             (_ (tick))]
         (- (get) a)))
    0))

まとめ

shiftとresetを使ってHaskellのStateモナドと同等のことができるようになった。他にも関数適用する形で状態を更新するmodifyなどがあるが、tickと同じようにgetとputの組み合わせで書ける。

do記法のように特殊なモナド構文を使わず、reifyの中では普通のlet、let*や関数呼び出しなどを使って処理が記述できるところは面白い。

次回

別ファイルに記述されたスタンダード・ライブラリを読み込む機能がほしい。その前準備として簡単なモジュール機構を実装する。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１８ shift/resetでつくるListモナド

前回のMaybeモナドに続いて、非決定性を扱うためのListモナドをつくってみたい。

非決定性の説明に関してはSICPを参照してほしい：

sicp.iijlab.net

前回と同じくreifyとreflect（実装内容は違うが）、そして今回新たにreturnを実装していく。

さらにreflectに使うためにmapとmergeも定義する。

まずmap：

(letrec [map [f xs acc]
           (if (nil? xs) acc
             (map f (cdr xs) (cons (f (car xs)) acc)))]
  ...)

関数型では非常に一般的なmap関数。末尾再帰型にするためにアキュミュレータ引数が追加されている。本来ならこの再帰関数をラップした(letfn [map2 [f xs] (map f xs nil)])のような関数を用意したくなるが、今回mapはreflect内でしか使わないのでこのままにしておく。あとアキュミュレータを使っているのに結果をリバースしないので要素が逆順になる、が今回はあまり関係ないので無視。

次にmerge：

(letrec [merge [xss acc]
           (cond
             [(nil? xss) acc]
             [(nil? (car xss)) (merge (cdr xss) acc)]
             [true (merge
                     (cons (cdr (car xss)) (cdr xss))
                     (cons (car (car xss)) acc))])]
  ...)

concatとかflattenなどとも呼ばれる「リストのリスト」をリストに変換する関数。ここでもアキュミュレータがむき出しになっているのと最後にアキュミュレータをリバースしないので要素が逆順になる。

mapやmergeは本来builtinではないにしろ（kontlangを使って定義できるため）、stdlib的なもので用意したくなる。近いうちに追加するかも。

reifyは前回と同じく、resetを隠蔽するマクロなだけ：

(let [reify (macro [expr] (reset expr))]
 ...)

それに対してreflectは前回とかなり違う：

(let [reflect (fn [m]
        (shift [k]
          (merge (map k m nil) nil)))]
  ...)

リストmを受け取り、map k mでその要素すべてを順に限定継続kに渡して、返ってくるリストをmergeしている。

ちなみにMaybeモナドの場合のreflectは：

(let [reflect (fn [m]
        (shift [k]
          (if (nil? m) m (k m))))]
  ...)

だった。reflectに各モナド特有のロジックが表れやすいようだ。

return:

(let [return list]
  ...)

Listモナドの場合、returnは値を単一要素のリストに変換するだけなので横着してlet [return list]としている。

組み合わせて使ってみる：

(reify
  (let [(x (reflect (list 1 2 3)))
        (y (reflect (list 4 5 6)))]
    (return (list x y))))

このプログラムだとなんの条件もつけていないので結果は

((1 6) (1 5) (1 4) (2 6) (2 5) (2 4) (3 6) (3 5) (3 4))

と、(1 2 3)と(4 5 6)の要素の組み合わせすべてとなる。

ここに条件を入れてやることでバックトラックつきの探索を行わせることができる。

例えば「shift/resetプログラミング入門」の例題にもなっている、ピタゴラスの定理に出てくる等式x^2 + y^2 = z^2を満たす１〜５の自然数の組み合わせを探索するプログラム：

(reify
  (let [(x (reflect (list 1 2 3 4 5)))
        (y (reflect (list 1 2 3 4 5)))
        (z (reflect (list 1 2 3 4 5)))]
    (if (= (* z z)
           (+ (* x x)
              (* y y)))
      (return (list x y z))
      nil)))

これは結果が

((3 4 5) (4 3 5))

となる。バックトラックのロジックはreify、reflectとreturnに隠蔽されて、letやifで直線的なコードを書くだけで非決定性プログラミングができるのがうれしいところ。

ちなみに今回の「ピタゴラスの定理」プログラムの全容：

(letrec [(map [f xs acc]
           (if (nil? xs) acc
             (map f (cdr xs) (cons (f (car xs)) acc))))
         (merge [xss acc]
           (cond
             [(nil? xss) acc]
             [(nil? (car xss)) (merge (cdr xss) acc)]
             [true (merge
                     (cons (cdr (car xss)) (cdr xss))
                     (cons (car (car xss)) acc))]))]
  (let [(reify (macro [expr] (reset expr)))
        (reflect (fn [m]
          (shift [k]
            (merge (map k m nil) nil))))
        (return list)]
    (reify
      (let [(x (reflect (list 1 2 3 4 5)))
            (y (reflect (list 1 2 3 4 5)))
            (z (reflect (list 1 2 3 4 5)))]
        (if (= (* z z)
               (+ (* x x)
                  (* y y)))
          (return (list x y z))
          nil)))))

次回はStateモナドを実装してみる。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１７ shift/resetでつくるMaybeモナド

shiftとresetが実装できたのでそれらを使ってモナドっぽい機能を実装してみる。

手始めに以前も紹介したこの資料に出てくるMaybeモナド的なものを試してみたい：

モナドをつくろう from dico_leque

www.slideshare.net

HaskellやOCamlでMaybeモナドといえばJust x（あるいはSome x）かNoneの値を取る型とそれを返す関数を繋げていくような演算がポイントとなる。

しかし今回実装しているのはなんちゃってとは言えLispである。Lisperなら黙ってnilを返そう。（そもそも代数的データ型やパターンマッチを実装していないのでSome xとかできないし・・・）

というわけで演算の結果が何らかの値かnilであるというような処理を繋げていって、途中の計算結果がnilになった場合はショートサーキットして全体の結果がnilになる、といった処理が書けるようにしたい。JustやSomeにあたるケースはそのような特定のタグをつけるのではなく、そのままの値を使う。

そのために

• Haskellのdoにあたるような「ここからはMaybeモナドのコンテキスト内である」と指示するreify
• x <- ...に（おおまかに）対応するような「これはモナディックな値である」と指示するreflect
• 値かnilかを返すfind関数

の三つを定義する。

まずreify：

(let [reify (macro [expr] (reset expr))]
  ...)

マクロで式をresetに包むだけ。reifyを定義しなくてもresetをそのまま使えば同じことができるが、resetはモナドを実装するプリミティブとしてとりあえず隠蔽しておく。

次にreflect：

(let [reflect (fn [m]
        (shift [k] (if (nil? m) m (k m))))]
  ...)

shiftで現在の限定継続をとり、reflectが受け取った値がnilならそのまま全体の値をnilとし、そうでないならそのnilではない値を限定継続に渡して評価を続ける。

そしてfind：

(letrec [find [f xs]
          (cond
            [(nil? xs) nil]
            [(f (car xs)) (car xs)]
            [true (find f (cdr xs))])]
  ...)

要素に対する述語関数とリストを受け取り、もし述語を満たす値があればその一つを返し、もし満たすものがないならnilを返す。find関数はMaybeモナドの一部ではない。Maybeモナドを使うためにnilを返し得る関数が必要だったので定義しただけである。

組み合わせて使ってみる：

(reify
  (let [(a (reflect (find (fn [x] (= x 2)) (list 1 0 3))))
        (b (reflect (find (fn [x] (= x 3)) (list 2 3 1))))]
    (list a b)))

この場合、aがnilになるので全体の値もnilになる。さらにbに束縛される値は評価されずじまいとなる。

上記のコードを全部合わせてインタプリタで走らせられるようにしたプログラムは以下のとおり：

(let [(reify (macro [expr] (reset expr)))
      (reflect (fn [m]
        (shift [k] (if (nil? m) m (k m)))))]
  (letrec [find [f xs]
            (cond
              [(nil? xs) nil]
              [(f (car xs)) (car xs)]
              [true (find f (cdr xs))])]
    (reify
      (let [(a (reflect (find (fn [x] (= x 2)) (list 1 2 3)))) (* ここは変更 *)
            (b (reflect (find (fn [x] (= x 3)) (list 2 3 1))))]
        (list a b)))))

aの式に少しだけ変更を加えていて、そのせいで今回はaもbもnilにならないので、最終的に結果は(2 3)となる。

というわけでMaybeモナドのように、途中結果がnilなら全体の結果もnilになるような処理が簡単に記述できるようになった。

次はsshiftとresetで非決定性プログラミングができるようなListモナドをつくってみる。

OCamlのFunctorをクラスっぽく使ってみた

OCamlのFunctorは一般的なOOPにおけるClassに似ているところと似ていないところがあるぞい。

最近1000行ほどのOCamlコードを一から書く機会があって、その時いろいろとFunctorを使ってみたのだが、気付いたらOOPっぽいことをしていて「面白いなー」「本当にこれでいいのかなー」と思ったのでメモ。

勉強がてら分散システムのプロトタイプをLwtを使って書いていたのだが

let my_addr = Sys.argv(1)
let other_addrs = List.filter ((!=) my_addr) [16000; 16001; 16002]
let other_sockets = ref []
...

let f = ...

let server () = Lwt_io.establish_server_with_client_socket my_addr f

こんなコードを書いて複数のプロセスを立ち上げてソケットを使って通信させていたのだが、テストのために同一プロセスで複数のインスタンスを走らせたくなった。

綺麗に副作用を分離させて純粋関数型で書いていれば、モジュールのデータを閉じ込めるレコード型を定義しておしまいだったのだろうけれど、上記のコードからもわかるとおり他のサーバへのコネクションをlist refで保持していたり、自分のポートに対する接続を処理するf関数でもモジュールのデータに対する更新を行なっていたり、と「インスタンスはただのレコードで、単一のモジュールですべてのインスタンスを扱う」という形に持っていくのは相当大変そうだった。

どうリファクタするのがいいかと少し悩んでいたのだが、Functorを使えば解決では？と思って試してみた。

こんな風に既存のモジュールをFunctorとして括って

module Make(C : sig val n : int end) = struct
  let my_addr = C.n
  let other_addrs = List.filter ((!=) my_addr) [16000; 16001; 16002]
  let other_sockets = ref []
  ...

  let f = ...

  let server () = Lwt_io.establish_server_with_client_socket my_addr f
end

あとは使う時に別のモジュールとして複数インスタンス化する：

module M0 = Mymodule.Make(struct let n = 16000 end)
module M1 = Mymodule.Make(struct let n = 16001 end)
module M2 = Mymodule.Make(struct let n = 16002 end)

...

async (fun () -> M0.server ())
async (fun () -> M1.server ())
Lwt_main.run @@ M2.server ()

これは結構うまくいったので、今後も使っていきたいと思う。

今まではモジュールをなるべく

• 純粋なデータ型を定義
• そのデータ型に対する処理を関数として提供

という形で書いていて、Functorもその流れでポリモーフィズムを追加するために使えるという認識だった。

今回の使い方は

• モジュールに内部データを持たせる
• その内部データに対する処理もモジュール内で定義
• それをFunctor化することで複数インスタンス化できるようにする
• さらにFunctorに渡すモジュールを使ってインスタンスの初期データを設定できるようにする

というもの。

使ってみるとこれってほとんどクラスだよな？と気付いた。

まあクラスと違ってモジュールはそのままだと普通の値としては使えず、例えば任意の個数をインスタンス化してどうこうするというのはfirst class moduleを使う必要があってちょっと構文上ごちゃつくかもしれないが・・・

ちなみに実装の継承がしたい場合は：

module Make(C : sig val n : int end) = struct
  include Mymodule.Make(C)

  ...
end

とすればいい。

モジュールが状態を保持し純粋性が失われていることになるので不必要に使いすぎないほうがいい手法かもしれないが、こういう使い方もあるのかとMLのモジュール機構の柔軟さと多用途性を改めて認識する機会となった。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１６ shift/reset

ついにshift / resetを実装するところまで到達！

resetで区切った限定継続をshiftで取り出して使う、という言語機能だ。

shift/resetプログラミング入門に出てくるような処理が実装できるようになる：

(* (reset
      (+ 3 
         (shift [k] (* 5 (k 2)))
       -1))
   2)

この例だと限定継続kが(fn [x] (+ 3 x -1))となって、(reset ...)部分が(* 5 (+ 3 2 -1))に入れ替えられ、全体の式は(* (* 5 (+ 3 2 -1)) 2)で結果は40となる。

前回との差分：

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

コード解説

まずはExp.tにResetとShift式を追加する：

type t =
...
| Reset of t
| Shift of string * t

次に値を追加。shiftやresetではなく、それらを使った結果として取り出せる「限定継続」を値として表す。なのでValcontモジュールのvalt型にContを追加：

type valt =
...
| Cont of string * (string * valt) list list * contt list

保持する要素としては

• 仮引数を表す文字列（限定継続の場合は必ず引数１になる）
• resetからshiftの間で追加された変数環境
• resetからshiftの間の継続

の三点。特に変数環境については、変数名と値のリストではなく、変数名と値のリストのリストであることに注意。

例えばこんなプログラムがある場合：

(reset
  (let [(x 10) (y 11) (z 12)]
    (+ x (* y z)
       (let [(a 1) (b 2) (c 3)]
         (+ a b c (shift [k] k))))))

(let [(x 10) (y 11) (z 12)]と(let [(a 1) (b 2) (c 3)]、そしてreset自体のクロージャの三つの「変数名と値のリスト」を保持する必要がある。（限定継続は保存されてプログラムのまったく違うところで呼び出される可能性もあるため、関数と同じくクロージャを保持する必要もある）

ValcontのContモジュールの方にはpop関数を追加：

  let pop = function
  | [] -> failwith "Popping empty continuation"
  | cont::cont' -> cont, cont'

「shiftから直近のresetまでの限定継続」というのはcontt list listである継続の先頭のリストで表されている。なのでpopはその先頭のリストとその残りをわけて返す関数。

式を追加したのでMacroモジュールにも場合分けのケースを追加：

let substitute e ss es =
  let env = List.combine ss es in
  let rec f = function
  ...
  | Exp.Reset e -> Exp.Reset (f e)
  | Exp.Shift(s, e) -> Exp.Shift(s, f e)
in
f e

マクロの中にshiftやresetが出てきてもその中の式をマクロ置換できるようにしている。

Utilsモジュールにヘルパ関数を二つ追加：

let break_off n xs =
  let rec f n acc xs =
    if n = 0 then List.rev acc, xs
    else match xs with
    | [] -> failwith "Not enough elements in list to break off"
    | x::xs' -> f (n-1) (x::acc) xs'
  in f n [] xs

let rec count y = function
| [] -> 0
| x::xs -> (if x = y then 1 else 0) + count y xs

あるリストを、先頭n個の要素を取る形で二つのリストに分割する関数break_offと、ある値と一致する要素の数を数えるcount。ここらへんはPervasivesのListモジュールに入っていても良さそうだが・・・ CoreやBatteriesには入っていそう。

Envモジュール：

let pop = function
| [] -> failwith "Popping empty environment"
| svs::env -> svs, env

let rest = function
| [] -> failwith "Taking rest of empty environment"
| _::env' -> env'

今までEnv.popと呼んでいた関数をEnv.restと名付け直した。これは先頭の要素を捨てて、残りのリストを返すもの。Env.popは先頭の要素と残りのリスト両方を返す関数として再定義。

最後にこれらを踏まえてExecuteモジュールに変更を加える。

まずExecute.eval：

let eval env cont = function
...
  | Exp.Reset e ->
    let free = Utils.dedupe @@ Exp.get_free [] [] e in
    let fvals = List.map (fun v -> v, Env.find v env) free in
    Eval(Env.extend_list fvals env, []::cont, e)

reset式の中に入った時点でクロージャを作って変数環境と継続に追加している。shiftで捕捉できるようにするためで、reset内でshiftに遭遇しなければこのクロージャはあってもなくても同じ。

Execute.evalのExp.Shiftケース：

...
  | Exp.Shift(s, e) ->
    let free = Utils.dedupe @@ Exp.get_free [s] [] e in
    let fvals = List.map (fun v -> v, Env.find v env) free in
    let cont', cont'' = Cont.pop cont in
    let n = 1 + Utils.count Cont.Env cont' in
    let env', env'' = Utils.break_off n env in
    let contv = Val.Cont(s, env', cont') in
    let closure = (s, contv)::fvals in
    Eval(Env.extend_list closure env'', []::cont'', e)

限定継続とその継続に含まれるCont.Envに対応するだけの変数環境をVal.Contに保持させ、shiftに含まれる式のクロージャを作成しVal.Contも変数環境に追加して、最終的にshiftに含まれる式を（限定継続の外の継続で）評価する。余談だが、ここのresetとshiftどちらもクロージャを持つという点がなかなかわからなくて実装中はバグの元だった。

次にExecute.applyでVal.Contが呼び出された時の処理：

let apply_cont env cont v = match cont with
...
| (Cont.Call([], vs) :: cont')::cont'' -> (match List.rev (v::vs) with
...
  | Val.Cont(s, svss, cont''') :: vs' ->
    let argcount = List.length vs' in
    if argcount = 1 then
      let final_cont = cont'''::cont'::cont'' in
      let f env svs = Env.extend_list svs env in
      let env' = List.fold_left f env (List.rev svss) in
      ApplyCont(env', final_cont, v)
    else failwith @@ Printf.sprintf "Continuation %s called with incorrect number of args: expected 1 received %d" s argcount

• 実引数が１であることを確認し
• Val.Contに保持されていた限定継続を現在の継続の先頭に追加
• Val.Contに保持されていた（１つ以上の）変数環境を、現在の変数環境の先頭に追加
• 新しい継続に実引数の値を渡す

という流れになっている。実引数が２個以上なら実行時エラー。

最後に、resetがない状態でshiftが呼ばれたらどうなるのか？という問題に対処する。対応するresetがない場合、shiftは現在の限定すべてをとってくることになっている。そうすると問題になるのがそのとってきた限定（されてない）継続のクロージャで、resetで作成していないのでうまく捕捉できない。

一番簡単な解決方法として、プログラム全体をresetで括ってしまうという手段にでた。

let run e = trampoline @@ Eval(Builtins.load Env.empty, Cont.final, Exp.Reset e)
...
let run' e = trampoline' @@ Eval(Builtins.load Env.empty, Cont.final, Exp.Reset e)

パースしたASTをトランポリンで評価していく前にExp.Resetで包んでしまう。これだけでプログラム全体を評価し始めると一番最初に全体の自由変数が捕捉されてクロージャに束縛される。対応するresetのないshiftで作成される限定継続はこのクロージャを保持することになる。

これで限定継続機能のshiftとresetの実装完了！

次回はこれらを使っていろいろと他の言語機能（可変な状態やバックトラックなど）らしきものを作ってみる。

Shibuya.lisp #86 でKontlangについて発表した

「めざそう言語処理系の沼」の内容がようやく発表したところに追いついたので、遅ればせながら・・・

5月28日のShibuya.lispがリモート開催されるということだったので、ひさしぶり（４年ぶりくらい・・・ 遠くに移ってしまったので・・・）に参加。

発表枠が空いていたのでKontlangについて話してみた：

speakerdeck.com

その二日前の火曜日に「shift/resetの前に末尾呼び出し最適化が実装できるか考えてみよう」と思って、３０分ほど考えてみたら先ほどの記事に書いたとおり4行で実装できた。その時けっこう感動してしまって誰かに話したくなったというのが本当のところ。

「そういえばShibuya.lispで話してみてもいいかも、S式言語だし」と思って調べてみたら二日後に開催予定で、スケジュールに恐れ慄きながらも枠をとってもらって発表。

内容は特に後半部分のステップ実行インタプリタのデモと末尾呼び出し最適化の説明がグダッてしまって申し訳なかった・・・　あれちゃんと説明しようと思ったらけっこう順を追って時間をかける必要があったんだな、と発表後に反省。すみませんでした・・・

ただ質疑応答でいろんな話ができたのがすごく楽しかった。OCamlエコシステムの話や、shift/resetによる限定継続とschemeのcall/ccによる継続の違い、記事で紹介した「モナドをつくろう」の発表者の@dico_lequeさんにいろいろ教えてもらったり、と大変得るものが多い時間だった。

次回参加するときはもうちょっと練ってから（あるいは内容を絞ってから）発表したい。

そして皆さんもぜひ参加してみてください。楽しい集まりです。

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

関数型言語の多くはループを再帰で、あるいは再帰を使った高等関数（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を実装する。