What does (λx.λy.x) applied to TRUE and then to FALSE reduce to?
AFALSE — the inner function returns the second argument
BTRUE — after two beta reductions, the body is TRUE with y discarded
Cλy.TRUE — the expression cannot reduce further without knowing FALSE
DIt is undefined because TRUE and FALSE are not built-in values
Beta reduction substitutes the argument for the bound variable. (λx.λy.x) TRUE → (λy.TRUE); then (λy.TRUE) FALSE → TRUE (y is discarded). This illustrates how Church-encoded booleans work: TRUE = λx.λy.x is a function that picks its first argument and ignores the second. The wrong answers reflect the misconception that TRUE/FALSE must be primitive values — in lambda calculus they are functions.
Question 2 Multiple Choice
A compiler implements closures by capturing the environment at the point a function is defined. Which lambda calculus concept directly corresponds to this mechanism?
AAlpha conversion — renaming bound variables to avoid conflicts
BBeta reduction — substituting arguments into function bodies
CVariable capture — free variables in a lambda body refer to the enclosing scope at definition time
DNormal form — the fully reduced expression stored in memory
A closure captures free variables from its defining scope — exactly what 'free variable' means in lambda calculus. When a λ-abstraction has free variables (names not bound by any enclosing λ), those names refer to the outer environment. Alpha conversion exists precisely to prevent unwanted variable capture during substitution. Closures in compiled languages implement this scoping rule at runtime.
Question 3 True / False
In lambda calculus, numbers like 3 are primitive values stored separately from functions.
TTrue
FFalse
Answer: False
Lambda calculus has no primitive values — numbers are encoded as functions called Church numerals. The Church numeral for n is a function that takes a function f and a starting value x, and applies f to x exactly n times. So 3 = λf.λx.f(f(f x)). This encoding shows that the boundary between 'code' and 'data' is an illusion: everything, including numbers, booleans, and data structures, can be represented as functions.
Question 4 True / False
Two lambda expressions that reduce to each other through beta reduction are considered computationally equivalent.
TTrue
FFalse
Answer: True
This is the foundation for compiler correctness. If optimizing a program produces a term that beta-reduces to the same normal form as the original, the transformation is semantically valid — the program's behavior is unchanged. Lambda calculus provides the precise mathematical criterion: two expressions are equivalent if they have the same normal form (or both fail to terminate). This is why lambda calculus underlies formal semantics used in compiler verification.
Question 5 Short Answer
Why does lambda calculus demonstrate that computation does not require built-in data types, conditionals, or loops?
Think about your answer, then reveal below.
Model answer: All of these constructs can be encoded purely as functions. Booleans become functions that select between two arguments; numbers become functions that apply another function n times (Church numerals); conditionals become applications of boolean functions; recursion is encoded using fixed-point combinators like the Y combinator. Since the Church-Turing thesis links lambda calculus to Turing machines in expressive power, any computable function can be expressed using only variables, abstractions, and applications — no primitive data or control structures are necessary.
The key insight is that function application is powerful enough to simulate all other programming constructs. This has a direct practical consequence: functional programming language compilers can use lambda calculus as their intermediate representation and apply transformations (inlining, specialization, constant folding) using beta reduction rules, with a formal guarantee that the optimized and original programs are equivalent.