Notes on Y Operator

Spring 2003 - Michael Elhadad

Recursion in Lambda Calculus

This is a short note on the Y-operator. There are no define and letrec primitives in the Lambda calculus that allow us to attach a procedure to a name. How then can we define recursive procedures in pure lambda calculus? The following discussion just gives a flavor of the solution. Assume we are looking for a way to define the factorial procedure. There is no way to define the name "fact". The only way we can refer to a name is by defining a binding for this name. So we define the following expression:

(lambda (fact)
  (lambda (n) 
    (if (= n 0) 1 (* n (fact (- n 1))))))

Call this expression f. We are now looking for a way to define the value fact such that (f fact) is equal to the factorial procedure. This fact procedure, if it exists, can only depend on the form of the expression f. We note this in functional terms as:

fact = (Y f)

If such an operator Y can be found, it then fulfils the following condition:

(f (Y f)) = (Y f)

That is, Y is the operator that when applied to a function returns its fixed point. Extraordinarily, such an operator can be defined in pure lambda calculus and is completely general. Its value is:

Y = (lambda (f) 
     ((lambda (x) (f (x x))) 
      (lambda (x) (f (x x)))))

When using applicative-order strategy, the following form must be used to avoid divergence:

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (y) ((x x) y))))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

You can verify in Scheme that:

(define fy
  (Y (lambda (fact) 
       (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))))

(fy 5) --> 120

From: Barzilay Eliyahu 
Date: Thu, 12 Dec 1996 18:40:06 +0200

(lambda (f)
  ((lambda (x) (f (x x)))
   (lambda (x) (f (x x)))))
(lambda (f)
  ((lambda (x) (f (lambda (y) ((x x) y))))
   (lambda (x) (f (lambda (y) ((x x) y))))))

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (y) ((x x) y))))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

(define fact0
  (lambda (g)
    (lambda (n) (if (= n 0) 1 (* n (g (1- n)))))))

(define fact (Y fact0))

(fact 3)
--->>> using fact definition
((Y fact) 3)
--->>> using Y definition
(((lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
               (lambda (x) (f (lambda (y) ((x x) y)))))) fact0) 3)
