継続（call-with-current-continuation, call/cc）がまだよく理解できていない。

なので、途中経過を勉強メモ。

素数夜曲: 女王陛下のLISP からの引用で、リストの各要素を掛け合わせる product という関数について検証する。

'(1 1 0 2)

というリストが有った場合、途中に 0 が含まれているわけだから、最後の 2 を掛け算しなくとも、0 に到達した時点で答えは 0 だと分かる。

;; call/cc を使えば、
;; 「0 に到達した時点で答えは 0 だと分かる」
;; という動作を実現できる
(define (product/call/cc lst)
 (call/cc (lambda (k)
           (cond ((null? lst) 1)
            ((zero? (car lst)) (k 0)) ;; ここで再帰を break して 0 を返す
            (else (* (car lst) (product/call/cc #?=(cdr lst))))))))


;; #?=(cdr lst) で再帰に使用するリストを吐き出させながら実行すると・・・
gosh> (product/call/cc '(1 1 0 2))
#?="./call_cc.scm":5:(cdr lst)
#?-    (1 0 2)
#?="./call_cc.scm":5:(cdr lst)
#?-    (0 2)
0
;; 最後の 2 は計算されずに (zero? (car lst)) が #t の時点で終了している


;; call/cc を使わずに馬鹿正直に計算させると
(define (product lst)
 (cond ((null? lst) 1)
  (else (* (car lst) (product #?=(cdr lst))))))


gosh> (product '(1 1 0 2))
#?="./call_cc.scm":9:(cdr lst)
#?-    (1 0 2)
#?="./call_cc.scm":9:(cdr lst)
#?-    (0 2)
#?="./call_cc.scm":9:(cdr lst)
#?-    (2)
#?="./call_cc.scm":9:(cdr lst)
#?-    ()
0
;; 0 が出現した後も計算を続けている

以上の call/cc の性質を利用すれば next や break などが再帰の中で実現できる。

この辺の実例は プログラミングGauche の19章に詳しく書いてあるので、そちらも参考にしながら継続する。

#Gauche #Scheme #Lisp #call/cc

SN 2013/07/06 18:39:06

Archives > Gauche_call_with_current_continuation_study_01.html