If you don’t want spoilers for my puzzle a few days ago, don’t read ahead!
I think lambda diagrams are extremely cool, and haven’t seen any detailed description on how they work online. I’ll start by showing some very simple examples of lambda diagrams, and then build up to more complicated ones.
First of all, what are lambda diagrams? They are pictorial representations of lambda expressions, and hence count as a pictorial system for a large portion of mathematics. I will assume that you understand how lambda calculus works for this post, and if you aren’t familiar then you can do no better than this video for a basic introduction.
The Basics
Let’s start simple: the lambda expression for “True”: λx.λy.x
Each time we see a new bound variable, we draw a horizontal line to represent that variable. So parsing from left to right, we start with a horizontal line for x.
Next is “λy.“, so we insert another horizontal line for y (below the first horizontal line).
Next we have an x in the function body, which we represent by a vertical line leaving the x line:
And there we have it, the lambda diagram for True!
Now let’s look at False: λx.λy.y
... continue reading