recursion - 小阴谋家 : why wrap (mk-length mk-length) into a function?

Question

在 The Little Schemer book ，在第 9 章中，在为任意长输入构建 length 函数时，建议执行以下操作(在 pages 170-171 上)，即以下代码片段(来自 page 168 本身):

((lambda (mk-length)
   (mk-length mk-length))                      
 (lambda (mk-length)
   ((lambda (length)                           
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))   
    (mk-length mk-length))))                   

部分(mk-length mk-length)，永远不会返回，并将无限地应用于自身:

Because we just keep applying mk-length to itself again and again and again...

和

But now that we have extracted (mk-length mk-length) from the function that makes length it does not return a function anymore.

现在，为了解决这个问题，本书建议:

Turn the application of mk-length to itself in our last correct version of length into a function.

就像这样:

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   ((lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0 )
         (else 
           (add1 (length (cdr l)))))))
   (lambda (x)
     ((mk-length mk-length) x)))))

令我困惑的是:

1. 如果(mk-length mk-length)

   does not return a function

   我们如何将(mk-length mk-length)的结果应用到某些东西上，就好像它是一个函数一样？

   (lambda (x)
     ((mk-length mk-length) x))
   

2. 将 (mk-length mk-length) 包装到函数中如何解决“永不返回”(即无限递归)问题？我的理解是，在:

   (lambda (x)
     ((mk-length mk-length) x))
   

x 将仅传递给无限递归函数，该函数永远不会返回。

Answer 1

您可能复制了错误的代码片段，即您实际谈论的之前的代码片段。您显示的第一个代码完全没问题。相反，循环是这个:

   ((lambda (mk-length)
      (mk-length mk-length))                      ; (1)
    (lambda (mk-length)
      ((lambda (length)                           ; (2)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))    ; (4)
       (mk-length mk-length))))                   ; (3)

这个问题已经得到解答 here :应用程序(1)触发应用程序(2)，应用程序(2)触发应用程序(3)立即，这相当于(1)!因此，循环。

将其包装在 lambda(又名eta-expansion)中会延迟应用程序(3)，直到调用构造的length在 (4) 中，这完全没问题(您也复制了一些拼写错误):

   ((lambda (mk-length)
      (mk-length mk-length))                      ; (1)
    (lambda (mk-length)                                   ; (5)
      ((lambda (length)                           ; (2)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))    ; (4)
       (lambda (x)                                ; (3)
         (mk-length mk-length) x))))

(3) 现在是一个 lambda 表达式，而不是一个应用程序。计算此 lambda 表达式会生成一个匿名函数。当 length 被调用时，此 lambda 函数将执行应用程序(mk-length mk-length)稍后。

(更长的解释:)(3) 立即返回绑定(bind)到 length 的 lambda 函数，并且 (lambda (l) ...) 愉快地返回这样，当该 (lambda (l) ...) 将应用于某个列表时，可能会导致此长度¹ 在 (4) 中调用，仅然后应用程序 (mk-length mk-length) 内部的 lambda (3) 实际上会被执行——最终给我们一个新的 (lambda (l) ...) 匿名函数，它将被应用到 (cdr l) 那里。

¹length 是 (lambda (x) ((mk-length mk-length) x)) 这意味着 (length (cdr l)) 与 ((mk-length mk-length) (cdr l)) 相同(其中 mk-length 绑定(bind)到整个 lambda 表达式 (5))，最后是 ((lambda (l) ...) (cdr l))。

妮娜