functional-programming - LISP 中的 REVERSE 函数

Question

任何人都可以详细解释以下纯 LISP 函数的工作原理:

(DEFINE (REVERSE (LAMBDA (L)
        (REV NIL L))))
(DEFINE (REV (LAMBDA (OUT IN)
        (COND ((NULL IN) OUT)
        (T (REV (CONS (CAR IN) OUT) (CDR IN))))))

该函数应该反转列表中元素的顺序，这很清楚，但我仍然无法理解它是如何工作的。

*编辑*

好吧，我相信我想通了。REVERSE 函数以列表作为参数调用，并调用 REV 函数并使用 NIL 和该列表 L作为参数。

REV:OUT 绑定(bind)到 NIL，IN 绑定(bind)到列表 L。现在，如果第一个参数 (IN) 为空 (NULL?) 我们就完成了，我们可以返回 OUT，这是列表，成功逆转。否则，我们必须继续递归调用 REV，其中 OUT+IN 的第一个元素 作为第一个参数，IN 的其余部分 作为第二个参数.这是它的工作原理吗？

唯一的问题是:这里的 LAMBDA 是怎么回事？

Answer 1

是的，这就是它的工作原理。这被称为编写 tail recursive 的累加器参数技术。功能。它有助于通过一些示例可视化其操作，例如

reverse [1,2,3,4] 
  = rev  NIL  [1,2,3,4]
  = rev  [1]    [2,3,4]
  = rev  [2,1]    [3,4]
  = rev  [3,2,1]    [4]
  = rev  [4,3,2,1]  NIL
  = [4,3,2,1]

您的代码似乎来自旧书(1982 年第 1 版，ISBN 0-471-08755-6)textbook .在今天的方案中，例如它的写法几乎相同，但没有额外的括号(重新定义了几个常量):

(define reverse (lambda (l) .... ))
(define rev (lambda (out in) .... ))

(define NIL '())
(define T    #t)
(define NULL null?)

所谓的“lambda 形式”，即以 lambda“关键字”开头的形式(格式良好，带括号的代码片段)，表示匿名函数。符号lambda 之后的列表指定了此类函数的形式参数。 define 允许我们命名由 lambda 形式创建的函数。这样我们就可以在它的定义中使用它的名字递归调用它。

这个递归调用在tail position ，所以这个函数的操作相当于一个循环(通过重用stack frame来实现函数调用，在每次迭代时重置形式参数，从而作为循环变量)。