The Y Combinator

Courtesy of CS 145

What is Lambda Calculus?

Lambda calculus is a minimal system that models computation using functions built up from variables, function definition, and function application. Despite its simplicity, lambda calculus is Turing complete, meaning it can model any computation

In essence, the lambda calculus is the most simple form of programming

Some key things in lambda calculus include:

Variables bound in function definitions
Anonymous function definitions using lambda expressions
Function application

Some key things that lambda calculus does NOT include:

Basic data structures (numbers, booleans, lists)
Any form of control flow
Recursive applications

Today, I want to go over how to build these features. I'll show how to encode booleans as a gentle introduction. Then we will jump into the crux of how we do recursion in the lambda calculus

I'll be using scheme/Racket to write all my lambdas

Encoding Boolean Data

; True 
(lambda (x y) x)

; False
(lambda (x y) y)

True and False are used to distinguish between two different things, and from here we can make all logical operators

In essence, that's what True and False are — simply a way to distinguish one thing from another

NOT

; NOT
(lambda (bool)
      (bool
          (lambda (x y) y) ; FALSE
          (lambda (x y) x) ; TRUE
      )
)

If bool is TRUE, it will return (lambda (x y) y) — which is false

If bool is FALSE, it will return (lambda (x y) x) — which is true

AND

; AND
(lambda (bool1 bool2)
  (bool1 
      bool2 (lambda (x y) y)
  )
)

AND will only return true if both bool1 and bool2 are both true. You can step through this example by setting up a truth table and evaluating all possible combinations of booleans

This is called β-reduction and is extremely important for writing complex programs in the lambda calculus

; OR
(lambda (bool1 bool2)
    (bool1 
        (lambda (x y) x) bool2
    )  
)

XOR

; XOR

(lambda (bool1 bool2)
  (
    bool1
        (NOT bool2)
        bool2
  )
)

For XOR, I am cheating a bit here by using a defined version of NOT. This goes against the rules of lambda calculus where we do not store any functions in memory. Here I use the keyword NOT as a shortcut so I don't need to write the entire lambda within the function

Don't think about how we derived each of these expressions (that was Alonzo Church's job)

Just know that we can represent any data expression in the lambda calculus — as a challenge, think about how you'd implement an If statement in the lambda calculus

How do we do numbers in the lambda calculus

There are many ways to define natural numbers in lambda calculus. I won't go over them in this blog, but I'll link some great videos.

The primary modes of expression natural numbers

Great, now that we know the basics of how the lambda calculus work, let's see how we do recursion in it

What is recursion?

"Defining things in terms of themselves"

Popular example — factorials

(define (factorial n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))
  )
)

What is the key to recursion in Lambda Calculus?

Well, it all has to do with self-application!

The simplest type of recursion is the following

(define (loop)
  (loop)
)

To evaluate loop, we call loop, which makes use evaluate loop, and so on

This loop is not legal in the lambda calculus, since we are defining the keyword loop and having to save it in memory

How can we just do this with anonymous lambdas?

(
 (lambda (x) (x x))
 (lambda (x) (x x))
)

=>

(
 (lambda (x) (x x))
 (lambda (x) (x x))
)

We call this the Z-Combinator, an infinitely expanding lambda expression. It's a bridge to helping us define general recursion in the lambda calculus, and repeated computation

How does this relate to the Y Combinator?

$$ \lambda f. (\lambda x. (f (x,x))) (\lambda x. (f (x,x))) $$ The Y Combinator is a way to name your function in a language that does not allow such pointers. It proves that function names, classes, etc. are just syntactic sugar

Think of it as a beautiful quine that gives our meaningless lambdas life — the bridge to Turing completeness

Take this factorial example

#lang lazy

(define fact
  (lambda (n)
    ((
      (lambda (self)
        (lambda (x)
          (if (= x 0)
              1
            (* x ((self self) (sub1 x))))))
      (lambda (self)
        (lambda (x)
          (if (= x 0)
              1
        (* x ((self self) (sub1 x)))))))
     n)))

We use define just to set fact as a temporary place holder, but otherwise we aren't storing any memory pointers for funcitons

The trick here is passing a duplicate of the function into itself again, so it can be ran just like our Z Combinator

(lambda (self)
        (lambda (x)
          (if (= x 0)
              1
            (* x ((self self) (sub1 x))))))

this accepts the argument self to be, well, itself, in the second part where it's copied. It then also takes in x to be n through the outermost layer

You can also see this in the recursive step where the function breaks itself down

((self self) (sub1 x))

This will repeat and repeat and create more and mroe functions until our call stack is complete at the end when x=0 and our entire function can resolve

ALSO — extremely important point

We are using LAZY evaluation here. That means that we do not try to evaluate the entire function immediately, but only each step as it came

If we tried resolving a whole stack of calls to make pre-compile, we would run out of memory, as our function would be a repeat of f(f(f(Y(f)))) so on and so on

Here's a more pure implementation of the Y combinator in Racket