Day 5 - Computing with λ-Calculus

is that the half-life 2 logo?
30 Apr 2025

Lambda Calculus is used in computing, and forms the basis for functional programming.

Conditions

We can represent true and false in these two expressions respectively:

true=λx. λy. x\text{true} = \lambda x.\ \lambda y.\ x false=λx. λy. y\text{false} = \lambda x.\ \lambda y.\ y

While it does not seem like the two represent anything at all, the idea lies in how they behave; the true function returns the first variable, and the false the second.

Now we can use these two boolean functions together to form an if statement, by passing in the functions as arguments bb (Input condition, either true or false), xx (Output if true), and yy (Output if false):

λb. λx. λy. b x y\lambda b.\ \lambda x.\ \lambda y.\ b\ x\ y

which maps to this:

def ifelse(b, x, y):
	if b:
		return x
	else:
		return y

But why?

Well let us follow this lambda expression, with bb = true.

(λb. λx. λy. b x y) true x y→(λx. λy. true x y) x y→(λy. true x y) y→true x y→x\begin{aligned} & (\lambda b.\ \lambda x.\ \lambda y.\ b\ x\ y)\ \text{true}\ x\ y \\ & \rightarrow (\lambda x.\ \lambda y.\ \text{true}\ x\ y)\ x\ y \\ & \rightarrow (\lambda y.\ \text{true}\ x\ y)\ y \\ & \rightarrow \text{true}\ x\ y \\ & \rightarrow x \\ \end{aligned}

You can try the same by passing in bb as false. We have now implemented a condition function.

Logic Gates

We can also construct logical operations using the true and false expressions. All inputs are either true or false.

NOT

Flips the input bb from true to false and vice versa.

λb. b true false\lambda b.\ b\ \text{true}\ \text{false}
  • If bb is true, the result is false.
  • If bb is false, the result is true.

AND

Returns true if both inputs pp and qq are true:

λp. λq. p q false\lambda p.\ \lambda q.\ p\ q\ \text{false}
  • If pp is true, the result is qq.
  • If pp is false, the result is false, regardless of qq.

OR

Returns true if at least one input is true:

λp. λq. p true q\lambda p.\ \lambda q.\ p\ \text{true}\ q
  • If pp is true, the result is true, regardless of qq.
  • If pp is false, the result is qq.

With this, we’ve shown that λ-Calculus can represent and compute logical operations purely through function abstraction and application, making it effectively a universal model of computation.