継続渡しスタイル第二回(最終回)

第二回にして最終回ですが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章 継続」を読んでいただければ、
さらなる理解が進むと思います。「コルーチン」の実装例なども紹介されています。

プログラミングGauche

プログラミングGauche

また、さらにさらに興味が湧いた人は、
SICP (計算機プログラムの構造と解釈)の「第 5 章 レジスタ計算機での計算」を読むと
CPS の真価が垣間見えることでしょう。

簡単に紹介すると Schemeアセンブリ言語を実装するのですが、そのアセンブリ言語
実行を制御するために CPS が使われていますので、CPS を知らないと理解がより難しくなるでしょう。

とても難しい本ですが様々なプログラミングテクニックの宝庫ですので、
ワンランク上のプログラマーを目指したい方はぜひ読まれる事をお勧め致します。

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版

SICP はネットでも全文が公開されていますので、ググってみてください。

*1:「大域脱出」と言います。

*2:他言語で言うところの例外処理です。