```
def square_sum(a, b):
return (a*a) + (b*b)
5, 2) square_sum(
```

`29`

Some basic ideas of the Lambda Calculus, and how to use it to implement a computation system in Python

Author

Matt Hodges

Published

July 17, 2022

This post is adapted from a Jupyter Notebook found on GitHub.

This post explores some basic ideas of the Lambda Calculus, and how to use it to implement a computation system with it. We will define numbers and operators from scratch, and use that to implement the `square_sum`

function.

If you’re new to the Lambda Calculus, or functional programming in general, you may wish to start with some of these resources:

- David Beazley’s Lambda Calculus from the Ground Up - PyCon 2019
- If you’re someone who learns well by watching and listening, I highly recommend that you watch this talk. A significant portion of the concepts below come from watching this talk more than once.

- Ben Eater’s Making a computer Turing complete
- Lambda Calculus | Wikipedia
- Currying | Wikipedia

This post assumes you are fairly familiar with Python and Python’s lambda expressions.

The Lambda Calculus asserts that any computational system can be implemented with a set of three simple rules: * You can define variables * You can define single-argument functions * You can call single-argument functions

That’s it. **No numbers. No operators. No control flow. No data structures.**

I find it fascinating that with these very minimal concepts, the Lambda Calculus asserts that we can create a fully functional computer! This is, of course, a very minimal explanation of the rules of the Lambda Calculus, and I invite you to consult the references above for more information and formal definitions!

Using the rules described above, we want to create a system that can calculate the square-sum of any inputs. Again, we *only* have single-argument functions. That means we have no integers, no addition, and no multiplication. We’re going to have to create those using nothing but single-argument functions that accept single-argument functions as input and can only return single-argument functions.

For reference, consider the `square_sum`

function, that may be written in Python as:

As previously mentioned, our computation system requires that we can only create functions and those functions must accept one and only one argument. This may seem like a limiting requirement, but let’s take a look at what we can do with the idea of Currying — a method for transforming multi-argument functions into a chain of single-argument functions. This allows us to re-write our Python implementation as:

In our curried version above, `square_sum`

accepts the first argument, `a`

and returns a function that accepts the second argument, `b`

. We can then call that returned `inner`

function to complete our calculation. Currying is a fundamental strategy for computation in the Lambda Calculus.

Unless you’re already familiary with the Lambda Calculus, or you’re a veteran of functional programming, you’re probaby very accustomed to computing by operating on *state*. You have data structures, or numbers, or bits, and you operate on them and then you persist new data structures, or numbers, or bits.

Our concept of integers is a perfect example. As children, we learned that the concept of `3`

can be represented by holding up three fingers on our hand, and seeing all three of them, and pointing to them. The Lambda Calculus asks us to adjust that concept away from *state* and towards *behavior*. Instead of holding up three fingers, what if we held up *one finger three times*. It may be harder for us see that idea of `3`

, but it is a representation of `3`

nonetheless.

Sit with this idea of behavior representing integers, because behavior will be how we represent *everything*. And in our system, functions are behavior. Our function could be the act of holding up a finger, pressing a button, or anything else we need it to be.

Let’s use that metaphor of pressing a button. The button press is our behavior, and behaviors are functions. And arguments are functions. And we can only return functions. So, let’s write that:

Not much to see here yet. In fact, our system isn’t designed to *see* anything. It’s designed to do computations within a given set of rules.

We’re designing a system of computation, and we can think about this system like instruction that run on a CPU. But we’re humans, and it’s helpful for us to be able to see the results of our computation in ways that we can understand. So, we’re going to introduce an external system that is *not* within the Lambda Calculus, but can interface with it. Think of this as a peripheral like a printer. It’s not used to *do* any of our computation. It can do special things that our CPU can’t do, and it’ll connect to our system as a function, because our system can only work with functions.

Let’s pretend our system has a printer attached that can only print the `*`

character. We’ll interface with it via an `emit`

function.

Here is our not-of-our-system `emit`

function:

This is kindof strange. Our external `emit`

function takes in some function and has an inner asterisk-generating function. Let’s hook it up to our `button_press`

function:

What just happened here? We call our `emit`

function (external from our system) by passing in our `button_press`

function (internal to our system). We did it one time, and it yielded a single `*`

. Again, this is just a convenience interface so that we can see what’s going on, and isn’t necessary to do any of our actual computation.

Above we began to describe how functions, or behaviors, can represent numbers. A single call to `button_press`

yielded some concept of `1`

. What if we didn’t think about it as one call to `button_press`

anymore, but as the idea of *one behavior*:

If you’ve made it this far, you’re probably thinking, “Hey, Python has a way to represent single-argument functions, and they’re called *lambdas*!” Let’s start using that instead of the expanded `button_press`

function:

Cool. So we know how to represent the concept of `1`

