レポートの一部。CPS変換。

CPS(Continuation Passing Style)変換とはすべての関数呼び出しやif文を末尾にしてしまう変換方法。例えば末尾でない関数適用があった場合に、「継続」(その後にすること)を生成し、それごと呼び出す関数に渡す。レジュメの例は次のようなもの。

let f x = g x + 5

let g y = y + y

これらの関数に対してCPS変換を行う。つまり、関数定義の際にはCPS変換前より引数を1つ多くし(この引数はクロージャ: k)、その関数で行う処理の演算結果を引数としたクロージャを返して(処理を移して)終わる。また、末尾でない関数を呼び出す際には、その前に「その後の処理(継続)のクロージャ: k, r」(このクロージャ内の最後の値を、関数の引数として1つ余分にとったクロージャに渡す。)を生成し、呼び出す関数の最後の引数に加えて渡す。

let rec f x k =
let k' z = (* fはもともと1引数関数なのでこのクロージャの引数も1つ *)
let r = z + 5 in k r
in g x k'

let rec g y k =
let r = y + y in k r

呼び出す側も呼び出される側もそれに合わせて変更する必要がある。クロージャで表現し、呼び出す側は関数呼び出し以降に行う処理をクロージャにし、呼び出される関数は通常より1つ余分なクロージャを受け取り、普段の処理が終わった結果をそのクロージャに渡してそれを返り値(末尾再帰)とする。すべての関数定義、関数適用に継続(クロージャ)を加えることで実装できる。

関数からのリターンは継続の呼び出しとなるので、関数呼び出し時のsave/restoreの処理が不必要になり、同時にリターンアドレスという概念がなくなる(関数の処理が終わったら継続を呼び出すから)。レジスタの退避がなくなるのでメモリはレジスタが足りなくなった場合に使われ、スタックが無くなる。

ただ、クロージャが頻繁に生成されるので、ヒープが大量に使われる。エスケープ解析(演習11回)によりスタックに確保していいクロージャを見つけることができる。