收集器功能如何在方案中工作？

Question

我很难理解如何在Scheme中使用收集器函数。我使用的书“小阴谋家”(由丹尼尔P弗里德曼和马蒂亚斯费莱森)。一个全面的例子，加上一些解释，将对我有很大帮助。使用收集器函数的函数示例如下：

(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))))))))))

这种编程风格被称为https://en.wikipedia.org/wiki/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)
  | match? list (x . xs)  ->  (identity xs col2)
                                where 
                                (col2 r)  =  (col (cons x r))

col2通过将(cons x r)传递给前一个处理程序col来处理其参数col。这意味着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)))           =  display ° {cons 1}

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

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

= (k3 '())                        ; (((display ° {cons 1}) ° {cons 2}) ° {cons 3}) []

= (k2 (cons 3 '()))                    ; ((display ° {cons 1}) ° {cons 2}) [3]

= (k1 (cons 2 (list 3)))                    ; (display ° {cons 1}) [2,3]

= (display (cons 1 (list 2 3)))                  ; display [1,2,3]

= (display (list 1 2 3))

更新:在最近我喜欢使用的模式匹配伪代码中，我们可以编写

identity []        col  =  col []
identity [a, ...d] col  =  identity d ( newl =>  col [a, ...newl] )

和

reverse  []        col  =  col []
reverse  [a, ...d] col  =  reverse  d ( newl =>  col [...newl, a] )

这希望是如此明显的视觉效果，几乎不需要任何解释！