What is PLUS times PLUS?

[Music] What you're watching right now is pure computation. Not quite algebraic manipulation. Not quite boolean logic either. Just pure computation. Specifically, it's evaluating three factorial. And sure enough, it found the result six.

What are all these weird lines though? Going back to the original setup, this pink chunk represents the factorial function. This yellow chunk represents the number three. And this blue chunk represents the application of the function to the number. We can make all sorts of other values. We've got 1, 2, 3 as well as plus and times. We can express any computational procedure, such as the factorial function. But the magic is that it's not immediately obvious whether a certain expression is a number, a function that operates on numbers, or something else entirely. And that's because in this language, there is no difference. Just like we applied factorial to three with function application, we can apply three to factorial in the exact same way, as though three was a function and factorial was a value. Okay, but you can't actually evaluate that, right? Well, you can, but it's certainly not the case that when evaluating it, the answer would make any sense, right? We're going to have to totally unlearn the concepts of functions, programs, values, and data types, 'cause today we're learning the lambda [Music] calculus.

But what even is computation? David Hilbert, one of the greatest mathematicians of the 1900s, wanted to know whether there was some procedure, some algorithm which can determine whether any given mathematical statement is true or false. Three men independently answered this question in different ways. The ideas they encountered along the way were so groundbreaking that they proved Hilbert's task impossible, spawned two of the paradigms underlying modern programming languages, showed that mathematics is essentially incomplete, and spawned the entire field of computer science. But Hilbert's question is a question about procedures, about ways of doing computation. We won't answer his question explicitly here. My goal instead is to give you a visceral understanding of how computation itself can be formalized. This video is the story of Alonzo Church's answer. His lambda calculus, to be clear, had nothing to do with derivatives or integrals or what you learned in calculus in high school. The term calculus, up until recently, was used to describe all sorts of logical systems. It might as well be called the way of the lambda. It's fundamentally a system for manipulating strings of symbols. Just like algebra teaches us to manipulate numbers and pluses and equals signs. In the lambda calculus, the strings look something like this. They're composed of parentheses, letters of the alphabet, and this notation involving a lambda and a dot. Those two always come together in a pair. We can build these strings ourselves following three templates. The blanks are places where you can put any other template, and the A's can be substituted for any letter in the alphabet. As an example, we can grab the third template, take a variable from the first template, slap it in one of the blanks, take template 2, and slap it in the other. There's still a blank left, so we can put another variable in. And just like that, we've made a lambda expression. Remember, these A's can be changed to any letter we want. Any combination of these templates forms a valid expression. Using them, we can create all sorts of different lambda terms. Even a variable itself is a valid expression.

Now, one thing you should know, these two templates have special interpretations. The template with a lambda and a dot represents a function definition. The letter that we put in is the name of the input, and the blank represents the return statement of the function. The third template involves applying such functions. In this case, we're suggesting the thing on the left, A, is going to be used as a function which takes in B. That's all we need to generate lambda expressions. We'll try evaluating these expressions in a sec, but first, let's visualize them. There's a ton of styles, but the one I chose is John Trump's lambda diagrams. After all, I'm biased. He was the first person to strongly solve Connect 4. Each of our three templates is part of a different shape in a lambda diagram. Variables from the first template are these vertical lines. Lambda abstractions or template 2 are the horizontal bars at the top. This branching structure at the bottom is template 3, representing function application. Notice that there's eight vertical lines here, just how the expression itself has eight variables. These correspond one to one, left to right. Note how they collide into different horizontal abstraction bars. Those horizontal bars corresponding to template 2 are associated each with one of the lambda dot pairs. Variables touch the bars which bind them. The X's connect to the lambda abstraction which binds the variable X, and the Y's touch the bar which binds Y. Template 3 for function application has two sub-expressions corresponding to the two blanks. This lambda expression as a whole has an application surrounding everything. It's shown in white. The lambda diagram for each of the sub-expressions is drawn on the left and right branch of the application. Don't worry too much about trying to read these. It's the kind of skill you have to practice for a while. I'll color in subcomponents so you can tell what's going on.

I've mentioned that these expressions can be evaluated. But what does that even mean? Remember that template 2 can be interpreted as a function, and template 3 can be interpreted as applying a value to a function. We want to create a strategy for evaluation that combines these interpretations. First, let's make a function by using template 2. This function is pretty simple. It just takes a value X in and applies X to B. We'll place that function in the spot where the function goes in template 3. We'll make our value just be some random expression. Now we're going to perform what's called beta reduction. We first note that X is the variable bound by the lambda. Since the function binds X, we first find all X's in the body of the function. In our case, there's just this one. Now we discard everything but the function body itself and the value we're plugging in. Now we take our value and replace every instance of X with that value, and we're left with a reduced expression.

