The Self-Reference Problem

The Problem

Consider computing factorial. In informal notation:

FACT n = IF (ISZERO n) ONE (MUL n (FACT (PRED n)))

This says: if n is zero, return one. Otherwise, multiply n by the factorial of n minus one. The definition works — but it refers to FACT inside its own body.

In lambda calculus, there are no names. Every function is an anonymous λx.body. There is no mechanism to say "call this function again." The body of a lambda term can refer to its parameter, but not to the function itself.

This is the self-reference problem: how can an anonymous function invoke itself?

No Names

Lambda calculus has exactly three kinds of terms:

• Variables: x, y, z
• Abstractions: λx.M
• Applications: M N

There is no def, no let, no where. There is no mechanism to say "let FACT equal this function." A variable inside a lambda body refers to a parameter bound by some enclosing λ -- it does not refer to the function itself.

In the print shop, a blank slug refers to a tag on this stick or an outer stick. No slug can say "this stick." The stick is the context, not a value.

Defining Factorial

Here is an informal definition of factorial:

FACT n = IF (ISZERO n) ONE (MUL n (FACT (PRED n)))

Read it carefully. The right side uses FACT -- the very thing being defined. In everyday math, this is fine: we write recursive definitions all the time. But translate this to lambda calculus:

FACT = λn. IF (ISZERO n) ONE (MUL n (??? (PRED n)))

What goes in place of ???? We want to write FACT, but FACT is just a label we invented. It is not a variable bound by any $\lambda$. It is not a term we can substitute. The definition is circular: it requires FACT to already exist in order to define FACT.

The Circular Need

The self-reference problem in one sentence: the function body needs access to the function itself.

In a language with names, this is easy:

def fact(n): return 1 if n == 0 else n * fact(n-1)

The name fact is in scope inside its own body. But in lambda calculus, λn.body gives the body access to n and nothing else. The body cannot see the function it lives in.

A lambda function can receive anything as an argument. What if the function received a copy of itself as an extra argument? Then the body would have something to call for the recursive step.

This is not yet a solution -- it is the shape of the solution. The question is: who provides the copy?

What We Need

The self-reference problem comes down to one thing.

A recursive function needs to call itself. But in lambda calculus, functions are anonymous. The body of λx.M can use x, but cannot reference the function λx.M.

The only way a lambda body can access something is if that something is passed in as an argument. So a recursive function needs to receive a copy of the function as an argument.

We need a way to give a function a copy of _____.

Foreshadowing

In Topic 04, you encountered self-application: λx.x x.

This function takes an argument and applies it to itself:

(λx.x x) a →β a a

When the argument is another self-application function, the result reproduces the original setup:

(λx.x x)(λx.x x) →β (λx.x x)(λx.x x) = Ω

That was divergence -- infinite repetition with no progress. But the mechanism is interesting: a function that can feed itself to itself. What if we could harness that mechanism -- self-application with a purpose -- to achieve controlled repetition instead of infinite loops?