Lambda Calculus in Python

Haskell Déjà vu

A while back I decided to learn Haskell, since functional programming sounded and looked cool. I found this fantastic series of lectures on the topic, and found this is how Quicksort looks in Haskell:

sort []     = []
sort (x:xs) = sort ls ++ [x] ++ sort rs
  where
    ls      = [ l | l <- xs, l <= x ]
    rs      = [ r | r <- xs, x <  r ]

It’s typed, lazy, and purely functional. It kind of reminds me of assembly. It might make for an excellent Zachtronics game. But it also gave me a sense of déjà vu back to when I first saw list comprehensions and lambda functions in Python:

quicksort = lambda arr:
    arr if len(arr) <= 1
    else quicksort([x for x in arr[1:] if x <= arr[0]]) + [arr[0]]
       + quicksort([x for x in arr[1:] if x > arr[0]])

Sure, the above code used a lot of things a pure lambda calculus would never use. But this got me thinking - just how far can you go with functional Python?

Building up to “Hello World”

Based on how big the text above is, you’ve probably guessed that this isn’t going to be as simple as it traditionally is.

Setting some ground rules

The book A Gentle Introduction to Haskell states

Because Haskell is a purely functional language, all computations are done via the evaluation of expressions (syntactic terms) to yield values (abstract entities that we regard as answers). Examples of expressions include atomic values such as the integer 5, the character ‘a’, and the function \x -> x+1, as well as structured values such as the list [1,2,3] and the pair (‘b’,4).

Thus, I’m going to give myself the liberty of using the above Python datatypes, though I argue it’s possible to recreate all of the above using binary encodings of the form

True = lambda x,y: x
False = lambda x,y: y
Ife = lambda b,x,y: b(x,y)

Moving onwards, let’s stick to the atomic types and lambda alone.

Evaluating expressions

The biggest hurdle I then faced is that there’s no clear way to run this cursed code. That is, suppose I write in the Python repl

>>> lambda _:'Hello World'
<function <lambda> at 0x102d1f520>

How can I evaluate such a function? Sure, there’s the obvious

>>> a = lambda _:'Hello World'
>>> a(_)
'Hello World'

But, there’s also the lesser obvious

>>> (lambda _:_(_)) (lambda _:'Hello World')
'Hello World'

This is legal python code. Don’t believe me? Copy it into your favorite Python repl, or if you’ll entertain me, the block below:

python

If you tried playing around with the above repl, you’ll noticed that its cursed in many ways. In particular, it only remembers one line of code, and only outputs something when you put it in a print statement.

The one line rule

That’s right - I decided to make this challenge even harder by instantiating one more restriction: only one line of code. This is why (lambda _:_(_)) (lambda _:'Hello World') was so crucial - and why the interactive Python repl above is so cursed. Unlike the a(_) evaluation, this one works inline.

So, let’s take a moment to digest what (lambda _:_(_)) (lambda _:'Hello World') means.

First lambda _:_(_) is just a Pythonic way of defining a function, that given an input function, will call said input function on itself. Recall that, in terms of normal Python functions a = lambda _:_(_) is equivalent to

def a(f):
    return f(f)

I think of this as a baseless, pseudo-recursion. Indeed,

>>> a = lambda _:_(_)
>>> a(a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Thus, the expression (lambda _:_(_))(in) is an anonymous function that evaluates an input function in with in as its input. As such

>>> (lambda _:_(_))(print("Hello World"))
Hello World
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
TypeError: 'NoneType' object is not callable

because print() in Python returns None. However

>>> (lambda _:_(_))(lambda _:print("Hello World"))
Hello World

works without issue. This is because we’re just giving the second lambda itself as input, the second lambda ignores this input, and then successlly runs print("Hello World") since its technically been called and evaluated.

This is great and all, but can’t we just do print("Hello World") outright? After all, we’re allowing (and are somewhat forced to) use print. Why would we need to use two lambdas to wrap a function like this?

Behold, loops!

This buildup to “Hello World” migh as well be a buildup to loops. Since str is technically not an atomic type, I’ve left you hanging without a proof that we can concatenate atomic chars into one string.

---