--->>> apply fact0 to (lambda (f)...
(((lambda (x) (fact0 (lambda (y) ((x x) y))))
  (lambda (x) (fact0 (lambda (y) ((x x) y))))) 3)
--->>> apply (lambda (x)... to (lambda (x)...
((fact0 (lambda (y) (((lambda (x) (fact0 (lambda (y) ((x x) y))))
                      (lambda (x) (fact0 (lambda (y) ((x x) y))))) y))) 3)
--->>> using fact0 definition
(((lambda (g)
    (lambda (n) (if (= n 0) 1 (* n (g (1- n))))))
  (lambda (y) (((lambda (x) (fact0 (lambda (y) ((x x) y))))
                (lambda (x) (fact0 (lambda (y) ((x x) y))))) y))) 3)
--->>> apply (lambda (y)... to (lambda (g)...
((lambda (n) (if (= n 0)
                1
                (* n ((lambda (y)
                        (((lambda (x) (fact0 (lambda (y) ((x x) y))))
                          (lambda (x) (fact0 (lambda (y) ((x x) y)))))
                         y)) (1- n))))) 3)
--->>> apply 3 to (lambda (n)...
(if (= 3 0)
    1
    (* 3 ((lambda (y)
            (((lambda (x) (fact0 (lambda (y) ((x x) y))))
              (lambda (x) (fact0 (lambda (y) ((x x) y)))))
             y)) (1- 3))))
--->>> compute if, 1-
(* 3 ((lambda (y)
        (((lambda (x) (fact0 (lambda (y) ((x x) y))))
          (lambda (x) (fact0 (lambda (y) ((x x) y)))))
         y)) 2))
--->>> apply 2 to (lambda (y)...
(* 3 (((lambda (x) (fact0 (lambda (y) ((x x) y))))
       (lambda (x) (fact0 (lambda (y) ((x x) y)))))
      2))
...


;;;=============================================================================
;;;=============================================================================
;;;=============================================================================
(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (y) ((x x) y))))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

;;;-----------------------------------------------------------------------------
;;; Normal

(define fact
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (1- n))))))
(fact 6)

(define fact0
  (lambda (g)
    (lambda (n)
      (if (zero? n)
          1
          (* n (g (1- n)))))))
(define fact (Y fact0))
(fact 6)

;;;-----------------------------------------------------------------------------
;;; Multiple variables - using cons

(define fact
  (lambda (n c)
    (if (zero? n)
        c
        (* n (fact (1- n) c)))))
(fact 6 2)

(define fact0
  (lambda (g)
    (lambda (n)
      (if (zero? (car n))
          (cdr n)
          (* (car n) (g (cons (1- (car n)) (cdr n))))))))
(define fact (lambda (n c) ((Y fact0) (cons n c))))
(fact 6 2)

;;;-----------------------------------------------------------------------------
;;; Multiple variables - using lambda's

(define fact
  (lambda (n c)
    (if (zero? n)
        c
        (* n (fact (1- n) c)))))
(fact 6 2)

(define (make-pair x y) (lambda (s) (s x y)))
(define (1st pair) (pair (lambda (x y) x)))
(define (2nd pair) (pair (lambda (x y) y)))

(define fact0
  (lambda (g)
    (lambda (n)
      (if (zero? (1st n))
          (2nd n)
          (* (1st n) (g (make-pair (1- (1st n)) (2nd n))))))))
(define fact (lambda (n c) ((Y fact0) (make-pair n c))))
(fact 6 2)

;;;-----------------------------------------------------------------------------
;;; Multiple variables - using currying

(define fact
  (lambda (n)
    (lambda (c)
      (if (zero? n)
          c
          (* n ((fact (1- n)) c))))))
((fact 6) 2)

(define fact0
  (lambda (g)
    (lambda (n)
      (lambda (c)
        (if (zero? n)
            c
            (* n ((g (1- n)) c)))))))
(define fact (Y fact0))
((fact 6) 2)

;;; Switch args
(define fact0
  (lambda (g)
    (lambda (c)
      (lambda (n)
        (if (zero? n)
            c
            (* n ((g c) (1- n))))))))
(define fact (Y fact0))
((fact 2) 6)

;;;-----------------------------------------------------------------------------
;;; Multiple variables going down

(define get-nth
  (lambda (l n)
    (if (zero? n)
        (car l)
        (get-nth (cdr l) (1- n)))))
(get-nth '(1 2 3 4 5) 2)

;;; Using lambda-cons
(define get-nth0
  (lambda (g)
    (lambda (pair)
      (if (zero? (2nd pair))
          (car (1st pair))
          (g (make-pair (cdr (1st pair)) (1- (2nd pair))))))))
(define get-nth (lambda (l n) ((Y get-nth0) (make-pair l n))))
(get-nth '(1 2 3 4 5) 2)

;;; Using currying
(define get-nth0
  (lambda (g)
    (lambda (l)
      (lambda (n)
        (if (zero? n)
            (car l)
            ((g (cdr l)) (1- n)))))))
(define get-nth (lambda (l n) (((Y get-nth0) l) n)))
(get-nth '(1 2 3 4 5) 2)

;;;-----------------------------------------------------------------------------
;;; Mutual recursion

(define (even? n)
  (if (zero? n)
      #t
      (odd? (1- n))))
(define (odd? n)
  (if (zero? n)
      #f
      (even? (1- n))))
(odd? 15)
(even? 15)

(define (make-pair x y) (lambda (s) (s x y)))
(define (1st pair) (pair (lambda (x y) x)))
(define (2nd pair) (pair (lambda (x y) y)))

;;; Version with two function structure and with normal recursion
(define even/odd?
  (make-pair
   (lambda (n)
     (if (zero? n)
         #t
         ((2nd even/odd?) (1- n))))
   (lambda (n)
     (if (zero? n)
         #f
         ((1st even/odd?) (1- n))))))
(define even? (1st even/odd?))
(define odd?  (2nd even/odd?))
(odd? 15)
(even? 15)

;;; Make the above with the Y fixpoint operator
(define even/odd?0
  (lambda (g)
    (make-pair
     (lambda (n)
       (if (zero? n)
           #t
           ((2nd g) (1- n))))
     (lambda (n)
       (if (zero? n)
           #f
           ((1st g) (1- n)))))))
(define even/odd? (Y even/odd?0))
(define even? (1st even/odd?))
(define odd?  (2nd even/odd?))
(odd? 15)
(even? 15)

;;;-----------------------------------------------------------------------------
;;; Multiple arguments using different delay mechanism

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (y1 y2) ((x x) y1 y2))))
     (lambda (x) (f (lambda (y1 y2) ((x x) y1 y2)))))))

