Posted on November 2, 2026
Tags: , ,
Suzhou - The Fool’s Spring, from Twelve Views of Tiger Hill

As the fog dissipated beneath the sea of trees it suddenly became all too clear that the fool had in fact been himself.

– safri

huh?

Lambda calculus is the back bone of functional programming, a type of programming that nobody can define.

So one way to define it is by a couple of characteristics:

  1. It’s based on the lambda calculus (huh?)
  2. Just a bunch of expressions innit
    • expressions = values, variables, other functions
  3. Functions are first-class (like on airplanes)
    • This literally just means that they can be put anywhere (including as an argument to another function)

Any language that is based solely on the lambda calculus is a pure functional programming language.

But apparently this is controversial, it can also refer to "referential transparency" where the
---
input -> function -> output
---
Where in other words, this is bad:
f(1) = X
f(2) = Y
Because they should get the same output

Fyi, this post probably isn’t useful to anybody.

Lambda Calculus

Recursive definition aside, the lambda calculus is a mathematical discovery that any program in existence can be created with three basic components:

  1. variables (a name for a value)
  2. abstractions (a function)
  3. expressions (variable, abstraction or both)

For the record, a “lambda” refers to the symbol “λ” but because I don’t know how to type that in emacs org-mode (what this blog is written in) example blocks so you get “\” instead.

The component we’ll spend most of our time looking at is abstractions.

Abstractions

Abstractions consist of two parts:

  1. da head
  2. da body

Take this dead simple lambda abstraction right here:

 \x.x
If you wanted a peak at Lambda Calculus 102, a more advanced function could look like:
(\x.x+1)
---
NOTE: I don't know how to input lambda's in emacs org-mode (how I write this blog) example codeblocks so just think of the lambda symbol when you see "/"

Now if you look even closer you might notice that there’s two x’s

This is a subtle hint to the fact that the x is in our head is the functions parameter where all x’s in the

Upon evaluation, this function is passed an input, to which that input then substitutes all x’s in the body

(\x.x+1) 4 = 5 :D

Alpha Equivalence

The author of Haskell Programming From First Principles really liked fancy words so I’m sorry but I shalst continue that trend here.

Alpha Equivalence basically just says that the letter we set as x has no meaning, value and is worthless.

\x.x
\y.y
\z.z

All represent the same function (😱)

Beta Reduction

Broadly speaking, beta reduction is the process where you substitute what you know about a function using a given input.

(\x.x) 5 = 5

This seems really simple until you start adding more abstractions:

(\x.x)(\y.y)

Here’s the definition I got for that:

In this case, we’d substitute the entire abstraction in for x. We’ll use a new syntax here, [x := z], to indicate that z will be substituted for all occurrences of x (here z is the function λ y.y).

Huh?

But it makes slightly more sense after applying the argument z and with this reduction:

((\x.x)(\y.y))z
  [x := (\y.y)]
           (\y.y)z
           [y := z]
                    z

But I’ve given up on understanding what in the hell they mean by “[x := z]”.

Our understanding goes as such:

Whenever you see [ x := y ], the right side substitutes the variable in the left side

ONWARD!!

Free Variables

B-b-b-but what happens if you add a variable that’s not in the abstraction’s head??

That would be a “free variable” which describes variables not defined in the head.

\x.xy
--- The free variable is y

CURRYYYYYY!!!!

One really fun feature of lambda calculus is that functions can quite literally only take one argument.

Something like:

\xy.xy

Is actually not possible in lambda calculus but the handsome Haskell Curry decided to make it possible anyways

The rule itself remains true, the above is just two nested lambdas:

\x.(\y.xy)

Where applying say “3” would reduce down to:

(\y.3 y)

But only actual masochists would enjoy writing that so functional programming languages usually make a secret handshake with the syntactic sugar kingdom and pretend that functions can take two arguments.

This becomes relatively clear with an example:

\xy.x + y
(\xy.x + y) 1 2
(\x.(\y.x + y)) 1 2
[x := 1]   --- replace the x with 1 :p
(\y. 1 + y) 2
[y := 2]   --- :p
1 + 2
3
:D

In this final state we’ve achieved something called beta normal form which is a fancy of way of saying it can’t be simplified further

In programming, beta normal form refers to the complete evaluation of a program!
This means that functional programming is literally just reducing functions with information that we know.

K that’s all fine but let’s get a bit more complicated:

(\xyz.xz(yz))(\mn.m)(\p.p)

This gets really hard to explain with text so here’s a break down of the process color coded by abstraction.

You’ll notice how at the end there we were able to discard the entirety of:

((\p.p)z)

As it was meant to replace all of the n’s in

(\n.z)

But there were no n’s!! Leaving us just with z

Combinators

Combinators are abstractions with no free variables,

It just combines the arguments given innit

These are combinators:

\x.x
\xyz.xyz

I feel like this isn’t a very useful word but I digress.

Divergence

It’s important to take this time to acknowledge the fact that some not so good functions choose not to reach their true beta normal form.

Normally, an abstraction will reduce into a nice neat little form but happens when the reduction creates a loop?

(\x.xx)(\x.xx)

The second abstraction is taken as an input to the first, replacing all instances of “x”, with that we get:

(\x.xx)(\x.xx)

Oh yea huh that’s a problem.

Abstractions of this nature “diverge” rather than “converge” and thus will never reduce to a beta normal form.

I thought this was a programming blog

Oh yea oops.

What’s really interesting about lambda calculus and functional programming is that all code execution is beta reduction.

If we take the haskell code:

ghci> (\x -> x*x) 3
9

We can see that it’s damn near exactly the same syntax we’ve been looking at.

The reduction follows the order:

  1. Oh hey I’m replacing all of my x’s with ‘3’
  2. K now I’m multiplying x by itself
  3. (outputs)

In another example, we can take simple arithmetic:

100 / 2

In this case our function is literally the division operator “/”, we can reduce it by simply evaluating the expression:

50

Credit

Tbh I don’t really have a target audience for this post as anybody that would willingly click on a post about lambda calculus is probably smarter than me anyways.

I didn’t really add any special knowledge either, I just read the first chapter of Haskell Progrmaming From First Principles (which you can read a sample of here) and watched the video Programming with Math | The Lambda Calculus made by the YouTuber Eyesomorphic.

So you should just use those tbh.