Okay, let's try a slightly trickier one. To make it clear, this is the function and this is the value. Same as before, X is the variable bound by the lambda. So we highlight all the instances of X in the body of the function. There's two this time. Discard all the scaffolding and perform the replacement. Still looks like abstract nonsense. This actually isn't as unfamiliar to you as it might seem. You already know how to do this in plain old algebra. Here's an algebraic function. We want to evaluate it at X = 5. We can first establish the function and then on a separate line, apply it to 5. But let's stick them on the same line. We'll wrap these two things in parentheses to imply that the first is a function and the second is the value we want to plug in. Now, since we tied the function to its value, there's no point in naming it F. Our inline notation is unambiguous about which function we want to apply to what value. We do still need to express that X is the thing in the body which 5 will be replacing. And the lambda calculus way to express that is by putting a lambda dot pair around it. Now, how do we evaluate it? Well, exactly the same procedure. Identify all the variables in the body which match the one bound by the lambda. In this case, all the X's. Drop all the slack, grab our value, and shove it everywhere we had an X. We're left with an algebraic expression which represents the answer. Not too alien now, is it?

Let's try one more, but alongside the diagram this time. Let's color the value in blue and the variable which it's about to replace as red. Now let's perform the beta reduction. See how the value takes the place of the variable and then the application scaffolding drops out. Let's watch that a few times over. This doesn't have to happen at the top level of the expression. Let's make a big expression which contains this somewhere inside. We can still beta reduce the entire expression by reducing this subcomponent.

All right, time to write some code. First, we've got to make a function that takes two variables. Pseudo code like this isn't permitted by our strict templates for making expressions. Of course, we have yet to define numbers and times and plus, but let's assume we know how those work for now. The real problem is that we're trying to make a function that takes in two variables. Only one letter is allowed to go between the lambda and the dot. Luckily, there's a workaround called currying. The trick here is to make a function wrap another function. Let's see what happens when we stick two arguments after this function and beta reduce it. It's best to be clear what the application order is so we don't misinterpret 5 as being a function which takes in 3. Now, let's beta reduce the innermost function application. Here's the function and the value we're passing in. Notice the bound variable is X. Find all the X's in the body. Rip off the scaffolding and replace. Getting the hang of beta reduction? Reduce one more time and we have the [Music] answer. Let that sink in a little bit.

Since a function can only really take one argument, a two-argument function is the same thing as a function which spits out a one-argument function. A three-argument function would spit out a two-argument function, and so on. So from now on, we'll permit two variables in the lambda, since we can think of it as shorthand for a curried function. Before we applied the function like this, but now we can just drop the extra parentheses as shorthand too.

All right, it's programming time. We're going to start with the values true and false. Conventionally, these are the two expressions which are used. Note that they're curried functions, one function directly inside the next. Let's use our shorthand to get a sense of what they do. Let's pass in two values. We'll start with true. Reduce once for the first argument. Reduce again for the second. We passed in v_sub_1 and v_2, and we got out just v_sub_1. Let's try again with false. Reduce once, reduce again. This time we got out v_2 instead of v_sub_1. This means these functions are fundamentally selectors. True picks out the first of two arguments, and false picks the second. We can make a term like this where X represents either true or false. If X is true, then the output will be T. If X is false, the output will be F.

So how do we make common logic gates using these values? Let's start with NOT. In other words, we want a function that maps true onto false and vice versa. NOT only takes in one variable, so our function should too. The trick is to use that argument as a selector. If the input is true, then the first argument is the one which will be picked. Since NOT true is false, false should be the thing in this blank. If the input is false, we want the selected value to be true. So this is NOT. If we want to write it in full, we can substitute in the trues and falses. But for now, let's leave it like this. Let's see what happens by passing in false. We're expecting true out, since NOT false is true. Beta reduce once. Substitute in the known value of false. Beta reduce twice more. And sure enough, it's true. Here's what NOT looks like as a diagram. I'll highlight the true subcomponent as green and false as red. Let's plug in true this time and check what we [Music] get. It's false, as desired.

How about AND? AND takes two variables in, so our function should too. We're going to use the same trick as with NOT, using X as a selector. If X is false, then the answer is false too. Remember that true AND something is just that something. So if X is true, then the answer is whatever Y is. So this is AND. I'll leave it as a challenge to you to find [Music] OR.

Okay. Now how about numbers? The underlying inspiration here is to represent one as F of X, two as F of F of X, and so on. In other words, the number N is represented by applying some function to some value X, N times over. Well, almost. The numbers are really two-argument functions which take in F and X and then apply F to X N times. It's important to understand the difference there. These numbers are functions that take in a function and a variable, and then iterate that function on that variable. So we can give two the function sign and the value five, and two will apply sign to five twice.

