プログラミングスタイルというと主に、
・手続き型
・オブジェクト指向型
・関数型
の3つがよく使われていると思います。
今回は
継続渡しスタイル
(Continuation Passing Style. 以下 CPS と略します)を紹介したいと思います。
CPS の基本的な考え方は、
・処理の次に何をするか?
でプログラムを書きます。
百聞は一見にしかず。論よりコード。早速プログラムを見てみましょう。
まず CPS で記述したいプログラムを普通の関数型で書きます。
(define (f) (* 3 (+ 1 2)))
これは、(1 + 2) * 3 を計算するプログラムです。
f は引数を取らない手続きです。
gosh> (f) 9
実行すると答えとして 9 を返します。正常に動作しています。
では、これを CPS で書いてみます。
(define (return x) x) (define (k+ a b k) (k (+ a b))) (define (k* a b k) (k (* a b)))
return 手続きは、引数の値を返すだけです。
k+ 手続きは引数の a と b を加算して、これを引数にして手続き k を呼び出します。
k* 手続きは、加算ではなく乗算になっただけで k+ と同じです。
ここで、k+ や k* の「引数 k が手続きである」という部分が、分かりづらいかも知れませんが、
この手続き(=関数)を引数にして与えることが出来る手続き(関数)を、「高階関数」と言います。
たとえば map です。
map は第一引数に手続き(関数)を、第二引数にリストを取ります。
第一引数に与えられた手続き(関数)を第二引数に与えられたリストの各要素に適用します。
具体例を示しましょう。
gosh> (map odd? '(1 2 3 4 5 6 7)) (#t #f #t #f #t #f #t)
odd? 手続きは奇数かどうかを調べる手続きです。
奇数の場合は #t を、そうでない場合は #f を返します。
map と同様に k+ および k* 手続きは高階関数です。引数 k は手続きを取ることを踏まえた上で、
(1 + 2) * 3 を計算してみましょう。
gosh> (k+ 1 2 (lambda (x) (k* x 3 return))) 9
CPS の場合はこのように計算します。
細かく見ていくと、まず 1 + 2 を計算したいので、k+ 手続きを使います。
引数 k の部分はまだ ??? にしておきます。
(k+ 1 2 ???)
ここまでは良いですよね?
次にやりたいことは乗算です。1 + 2 の加算の結果に 3 を掛けたいわけです。
(k+ 1 2 (lambda (x) (k* x 3 ???)))
k* の引数 k の部分はまだ ??? にしておきます。
最後に閉じカッコが 3 つもあって目がくらみそうな人がいるかも知れませんが、
・1つ目は k* 手続きの呼び出しのための閉じカッコ
・2つ目は無名関数の定義終了の閉じカッコ
・3つ目は k+ 手続きの呼び出しのための閉じカッコ
ですw
初めて 3D ゲームをプレイすると目がくらむような感覚がありますがそれと同じです。
慣れれば平気です。たぶん。
lambda というのは無名関数です。その名の通り、名前をつけない関数です。
例えば、引数 a b を取り、a と b を加算する無名関数を書くとこうなります。
gosh> (lambda (a b) (+ a b)) #<closure (#f a b)>
妙な結果が表示されますが、これは手続きであることを表しています。
Scheme で手続きを実行するには、カッコで括って
(手続き名 引数 ...)
としますから、先程の無名関数を実行するにはカッコで括って、引数 a b を与えます。
gosh> ((lambda (a b) (+ a b)) 3 4) 7
a に 3、b に 4 を与え、無名関数を評価すると a + b が計算されて、その結果 7 を返します。
この辺がわかりにくいかも知れませんが、大丈夫でしょうか?
元に戻って、3 を掛け算するところまではできました。
さて、次に何をすべきでしょうか?
そうです。「値を返す」を最後にしなければいけませんね。
(k+ 1 2 (lambda (x) (k* x 3) return)
つまり k* の引数 k には return 手続きを指定すれば良いわけです。
というわけで、CPS で (1 + 2) * 3 を計算するには当初に示した通り、以下のようにプログラムを書きます。
gosh> (k+ 1 2 (lambda (x) (k* x 3 return))) 9
k+ 手続きでは a に 1、b に 2、k に (lambda (x) (k* x 3 return)) が与えられ呼び出されます。
(+ a b) を計算してこれを k に与えるので、k に与えられた無名関数の x は (+ a b) の結果になります。
つまり x には 3 が与えられ、k* 手続きが呼び出されます。つまり (k* 3 3 return) として呼び出します。
k* 手続きでは a に 3、b に 3、k に return が与えられ呼び出されます。
(* a b) を計算してこれを k に与えるので、(return 9) を呼び出します。
return は引数の x の値を返すだけなので、 9 を返します。
このように、「次に何をするか?」という観点で
プログラムを記述するスタイルを、CPS (Continuation Passing Style : 継続渡しスタイル)と言います。
はじめに普通に関数型で書いたプログラムのほうが簡単なのに
なんで CPS なんかで書くの?
と思ったそこのあなた! あなたは正しいw
なんでこんな面倒くさい書き方するかと言えば、
それが CPS だから。
としか言わざるを得ません。
最後に、今回 CPS を紹介しましたが、CPS でプログラム書く人はまず居ません。
こんなプログラミングスタイルもあるのか、ぐらいに思ってもらえれば良いですw