(define fact
  (lambda (n c)
    (if (zero? n)
        c
        (* n (fact (1- n) c)))))
(fact 6 2)

(define fact0
  (lambda (g)
    (lambda (n c)
      (if (zero? n)
          c
          (* n (g (1- n) c))))))
(define fact (Y fact0))
(fact 6 2)

;;;-----------------------------------------------------------------------------
;;; Multiple arguments using general delay mechanism

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda args (apply (x x) args))))
     (lambda (x) (f (lambda args (apply (x x) args)))))))

(define fact0
  (lambda (g)
    (lambda (n c)
      (if (zero? n)
          c
          (* n (g (1- n) c))))))
(define fact (Y fact0))

;;;-----------------------------------------------------------------------------
;;; Using delay solves the problem with no apply but need to force g

(define Y
  (lambda (f)
    ((lambda (x) (f (delay (x x))))
     (lambda (x) (f (delay (x x)))))))

(define fact0
  (lambda (g)
    (lambda (n c)
      (if (zero? n)
          c
          (* n ((force g) (1- n) c))))))
(define fact (Y fact0))
(fact 6 2)

;;;-----------------------------------------------------------------------------
;;; Dropping first delay does not matter if second one goes beyond the f

(define Y
  (lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (delay (f (x x)))))))

(define fact0
  (lambda (g)
    (lambda (n c)
      (if (zero? n)
          c
          (* n ((force g) (1- n) c))))))
(define fact (Y fact0))
(fact 6 2)

;;; This is what happens:
(fact 6 2)
((Y fact0) 6 2)
(((lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (delay (f (x x)))))) fact0) 6 2)
(((lambda (x) (fact0 (x x)))
  (lambda (x) (delay (fact0 (x x))))) 6 2)
((fact0 ((lambda (x) (delay (fact0 (x x))))
         (lambda (x) (delay (fact0 (x x)))))) 6 2)
(((lambda (g)
    (lambda (n c)
      (if (zero? n)
          c
          (* n ((force g) (1- n) c)))))
  ((lambda (x) (delay (fact0 (x x))))
   (lambda (x) (delay (fact0 (x x)))))) 6 2)
((lambda (n c)
   (if (zero? n)
       c
       (* n ((force ((lambda (x) (delay (fact0 (x x))))
                     (lambda (x) (delay (fact0 (x x)))))) (1- n) c)))) 6 2)
(if (zero? 6)
    2
    (* 6 ((force ((lambda (x) (delay (fact0 (x x))))
                  (lambda (x) (delay (fact0 (x x)))))) (1- 6) 2)))
(* 6 ((force ((lambda (x) (delay (fact0 (x x))))
              (lambda (x) (delay (fact0 (x x)))))) 5 2))
(* 6 ((force (delay (fact0 ((lambda (x) (delay (fact0 (x x))))
                            (lambda (x) (delay (fact0 (x x)))))))) 5 2))
(* 6 ((fact0 ((lambda (x) (delay (fact0 (x x))))
              (lambda (x) (delay (fact0 (x x)))))) 5 2))
...

;;;-----------------------------------------------------------------------------
;;; With this version we can use as many variables as we want and even non
;;; functions - like the even/odd example from above with cons & car/cdr!

(define Y
  (lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (delay (f (x x)))))))

(define even/odd?0
  (lambda (g)
    (cons
     (lambda (n)
       (if (zero? n)
           #t
           ((cdr (force g)) (1- n))))
     (lambda (n)
       (if (zero? n)
           #f
           ((car (force g)) (1- n)))))))
(define even/odd? (Y even/odd?0))
(define even? (car even/odd?))
(define odd?  (cdr even/odd?))
(odd? 15)
(even? 15)

Last modified 24 June 2001 Michael Elhadad