本稿は、Schemeなどの言語で明示的にサポートされている 継続(continuation) という概念と、それにまつわる諸概念の学習記録である。
- プログラミング言語の種類によらず、再帰関数の作成時に、継続渡し方式(cps: continuation passing style)を応用できるようになる。
- なんらかの再帰関数を、継続渡しを用いた形にリファクタリングできるようになる。
- 非末尾再帰形の再帰関数を、末尾再帰形の再帰関数にリファクタリングできるようになる。
継続については下記サイトを主軸に勉強した。とても分かりやすい。
継続とは，動作中に凍結したプログラムだ.
すなわち計算処理の状態を含んだ一つの関数的オブジェクトだ.
保存された計算処理は，それが中断された時点から再開する.
継続とは、これから評価すべき環境(処理およびデータ)を、「後で評価可能な環境」として保持したもの。
後で評価可能な環境とは、「自由変数と束縛変数と処理」のことであり、これはすなわちクロージャのこと。
（無名）関数とクロージャの違いは、lambda式内に自由変数があるか否か
[・ _ゝ・]日記を書くはやみずさん- クロージャと記号論理学と高校数学
プログラミングにおいては、自由変数とは関数の中で参照される局所変数や引数以外の変数を意味する。
クロージャとは、関数が保持する情報の他に、自由変数(グローバル変数や、関数の外にある変数の値)も保持できるもののこと。
したがって、クロージャを使えば、クロージャを定義した時点での環境を包み込んで、それを継続として扱える。
下記コードだと、 addn がクロージャである(自由変数nを束縛するため)。
- クロージャの例
def add1(): # クロージャを生成する関数
n = 1
def addn(x): # クロージャ(addnの外側にある変数(自由変数)nを束縛するため)
return x + n
return addn
f = add1()
print(f(5)) # 6
print(f(10)) # 11ちなみに、クロージャの名前の由来は、 開いた関数 を 閉じた関数 にすることから。
cf. ある論理式Aが自由変数を含むとき、 論理式Aは開いている といい、自由変数を1つも含まないとき、 論理式Aは閉じている という。
→ (関数 | 論理式)が(関数の中で参照される局所変数や引数以外の変数 | 自由変数)を1つも含まないとき、(関数 | 論理式)は閉じている。
ある関数内で再帰的に同じ関数を呼び出したとき、呼び出し先から呼び出し元に戻ってきた後に行われる処理が何もなければ末尾再帰である。
- 末尾再帰の例
def sum(x, acc):
"""
1からxまでの総和を求める(末尾再帰)
"""
if x == 0:
return acc
else
sum(x - 1, acc)
sum(10, 0) # 55- 非末尾再帰の例
def sum(x):
"""
1からxまでの総和を求める(add呼び出しの後に+演算があるため末尾再帰ではない)
"""
if x == 0:
return 1
else
return x + sum(x - 1)
sum(10) # 55ある関数 function があるとする。この function の任意の処理の間で分断する。
このとき、分断からの処理を実行するには、分断までの環境(変数の値等)が必要となる。
この情報のことを 継続 という。
global_a = 10
def function():
a, b, c = 1, 2, 3
x = a
x = x + b
# ---------------ここで分断する
x = x + c
return x + global_a
function() # 16 (= 1 + 2 + 3 + 10)次に、関数呼び出しがある場合の継続について考える。
この場合も同様で、 function2 の処理が終わった後に function1 の残りを処理するため、function2 呼び出しまでの環境を覚えておく必要がある。
このとき、 function2 から function1 へ戻るための情報(function1の続きへのアドレス、戻り値、変数の値等)が 継続 である。
def function1(x):
y = 1
z = []
function2(10, z) # ---------------ここで分断する
return x + y + z[0]
def function2(x, z):
z[0] = 2 * x
function1(1) # 31 (= 10 + 1 + (2 * 10))一般的な手続き型言語における継続は、下図のように表せる。
図の通り、関数呼び出しがある度、呼び出し元の続きを処理するために 暗黙的に 継続が作られる。
ここで、 func1 の継続には、 func0 の継続が含まれていることに注意する。
cf. C系の言語においては、コールスタックとして継続を保持している。
コールスタックは言語のユーザに意識させないようになっているため、継続は 暗黙的に 作られるといえる。
- 暗黙的な継続の利用の図
+------------+
| func0 |
| call func1 |
+------------+
* |
* +------------+
* |
* v
* +------------+
* | func1 |
* | call func2 |
* +------------+
* * |
* * +------------+
* * |
* * v
* * +------------+
* * | func2 |
* * | |
* * | return |
* * +------------+
* * :
* * +............+
* * :
* next1 v
* +------------+
* | return |
* +------------+
* :
* +............+
* :
next0 v
+------------+
| return |
+------------+
legend -------------------------------------------------------
+----------------+ call +----------------+
| funcA |------------------>| funcB |
| | | process |
| return |<..................| return |
+----------------+ return +----------------+
*
* duration of retention of continuation of funcA
*
nextA
+----------------+
| |
+----------------+
ここで、関数を呼び出した際、引数だけでなく、 明示的に 継続(評価可能な環境)を呼び出し先の関数に渡すことを考えると、下図のようになる。
なお、継続を渡して最後に評価するという考えにおいては、return (呼び出し元へ戻る)という概念は存在しないことに注意する。
このように、関数呼び出しの際に、継続も一緒に渡すことを 継続渡し(continuation passing) という。
- 継続渡しの図
+----------------------------+
| func0 |
| call func1 |
+----------------------------+
| (continuation of func0)
+-------+
|
v
+----------------------------+
| func1 |
| call func2 |
+----------------------------+
| (continuation of func1, continuation of func0)
+-------+
|
v
+----------------------------+
| func2 |
| call continuation of func1 |
+----------------------------+
| (continuation of func0)
+-------+
|
next v
+----------------------------+
| continuation of func1 |
| call continuation of func0 |
+----------------------------+
|
+-------+
|
next v
+----------------------------+
| continuation of func0 |
+----------------------------+
末尾再帰とは、再帰呼出しのうち、再帰呼出し以降に処理がないタイプのことをいった。
ここで、上図の func1 の継続を考える。
func2 から func1 のnextへ処理が帰ってきたとき、 func1 のnextの処理が、 func0 へ帰ることのみならば、わざわざ func1 のnextに帰らず、 func0 のnextへ直接帰れば良い。
言い換えれば、 func1 の継続を使用しない場合、 func2 には func0 の継続のみを渡せば良い。
同様に、N段階の再帰においても、各々の継続が呼び出し元へ帰ることのみであれば、その継続は不要であるため、最初の関数の継続を渡すのみで良い。
ここで、最初の継続のみ渡せば良い場合、各再帰呼び出しによってスタックを使用する必要がない。
末尾呼び出し最適化 とは、コンパイラが末尾呼び出しを見つけたら、スタックを使用しないように内部の処理を最適化し、再帰呼び出しによってスタックオーバーフローを起こさないようにすることをいう。
pythonによる末尾呼び出し最適化可能なコードを以下に示す。
caution: ただし、pythonにおいてこのコードは末尾呼び出し最適化されない。pythonは末尾呼び出し最適化をサポートしていないため、関数呼び出しのたびに継続を作ってしまう。
def sum(x, continuation):
"""1からxまでの総和を求める"""
def temp(y):
continuation(y + x)
if x > 1:
sum(x - 1, temp)
else:
continuation(x)
sum(10, print) # 55上記のコードを見ると、クロージャ temp は、自由変数 x を内包し、 y が入力されたら出力が定まる。
さらに、上記のコードの処理を関数呼び出し毎に確認していくと、継続がどのように作られていくのかがよく分かる。
ここでは、 sum(3, print) を呼び出した場合を確認してみることにする。
sum(3, print)
最初にsumを呼び出す際、呼び出し元では、そのsumを評価した後に実行したい処理を引数に継続として渡す。
ここでは、「sumの評価結果を表示する」ためにprintをsumに渡している。
また、もちろんsumの入力であるxにも3を渡している。
sum(3, print)def sum(3, print): ...
0.で、xは3に束縛され、また、continuationはprintに束縛されている。
これにより、tempは、「入力に3を足して表示する」関数として定義される。
さらに、ifのtrue節に入るため、次のsum(3 - 1, temp)<=>sum(2, temp)を呼び出す。
def sum(x, continuation):
# def sum(3, print):
"""1からxまでの総和を求める"""
def temp(y):
# def temp1(y): 「入力+3を表示する関数」
continuation(y + x)
# temp1(y) => print(y + 3)
if x > 1:
# if 3 > 1:
sum(x - 1, temp)
# sum(3 - 1, temp1) # 評価される
else:
continuation(x)
# print(3) # 評価されないdef sum(2, temp1): ...
基本的に1.と同様。tempの定義では、内部で最後にcontinuationを評価するようにしてある。
これで、関数実行後に継続を評価することになる。
def sum(x, continuation):
# def sum(2, temp):
"""1からxまでの総和を求める"""
def temp(y):
# def temp2(y): 「「入力+3を表示する関数」に入力+2を渡して評価する関数」
continuation(y + x)
# temp2(y) => temp1(y + 2)
# => print((y + 2) + 3)
if x > 1:
# if 2 > 1:
sum(x - 1, temp)
# sum(2 - 1, temp2) # 評価される
else:
continuation(x)
# continuation(2) => temp1(2)
# => print(2 + 3) # 評価されないdef sum(1,temp2): ...
最後の再帰呼出し。上記までに作成した継続を評価する。これにより、再帰呼び出し内の処理が終わった後に、残っていた処理を全て処理してしまう。
def sum(x, continuation):
# def sum(1, temp):
"""1からxまでの総和を求める"""
def temp(y):
# def temp3(y): 「「「入力+3を表示する関数」に入力+2を渡して評価する関数」に入力+1を渡して評価する関数」
continuation(y + x)
# temp3(y) => temp2(y + 1)
# => temp1((y + 1) + 2)
# => print(((y + 1) + 2) + 3)
if x > 1:
# if 1 > 1:
sum(x - 1, temp)
# sum(1 - 1, temp3) # 評価されない
else:
continuation(x)
# continuation(1) => temp2(1)
# => temp1(1 + 2)
# => print((1 + 2) + 3) # 評価されるcontinuation(x)
継続を処理する。この例を見て分かるように、継続渡しによる末尾再帰は、結局は再帰関数内でのクロージャの作成とその実行によって実現される。
print((1 + 2) + 3) # 6継続渡しによる末尾最適化済みのプログラムは下図のように表せる。
+----------------------------+
| func0 |
| call func1 |
+----------------------------+
| (continuation of func0)
+-------+
|
v
+----------------------------+
| func1 |
| call func2 |
+----------------------------+
| (continuation of func0)
+-------+
|
v
+----------------------------+
| func2 |
| call continuation of func1 |
+----------------------------+
|
+---------------+
|
next v
+----------------------------+
| continuation of func0 |
+----------------------------+
ちなみに、上図を見て分かる通り、末尾呼び出し最適化済みの処理は、再帰構造になっておらず、継続を渡していくことによる、ただの処理の連鎖になる。
したがって、末尾再帰最適化よりも、末尾呼び出し最適化の方が本質をついた呼び方だと言える。
末尾呼び出し最適化がされていない関数を、末尾呼び出し最適化された関数にリファクタリングする手順を以下に示す。
例として、リスト内の全要素を足し合わせる add-elements 関数をcpsにリファクタリングする。
add-elements関数仕様- 入力: 加算可能な数値が入ったリスト 例:
(1 2 3 4) - 出力: リスト内の全要素の総和 例:
10 - その他: デバッグのため
breakを設定する。
- 入力: 加算可能な数値が入ったリスト 例:
先に、上記仕様の関数をコードに落とし込んだ結果を示す。
- 関連データ・関数
;; デバッグ処理を有効化
(declaim (optimize (debug 3)))
;; ヘルパー関数
(defun two-or-more-p (lst)
"リスト内に2個以上要素が入っているか?"
(if (cdr lst)
t
nil))
;; 少ないリスト数
(progn (defparameter *small-list* (make-list 5 :initial-element 1))
nil)
;; 多いリスト数(継続渡し方式でないとスタックオーバーフローするくらい大きなサイズとする)
(progn (defparameter *large-list* (make-list 5000000 :initial-element 1))
nil)- 末尾呼び出し最適化されていない関数
(defun add-elements (lst)
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (two-or-more-p lst)
(+ (car lst)
(add-elements (cdr lst)))
(car lst)))
(prin1 (add-elements *small-list*)) ; 呼び出し数が少なければcpsでなくてもスタックオーバーフローしない
(prin1 (add-elements *large-list*)) ; 呼び出し数が多いとスタックオーバーフローする- 継続渡し形式(末尾呼び出し形式)にした関数
(defun add-elements/cps (lst cont)
"末尾呼び出し形式&継続渡し形式"
(break)
(if (two-or-more-p lst)
(add-elements/cps (cdr lst)
#'(lambda (m)
(funcall cont (+ (car lst) m))))
(funcall cont (car lst))))
(prin1 (add-elements/cps *small-list* #'values))
(prin1 (add-elements/cps *large-list* #'values)) ; 呼び出し数が多くてもcpsであるからオーバーフローしないadd-elements の仕様は、下記のとおりに解釈できる。
- 全要素の総和とは、「ある要素」を、「以降の要素の総和」と足し合わせたものである
- 要素1つのみの総和とは、その要素自身である
見て分かるとおり、この解釈は、数学的帰納法としての解釈にほぼ等しい。
sum(list) := car(list) + sum(cdr(list))sum(element) := element
これを素直にコードに落とし込むと、下記の通りになる。
(defun add-elements (lst)
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (two-or-more-p lst)
(+ (car lst)
(add-elements (cdr lst)))
(car lst)))このコードは、再帰呼び出しした後、その結果を (car lst) と足し合わせる処理がある。
したがって、再帰呼び出しした際、その呼び出し元の継続が暗黙的に作成されてしまう。
ここで、継続が暗黙的に作成されないように修正する方法は下記の2種類ある。
- 再帰呼び出しの後に何も処理がないように、関数のアルゴリズム自体を書き換える。
- 再帰呼び出しの後にすべき処理をクロージャに包み込んで、再帰呼び出し先に一緒に渡してしまい、暗黙的な継続の作成を阻止する。
上の例のように簡単な関数のアルゴリズムであれば、関数のアルゴリズムを書き換えたほうが簡単である。
実際に、アルゴリズムを書き換えたものは下記のようにも修正できる。
このとき、引数に渡した値は accumulator といい、計算の途中結果を意味する。
accumulatorを用いた末尾呼び出し
(defun add-elements (lst &optional (acc 0))
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (two-or-more-p lst)
(add-elements (cdr lst) (+ (car lst) acc))
(+ (car lst) acc)))簡単なアルゴリズムの場合、上記のように書き換えるのは簡単である。
しかし、複雑なアルゴリズムの場合 継続渡し方式ならば、ほぼ機械的に末尾呼び出しに変形できる。
したがって、継続渡し方式の方がより汎用性があるといえる。
以下では、継続渡し方式による末尾呼び出し最適化を行うことにする
上記の関数を継続渡し方式に修正する手順を以下に示す。
仮引数に、継続渡しのための仮引数を追加する。
継続を意味する変数を cont (continuationの略)とする。
(defun add-elements (lst cont) ; 1.
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (two-or-more-p lst)
(+ (car lst)
(add-elements (cdr lst)))
(car lst)))この関数における「継続」は (+ (car lst) (add-elements (cdr lst))) である。つまり、「add-elementsの評価結果を(car lst)と足す」である。
これをクロージャに包み込むと、 #'(lambda (<add-elementsの戻り値>) (+ (car lst) <add-elementsの戻り値>)) となる。
実際のコードとしては、例えば add-elementsの戻り値 を m とおいて #'(lambda (m) (+ (car lst) m)) とすれば良い。
:NOTE: ここで、 lst は自由変数であるため、 lst は、ひいては (car lst) は、クロージャの定義時に評価された値に束縛されることに注意する。
つまり、lst は、クロージャを定義した時点のリスト自体を表すことになる。
(defun add-elements (lst cont) ; 1.
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (two-or-more-p lst)
(+ (car lst) ;; 2-1. (add-elements)呼び出し後の本関数の処理(=継続)は、「add-elementsの評価結果を(car lst)と足す」である
(add-elements (cdr lst))) ;; => 継続をクロージャとすると #'(lambda (add-elementsの戻り値) (+ (car lst) add-elementsの戻り値))
(car lst)))2-1. で抽出した継続を、(add-elements) の引数に渡す。
こうすることで、 (add-elements) の評価の末尾で、渡した継続が評価されることになる。
(defun add-elements (lst cont) ; 1.
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (two-or-more-p lst)
(add-elements (cdr lst) #'(lambda (m) (funcall cont (+ (car lst) m)))) ; 2-2.
(car lst)))再帰呼び出しの最後で、もともと戻り値を返していた箇所を、その戻り値を入力にして継続を評価するように変更する。
これによって、今までクロージャに内包し続けてきた継続を全て評価しきることになる。
(defun add-elements (lst cont) ; 1.
"末尾呼び出し形式&継続渡し形式"
(break)
(if (two-or-more-p lst)
(add-elements (cdr lst) #'(lambda (m) (funcall cont (+ (car lst) m)))) ; 2-2.
(funcall cont (car lst)))) ; 3.これで、非再帰呼び出しの形式から、継続渡し方式による末尾呼び出し形式にリファクタリングできた。
例として、木の全ての葉の個数を足し合わせる count-leaf 関数をcpsにリファクタリングする。
count-leaf関数仕様- 入力: コンスセルをノードとして構成された木 例:
((a . b) . ((c . d) . e)) - 出力: 木の全ての葉の個数の総数 例:
5 - その他: デバッグのため
breakを設定する。
- 入力: コンスセルをノードとして構成された木 例:
+-------+
| | |
+-------+
| |
+-----------------+ +-----------------+
| |
+-------+ +-------+
| | | | | |
+-------+ +-------+
| | | |
+-------+ +-------+ +-------+ +-------+
| | | |
'a 'b +-------+ 'e
| | |
+-------+
| |
+---+ +---+
| |
'c 'd
先に、上記仕様の関数をコードに落とし込んだ結果を示す。
- 関連データ・関数
;; デバッグ処理を有効化
(declaim (optimize (debug 3)))
;; ブランチが少ないツリー
(progn (defparameter *small-tree* (make-list 5 :initial-element 1))
nil)
;; ブランチが多いツリー(継続渡し方式でないとスタックオーバーフローするくらい大きなサイズとする)
(progn (defparameter *large-tree* (make-list 5000000 :initial-element 1))
nil)- 末尾呼び出し最適化されていない関数
(defun count-leaf (tree)
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (consp tree)
(+ (count-leaf (car tree))
(count-leaf (cdr tree)))
1))
(prin1 (count-leaf *small-tree*)) ; 呼び出し数が少なければcpsでなくてもスタックオーバーフローしない
(prin1 (count-leaf *large-tree*)) ; 呼び出し数が多いとスタックオーバーフローする- 継続渡し形式(末尾呼び出し形式)にした関数
(define count-leaf/cps (tree cont)
(if (consp tree)
(count-leaf/cps (car tree)
#'(lambda (n)
(count-leaf/cps (cdr tree)
#'(lambda (m)
(funcall cont (+ n m))))))
(funcall cont 1)))
(prin1 (count-leaf/cps *small-tree* #'values)) ; 呼び出し数が少なければスタックオーバーフローしない
(prin1 (count-leaf/cps *large-tree* #'values)) ; 呼び出し数が多くてもスタックオーバーフローしないcount-leaf の仕様は、下記のとおりに解釈できる。
- あるノードにおける葉の数は、ノードのcar側の枝の下にある葉の数と、ノードのcdr側の枝の下にある葉の数の和である
- ある葉における葉の数は、1である
この問題を解く計算式を考えると、下記のとおりになる。
count-leaf(node) := count-leaf(car(node)) + count-leaf(cdr(node))dount-leaf(leaf) := 1
これを素直にコードに落とし込むと、下記の通りになる。
(defun count-leaf (tree)
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (consp tree)
(+ (leaf-count (car tree))
(leaf-count (cdr tree)))
1))このコードも、再帰呼び出しを2回実行した後、その結果を足し合わせている。
したがって、再帰呼び出しした際、その呼び出し元の継続が暗黙的に作成されてしまう。
ここでも accumulator によって末尾呼び出しに修正できるが、やや面倒である。
例えば、以下のようにすれば、末尾呼び出しにできる。
accumulatorを途中で見つけた葉の数を覚えておくために使用する。- 親ノードに戻れるようにするため、ツリー全体の情報と、現在位置(インスタンスへの参照)を引数に覚える。
- ツリーのルートから深さ優先探索を行い、途中で葉を見つけたら
accumulatorをインクリメントする。
ただし、この方法は探索の各時点における情報を管理する必要があり、再帰呼出しの利点を活かせていない。
やはりこの場合、継続渡しを用いた末尾呼び出しへの修正を考えたほうが良い。
以下では、継続渡し方式による末尾呼び出し最適化を行うことにする
上記の関数を継続渡し方式に修正する手順を以下に示す。
仮引数に、継続渡しのための仮引数を追加する。
継続を意味する変数を cont (continuationの略)とする。
(defun count-leaf (tree cont) ; 1.
"非末尾呼び出し形式&非継続渡し形式"
(break)
(if (consp tree)
(+ (leaf-count (car tree))
(leaf-count (cdr tree)))
1))この関数における「継続」は、やや複雑になる。というのも、再帰呼出しが2回あるため、再帰呼び出し後の継続の中に、さらに再帰呼び出しが内包される形になる。
再帰関数が作成する継続は2段階に分けられる。
(count-leaf (car tree))再帰呼び出し自体(count-leaf (cdr tree))継続1(+ 0: 1:)継続2
; 再帰呼び出し処理があるパスの、
; 再帰呼び出し自体&それ以降の処理
(+ (count-leaf (car tree))
(count-leaf (cdr tree))); 再帰呼び出しと、それ以降の処理をステップ毎に列挙する
; 0: は再帰呼出し自体
; 0:
(count-leaf (car tree))
; 1:
(count-leaf (cdr tree))
; 2:
(+ 0:の戻り値 1:の戻り値)再帰呼び出しのcont部分に継続を渡す。
(make-cont x:) は、処理 x: 以降の処理を内包するクロージャを作成する仮想的な関数である。
この仮想的な関数を導入することで、継続渡し方式への変換が後々楽になる。
; 0:
(count-leaf/cps (car tree) (make-cont 1:))
; 1:
(count-leaf/cps (cdr tree) (make-cont 2:))
; 2:
(+ 0:の戻り値 1:の戻り値)再帰呼び出し後の処理の最後に、継続の呼び出しを追加する。
こうすることで、再帰呼出し後に、蓄積した継続を全て処理するようになる。
; 0:
(count-leaf/cps (car tree) (make-cont 1:))
; 1:
(count-leaf/cps (cdr tree) (make-cont 2:))
; 2:
(funcall cont (+ 0:の戻り値 1:の戻り値))抽出した複数の継続のうち、最後の継続、つまり2:をクロージャに閉包する。
ここで作成したクロージャの引数は、1:の戻り値を受け取る。
ここでは、1:の戻り値を m とする。
; 0:
(count-leaf/cps (car tree) (make-cont 1:))
; 1:
(count-leaf/cps (cdr tree) (make-cont 2:)) ; (count-leaf/cps (cdr tree))の戻り値をmとする
; 2:をcontとして閉包する
#'(lambda (m) ; m = 1:の戻り値
(funcall cont (+ 0:の戻り値 m)))再帰呼び出し後の最後の処理から前の処理に遡りつつクロージャに閉包していく。
ここで作成したクロージャの引数は、0:の戻り値を受け取る。
ここでは、0:の戻り値を n とする。
; 0:
(count-leaf/cps (car tree) (make-cont 1:)) ; (count-leaf/cps (car tree))の戻り値をnとする
; 1:
; contとして閉包する
#'(lambda (n) ; n = 0:の戻り値
(count-leaf/cps (cdr tree) n))
; 2:
#'(lambda (m) ; m = 1:の戻り値
(funcall cont (+ n m)))上記で別々に作成したクロージャをまとめていく。
まず、1:の中に2:を入れる。
; 0:
(count-leaf/cps (car tree) (make-cont 1:))
; 1:
#'(lambda (n) ; n = 0:の戻り値
(count-leaf/cps (cdr tree)
#'(lambda (m) ; m = 1:の戻り値
(funcall cont (+ n m)))))次に、0:の中に1:を入れる。
これで全てのクロージャを一つにまとめられた。
これがcpsの再帰呼び出しになる。
; 0: = count-leaf/cpsの継続
(count-leaf/cps (car tree)
#'(lambda (n) ; n = 0:の戻り値
(count-leaf/cps (cdr tree)
#'(lambda (m) ; m = 1:の戻り値
(funcall cont (+ n m))))))関数呼び出し処理にcpsの再帰呼び出しを入れる。
(define count-leaf/cps (tree cont)
(if (consp tree)
(count-leaf/cps (car tree)
#'(lambda (n) ; n = 0:の戻り値
(count-leaf/cps (cdr tree)
#'(lambda (m) ; m = 1:の戻り値
(funcall cont (+ n m))))))
(funcall cont 1)))これで、再帰呼出し処理を機械的にcpsに変換できた。
上記で実施した手順をまとめると、非末尾再帰を継続渡し形式によって末尾再帰に変換するルールが分かる。
このルールを以下に示す。
- 関数の仮引数に継続用の変数を追加する
- 関数の戻り値を返す部分を継続の呼び出し処理に修正する
- 再帰呼出し処理とその後の処理の部分を抽出する
- 再帰呼び出しの継続部分に継続を渡す
- 再帰呼び出し後の処理に継続の呼び出しを追加する
- 継続の最後の処理をクロージャに閉包する
- 他の処理も6.と同様にクロージャに閉包する
- クロージャを一つにまとめる
- 最初の再帰呼び出しに継続を代入する
- コード例
(defun foo (n)
(if (predicate)
(bar (foo n) (foo n))
(result)))継続用の変数は continuation の略である cont をよく用いる。
(defun foo (n cont)
(if (predicate)
(bar (foo n) (foo n))
(result)))関数の戻り値を返す部分を、戻り値を入力とした cont の呼び出し処理に置き換える。
(defun foo (n cont)
(if (predicate)
(bar (foo n) (foo n))
(funcall cont result)))再帰呼出し処理と、その後の処理の部分を抽出する。
(bar (foo n) (foo n))後で分かりやすくするために、各処理を分解しておく。
ここで、ある処理について、それ以前の処理の戻り値を使用している場合は、その戻り値を使用している箇所を明示しておく。
; 0:
(foo n)
; 1:
(foo n)
; 2:
(bar 0:の戻り値 1:の戻り値)再帰関数の呼び出し箇所において、継続渡し用の仮引数に、その処理の次の処理を継続として渡すように明示する。
(make-cont x:) は、処理 x: 以降の処理を内包するクロージャを作成する仮想的な関数。
; 0:
(foo n (make-cont 1:))
; 1:
(foo n (make-cont 2:))
; 2:
(funcall cont (bar 0:の戻り値 1:の戻り値))再帰呼び出しの後の継続を全て評価するため、再帰呼び出し後の処理に継続の呼び出しを追加する。
; 0:
(foo n (make-cont 1:))
; 1:
(foo n (make-cont 2:))
; 2:
(funcall cont (bar 0:の戻り値 1:の戻り値))継続の最後の処理をクロージャに閉包する。
このクロージャの引数には、クロージャに閉包する処理の前の処理の戻り値が渡されることになる。
こうすることで、クロージャが評価された時、その最後に、引数で渡された戻り値を使って継続が評価されることになる。
; 0:
(foo n (make-cont 1:))
; 1:
(foo n (make-cont 2:)) ; 1: (foo n) の戻り値をxとする
; 2:
#'(lambda (x) ; x = 1:の戻り値
(funcall cont (bar 0:の戻り値 x)))上記6.のクロージャへの閉包と同様に、各処理を最後から前に遡りながら、クロージャに閉包していく。
; 0:
(foo n (make-cont 1:)) ; 0: (foo n) の戻り値をyとする
; 1:
#'(lambda (y) ; y = 0:の戻り値
(foo n (make-cont 2:)))
; 2:
#'(lambda (x) ; x = 1:の戻り値
(funcall cont (bar y x)))上記で作成したクロージャを一つにまとめる。
(make-cont ?:) の部分に ?: を代入する。
2:を1:の(make-cont 2:)に代入する。
; 0:
(foo n (make-cont 1:))
; 1:
#'(lambda (y) ; y = 0:の戻り値
(foo n #'(lambda (x) ; x = 1:の戻り値
(funcall cont (bar y x)))))1:を0:の(make-cont 1:)に代入する。
; 0:
(foo n
#'(lambda (y) ; y = 0:の戻り値
(foo n
#'(lambda (x) ; x = 1:の戻り値
(funcall cont (bar y x))))))これで、再帰呼び出し後の継続を作成できた。
最初の再帰呼び出しの継続用の仮引数部分に、上記で作成した継続を代入する。
(defun foo (n cont)
(if (predicate)
(foo n
#'(lambda (y) ; y = 0:の戻り値
(foo n
#'(lambda (x) ; x = 1:の戻り値
(funcall cont (bar y x))))))
(funcall cont result)))これで、非末尾再帰を継続渡し形式によって末尾再帰に変換できた。