Exploring the Lambda Calculus with Python

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:

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

Rules of Our System

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!

The Challenge

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:

def square_sum(a, b):
    return (a*a) + (b*b)


square_sum(5, 2)
29

Currying

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:

def square_sum(a):
    def inner(b):
        return (a*a) + (b*b)
    return inner


square_sum(5)(2)
29

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.

Our Basic Building Block

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:

def button_press(f):
    def g(x):
        return f(x)
    return g

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:

def emit(func):
    def asterisk(x):
        return f'{x}*'
    return func(asterisk)('')

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:

emit(button_press)
'*'

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.

Numbers

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:

def ONE(f):
    def g(x):
        return f(x)
    return g

emit(ONE)
'*'

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:

ONE = lambda f : lambda x : f(x)

emit(ONE)
'*'

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:

TWO = lambda f : lambda x: f(f(x))

emit(TWO)
'**'

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:

THREE = INCREMENT(TWO)

emit(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:

ZERO = lambda f : lambda x : x

emit(ZERO)
''

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!

ONE = INCREMENT(ZERO)

emit(ONE)
'*'

Operators

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):
    def inner(b):
        return a + b
    return inner

add(2)(3)
5
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:

ADD = lambda a : lambda b: b(INCREMENT)(a)

FIVE = ADD(TWO)(THREE)
emit(FIVE)
'*****'

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:

MULT = lambda a : lambda b : lambda f : b(a(f))

SIX = MULT(TWO)(THREE)
emit(SIX)
'******'

Using Our Computer

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:

emit(RESULT)
'*****************************'

Our printer has output 29 asterisks! Pretty cool!

What’s Next?

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!

License

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.