Lambda Calculus and the Y Combinator

28.1 Lambda Calculus Basics

Lambda calculus (Alonzo Church, 1930s) has only three constructs: variables, abstraction λx.M, and application M N. Lisp's lambda comes directly from it.

28.2 Church Encodings

;; Booleans
(define TRUE  (lambda (a) (lambda (b) a)))
(define FALSE (lambda (a) (lambda (b) b)))
(define IF    (lambda (c) (lambda (t) (lambda (e) ((c t) e)))))
(((IF TRUE) 'yes) 'no)                   ; yes

;; Numerals: n = apply f n times
(define ZERO (lambda (f) (lambda (x) x)))
(define (SUCC n) (lambda (f) (lambda (x) (f ((n f) x)))))
(define (ADD m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
(define (church->int n) ((n (lambda (x) (+ x 1))) 0))
(church->int (ADD (SUCC ZERO) (SUCC (SUCC ZERO))))   ; 3

;; Pairs
(define (PAIR a b) (lambda (sel) (sel a b)))
(define (FST p) (p (lambda (a b) a)))
(define (SND p) (p (lambda (a b) b)))
(FST (PAIR 1 2))                         ; 1

28.3 The Y Combinator: Recursion Without Names

The Y combinator shows that recursion can be built from anonymous functions alone, the theoretical foundation behind letrec and recursive definitions.

;; Applicative-order Y combinator (Z combinator)
(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (v) ((x x) v))))
     (lambda (x) (f (lambda (v) ((x x) v)))))))

(define factorial
  (Y (lambda (self)
       (lambda (n)
         (if (= n 0) 1 (* n (self (- n 1))))))))
(factorial 5)                            ; 120