継続渡しスタイル（CPS）チートシート

例によって，少なくとも約1名（自分自身）には役立ちそうだったので，各言語の継続渡しスタイル（Continuation-passing style，CPS）のサンプル記述を記事としてまとめた．

#Python（Python 3）：解説付き
対話モードで，xに10を代入してから，x + 20を評価させてみる．

>>> x = 10
>>> x + 20
30

このプログラム記述をファイルにしてPythonインタプリタに実行させても，何も表示されない．対話モード（REPL）では，式として評価されたものはその結果を表示するのに対し，ファイル実行（スクリプト）では，そのような表示は行わないためである．

C:\Users\hoge>type sample.py
x = 10
x + 20
C:\Users\hoge>python sample.py

C:\Users\hoge>

もし，ファイル実行で評価結果を表示させたい場合は，評価結果を得た後に，たとえばprintを用いて表示させるようにする必要がある．

C:\Users\hoge>type sample.py
x = 10
print(x + 20)

C:\Users\hoge>python sample.py
30

C:\Users\hoge>

ここで，式として記述する場合は，評価結果を処理する関数を必ず指定しなければならない仕組みを考える．次は，x + 20を評価したら，その評価結果を関数fに引数として渡して呼び出す関数cadd20を定義し，fにprintを指定して実行した例である．

C:\Users\hoge>type sample.py
def cadd20(x, f): f(x + 20)
x = 10
cadd20(x, print)

C:\Users\hoge>python sample.py
30

C:\Users\hoge\python>

このように，結果を処理する手続きをあらかじめ指定する仕組みを想定したプログラミング手法を『継続渡しスタイル』（continuation-passing style，CPS）と呼ぶ．このスタイルは，そうとは意識されない形を含め，様々な実装に応用されている．

• コールバック関数（指定する手続き）とハンドラー（呼び出す関数）
• 例外処理のtry（呼び出す手続き）とexcept（指定する手続き）
• CPSに自動変換して明確となった値受け渡しからの中間言語記述生成

なお，関数のCPSへの変換は容易であるが，変換した関数を使用するには工夫が必要である．ここでは，既存関数のCPSへの変換と利用例を示す（このチートシートの本体）．

from operator import add, sub, mul

# func(x, y) = (x + y) * (x - y)
def func(x, y): return mul(add(x, y), sub(x, y))

print(func(10, 20))    # => -300

def cps(f):
    def cps(x, y, c): return c(f(x, y))
    return cps

cps(add)(10, 20, print)    # => 30

def cfunc(x, y, c):
    return cps(add)(x,  y,  lambda c1:    # x + y -> c1
           cps(sub)(x,  y,  lambda c2:    # x - y -> c2
           cps(mul)(c1, c2, c)))          # c1 * c2 -> c

cfunc(10, 20, print)    # => -300

#Scheme（Gauche，Guile）

; func(x, y) = (x + y) * (x - y)
(define (func x y) (* (+ x y) (- x y)))
(display (func 10 20))    ; => -300

(define (cps f) (lambda (x y c) (c (f x y))))
((cps +) 10 20 display)    ; => 30

(define (cfunc x y c)
  ((cps +) x y (lambda (c1)    ; x + y -> c1
  ((cps -) x y (lambda (c2)    ; x - y -> c2
  ((cps *) c1 c2 c))))))       ; c1 * c2 -> c
(cfunc 10 20 display)    ; => -300

#Ruby（CRuby）

# func(x, y) = (x + y) * (x - y)
def func1(x,y) (x+y)*(x-y) end
p func1(10,20)    # => -300

add = -> x,y { x+y }
sub = -> x,y { x-y }
mul = -> x,y { x*y }
prn = -> x { p x }

cps = -> f { -> x,y,c { c.(f.(x,y)) } }
cps[add][10,20,prn]    # => 30

cfunc = -> x,y,c {
  cps.(add).(x, y, -> c1 {     # x + y -> c1
  cps.(sub).(x, y, -> c2 {     # x - y -> c2
  cps.(mul).(c1,c2,c) }) })    # c1 * c2 -> c
}
cfunc[10,20,prn]    # => -300

#JavaScript（Node.js）

// func(x, y) = (x + y) * (x - y)
function func1(x,y) { return (x+y)*(x-y) }
console.log(func1(10,20))    // => -300

add = (x,y) => x+y
sub = (x,y) => x-y
mul = (x,y) => x*y

cps = f => (x,y,c) => c(f(x,y))
cps(add)(10,20,console.log)    // => 30

cfunc = function(x,y,c) {
    return cps(add)(x, y, c1 =>    // x + y -> c1
           cps(sub)(x, y, c2 =>    // x - y -> c2
           cps(mul)(c1,c2,c)))    // x * y -> c
}
cfunc(10,20,console.log)    // => -300

#備考

##記事に関する補足

• そのうち『Iコンビネータ』に関する説明を追加するかもしれない（謎）．

##参考文献

• お気楽 OCaml プログラミング入門：継続渡しスタイル

##変更履歴

• 2020-08-09：Schemeのcall/cc利用例削除（Twitterコメントより）
• 2020-08-07：参考文献欄を追加
• 2020-08-07：JavaScriptの例を追加
• 2020-08-07：初版公開（Python，Scheme，Ruby）