LISP中的REVERSE功能 [英] REVERSE function in LISP

问题描述

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

Could anybody explain in detail how the following pure LISP function works:

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

该函数应该颠倒列表中元素的顺序，这很明显，但是我仍然无法理解它是如何工作的.

The function should reverse the order of the elements in a list, that's clear, but I am still unable to understand how it works.

* EDIT *

*EDIT*

好的，我相信我已经知道了. REVERSE函数以列表作为参数调用，并调用REV函数以NIL和列表L作为参数.

okay i believe i figured it out. The REVERSE function is called with a list as argument, and calls a REV function with NIL and that list L as arguments.

REV :OUT绑定到NIL，而IN绑定到列表L. 现在，如果第一个参数(IN)为空(NULL?)，我们完成了操作，我们可以成功地返回列表的OUT. 否则，我们必须以OUT+the first element of IN作为第一个参数并以rest of IN作为第二个参数来递归调用REV.这是怎么运作的?

REV: OUT is bound to NIL and IN is bound to the list L. Now, if the first argument (IN) is empty (NULL?) we are done and we can return OUT, which is the list, successfully reversed. Otherwise we have to continue by recursively calling REV with OUT+the first element of IN as first argument and the rest of IN as the second argument. Is this how it works?

唯一的问题是:这里的LAMBDA是什么?

The only question is: What's about the LAMBDA thing here?

推荐答案

是的，它是这样工作的.这称为用于编写尾递归函数的累加器参数技术.举例来说，它有助于形象化其操作.

Yes, it is how it works. This is known as accumulator argument technique for writing tail recursive functions. It helps to visualize its operation with some example, e.g.

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年第一版，ISBN 0-471-08755-6)教科书.在今天的计划中它的写法几乎相同，但是没有多余的括号(重新定义了几个常量):

It seems your code comes from an oldish (1st ed. 1982, ISBN 0-471-08755-6) textbook. In today's Scheme e.g. it's written almost the same, but without the extra parentheses (with few constants redefined):

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

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

所谓的"lambda形式"，即以lambda关键字"开头的形式(形式良好，带括号的代码段)表示匿名功能.符号lambda之后的列表指定了该功能的形式参数. define允许我们命名由lambda形式创建的函数.这样，我们可以使用其名称在其定义内对其进行递归调用.

The so-called "lambda forms", i.e. forms (well-formed, parenthesized snippets of code) starting with lambda "keyword", signify anonymous functions. The list after the symbol lambda specifies formal parameters of such function. define allows us to name the function created by a lambda-form. That way we can make recursive call to it inside its definition, using its name.

此递归调用位于尾部位置中，因此此功能的操作等效于循环(通过对函数调用重新使用堆栈框架，重置形式参数来实现在每次迭代中用作循环变量).

This recursive call is in tail position, so the operation of this function is equivalent to a loop (achieved by reusing the stack frame for the function call, resetting the formal parameters on each iteration which thus serve as loop variables).

这篇关于LISP中的REVERSE功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！