Learning the Y Combinator

The y-combinator provides a way to represent recursive functions inside the λ-calculus. To explain how the y-combinator works, I've shown the process of a factorial function being transformed from typical Scheme to nothing but single argument anonymous functions, the only object allowed in the λ-calculus.

;; Start with a normal factorial function.
(define (factorial x)
  (if (zero? x)
      1
      (* x (factorial (sub1 x)))))

The λ-calculus only has anonymous functions, so we can't define factorial recursively. Instead of using a recursive definition, we make the procedure take itself as an argument.

;; Returns 720
(let ([factorial (λ (recurse x)
		   (if (zero? x)
		       1
		       (* x (recurse recurse (sub1 x)))))])
  (factorial factorial 6))

The λ-calcus doesn't support functions that take multiple arguments, so lets break our function up with currying. Currying a function makes it so that if it's called with one argument, a function that returns the next argument will be returned. This continues until the last argument is given. Then the expression in the body of the function returns.

;; Returns 720
(let ([factorial (λ (recurse)
		   (λ (x)
		     (if (zero? x)
			 1
			 (* x ((recurse recurse) (sub1 x))))))])
  ((factorial factorial) 6))

The λ-calclus doesn't have let bindings, but we can name local variable by using functions.

;; Returns 720
((λ (factorial)
   ((factorial factorial) 6))
 (λ (recurse)
   (λ (x)
     (if (zero? x)
	 1
	 (* x ((recurse recurse) (sub1 x)))))))

In the first lambda, the name factorial is too specific. Any function could be passed in, so there's no reason to use the name 'factorial'. Lets rename 'factorial' to 'f' instead. Now it's clear that other functions can be passed to our first lambda.

;; Returns 720
((λ (f)
   ((f f) 6))
 (λ (recurse)
   (λ (x)
     (if (zero? x)
	 1
	 (* x ((recurse recurse) (sub1 x)))))))

While we're making things more general. Lets replace our six with a new argument.

;; Returns 720
((λ (f x)
   ((f f) x))
 (λ (recurse)
   (λ (x)
     (if (zero? x)
	 1
	 (* x ((recurse recurse) (sub1 x))))))
 6)

Multiple arguments aren't allowed in the λ-calculus, so we'll curry our new lambda.

;; Returns 720
(((λ (f)
    (λ (x)
      ((f f) x)))
  (λ (recurse)
    (λ (x)
      (if (zero? x)
	  1
	  (* x ((recurse recurse) (sub1 x)))))))
 6)

Now if we rename recurse to f, our outer function matches the y-combinator. The lambda with the factorial logic is what's passed into the y-combinator. Then the function created by it is called with 6. See if you can see the resemblance between the equation and the code. Remember that the code includes some extra logic for the factorial function. λ f.(λ x.f (x x)) (λ x.f (x x))

;; Returns 720
(((λ (f)
    (λ (x)
      ((f f) x)))
  (λ (f)
    (λ (x)
      (if (zero? x)
	  1
	  (* x ((f f) (sub1 x)))))))
 6)

All functions passed into the y-combinator will look like the following.

(λ (recurse)
  (λ (x)
    ...))

When we make a recursive call, we want to pass in the function we can recurse with, but since we only have single argument functions, the call looks weird. Every argument belongs to a different application.

((recurse recurse) x)

Here's a length function. Notice the currying inside the y-combinator.

;; An example of a length function.
;; Returns 5
(((λ (f)
    (λ (x)
      ((f f) x))) ;; This is where the currying happens. We call our function with itself and a single argument.
  (λ (f)
    (λ (x)
      (if (null? x)
	  0
	  (+ 1 ((f f) (rest x)))))))
 '(1 2 3 4 5))

We can have recursive functions that take more than one argument too, but we have to change the combinator or represent arguments a different way.

(λ (recurse)
  (λ (x)
    (λ (y)
      ...)))

An example of a map function.

;; Returns '(1 2 3)
((((λ (f)
     (λ (x)
       ((f f) x)))
   (λ (f)
     (λ (map-f)
       (λ (map-lst)
	 (if (null? map-lst)
	     empty
	     (cons (map-f (first map-lst))
		   (((f f) map-f) (rest map-lst))))))))
  add1)
 '(0 1 2))