Page:AIM-453.djvu/72

From Wikisource
Jump to navigation Jump to search
There was a problem when proofreading this page.
Steele and Sussman
70
The Art of the Interpreter

{Y-operator} Pages 26, 57

While the interpreter of Figure 8 cannot DEFINE recursive procedures, it is possible to define recursive procedures by using a variant of the "paradoxical combinator", also known as the Y-operator:

(DEFINE (Y F)
        ((LAMBDA (G)
                 (LAMBDA (X)
                         ((F (G G)) X)))
         (LAMBDA (G)
                 (LAMBDA (X)
                         ((F (G G)) X)))))

Using this we define the doubly-recursive algorithm for computing the Fibonacci function:

(DEFINE (FIB K)
        ((Y (LAMBDA (F)
                    (LAMBDA (N)
                            (COND ((= N 0) 1)
                                  ((= N 1) 1)
                                  (T (+ (F (- N 1)) (F (- N 2))))))))
         K))

That this manages to work is truly remarkable. Notice that this is almost identical to the LABEL construct which was actually introduced by LISP 1, though at the time it was invented the implementors didn't realize this correspondence [LISP History].