So how do we do math on these? Let's start with succession. This is the function that when given N returns N + 1. It takes one number as an input. The thing that it spits out is also a number. So we're going to make the body look like a number. We want to apply F to X N + 1 times. We can start by applying F to X N times. We do this by using the numeral as a function and passing F and X into it. All that's left is to apply F just one more time. Let's evaluate the successor of five. I've colored the extra F red. Keep an eye on it during reduction. Check it out. That's six.

How about addition then? Addition is a function that takes in two numbers. Since we already defined the successor function, we can use it here. Calling successor adds one to a number. To get N + M, we just have to call successor on N, M times over. Remember, the number M itself is a function which, when applied to the successor function, will iterate that function M times. So M succ N is the same as adding 1 to N, M times over. Plugging this into our function body, we get this. That's an addition function. Let's add five and three together. It's eight. This addition function takes a lot of beta reductions to complete. I'll spoil a faster one here. Multiplication can be defined in terms of repeated addition, but there's also a quicker way. Here's exponentiation, too.

Now, I promised you in the thumbnail that we'd find the answer to plus. So, here goes. Let's plug in the function for times. Reducing, we get this. Okay, that's kind of weird. We get another function, but let's just roll with it. What happens when we stick a number in? Let's call it a reduce. Substitute the definition of plus. This is still a function. Let's keep sticking numbers in until we get a number out. Okay, after inserting four arguments, we got a number out. Let's write it in a more familiar notation. This term is just A plus C. And there's a few examples of exponentiation going on here. Okay, so what we learned here is that plus * plus is a function of four arguments which spits out this power tower. Obviously, this is completely ridiculous, but it serves to prove a point. In a world where everything is a function, you can do things that normal math just doesn't permit. And strange emergent behavior is the norm. But it's going to get plenty weirder yet.

We're going to need some voodoo magic to make the factorial function. Here's a typical implementation in Python. The core idea is to return N times the factorial of the previous number. However, we don't want to go into the negatives. So, we add a base case. All right, let's try it in the lambda calculus. Factorial just takes in one variable. Let's say you have an IS_ZERO function available which checks if a number is zero and gives back true or false. We could make it, but let's not get distracted. IS_ZERO of N yields a boolean. And as we know, booleans work as selectors. Thus, we already know how to make this IF THEN ELSE block. Therefore, factorial takes this form: the boolean, what we want to return if it's true, and what we want to return if it's false. If it's true, just like our Python function, we simply return one. If it's false, we return the recursive call. We multiply N by the factorial of N minus one.

Now, wait a minute. Our definition of the factorial function contains itself inside. In Python, this is fine. We can instantiate the function anywhere, even within itself. But a lambda calculus term is self-contained. How would I draw a diagram of this term if I don't know what this component is? You could argue as is, this definition's infinitely long. How on earth are we going to define recursion?

Time for a mind-blowing detour. Let's talk about normal functions on the real numbers. A fixed point is some number that you can plug into a function and you get the same number back. In other words, X is a fixed point if F of X equals X. Graphing this, it's where the line Y = X intersects with your function. S evidently has exactly one fixed point exactly at 0. Y = X squared has two fixed points, 0 and 1. Those are the only reals which are their own squares. But what about Y = X + 2? It doesn't even have a fixed point. What about arbitrary functions? If you can find all fixed points of the Riemann zeta function plus its input, you would solve the Riemann hypothesis and win a million.

Okay, now hold that thought. Check out this lambda term. If we apply it to itself, we get this term called the Turing fixed-point combinator. It does something so cool, it's unreal. Let's just imagine you have some function. Apply the fixed point to F and see what happens. We know theta is U. So let's apply that identity. Expand the first U to its definition. Beta reduce the first argument U. Beta reduce the second argument F and substitute theta for U. Do you see it? We reduced theta F to F of theta F. In other words, up to beta reduction, theta F equals F of theta F. So theta F is a fixed point of F. Just think about that for a second. Unlike real-valued functions, not only does every function in the lambda calculus have a fixed point, but there's a trivial way to find them, too.

But wait, if that's the case, why am I making this video instead of solving the Riemann hypothesis? It's kind of like trying to solve for the root of negative 1. There's always a fixed point out there, but it's not necessarily among the real numbers. In our case, theta F isn't necessarily a real number. It can be an arbitrary non-numerical lambda expression. So, we can go ahead and define X squared + 2, slap theta in front of it, and sure enough, we find a fixed point. But this fixed point isn't even a number. It's a fixed point of a lambda calculus construct which emulates the function X squared + 2.

