8

我无法理解 Scheme 中收集器函数的使用。我正在使用“The Little 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))))))))

...以示例调用 being(identity '(a b c) self)和 the self-functionBeing (define self (lambda (x) x))。该identity函数返回给定的列表l,因此给定调用的输出将是(a b c)。使用的确切语言是 R5RS Legacy 语言。

4

2 回答 2

5

鉴于定义中如何定义这些“收集器”函数identity,调用

(identity xs col)

对于任何列表xs和一些“收集器”功能col,相当于调用

(col xs)

所以相同的列表将被“返回”,即传递给它的参数“收集器”/延续函数col。这解释了它的名字identity,那么。

为了比较,areverse可以编码为

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

这种编程风格被称为延续传递风格:每个函数都传递一个“延续”,假设它将传递其余计算的结果,因此原始延续/收集器函数将传递最终结果最终。每个收集器的参数代表它将收到的未来“结果”,然后收集器函数本身指定如何处理它。

不要被术语混淆:这些函数不是函数捕获的“延续” 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))

col2r通过传递(cons x r)给前一个处理程序来 处理其参数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] )

希望它在视觉上非常明显,几乎不需要解释!

于 2016-11-26T18:23:49.513 回答
2

我正在添加第二个答案,希望它可以澄清剩余的疑问,以防万一(因为缺少“已接受”标记表明)。

在 Gerald J. Sussman 的声音中,正如在 SICP 讲座中听到/看到的那样,在互联网管道上到处都有视频,我们可以在写作时阅读它,

(define identity

“身份”被定义为

  (lambda

那个函数,当给定的时候

           (l col)

两个参数,lcol,将

    (cond
      ((null? l)

——如果(null? l)是真的——

  • OK,这意味着l是一个列表,NB

                   (col '()))
    

返回表达式的值 (col '())

  • 好的,这现在意味着col是一个函数,期望一个参数,作为一种可能的空列表,
      (else (identity (cdr l)

否则它将使用更新的值进行尾递归调用,其中一个是(cdr l),

                      (lambda (newl)
                        (col (cons (car l) newl)))))))

另一个是新构造的函数,这样当用它的参数newl(一个列表,正如预期的那样col——因为它出现在相同的角色,它必须遵循相同的约定)调用时,将依次调用使用由list 前缀产生的col列表的函数。(car l)newl

因此,这个函数identity, 遵循方程

( identity   (cons (car l) (cdr l))           col                        )
==
( identity       (cdr l)     (lambda (newl)  (col  (cons (car l) newl))) )

( identity   '()   col )
==
( col        '()       )

描述一个迭代过程,即转换函数调用的过程

(identity [a,      b,      c, ...,    n]    col      )

进入通话

(col
     (cons a (cons b (cons c ... (cons n '()) ... ))))

重新创建完全相同的列表,然后将其作为参数提供给col它提供的函数。

于 2018-09-08T13:52:27.697 回答