解释《小阴谋家》第 137 页的延续示例

Question

有问题的代码是这样的：

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen))))))

我整天盯着这个，但我似乎不太明白它。当您重复该函数时，您正在重新定义 col 但在示例中它们似乎使用原始定义。为什么不改变呢。如何在不传入参数 newlat 和 seen 的情况下重复它。

很难解释我的问题，因为我似乎遗漏了一块。如果有人可以给出比这本书更明确的演练，我也许能够理解它是如何工作的。

Answer 1

让我们来看一个例子；也许这会有所帮助。 :-) 为简单起见，我将使用 list 作为收集器/延续，它将仅返回一个包含延续参数的列表。

(multirember&co 'foo '(foo bar) list)

开始时，

a = 'foo
lat = '(foo bar)
col = list

在第一次迭代时，(eq? (car lat) a) 条件匹配，因为 lat 不为空，并且 的第一个元素纬度 是'foo。这样就设置了 multirember&co 的下一个递归：

a = 'foo
lat = '(bar)
col = (lambda (newlat seen)
        (list newlat (cons 'foo seen))

在下一次迭代中，else 匹配：因为 lat 不为空，并且lat 的第一个元素是 'bar （而不是 'foo）。因此，对于下一次递归，我们有：

a = 'foo
lat = '()
col = (lambda (newlat seen)
        ((lambda (newlat seen)
           (list newlat (cons 'foo seen)))
         (cons 'bar newlat)
         seen))

为了便于人类阅读（并避免混淆），我们可以重命名参数（由于词法范围），而不需要对程序的语义进行任何更改：

col = (lambda (newlat1 seen1)
        ((lambda (newlat2 seen2)
           (list newlat2 (cons 'foo seen2)))
         (cons 'bar newlat1)
         seen1))

最后， (null ? lat) 子句匹配，因为 lat 现在为空。因此，我们称其

(col '() '())

扩展为：

((lambda (newlat1 seen1)
   ((lambda (newlat2 seen2)
      (list newlat2 (cons 'foo seen2)))
    (cons 'bar newlat1)
    seen1))
 '() '())

which（当替换 newlat1 = '() 和 seen1 = '() 时）变为

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 (cons 'bar '())
 '())

or (评估 (cons 'bar '( )))

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 '(bar)
 '())

现在，替换值 newlat2 = '(bar) 和 seen2 = '()，我们得到

(list '(bar) (cons 'foo '()))

或者，换句话说，

(list '(bar) '(foo))

给出我们的最终结果

'((bar) (foo))

Answer 2

我在这里找到了一个很棒的答案：
http://www.michaelharrison.ws/weblog/?p=34

我一直在努力解决这个问题也。关键是理解词法作用域（对我来说，是 Javascript）以及在 eq 和 not eq 分支上传递给 multirember&co 的内部函数。明白了这一点，你就会明白整个过程。

Answer 3

很长一段时间以来，我一直在努力理解 multirember&co 内部发生的事情。问题是，当我以为我已经得到它的那一刻 - 下一个任务/示例证明我还没有。

对我有帮助的是整合正在发生的事情的视觉表示（对我来说，文本演练很难理解，出于某种原因）。

所以，我整理了两个流程图：

一，仅显示不同递归步骤之间的关系：

---

还有另一个，反映实际值：

现在，每当我感觉自己又失去了“争论的线索”时，我只要参考这个流程图，它就会让我回到正轨。

通过流程图查看“全貌”后我明白的另一件事是，a-friend函数只是检查是否seen是否保存任何值（尽管它以相反的方式返回它，即当 seen 中有值时 #f 和 #t 当 saw 是空的，这可能会令人困惑

PS：我 。为evens-only*&co做了类似的流程图，稍后出现在书。

Answer 4

上面的链接（http://www.michaelharrison.ws/weblog/?p=34）很好地解释了整个练习是如何避免命令式编程（C，Java）需要声明两个“持有者”或“收集器” “变量（或列表、向量）显式地存在于内存中，以便在您迭代列表时捕获您的答案。通过 FP 语言方案使用延续，您在单步执行（草莓金枪鱼和剑鱼）时不会将测试结果“推送”到任何单独创建的“篮子”中；相反，当您发送适当的 consing 函数时，您将两个列表组合在一起 - 一个用于 eq?是的，另一个为 eq？ false——通过重复。 。 。最后结束于第三个 col 函数，在 TLS 的第一个示例中，它是“a-friend”，它询问为保存所有匹配而构建的列表是否为空（null？）。然后，TLS 会要求您使用新的“最后”列再次“运行”multirember&co，该列仅询问包含所有“非金枪鱼”原子的列表包含多少个（“最后朋友”）。因此，有两个“一流”函数用于处理收集任务，即构建两个单独的列表，然后在递归展开结束时，原始 col（“朋友”）提出最终问题。也许“multirember&co”这个名字并不是最伟大的名字，因为它实际上不会重建列表减去要删除的原子；相反，它构建两个单独的列表（永远不会显示），然后应用最终的 col (a-friend 或 last-friend) 。 。 。它显示#t 或#f，或“非金枪鱼”列表的长度。

这是一些输出：

> (multirember&co 'tuna '(and tuna) a-friend)
#f
> (multirember&co 'tuna '(and not) a-friend)
#t

这是一个返回不匹配列表的列：

(define list-not  (lambda (x y) x))

及其用途：

> (multirember&co 'tuna '(and not) list-not)
(and not)

Answer 5

让我们使用一些等式伪代码，为了清楚起见，省略了一些括号（因此，我们为调用 (fxy) 编写 fx y，这是明确的）

multirember&Co a lat col
    = col [] []                                , IF lat == [] 

    = multirember&Co a (cdr lat)
         ( newlat seen => 
             col newlat
                 (cons (car lat) seen) )       , IF (car lat) == a

    = multirember&Co a (cdr lat)
         ( newlat seen => 
             col (cons (car lat) newlat)
                 seen )                        , OTHERWISE

：不言而喻，这是做什么的？ ：） 还没有？ :) 用想象中的模式匹配伪代码（带有守卫）再次重写，我们有

multirember&Co  =  g   where
    g a [b, ...lat] col | b == a  =  g a lat ( n s =>  col     n     [b, ...s] )
                        | else    =  g a lat ( n s =>  col [b, ...n]     s     )
    g a []          col           =                    col     []        []

模式匹配的语义应该非常明显： [b, ...lat] 匹配 [ 1,2,3]，其中 b = 1 和 lat = [2,3]。因此，这只是一个三例方程：

• 当第二个参数是空列表时，“收集器”函数 col 立即被输入两个空列表作为其两个参数；

• 当第二个参数（是一个列表）的head元素与第一个参数相同时，结果与使用以下tail递归的结果相同列表，带有修改后的收集器 - 之后它将收到两个参数，n和s，--将< /em> 在当前头元素前面添加（即a) 到 s 列表，并将这两个列表提供给 this 调用的收集器函数 col;

• 否则，在构建的收集器接收到 n 和 s 后，头元素将被添加到 n 列表中，并且两者都将被进一步馈送到当前收集器函数中。

换句话说，我们正在处理从递归调用返回的两个结果，如果头是a，则将头添加到第二个结果，如果不是，则将头添加到第一个结果。

因此，调用

    (g 1 [ 2, 1, 3, 1, 4, 5 ] col)

与调用相同（将导致），

    (col [ 2, ...[3, ...[4, ...[5, ...[]]]]]
         [    1, ...[1,            ...[]]  ])

即

    (col [ 2,     3,     4,     5          ]
         [    1,     1                     ])

---

另一种看待它的方式是，以下是另一个等效的公式：

multirember&Co a lat col  =  g a lat id id   where
    id      x  =  x              ; identity function  
    (f ∘ g) x  =  f (g x)        ; function composition
    g a [b, ...lat] c d 
               | b == a  =  g a lat  c     (d ∘ (x => cons b x))  ;    (d ∘ {cons b})
               | else    =  g a lat (c ∘ (x => cons b x))   d     ; (c ∘ {cons b})
    g a []          c d  =  col     (c [])                (d [])

因此，

multirember&Co 1 [ 2, 1, 3, 1, 4, 5 ] col 
=
col (((((id ∘ {cons 2}) ∘ {cons 3}) ∘ {cons 4}) ∘ {cons 5}) [])   ; { } is for
    ( ( (id ∘       {cons 1}) ∘ {cons 1}                  ) [])   ;  partial application
=
col     (id   (cons 2     (cons 3     (cons 4    (cons 5   [])))))
        (id         (cons 1     (cons 1                    []) ) )  

这是不言而喻的同一件事。

在另一个伪代码（带有列表推导）中，这表明它只

multirember&Co a lat col  
   = col [ b for b in lat if (b /= a) ] 
         [ b for b in lat if (b == a) ] 
   = ( ((n,s) => col n s) ∘ {partition {/= a}} ) lat

执行一次列表 lat 遍历（在原始代码中），有效地构建模仿原始列表结构的 lambda 函数的嵌套链；然后评估该链以创建两个结果，并将它们传递给最顶层的收集器函数 col。

所有这些都向我们展示了Continuation-Passing Style的力量（这就是它）实际上，创建自己的函数调用协议，例如，从每个递归函数调用传回两个结果，即使通常在 lambda 演算中函数只能有一个 > 结果（即使是一对）。

Answer 6

该代码不会像通常那样构建解决方案，而是构建一个计算解决方案的代码，就像使用低级操作构建树一样，例如 cons、+、- 等，而不是使用高级累加器或过滤器。

这就是为什么很难说该过程是迭代的还是递归的，因为根据迭代过程的定义，它们为本地状态使用有限量的内存。然而，这种进程使用大量内存，但这是在环境中分配的，而不是在本地参数中分配的。

首先，我在这里复制代码，以便能够在不滚动太多的情况下查看对应关系：

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen)))))))

让我们尝试拆分问题，看看到底发生了什么。

• 情况 1：

---

(multirember&co 'a
                '()
                (lambda (x y) (list x y)))

is the same as    

(let ((col (lambda (x y) (list x y))))
  (col '() '()))

这是一个简单的情况，它永远不会循环。

现在是有趣的案例：

• 案例 2：

---

(multirember&co 'a
                '(x)
                (lambda (x y) (list x y)))

is the same as    

(let ((col
       (let ((col (lambda (x y) (list x y)))
             (lat '(x))
             (a 'a))
         (lambda (newlat seen)
           (col (cons (car lat) newlat)
                seen)))))
  (col '() '()))

在这种情况下，流程生成此代码作为结果，并最终对其进行评估。请注意，本地它仍然是尾递归的，但全局它是一个递归过程，并且它需要内存不是通过分配某些数据结构，而是通过让评估器仅分配环境帧。每个循环都会通过添加 1 个新框架来加深环境。

• 情况 3

---

(multirember&co 'a
                '(a)
                (lambda (x y) (list x y)))

is the same as    

(let ((col
       (let ((col (lambda (x y) (list x y)))
             (lat '(a))
             (a 'a))
         (lambda (newlat seen)
           (col newlat
                (cons (car lat) seen))))))
  (col '() '()))

这构建了代码，但在另一个分支上，将结果累积到另一个变量中。

---

所有其他情况都是这 3 种情况中 1 种的组合，通过添加新层，每个 1 的作用就很清楚了。

Answer 7

我希望本演练有所帮助

正如 Chris 建议的那样，我已将 newlat/seen 重命名为 n/s 并添加了索引。
这本书给函数起了可怕的名字（a-friend new-friend Latest-fried），所以我只保留了 L（代表 lambda）和定义。

multirember&co 'tuna '(strawberries tuna and swordfish) a-friend)
  multirember&co 'tuna '(tuna and swordfish) (L(n1 s1)(a-friend (cons 'strawberries n1) s1))
    multirember&co 'tuna '(and swordfish) (L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))
      multirember&co 'tuna '(swordfish) (L(n3 s3)((L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2)) (cons 'and n3) s3))
        multirember&co 'tuna '() (L(n4 s4)((L(n3 s3)((L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2)) (cons 'and n3) s3)) (cons 'swordfish n4) s4))

((lambda(n4 s4)((lambda(n3 s3)((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) (cons 'and n3) s3)) (cons 'swordfish n4) s4)) '() '())
               ((lambda(n3 s3)((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) (cons 'and n3) s3)) '(swordfish) '())
                              ((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) '(and swordfish) '())
                                             ((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) '(and swordfish) '(tuna))
                                                            (a-friend '(strawberries and swordfish) '(tuna))