Okay, so maybe Turing's fixed-point combinator can't do the impossible, but it is the magic bullet to help us make our factorial. This is where the voodoo magic comes in. Hang with me. I'm going to remove the problematic recursive call and replace it with some F, which we'll add as an argument for this function. I'm going to call this new function Big F. Now let's consider what a fixed point of Big F would be like. We already know that this equation is true of any fixed point by definition, using the magic of Turing's fixed-point combinator. Plugging in the first F and beta reducing once, we get this expression. Now remember that there's no recursive nesting this time. This component is finite and closed form. But this time, through beta reduction, we derived the recursive equivalence relation that we wanted to begin with. This term theta F satisfies the recursive equivalence characteristic of the factorial function. And that means that theta F is the factorial function. Let me color it in so it makes more sense. This is the fixed-point operator in blue. Here's F inside of it. Here's zero, the number one in the base case, the multiplication function, the function which subtracts one, and the recursive function call. Now let's apply this factorial function to the number three. Hold on tight. [Music] It's six.

Now, I knowingly hid some complexity about beta reduction from you, but now I think you're ready. Consider this term for 1 + 1. As we've done a million times, we can beta reduce it to two, but this time let's keep track of the intermediate steps. Okay, we've arrived at two. I've colored it blue because it's special. It can't be reduced further. The fancy word for this is beta normal form. But I want to take a closer look at the second node. If I beta reduce it, it looks like this. But stepping back, let me highlight the function-value pair which just got reduced. Here's the function and here's the value. And here it is getting reduced again. But there's actually a different reduction available here. Here it is. And here it is actually taking place. Going back to our tree of reductions. Since there are two options at this node, let's follow both paths at the same [Music] time. Looks like all paths lead to two. Of course, I mean, that's what we should expect. The answer to the problem shouldn't depend on the order that you do the steps, right?

Let's try 2 * 2. [Music] Here's the reduction graph. Looks like in this case we can only get to four also. All right, I'll stop leading you on. This is a lambda term called Omega [Music] 3. See where this is going? When we beta reduce this term, it actually just gets bigger. There's no branching, but this is never going to get to beta normal form. Here's an even weirder term. It is reducible, but it doesn't reduce to a different lambda term. There's not much of a graph to draw because it reduces to itself. Here's our old friend factorial of three. The search tree on this is super deep. So, I'll just show you the tip of the iceberg. That's the first thousand nodes. Here's the path straight to the answer of six. But let me show you something else. This is another path that seemingly goes in a totally different direction. In fact, this alternate reduction path goes on indefinitely, sort of like Omega 3. Up to the order that you perform your reductions, you may or may not ever reach the answer. It turns out in this path, it's unrolling the recursive definition of factorial, so to speak, before the base case is ever taken advantage of. The proof is unfortunately too long for this video, but the Church-Rosser theorem shows that if there's one of these blue irreducible answers in our tree, there isn't another. Sometimes there isn't one at all, and sometimes you can go down a beta reduction path in the wrong direction, but there's never more than one node in this special beta normal form.

Lambda calculus is a deep subject, and we've only scratched the surface. Just to give you a taste of what else is out there, the Church-Turing thesis showed that the lambda calculus can do everything that any traditional computer can. There's also the entire field of typed lambda calculus, where we assign data types to variables. It even turns out that any given typed program in the lambda calculus corresponds to some proof. Merely writing a program in the typed lambda calculus proves something. People have even made programming languages which convert a mathematical proof into a runnable program. Which brings us to the whole topic of how this is actually used in programming. Lisp, Haskell, and other programming languages are intrinsically based in the lambda calculus, unlike say C or Rust. Even Python has adopted the ability to make small anonymous functions called lambdas, which emulate the properties of the lambda calculus.

But I don't like the lambda calculus for its utility. The philosophical implications of these alternative models of computing run deep. They give us a fresh perspective on the structure of information and the nature of computation itself. I want to give an enormous thank you to 6884, who made all the music which made this video come to life. This also couldn't have been possible if not for John Trump, the inventor of this sick diagrammatic notation for the lambda expressions, or Peter Selinger, who wrote this book, Lecture Notes on the Lambda Calculus. His clear formalizations of a lot of the things I thought I understood helped me get through plenty of snags in rendering these diagrams. This video, to the best of my knowledge, is the first which shows beta reduction animations of any visualization method for the lambda calculus. And jeez, did it take a while to make. If you like this content, then there's nothing I would appreciate more than you joining our Discord server. We talk about math, puzzles, game theory, and so on. I can't wait to see you there. But until then, this has been Two Swap.