Schemeではコレクタ機能はどのように機能しますか？

Question

Schemeでコレクタ機能の使用を理解するのに問題があります。私は本書「The Little Schemer」（Daniel P. FriedmanとMatthias Felleisen）を使っています。いくつかの説明を含む包括的な例は私を大いに助けてくれるだろう。例えば、呼が(identity '(a b c) self)であるとself-functionは(define self (lambda (x) x))であると...

(define identity 
    (lambda (l col) 
    (cond 
     ((null? l) (col '())) 
     (else (identity (cdr l) 
         (lambda (newl) 
         (col (cons (car l) newl))))))) 

：コレクタ関数を使用して関数の例は次のコードです。 identity関数は指定されたリストlを返します。したがって、指定された呼び出しの出力は(a b c)になります。使用される正確な言語は、R5RSレガシー言語です。それらの「コレクタ」機能を任意のリストxsと、いくつかの「コレクタ」機能colため

(identity xs col) 

を呼び出し、identity定義で定義されているかを考えると

Answer 1

は、そう

(col xs) 

を呼び出すことと同じですと同じリストは "返される"、すなわち引数 "collector" /継続関数colに渡されます。その名前はidentityです。各機能は、それが残りの結果を渡されることが想定され、「継続」を渡されます。

は比較のために、reverseは

(define reverse  ; to be called as e.g. (reverse l display) 
    (lambda (l col) 
    (cond 
     ((null? l) (col '()))  ; a reversed empty list is empty 
     (else (reverse (cdr l)  ; a reversed (cdr l) is newl -- 
        (lambda (newl) ; what shall I do with it when it's ready? 
         (col   ; append (car l) at its end and let col 
          (append newl       ; deal with it! 
            (list (car l)))))))))) 

プログラミングのこのスタイルはcontinuation-passing styleとして知られているようにコード化することができその結果、元の継続/コレクタ機能が最終的に最終結果をパスするようになる。各コレクターの引き数は受け取る将来の "結果"を表し、コレクター関数自体はそれがどのように処理されるかを指定します次にです。

これらの関数は、call/cc関数で捕捉された「継続」ではなく、「次に何をするべきか」を表す通常のScheme関数です。

定義は

identity : 
    to transform a list xs 
     with a collector function col, 
    is 
    | to call (col xs)        , if xs is empty, or 
    | to transform (cdr xs) 
     with a new collector function col2 
     such that 
       (col2 r) = (col (cons (car xs) r)) , otherwise 

（あるいは我々として、擬似コードでこれを書くことができます）として読み取ることができ

(identity list col) = 
    | empty? list   -> (col list) 
    | matches list (x . xs) -> (identity xs col2) 
           where 
           (col2 r) = (col (cons x r)) 

col2は、前のハンドラcolに(cons x r)を渡すことによって、その引数rを処理します。これは、が(cons x r)に変換されたことを意味しますが、値として返されるのではなく、それ以降の処理のためにcolに入力されます。したがって、新しい値(cons x r)を前の "コレクタ"に渡すことによって "返す"。

サンプルコール：

(identity (list 1 2 3) display)  

= (identity (list 2 3) k1) 
     ; k1 = (lambda (r1) (display (cons 1 r1))) 

= (identity (list 3) k2) 
     ; k2 = (lambda (r2) (k1 (cons 2 r2))) 

= (identity (list) k3) 
     ; k3 = (lambda (r3) (k2 (cons 3 r3))) 

= (k3 '()) 

= (k2 (cons 3 '())) 

= (k1 (cons 2 (list 3))) 

= (display (cons 1 (list 2 3))) 

= (display (list 1 2 3))