第二回にして最終回ですがw、
CPS でもう少しプログラムを書いてみましょう。
まずは、階乗を求めるプログラム。鉄板ですねw
まずは普通の関数型で書きます。
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))
5! + 7 を計算してみます。
gosh> (+ 7 (fact 5)) 127
次に CPS で書きます。
(define (k+ a b k) (k (+ a b))) (define (k* a b k) (k (* a b))) (define (return x) x) (define (kfact n k) (if (= n 1) (k 1) (kfact (- n 1) (lambda (x) (k (* n x))))))
同様に 5! + 7 を CPS で計算してみます。
gosh> (kfact 5 (lambda (x) (k+ x 7 return))) 127
次は与えられた数字のリストを掛け算する手続きです。
(define (k+ a b k) (k (+ a b))) (define (k* a b k) (k (* a b))) (define (return x) x) (define (non-number-value-error x) (error x 'ハ数字デハナイノデ、ケイサンデキマセン)) (define (kproduct numbers k k-value-error) (let ((break k)) (define (iter ls k) (cond ((null? ls) (k 1)) ((not (number? (car ls))) (k-value-error (car ls))) ((zero? (car ls)) (break 0)) (else (iter (cdr ls) (lambda (x) (k (* (car ls) x))))))) (iter numbers k)))
CPS を利用して、リスト内にゼロが現れた場合は処理を打ち切ります。
また、リストに数字以外のものが含まれていた場合は、エラー表示をして処理を打ち切ります。
まずは正常ケースを試してみます。
gosh> (kproduct '(1 2 3 4 5 6) return non-number-value-error) 720
1 * 2 * 3 * 4 * 5 * 6 = 720 です。正しい結果を返しました。
次に異常ケースを試してみます。リストに数字以外の文字が入っていたらどうなるでしょうか。
gosh> (kproduct '(1 2 n 4 5 6) return non-number-value-error) *** ERROR: n ハ数字デハナイノデ、ケイサンデキマセン Stack Trace: _______________________________________ 0 (eval expr env) at "/usr/local/share/gauche-0.9/0.9.6/lib/gauche/interactive.scm":267
このように CPS を使用すると、処理を中断したり*1、エラー処理をハンドリング*2することができます。
今回は error 手続きを呼ぶだけなのであまり有り難みが無いプログラムなのですが、
non-number-value-error 手続きにエラー時にやりたい事を好きに書くことができます。
最後に与えられた文字列を反転する処理を CPS で書いてみます。これも鉄板ですね。
(define (return x) x) (define (kreverse ls k) (if (null? ls) (k nil) (kreverse (cdr ls) (lambda (x) (k (append x (cons (car ls) nil)))))))
実行してみます。
gosh> (kreverse '(a b c 1 2 3) return) (3 2 1 c b a)
以上のように CPS の一例を見てきましたが、
CPS に興味が湧いた人は、
「プログラミングGauche」の「19章 継続」を読んでいただければ、
さらなる理解が進むと思います。「コルーチン」の実装例なども紹介されています。
- 作者: Kahuaプロジェクト,川合史朗
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/03/14
- メディア: 大型本
- 購入: 22人 クリック: 713回
- この商品を含むブログ (244件) を見る
また、さらにさらに興味が湧いた人は、
SICP (計算機プログラムの構造と解釈)の「第 5 章 レジスタ計算機での計算」を読むと
CPS の真価が垣間見えることでしょう。
簡単に紹介すると Scheme でアセンブリ言語を実装するのですが、そのアセンブリ言語の
実行を制御するために CPS が使われていますので、CPS を知らないと理解がより難しくなるでしょう。
とても難しい本ですが様々なプログラミングテクニックの宝庫ですので、
ワンランク上のプログラマーを目指したい方はぜひ読まれる事をお勧め致します。
- 作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一
- 出版社/メーカー: 翔泳社
- 発売日: 2014/05/17
- メディア: 大型本
- この商品を含むブログ (4件) を見る