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*
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 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?
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]
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?)
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).