using only single-argument functions. We can represent `2`

by calling our function twice, because in our system numbers are behaviors:

This is all well and good, but we’re not really going to try to implement every single number are we? That wouldn’t make a very good computer. How can we represent all countable numbers?

If you look closely at our definitions above, `ONE`

is a single call to `f()`

, while `TWO`

is `f(f())`

. This means that if we’re at any given number, we can get to the next number by calling `f()`

again. We can define an `INCREMENT()`

function to do just that. I find it helpful to start by looking at this through the expanded Python functions first:

```
def ONE(f): # f is the behavior we want to do
def g(x): # x is the curried second argument
return f(x)
return g
def INCREMENT(n): # n is the concept of the number we already have
def g(f): # f is the behavior we want to do
def h(x): # x is the curried second argument
return f(n(f)(x)) # we call f() again on our n(f)(x)
return h
return g
emit(INCREMENT(ONE))
```

`'**'`

Spend some time stepping through the above code to understand it. We’re essentially wrapping nested functions as many times as we need to get to the next number. Once you’ve wrapped your head around it, see that we can re-write the above as lambdas:

```
ONE = lambda f : lambda x : f(x)
INCREMENT = lambda n : lambda f : lambda x : f(n(f)(x))
TWO = INCREMENT(ONE) # our calculated TWO from ONE
emit(TWO)
```

`'**'`

If we can calculate `TWO`

from `ONE`

, we can calculate `THREE`

:

Pretty neat! We can keep doing this to infinity, either by saving values, or calculating them on the fly! But you may be wondering, what about `ZERO`

? Well, we’ve defined `ONE`

as a single call to any behavior `f()`

, so `ZERO`

would simply be no calls to that behavior:

See how `ZERO`

doesn’t call `f()`

at all? What’s fun here is that we no longer need to have defined `ONE`

, we can calculate it from `ZERO`

!

Now that we know we can represent numbers as function calls, let’s start working on math operators. We’ve already introduced one critical operator, `INCREMENT`

, and we can use that to introduce others. Let’s start with `ADD`

. Addition is can be thought of as incrementing `M`

times on a number `N`

. For example, `2 + 3`

could be described as incrementing 2, three times. Before we attempt to implement that in our system, let’s look again to how we would Curry this in Python:

```
def ADD(a): # Our first number, which is always a function
def inner(b): # Our second number, which is always a function
return b(INCREMENT)(a) # Increment a, b times
return inner
FIVE = ADD(TWO)(THREE)
emit(FIVE)
```

`'*****'`

Since *everything* is *always* a function, our numbers can be used not only as representations of calculations, but also as executors. Here’s our `ADD`

as a lambda:

The last missing operator of our computational system multiplication. Multiplication should feel a lot like nested functions you see often in programming.

```
def MULT(a): # Our first number, which is always a function
def outer(b): # Our second number, which is always a function
def inner(f): # The function we want to do a*b times
return b(a(f)) # do f, a times, and do that b times
return inner
return outer
SIX = MULT(TWO)(THREE)
emit(SIX)
```

`'******'`

Again, we can represent `MULT`

as a lambda:

We’ve now defined everything necessary to implement our `square_sum`

function in the Lambda Calculus. Let’s build it here from these basic principles. We want to calculate `square_sum(5, 2)`

.

```
ZERO = lambda f : lambda x : x
INCREMENT = lambda n : lambda f : lambda x : f(n(f)(x))
ADD = lambda a : lambda b: b(INCREMENT)(a)
MULT = lambda a : lambda b : lambda f : b(a(f))
square_sum = lambda a : lambda b : ADD(MULT(a)(a))(MULT(b)(b))
TWO = ADD(INCREMENT(ZERO))(INCREMENT(ZERO))
FIVE = INCREMENT(ADD(TWO)(TWO))
RESULT = square_sum(FIVE)(TWO)
```

And that’s it! Using nothing but single-argument lambda functions, we’ve successfully defined non-negative integers, the addition and multiplication operators, and the square-sum function. It’s a little hard to visualize, but the actual answer *is* calcuated in our `RESULT`

variable. We can output it to our metaphorical printer:

Our printer has output 29 asterisks! Pretty cool!

Our system barely scratches the surface, but you can continue to implement more operators, comparators, control flow, and everything else you might need for a full computer. I highly recommend consulting the references at the top of the post for further reading!

```
Copyright (c) 2022, Matt Hodges
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
* Neither the name of Exploring the Lambda Calculus with Python nor the names of its
contributors may be used to endorse or promote products derived from
this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
```

🖤 Thank you for reading a personal blog. This post was written in a specific time and place. I reserve the right to learn new things and to change my mind. This site has no traffic analytics, social trackers, or ads. If you enjoyed this post, please consider sharing it however you like to share posts.