集合函數在Scheme中如何工作？

Question

我無法理解Scheme中收集器函數的使用。我正在使用「小小的Schemer」一書（Daniel P. Friedman和Matthias Felleisen）。一個有一些解釋的綜合例子將大量幫助我。使用收集器功能的功能的一個例子是下面的代碼片斷：

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

...一個示例呼叫是(identity '(a b c) self)和self-function是(define self (lambda (x) x))。 identity函數返回給定列表l，因此給定調用的輸出將是(a b c)。使用的確切語言是R5RS舊版語言。

Answer 1

鑑於這些「收藏家」的功能是如何在identity定義中定義，調用

(identity xs col) 

任何名單xs和一些「收藏家」的功能col，相當於調用

(col xs) 

所以相同的列表將被「返回」，即傳遞給它的參數「收集器」/繼續功能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通過傳遞(cons x r)以前的處理程序col處理它的參數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))