Lambda Calculus Encoding and Fixed-Point Combinators

Understanding Lambda Calculus Encodings

Lambda calculus provides a minimalistic yet powerful framework for representing data and computation using only functions. In this course we explore how common programming constructs—pairs, booleans, numbers, and recursion—are encoded in pure lambda calculus, and we examine the behavior of the famous fixed‑point combinator Y. Each section builds on the quiz questions, turning the multiple‑choice items into deeper learning material.

1. Pair Encodings and Projection Functions

In the Church encoding, a pair pair v w is defined as a function that takes a selector f and applies it to both components:

• Definition: pair ≡ λv.λw.λf. f v w

Two projection functions retrieve the components:

• first (or left): first ≡ λp. p (λv.λw. v)
• second (or right): second ≡ λp. p (λv.λw. w)

When we apply first to a pair, the selector λv.λw. v discards the second argument and returns the first one. Therefore, the reduction sequence is:

first (pair v w)
→ (λp. p (λv.λw. v)) (λv.λw.λf. f v w)
→ (λv.λw.λf. f v w) (λv.λw. v)
→ λw. (λv.λw. v) v w
→ λw. v
→ v

Key takeaway: first (pair v w) reduces to v, the first component of the pair.

2. Boolean Logic in Lambda Calculus

Booleans are encoded as functions that choose between two alternatives:

• true: λa.λb. a
• false: λa.λb. b

Using these definitions, we can construct logical operators. The AND operator must return true only when both arguments are true. Its correct encoding is:

AND ≡ λa.λb. a b false

Explanation of the reduction:

• If a = true, the term becomes true b false → b, which yields true only when b is also true.
• If a = false, the term becomes false b false → false, regardless of b.

Thus the expression λa.λb. a b false faithfully implements logical conjunction.

3. Church Numerals and Arithmetic

Natural numbers are represented as iterated applications of a successor function s to a base value z:

0 ≡ λs.λz. z
1 ≡ λs.λz. s z
2 ≡ λs.λz. s (s z)
3 ≡ λs.λz. s (s (s z))
⋯

Therefore the numeral 3 is encoded as λs.λz. s (s (s z)). This representation makes addition, multiplication, and exponentiation simple to define via function composition.

4. Self‑Application and Divergence

The term L ≡ (λx. x x) (λx. x x) is a classic example of a non‑terminating expression. Reducing L yields:

L → (λx. x x) (λx. x x)
   → (λx. x x) (λx. x x)   // the same term appears again
   → …

Because the reduction repeats indefinitely, L has no normal form. In lambda calculus terminology, the term diverges.

5. Evaluation Strategies and Reduction Order

Consider the application (λx.λy. y) L v. The outer lambda abstracts two parameters, but the body returns the second one (y) and completely ignores the first (x). Under normal order (evaluate the leftmost outermost redex first), the reduction proceeds as:

(λx.λy. y) L v
→ (λy. y) v          // x is substituted by L, but never used
→ v

Notice that L is never evaluated. This illustrates an important property of lazy (normal‑order) evaluation: arguments are only reduced when needed.

6. Fixed‑Point Combinators and Recursion

The fixed‑point combinator Y enables recursion without naming functions. Its definition is:

Y ≡ λg. (λx. g (x x)) (λx. g (x x))

Applying Y to a function g yields a term that satisfies the equation Y g ≡ g (Y g). Both sides expand to the same infinite unfolding of g, which is why they are β‑equivalent. This property is the cornerstone of defining recursive functions such as factorial or the even‑odd test.

7. Recursive Definitions Using Y

To define the predicate even on Church numerals, we need an auxiliary term that detects zero. The standard iszero combinator is:

iszero ≡ λn. n (λx. false) true

It applies the numeral n to a function that always returns false; if n is zero, the base case true is returned. Using Y, the recursive definition becomes:

even ≡ Y (λe. λn. iszero n true (e (pred n)))

Here pred is the predecessor function, and iszero decides when the recursion should stop.

8. Building Complex Boolean Operators

Having defined and, or, and not, we can express exclusive‑or (xor) as:

XOR ≡ λa.λb. or (and a (not b)) (and (not a) b)

This formulation captures the intuitive truth table: xor is true exactly when one of the arguments is true and the other is false.

9. Summary of Key Encodings

• Pairs: pair ≡ λv.λw.λf. f v w
• First projection: first ≡ λp. p (λv.λw. v)
• Booleans: true ≡ λa.λb. a, false ≡ λa.λb. b
• AND: λa.λb. a b false
• OR: λa.λb. a a b (not shown in quiz but useful)
• NOT: λa. a false true
• XOR: λa.λb. or (and a (not b)) (and (not a) b)
• Church numeral n: λs.λz. sⁿ z
• Y combinator: λg. (λx. g (x x)) (λx. g (x x))

10. Frequently Asked Questions (FAQ)

• Why does first (pair v w) return v? The selector passed to the pair selects the first argument, discarding the second.
• Can we use applicative order (eager) evaluation with these encodings? Yes, but some terms like L will still diverge; lazy evaluation simply postpones unnecessary work.
• How does the Y combinator avoid naming a function recursively? It creates a self‑referential structure by passing a function to itself, achieving recursion through fixed‑point semantics.
• What is the role of iszero in recursive definitions? It acts as the base‑case test, ensuring recursion terminates when the numeral reaches zero.

11. Further Reading and Practice

To solidify your understanding, try encoding additional arithmetic operations (addition, multiplication) and more complex data structures (lists, trees) using the same principles. Explore how the Y combinator can define the factorial function:

FACT ≡ Y (λf. λn. iszero n 1 (mult n (f (pred n))))

Experiment with both normal‑order and applicative‑order reductions to see how evaluation strategy influences performance and termination.

By mastering these encodings, you gain a deeper appreciation of the expressive power of lambda calculus—a foundation that underlies functional programming languages such as Haskell, Scheme, and modern JavaScript functional patterns.