5

我正在阅读The Little Schemer并对以下代码感到困惑：

((lambda (len)
   (lambda (l)
      (cond
         ((null? l) 0)
         (else 
            (+ 1 (len (cdr l)))))))
   eternity)

(define eternity
    (lambda (x)
         (eternity x)))

代码是判断空列表，否则永远不会停止。

为什么“ len”不是递归？

4

2 回答 2

6

尽管将文本替换应用于 Lisp 表单可能很危险（因为存在多重评估等危险），但在这种情况下，查看此表单并了解它如何组合在一起可能会有所帮助：

((lambda (len) 
   (lambda (l)
     ...))
 eternity)

是一个应用程序，即一个函数调用。被调用的函数接受一个参数，称为len，并返回另一个接受单个参数的函数l。被调用的函数是用 调用的eternity。当调用完成时，结果是这个函数：

(lambda (l)
  (cond
    ((null? l) 0)
    (else (+ 1 (eternity (cdr l))))))

现在，这个函数接受一个列表l，如果它是空的，则返回0。否则，它计算(cdr l)（列表的其余部分），并eternity使用该值调用。当它返回时，1被添加到结果中，这就是整个函数的返回值。当然，问题在于eternity 

(define eternity
  (lambda (x)
    (eternity x)))

也可以写成

(define (eternity x)
  (eternity x))

只需接受一个参数x，然后调用eternitywith x。那是一个无限循环。在上面，我写了“当返回时”，但实际上，(eternity (cdr l)) 永远不会返回。所以，

((lambda (len)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (+ 1 (len (cdr l)))))))
 eternity)

是一个函数调用，它返回一个函数(lambda (l) …)，0如果调用一个空列表，则返回一个函数，并进入一个非空列表的无限循环。

从程序分析的角度来看，值得注意的是，还有其他值不会进入无限循环。例如，如果你用一个字符串调用它，那么(cdr l)将是一个错误。

于 2013-10-23T15:35:43.900 回答
2

就像你说的，这是将长度函数定义为部分函数，​​它只为空列表完成。但这还没有到 y-combinator 部分，它不是一个匿名函数调用自身的例子。

l是一个原子列表，它是计算时返回的函数的参数(lambda (len) ...)。

len是作为参数传递给外部 lambda 的函数。

外部表达式创建一个eternity传入的 lambda 作为其参数。外部 lambda 返回一个通过评估内部 lambda 创建的函数，返回的函数是eternity作为参数的东西。

如果代码被传递一个空列表（意味着将整个第一部分包装'()在另一组括号中），那么它当然会评估为 0。len永远不会被评估。

如果代码传递了一个非空的纬度，那么它将尝试评估len参数并且你得到一个无限递归。

于 2013-10-23T15:04:37.157 回答