Page:AIM-453.djvu/72

---

 

{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].