收集器功能在Scheme中如何工作? [英] How do collector functions work in Scheme?

问题描述

我无法理解Scheme中收集器功能的使用.我正在使用《小策划者》这本书(丹尼尔·P·弗里德曼和马蒂亚斯·弗莱森).一个有一些解释的综合例子将对我有很大帮助.以下代码段是使用收集器函数的函数示例:

I am having trouble understanding the use of collector functions in Scheme. I am using the book "The Little Schemer" (by Daniel P. Friedman and Matthias Felleisen). A comprehensive example with some explanation would help me massively. An example of a function using a collector function is the following snippet:

(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旧版语言.

... with an example call being (identity '(a b c) self) and the self-function being (define self (lambda (x) x)). The identity function returns the given list l, so the output of the given call would be (a b c). The exact language used is the R5RS Legacy-language.

推荐答案

给出在identity定义中如何定义那些收集器"函数，调用

Given how those "collector" functions are defined in the identity definition, calling

(identity xs col)

对于任何列表xs和某些收集器"功能col，等同于调用

for any list xs and some "collector" function col, is equivalent to calling

(col xs)

因此 same 列表将被返回"，即传递给其参数"collector"/延续函数col.那就解释了它的名字，identity.

so the same list will be "returned" i.e. passed to its argument "collector" / continuation function col. That explains its name, identity, then.

为了比较，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))))))))))

这种编程风格被称为 延续传递风格 :向每个函数传递一个继续"，假定该函数将传递其余计算的结果，以便最终将最终的原始结果传递给原始的延续/收集器函数.每个收集器的参数代表将来将收到的结果"，然后收集器函数本身指定如何处理然后.

This style of programming is known as continuation-passing style: each function is passed a "continuation" that is assumed that it will be passed the result of the rest of computation, so that the original continuation / collector function will be passed the final result eventually. Each collector's argument represents the future "result" it will receive, and the collector function itself then specifies how it is to be handled then.

请不要对术语感到困惑:这些功能不是call/cc功能所捕获的延续"，它们是正常的Scheme功能，代表下一步要做的事情".

Don't get confused by the terminology: these functions are not "continuations" captured by the call/cc function, they are normal Scheme functions, representing "what's to be done next".

定义可以理解为

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.

(或者我们也可以用伪代码写出来)

(or we can write this in a pseudocode, as)

(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来处理其自变量r.这意味着将r转换为(cons x r)，但不是将其作为值返回，而是将其馈送到col中进行进一步处理.因此，我们通过将新值(cons x r)传递给先前的收集器"来返回".

col2 handles its argument r by passing (cons x r) to the previous handler col. This means r is transformed into (cons x r), but instead of being returned as a value, it is fed into col for further processing. Thus we "return" the new value (cons x r) by passing it to the previous "collector".

一个示例调用，例如:

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

---

update:用我最近很喜欢使用的模式匹配伪代码，我们可以编写

---

update: in a pattern-matching pseudocode I've been fond of using as of late, we could write

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

希望在视觉上如此明显，以至于几乎不需要解释！

which hopefully is so much visually apparent that it almost needs no explanation!

这篇关于收集器功能在Scheme中如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！