scheme continuations -need説明

Question

次の例では、継続にジャンプして終了します。誰かが関数の流れを説明することができます。私は継続の周りを円で移動しており、関数の入口点と出口点を知らない。

(define (prod-iterator lst) 
    (letrec ((return-result empty) 
     (resume-visit (lambda (dummy) (process-list lst 1))) 
     (process-list 
     (lambda (lst p) 
      (if (empty? lst) 
       (begin 
       (set! resume-visit (lambda (dummy) 0)) 
       (return-result p)) 
       (if (= 0 (first lst)) 
        (begin 
        (call/cc ; Want to continue here after delivering result  
         (lambda (k) 
         (set! resume-visit k) 
         (return-result p))) 
        (process-list (rest lst) 1)) 
        (process-list (rest lst) (* p (first lst)))))))) 
    (lambda() 
     (call/cc 
     (lambda (k) 
     (set! return-result k) 
     (resume-visit 'dummy)))))) 

(define iter (prod-iterator '(1 2 3 0 4 5 6 0 7 0 0 8 9))) 
(iter) ; 6                   
(iter) ; 120                  
(iter) ; 7                   
(iter) ; 1                   
(iter) ; 72                  
(iter) ; 0                   
(iter) ; 0 

ありがとうございます。

Answer 1

このプロシージャは、リストを反復し、ゼロ以外のメンバを掛けてゼロが見つかるたびに結果を返す。 Resume-visitにはリストの残りの部分を処理するための継続が格納され、return-resultにはイテレータのコールサイトが続きます。最初は、リスト全体を処理するようにresume-visitが定義されています。ゼロが見つかるたびに、継続がキャプチャされ、呼び出されるとlstにその時点での値である(process-list (rest lst) 1)が実行されます。リストがなくなると、resume-visitはダミープロシージャに設定されます。また、プログラムはiterを呼び出すたびに、それは次のことを実行する：

(call/cc 
    (lambda (k) 
    (set! return-result k) 
    (resume-visit 'dummy))) 

それが呼び出し元に値を返す呼び出し、呼び出し元の継続を捕捉、すなわち。継続は保存され、プログラムはジャンプして残りのリストを処理します。 プロシージャがresume-visitを呼び出すと、ループに入ります。return-resultが呼び出されると、ループが終了します。

process-listを詳しく調べる場合は、リストは空ではないものとします。このプロシージャは、基本的な再帰を使用し、ゼロが見つかるまで結果を累積します。その時点で、pは累積値であり、lstはゼロを含むリストです。 (begin (call/cc (lambda (k) first)) rest)のような構造を持つ場合、まずfirstの式を実行し、kを継続にバインドします。呼び出されるとrest式を実行するプロシージャです。この場合、その継続が格納され、別の継続が呼び出され、累積結果pをiterの呼び出し元に返します。その継続は、次回のiterが呼び出されたときに呼び出されます。その後、ループは残りのリストと続けられます。それは継続とのポイントです、他のすべては基本的な再帰です。

Answer 2

覚えておく必要があることは、(call/cc f)を呼び出すと、call/ccの引数として渡された関数fが現在の継続に適用されることです。その継続が関数fの内部でいくつかの引数aで呼び出された場合、実行はcall/ccへの対応する呼び出しに行き、引数aがそのcall/ccの戻り値として返されます。

あなたのプログラムは、return-resultという変数に "call/ccをiterにコール"の継続を保存し、リストの処理を開始します。 0を見ると、「リスト要素0を処理する」という継続はresume-visitに格納され、pの値はreturn-resultに呼び出されて返されます(return-result p)。この呼び出しにより、実行はcall/ccのiterに戻り、call/ccは、渡された値pを返します。したがって、最初の出力が表示されます。

iterへの残りの呼び出しは、類似しており、この2つの継続の間で実行が前後します。手作業による分析は少し頭がひっくり返っているかもしれません。継続が復元されたときの実行コンテキストが何であるかを知る必要があります。

Answer 3

あなたは同じをこのように実現することができます：

(define (prod-iter lst) (fold * 1 (remove zero? lst))) 

...それは一度だけ横断することにより、より良い実行可能性にもかかわらず。継続のために

、すべてのコール/ ccがないことをリコール（しゃれが意図した）この方法を適用する「K」を待つされています

(call/cc (lambda (k) (k 'return-value))) 
    => return-value 

ここのトリックは、あなたが呼び出しは/そのを返すCCせることができますということですそれは呼び出し/ ccの後に他の場所に適用することができるように独自の継続は次のように戻ってきた：

;; returns twice; once to get bound to k, the other to return blah 
(let ([k (call/cc (lambda (k) k))]) ;; k gets bound to a continuation 
    (k 'blah)) ;; k returns here 
    => blah 

は、これは継続が変数に保存することによって、複数回返すことができます。継続は単に適用される値を返します。

クローズは、引数がバインドされる前に環境変数を保持する関数です。彼らは普通のラムダです。

継続渡しスタイルは、後で適用される引数としてクロージャを渡す方法です。我々は、これらの閉鎖論は、継続であると言う。ここでは、私のスドクジェネレーター/ソルバーの現在のコードの半分が、継続継承スタイルがアルゴリズムをどのように単純化できるかを示す例として挙げられています：

#| the grid is internally represented as a vector of 81 numbers 
example: (make-vector 81 0) 

this builds a list of indexes |# 
(define (cell n) (list (+ (* (car 9) (cadr n)))) 
(define (row n) (iota 9 (* n 9))) 
(define (column n) (iota 9 n 9)) 
(define (region n) 
    (let* ([end (+ (* (floor-quotient n 3) 27) 
       (* (remainder n 3) 3))] 
     [i (+ end 21)]) 
    (do ([i i 
      (- i (if (zero? (remainder i 3)) 7 1))] 
     [ls '() (cons (vector-ref *grid* i) ls)]) 
     ((= i end) ls)))) 

#| f is the continuation 

usage examples: 
(grid-ref *grid* row 0) 
(grid-set! *grid* region 7) |# 
(define (grid-ref g f n) 
    (map (lambda (i) (vector-ref g i)) (f n))) 
(define (grid-set! g f n ls) 
    (for-each (lambda (i x) (vector-set! g i x)) 
    (f n) ls))