Lambdasort

Quicksort written in Python only using lambdas!

GitHub: https://github.com/lucasoshiro/lambdasort

Lambda calculus

Python, just like many other programming languages, supports high-order functions and anonymous functions. This means, basically, that we can do this:

# anonymous function (lambda). This is equivaltent to sqrt:
lambda n: n ** 0.5

# function that takes another function as parameter
def apply_func(func, parameter):
    return func(parameter)

# function that returns another function. in this case, this is a mutiplier factory
def multiplier_factory(n):
    return lambda x: n * x

Right. This way, functions are values that can be created and returned by other functions.

What if we write a code that the type of every value is a function? For example:

t = lambda a: lambda b: a
f = lambda a: lambda b: b
x = (lambda a: lambda b: a(b)(f))(t)(f)

At first look it seems to be useless. However, believe it or not (spoiler: this will be explained further), that is a boolean and of True and False!

This is the famous lambda calculus. It only has functions that get functions as parameters and return other functions. For us, that is enough, but if you want to read more about it, I really suggest you this article on Wikipedia.

Even though it seems to be insufficient to do anything, actually lambda calculus can solve any problem that can be solved with an algorithm, as it is Turing-complete! Alan Turing itself has proven it!

The excellent Programming with Nothing by Tom Stuart shows how to write a fizzbuzz using lambda calculus in Ruby. When I read it the first time I wanted to do something similar to it, so I made this: A QUICKSORT IN LAMBDA CALCULUS.

I will tell you all the steps of how I did that!

The beginning: a normal quicksort in Python

The first step was to write a quicksort in Python, but with a difference compared to the traditional quicksort: it doesn’t change the original list, instead, it returns a new list, just like the sorted in Python:

def car(A):
    return A[0]

def cdr(A):
    return A[1:]

def cons(A, x):
    return [x] + A

def concat(A, B):
    return A + B

def quicksort(A):
    if len(A) <= 1: return A
    L, R = partition(A)
    p = car(R)
    L = quicksort(L)
    R = quicksort(cdr(R))
    return concat(L, concat([p], R))

def partition(A):
    p = car(A)

    L, R = [], []

    for x in cdr(A):
        if x < p:
            L, R = cons(x, L), R
        else:
            L, R = L, cons(x, R)

    L, R = L, cons(p, R)

    return L, R

Take a look in the use of the functions car, cdr and cons. I followed the Lisp nomenclature for those functions. They will be further implemented the same way as some Lisp dialects, so I tried to be closer to them in how lists work instead of the usual in Python:

• The car function returns the first element
• The cdr function returns a list with the rest of the elements. In other words, all the elements except the first
• By now, I also implemented cons as a function that returns a new list that looks the same as the provided but appending a new element to its beginning, but cons is more than that (I’ll discuss it later)
• The concat function concatenates two lists.

The rest is only a standard quicksort:

• The partition function splits a list in two, the left one being a list that all of its elements are lesser than the first element of the right one (the pivot), and the right one being a list that all elements are greater or equal to the pivot.

• The quicksort function calls partition to split the list that we want to sort into two and sorts each one using quicksort itself, recursively, being the base of the recursions lists with length lesser or equal to 1.

As for the weird constructions L, R = ..., by now it is useless to do those parallel attributions, but this will be helpful in the future.

You can see it here.

Redefining types

As the idea is to rewrite quicksort using only lambdas, we need to somehow represent data using only functions. The types here are:

• integers (the values in the list that we want to sort)
• lists
• pairs (used by the functions that return more than one value)
• booleans (used by the verifications)

Luckily, the creator of lambda calculus, Alonzo Church has also shown us how to do that. There’s an article about it on Wikipedia.

Booleans

Let’s start by the easier ones, booleans:

#boolean constants
LAMBDA_TRUE = lambda a: lambda b: a
LAMBDA_FALSE = lambda a: lambda b: b

#boolean opearations
LAMBDA_OR = lambda a: lambda b: a(LAMBDA_TRUE)(b)
LAMBDA_AND = lambda a: lambda b: a(b)(LAMBDA_FALSE)
LAMBDA_NOT = lambda a: a(LAMBDA_FALSE)(LAMBDA_TRUE)

Yeah, true is only a function that takes two arguments and returns the first one, and false is a function that takes two arguments and returns the second one.

I know that you’re thinking: “it should be lambda a, b: a and lambda a, b: b, why there are two lambdas?”. This is because in the definition of lambda calculus, functions can only take one argument. Contrary to that definition, in Python lambda can take zero or more arguments, but here I’m restricting myself to only use functions that take only one argument in order to stick to the definition. This way, what would be written as lambda a1, a2, a3, ..., an: will be written as lambda a1: lambda a2: lambda a3: ... lambda an:. When calling the function, we use (a1)(a2)(a3)...(an) instead of (a1, a2, a3, ..., an). The name of that conversion is currying, named after Haskell Curry. An example of language that natively uses currying to handle function is Haskell (you don’t say!).

After that, I implemented the tree basic boolean operations:

• not: takes a Church boolean, and calls it using as parameters false and true. If the boolean is true, it returns the first argument (false); if it is false, then it returns the second argument (true).

• or: takes two Church booleans, calls the first one passing as arguments true and the second boolean. If the first argument of or is true, then it returns its first argument (true); if it is false, then it returns its second argument (the second argument of or).

• and: much like or. Try to simulate it mentally ;-)

We can also define an if:

if

LAMBDA_IF = lambda c: lambda t: lambda e: c(t)(e)

In if, cis the condition; t is the “then” block, what happens when the condition is true, and e is the “else” block, what happens when the condition is false.

This way, if is closer to an if-expression in Python (or ternary operator) than a control flow if:

use_5 = LAMBDA_TRUE
dont_use_5 = LAMBDA_FALSE

a = LAMBDA_IF(use_5)(5)(0) # a = 5
b = LAMBDA_IF(dont_use_5)(5)(0) # a = 0

Conversion

I also defined two functions to convert Church booleans to Python booleans (l2b) and vice-versa (b2l):

#boolean conversion
def l2b(l):
    return l(True)(False)

def b2l(b):
    return LAMBDA_TRUE if b else LAMBDA_FALSE

Mental exercise: simulate them!

You can see it here

Integers

Church numerals are defined as:

LAMBDA_ZERO = lambda p: lambda x: x
LAMBDA_ONE = lambda p: lambda x: p(x)
LAMBDA_TWO = lambda p: lambda x: p(p(x))
# etc

This is, all the integers are functions that take two arguments p and x this way:

• 0 is a function that returns x (just like false)
• 1 is a function that returns p(x)
• 2 is a function that returns p(p(x))

and so on. However, we can represent negative numbers using this encoding.

Increment and decrement

Increment is easy to define, it is a function that adds another layer of p(...):

LAMBDA_INCREMENT = lambda l: lambda p: lambda x: p(l(p)(x))

But decrement is far harder. Explaining it takes some time, and understanding it is not useful for us right now. If you really want to know how it works, try it by yourself. If you don’t care, just trust me Church that it works:

LAMBDA_DECREMENT = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)

If you tried to simulate it by yourself, you probably tried to figure out what happens if you decrement zero. And you found that the decrement of zero is zero here. Sadly this is a limitation, and we’ll need to remember it soon in the future.

Add and subtraction

Ok, we have increment and decrement. If we increment n times a number m, then we’ll have m + n, and if we decrement n times we’ll have m - n.

We can define add and subtraction this way:

LAMBDA_ADD = lambda m: lambda n: n(LAMBDA_INCREMENT)(m)
LAMBDA_SUB = lambda m: lambda n: n(LAMBDA_DECREMENT)(m)

Note that increment and decrement will passed as the p argument of the number n and m will be the x argument. In other words, m will be incremented or decremented the same amount of times than the number of calls that p has in n, this is, n times. Very, very beautiful.

Even so, a consequence of the decrement of zero being zero here is that n - m will always be zero if m > n.

Multiplication and division are also possible, but they won’t be useful for this quicksort.

Comparisons

The integer operations that will actually be useful for implementing quicksort are the comparisons. Let’s start by defining the function that tells if a Church number is or not zero (mental exercise: why does this work?):

LAMBDA_EQZ = lambda n: n(lambda x: LAMBDA_FALSE)(LAMBDA_TRUE)

Using only the operation of equals zero, combined with boolean and arithmetic operations we can define the others:

• m <= n: (m - n) == 0 (remember: m - n = 0 if n > m)
• m == n: (m <= n) and (n <= m)
• n < m: (m <= n) and not (m == n)

Or, in Python / lambda calculus:

LAMBDA_LEQ = lambda m: lambda n: LAMBDA_EQZ(LAMBDA_SUB(m)(n))
LAMBDA_EQ = lambda m: lambda n: LAMBDA_AND(LAMBDA_LEQ(m)(n))(LAMBDA_LEQ(n)(m))
LAMBDA_LESS = lambda m: lambda n: LAMBDA_AND(LAMBDA_LEQ(m)(n))(LAMBDA_NOT(LAMBDA_EQ(m)(n)))

Conversion

If we want to convert a Church number to a Python integer we’ll only need to pass the increment function as the first argument (p) and 0 as the second:

def l2i(l):
    return l(lambda x: x + 1)(0)

We can do the inverse: we can increment several times the Church zero until we reach the number:

def i2l(i):
    l = LAMBDA_ZERO
    for j in range(0, i):
        l = LAMBDA_INCREMENT(l)

    return l

We can also define functions to convert Python integer lists into Church number lists and vice-versa:

def llist2pylist(L):
    return list(map(l2i, L))

def pylist2llist(L):
    return list(map(i2l, L))

Using Church numbers

As we can convert Python integer lists into Church number lists and vice-versa and we can compare Church numbers, we can apply the first change to Quicksort:

def quicksort(A):
    if len(A) <= 1: return A
    L, R = partition_wrapper(A)
    p = car(R)
    L = quicksort(L)
    R = quicksort(cdr(R))
    return concat(L, concat([p], R))

def partition_wrapper(A):
    B = pylist2llist(A)
    L, R = partition(B)
    return llist2pylist(L), llist2pylist(R)

def partition(A):
    p = car(A)

    L, R = [], []

    for x in cdr(A):
        if l2b(LAMBDA_LESS(x)(p)):
            L, R = cons(x, L), R
        else:
            L, R = L, cons(x, R)
    L, R = L, cons(p, R)

    return L, R

The partition function now operates over Church number lists. In order to do that, we replaced x < p by LAMBDA_LESS(x)(p), that returns a Church boolean instead of True and False. I needed to use l2b to convert the Church boolean to a Python boolean so we can keep the compatibility with if.

The function partition_wrapper adapts the new partition in a way that it takes Python integers, but partitioning using the new partition function.

In the following sections I will make several substitutions of types, functions and operators by functions in lambda calculus, just like I did so far. I’ll try to change only what is relevant for each step, using the conversion functions if necessary.

You can see it here.

Pairs and lists

Our basic data structure is the pair. The pair is really a pair of values, just like a Python tuple of size 2. In Church encoding, a pair and its basic operations are defined like this:

LAMBDA_CONS = lambda a: lambda b: lambda l: l(a)(b)
LAMBDA_CAR = lambda p: p(lambda a: lambda b: a)
LAMBDA_CDR = lambda p: p(lambda a: lambda b: b)

The first function, LAMBDA_CONS, defines the pair. Note that, when passing two values as its arguments (e. g. LAMBDA_CONS(15)(20)), it will return a function that takes an argument l and returns the l call using the pair elements as arguments (in our example, l(15)(20)). That is: LAMBDA_CONS(15)(20) = lambda l: l(15)(20). In Python and other languages that supports first-class functions, those two values are stored in a closure, and we can even get them this way:

l = LAMBDA_CONS(15)(20)
a, b = (x.cell_contents for x in l.__closure__) # a = 15, b = 20

About LAMBDA_CAR and LAMBDA_CDR, they return the first and the second element of the pair, respectively.

Mental exercise: try to understand why LAMBDA_CAR and LAMBDA_CDR work!

Lists

If you paid enough attention, you noted that car, cdr and cons are the same names that we used to define the functions that operate over lists. And yes, they are the same! This happens because the way lists are implemented in Church encoding.

Church lists just are pairs where:

• the first element is the first element of the list
• the second element is a list with the rest of the elements

That is a recursive definition where the base of the recursion (an empty list) can be implemented by many ways. Here we are using to represent an empty list the boolean LAMBDA_FALSE:

LAMBDA_EMPTY = LAMBDA_FALSE

This way, a list with the values [1, 2, 3] can be declared this way:

LAMBDA_CONS(1)(LAMBDA_CONS(2)(LAMBDA_CONS(3)(LAMBDA_FALSE)))

In practice, they are recursive pairs:

(1, (2, (3, LAMBDA_EMPTY)))

So many parentheses! But note that, at this point, LAMBDA_CAR, LAMBDA_CDR and LAMBDA_CONS, when applied to lists have the same behaviour than car, cdr and cons that we defined to operate over Python lists:

• LAMBDA_CAR returns the first element of the first pair, this is, the first element of the list (1)
• LAMBDA_CDR returns the first element of the second pair, this is, the rest of the list ((2, (3, LAMBDA_EMPTY)))
• LAMBDA_CONS adds another pair, appending another element

As the definition of those lists is recursive, the iteration over them will also be done in a recursive way. The function that we’ll use to know whether the recursion has reached the end is this:

LAMBDA_ISEMPTY = lambda l: l(lambda h: lambda t: lambda d: LAMBDA_FALSE)(LAMBDA_TRUE)

That is:

• if l is empty (it is equal to LAMBDA_EMPTY), then it returns the second argument: LAMBDA_TRUE
• if l is not empty, then l is a pair. l is called with the function (lambda h: lambda t: lambda d: LAMBDA_FALSE) as argument. That function discards everything and return LAMBDA_FALSE. Try to simulate it ;-).

Conversion

Pairs can be converted from and to Python lists that have only two elements. The pythonic way to do that would be using tuples of size 2, but, in order to keep the code homogeneity, I’m using lists:

def l2p(l):
    return [LAMBDA_CAR(l), LAMBDA_CDR(l)]

def p2l(p):
    return LAMBDA_CONS(p[0])(p[1])

We can also convert Python lists and Church lists:

def ll2pl(l):
    if l2b(LAMBDA_ISEMPTY(l)): return []
    return [LAMBDA_CAR(l)] + ll2pl(LAMBDA_CDR(l))

def pl2ll(l):
    if len(l) == 0: return LAMBDA_EMPTY
    return LAMBDA_CONS(l[0])(pl2ll(l[1:]))

Using Church pairs in partition

As partition returns two values (a Python tuple), we can use here a Church pair:

    # before:
    return L, R

    # after:
    return LAMBDA_CONS(L)(R)

Using Church lists in partition

Let’s use Church lists in quicksort! First of all, we’re going to convert partition to operate over Church lists. Currently, our situation is this:

def partition(A):
    p = car(A)

    L, R = [], []

    for x in cdr(A):
        if l2b(LAMBDA_LESS(x)(p)):
            L, R = cons(x, L), R
        else:
            L, R = L, cons(x, R)
    L, R = L, cons(p, R)

    return L, R

So, we need to replace car, cdr, cons and [] by their corresponding in lambda calculus:

def partition(A):
    p = LAMBDA_CAR(A)
    L, R = LAMBDA_EMPTY, LAMBDA_EMPTY

    for x in lliterator(LAMBDA_CDR(A)):
        if l2b(LAMBDA_LESS(x)(p)):
            L, R = LAMBDA_CONS(x)(L), R
        else:
            L, R = L, LAMBDA_CONS(x)(R)
    L, R = L, LAMBDA_CONS(p)(R)

    return LAMBDA_CONS(L)(R)

Note that I created the generator lliterator to iterate over Church lists:

def lliterator(l):
    while not l2b(LAMBDA_ISEMPTY(l)):
        yield LAMBDA_CAR(l)
        l = LAMBDA_CDR(l)

Using Church lists in quicksort

Now we’re going to add Church lists to the function quicksort! We still need to define the function concat for Church lists. We can implement it recursively:

• If the list on the left is empty, we need to use the list on the right
• If the list on the left is not empty, it returns a new list where:
  • the first element is the first element (car) of the list on the left
  • the rest of the list is the concatenation of the rest (cdr) of the list on the left with the list on the right

That is (note the currying):

def LAMBDA_CONCAT(l1):
    def _LAMBDA_CONCAT(l2):
        if l2b(LAMBDA_ISEMPTY(LAMBDA_CDR(l1))):
            return LAMBDA_CONS(LAMBDA_CAR(l1))(l2)
        else:
            return LAMBDA_CONS(LAMBDA_CAR(l1))(LAMBDA_CONCAT(LAMBDA_CDR(l1))(l2))
    return _LAMBDA_CONCAT

This is a little different to the other operations that were written in a single expression. Spoiler: we’re going to handle this further!

Once having concat defined, we can replace all the Python list operations by Church list operations in quicksort:

def quicksort(A):
    # len(A) <= 1
    if l2b(LAMBDA_ISEMPTY(A)): return A
    if l2b(LAMBDA_ISEMPTY(LAMBDA_CDR(A))): return A

    L, R = partition(A)
    p = LAMBDA_CAR(R)

    L = quicksort(L)
    R = quicksort(LAMBDA_CDR(R))

    return LAMBDA_IF(LAMBDA_ISEMPTY(L))(LAMBDA_CONS(p)(R))(LAMBDA_CONCAT(L)(LAMBDA_CONS(p)(R)))

You can see it here.

Replacing loops by recursive functions

As in lambda calculus there aren’t any states, we can’t use loops as we do in imperative languages, that is, repeating a code snippet and changing the state of a variable.

And due to the lack of states, instead of changing an existing value we return a new value, just like we did when replacing the standard behaviour of quicksort to return a sorted list instead of sort the original list.

Even when we are write code in languages that support both the functional and imperative paradigms, like Python, if we restrict ourselves to write a code in a functional manner we can’t use loops.

And how can we solve the problems that would be solved using loops? There are many solutions depending on the case, for example, we could use reduce, list comprehensions, map, filter, recursive functions, etc. In this quicksort we only have one loop, in partition. We’re going to replace it by a recursive function.

Replacing for by while

Currently, the loop is this:

p = LAMBDA_CAR(A)
L, R = LAMBDA_EMPTY, LAMBDA_EMPTY

for x in lliterator(LAMBDA_CDR(A)):
    if l2b(LAMBDA_LESS(x)(p)):
        L, R = LAMBDA_CONS(x)(L), R
    else:
        L, R = L, LAMBDA_CONS(x)(R)

After removing the iterator lliterator and replacing the for by a while, we get this:

p = LAMBDA_CAR(A)
L, R = LAMBDA_EMPTY, LAMBDA_EMPTY

S = LAMBDA_CDR(A)
while True:
    if l2b(LAMBDA_ISEMPTY(S)): break
    x = LAMBDA_CAR(S)
    if l2b(LAMBDA_LESS(x)(p)):
        L, R = LAMBDA_CONS(x)(L), R
    else:
        L, R = L, LAMBDA_CONS(x)(R)
    S = LAMBDA_CDR(S)

In other words: at first S is equal to the input list without the first element (the pivot p). Each iteration of while removes a value from S and stores it in x. If x < p, we append x to the beginning of L, otherwise we append to the end of R. The stop condition is when the list S is empty.

For now on we can identify the elements that will be useful for writing this loop as a recursive function:

• the inputs L and R that are, at first, empty Church lists;
• the input S that is, at first, equal to LAMBDA_CDR(A);
• the outputs, that are the values of L and R at the end of the loop;
• the stop condition, that are when S is empty.

Converting while to recursion

Cool, what we have so far is enough to write a recursive function (that I’m calling here _partition), given the while loop code:

p = LAMBDA_CAR(A)
L, R = LAMBDA_EMPTY, LAMBDA_EMPTY

S = LAMBDA_CDR(A)

def _partition(S, L, R):
    if l2b(LAMBDA_ISEMPTY(S)): return L, R
    x = LAMBDA_CAR(S)
    if l2b(LAMBDA_LESS(x)(p)):
        nL, nR = LAMBDA_CONS(x)(L), R
    else:
        nL, nR = L, LAMBDA_CONS(x)(R)
    S = LAMBDA_CDR(S)
    return _partition(S, nL, nR)

nL, nR = _partition(S, L, R)

Note that _partition doesn’t change the state of the inputs L and R. Instead of changing the original input data, it returns new data that are stored in the variables nL and nR, that are the L and R arguments of the next recursive call.

We can also make that function return Church pairs instead of tuples:

p = LAMBDA_CAR(A)
L, R = LAMBDA_EMPTY, LAMBDA_EMPTY

S = LAMBDA_CDR(A)

def _partition(S, L, R):
    if l2b(LAMBDA_ISEMPTY(S)): return LAMBDA_CONS(L)(R)
    x = LAMBDA_CAR(S)
    if l2b(LAMBDA_LESS(x)(p)):
        nL, nR = LAMBDA_CONS(x)(L), R
    else:
        nL, nR = L, LAMBDA_CONS(x)(R)
    S = LAMBDA_CDR(S)
    return _partition(S, L, R)

LR = _partition(S, L, R)
nL, nR = LAMBDA_CAR(LR), LAMBDA_CDR(LR)

You can see it here.

Replacing variables by lets

A let expression allows us to define a value to a variable inside a scope so that its value will never be changed. In Python, this concept makes little sense, but it is implemented in many ways by different languages. I’ll show you some of them.

Starting by Kotlin, let is a method that can be called by any object so we can assign a temporary name to it:

val x = 2.let { a -> 
   3.let { b ->
      a + b * a
   }
}

In Haskell, let is an expression where the first half is the value attribution and the second half is the expression that we want to evaluate:

x = let a = 2
        b = 3
    in a + b * a

In Hy (Python with Lisp syntax), it is very close to Haskell: first we attribute the values to the variables, then we declare the expression that will use them:

(setv x
   (let [
      a 2
      b 3
      ]
      (+ a (* b a))
   )
)

(x will be 8 in the three examples above)

That construction is a very common in functional languages, as their variables have a fixed value inside a scope. In addition, they are easy to be written using lambda calculus. We can write the example above like that:

def _f(a, b):
   return a + b * a
x = _f(2, 3)

# or using lambda and currying:

x = (lambda a: lambda b: a + b * a)(2)(3)

Note that, like before, we are attributing a = 2 and b = 3 and then calculating a + b * a.

Our mission in this step is to put all the variables that are not argument or constants in lets, so they could be used in lambda calculus.

For now on, the code will be very unreadable, but let’s focus in an example of how that substitution is made. In the function _partition that we defined before, we’re going to replace x by a let. By now, this function looks like this:

def _partition(S, L, R):
    if l2b(LAMBDA_ISEMPTY(S)): return LAMBDA_CONS(L)(R)
    x = LAMBDA_CAR(S)
    if l2b(LAMBDA_LESS(x)(p)):
        nL, nR = LAMBDA_CONS(x)(L), R
    else:
        nL, nR = L, LAMBDA_CONS(x)(R)
    S = LAMBDA_CDR(S)
    return _partition(S, L, R)

The if here only changes the values of L and R, we can write it as an if-expression:

def _partition(S, L, R):
    if l2b(LAMBDA_ISEMPTY(S)): return LAMBDA_CONS(L)(R)
    x = LAMBDA_CAR(S)
    nL, nR = (LAMBDA_CONS(x)(L), R) if l2b(LAMBDA_LESS(x)(p)) else (L, LAMBDA_CONS(x)(R))

    S = LAMBDA_CDR(S)
    return _partition(S, nL, nR)

We’re only evaluating x in order to be used by that if-expression, so we can use a let here:

• attribution: x = LAMBDA_CAR(S)
• expression: the if-expression that we just defined

To do that, let’s declare a new function called _partition2 that takes x as its argument and call it soon after, passing as the argument x = LAMBDA_CAR(S):

def _partition(S, L, R):
    if l2b(LAMBDA_ISEMPTY(S)): return LAMBDA_CONS(L)(R)

    def _partition2(x):
        return (LAMBDA_CONS(x)(L), R) if l2b(LAMBDA_LESS(x)(p)) else (L, LAMBDA_CONS(x)(R))

    nL, nR = _partition2(LAMBDA_CAR(S))

    S = LAMBDA_CDR(S)
    return _partition(S, nL, nR)

We have a let! We can also replace the tuple by a Church pair:

def _partition(S, L, R):
    if l2b(LAMBDA_ISEMPTY(S)): return LAMBDA_CONS(L)(R)

    def _partition2(x):
        return LAMBDA_CONS(LAMBDA_CONS(x)(L))(R) if l2b(LAMBDA_LESS(x)(p)) else LAMBDA_CONS(L)(LAMBDA_CONS(x)(R))

    LR = _partition2(LAMBDA_CAR(S))
    nL, nR = LAMBDA_CAR(LR), LAMBDA_CDR(LR)

    return _partition(LAMBDA_CDR(S), nL, nR)

You can see it here.

Rewriting functions using lambda

At this point, having all the variables replaced by let, the partition and quicksort functions don’t have variables anymore. They only have some ifs, the return expression, and the definition of internal functions used by the lets (and they have the same characteristics).

Take a look at this (yeah, only a look because this code is unreadable):

def quicksort(A):
    if l2b(LAMBDA_ISEMPTY(A)): return A
    if l2b(LAMBDA_ISEMPTY(LAMBDA_CDR(A))): return A

    def _quicksort(A, LR):
        return LAMBDA_IF(LAMBDA_ISEMPTY(quicksort(LAMBDA_CAR(LR))))(LAMBDA_CONS(LAMBDA_CAR(LAMBDA_CDR(LR)))(quicksort(LAMBDA_CDR(LAMBDA_CDR(LR)))))(LAMBDA_CONCAT(quicksort(LAMBDA_CAR(LR)))(LAMBDA_CONS(LAMBDA_CAR(LAMBDA_CDR(LR)))(quicksort(LAMBDA_CDR(LAMBDA_CDR(LR))))))

    return _quicksort(A, partition(A))

def partition(A):
    def _partition(S, L, R, p):
        if l2b(LAMBDA_ISEMPTY(S)): return LAMBDA_CONS(L)(R)
        def _partition2(x, L, R, p):
            if l2b(LAMBDA_LESS(x)(p)): return LAMBDA_CONS(LAMBDA_CONS(x)(L))(R)
            else: return LAMBDA_CONS(L)(LAMBDA_CONS(x)(R))

        def _partition3(S, LR, p):
            return _partition(LAMBDA_CDR(S), LAMBDA_CAR(LR), LAMBDA_CDR(LR), p)

        return _partition3(S, _partition2(LAMBDA_CAR(S), L, R, p), p)

    def _partition4(LR):
        return LAMBDA_CONS(LAMBDA_CAR(LR))(LAMBDA_CONS(LAMBDA_CAR(A))(LAMBDA_CDR(LR)))

    return _partition4(_partition(LAMBDA_CDR(A), LAMBDA_EMPTY, LAMBDA_EMPTY, LAMBDA_CAR(A)))

We can replace all the ifs by if-expressions and those if-expressions by LAMBDA_IF that we defined using Church booleans. Besides that, the internal functions can be defined using lambda instead of def as they only have the return expression. Now we have this awful code:

def quicksort(A):
    _quicksort = lambda A: lambda LR: LAMBDA_CONCAT(quicksort(LAMBDA_CAR(LR)))(LAMBDA_CONS(LAMBDA_CAR(LAMBDA_CDR(LR)))(quicksort(LAMBDA_CDR(LAMBDA_CDR(LR)))))

    _quicksort2 = lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(A))(lambda A: A)(lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(LAMBDA_CDR(A)))(A)(_quicksort(A)(partition(A))))

    return _quicksort2(A)(A)

def partition(A):
    _partition2 = lambda x: lambda L: lambda R: lambda p: LAMBDA_IF(LAMBDA_LESS(x)(p))(LAMBDA_CONS(LAMBDA_CONS(x)(L))(R))(LAMBDA_CONS(L)(LAMBDA_CONS(x)(R)))

    _partition3 = lambda S: lambda LR: lambda p: _partition(LAMBDA_CDR(S))(LAMBDA_CAR(LR))(LAMBDA_CDR(LR))(p)

    _partition = (lambda S: LAMBDA_IF(LAMBDA_ISEMPTY(S))(lambda L: lambda R: lambda p: LAMBDA_CONS(L)(R))(lambda L: lambda R: lambda p: _partition3(S)(_partition2(LAMBDA_CAR(S))(L)(R)(p))(p)))

    _partition4 = (lambda A: lambda LR: LAMBDA_CONS(LAMBDA_CAR(LR))(LAMBDA_CONS(LAMBDA_CAR(A))(LAMBDA_CDR(LR))))(A)

    return _partition4(_partition(LAMBDA_CDR(A))(LAMBDA_EMPTY)(LAMBDA_EMPTY)(LAMBDA_CAR(A)))

In this case, the internal functions (even though they are now variables) can be constants. This way, they don’t need to be inside quicksort and partition that could only have the return expression. Then, they could be written using lambda instead of def:

_quicksort = lambda A: lambda LR: LAMBDA_CONCAT(quicksort(LAMBDA_CAR(LR)))(LAMBDA_CONS(LAMBDA_CAR(LAMBDA_CDR(LR)))(quicksort(LAMBDA_CDR(LAMBDA_CDR(LR)))))
_quicksort2 = lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(A))(lambda A: A)(lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(LAMBDA_CDR(A)))(A)(_quicksort(A)(partition(A))))
quicksort = lambda A: _quicksort2(A)(A)
_partition2 = lambda x: lambda L: lambda R: lambda p: LAMBDA_IF(LAMBDA_LESS(x)(p))(LAMBDA_CONS(LAMBDA_CONS(x)(L))(R))(LAMBDA_CONS(L)(LAMBDA_CONS(x)(R)))
_partition3 = lambda S: lambda LR: lambda p: _partition(LAMBDA_CDR(S))(LAMBDA_CAR(LR))(LAMBDA_CDR(LR))(p)
_partition = (lambda S: LAMBDA_IF(LAMBDA_ISEMPTY(S))(lambda L: lambda R: lambda p: LAMBDA_CONS(L)(R))(lambda L: lambda R: lambda p: _partition3(S)(_partition2(LAMBDA_CAR(S))(L)(R)(p))(p)))
_partition4 = (lambda A: lambda LR: LAMBDA_CONS(LAMBDA_CAR(LR))(LAMBDA_CONS(LAMBDA_CAR(A))(LAMBDA_CDR(LR))))
partition = lambda A:_partition4(A)(_partition(LAMBDA_CDR(A))(LAMBDA_EMPTY)(LAMBDA_EMPTY)(LAMBDA_CAR(A)))

Recursion and Y combinator

Some of those lambda functions are recursive:

• quicksort calls _quicksort2 that calls quicksort
• _partition calls _partition3 that calls _partition

However, a property of lambda calculus is that a function doesn’t need to have a name. But how can a function reference itself without knowing its name? The answer is Y Combinator.

To illustrate Y combinator, take a look at this factorial function:

def fac(n):
   return 1 if n == 0 else n * fac(n-1)

# using lambda:
fac = lambda n: 1 if n == 0 else n * fac(n-1)

Then we can use Y combinator to replace the fac call:

fac = (lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1))

# we even don't need to name fac. This expression calculates 5! = 120 recursively:
(lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1))(5)

What happens inside that thing? Note that we have a function (lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1)), very similar to the original fac, except that it takes an argument f and calls f(f) instead of fac. The idea of Y combinator here is that f will always be the same function and that it passes itself as an argument, recursively, in order to the allow the recursive calls to make another recursive calls. Who will guarantee the base of that recursion is (lambda f: f(f)), that will provide the first passing of that function to itself.

Mental exercise: try to simulate fac(2) and see the magic happening.

Using Y combinator

Ok, now we can replace the recursive call in quicksort by a Y combinator. By now it looks like this:

_quicksort2 = lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(A))(lambda A: A)(lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(LAMBDA_CDR(A)))(A)(_quicksort(A)(partition(A))))
quicksort = lambda A: _quicksort2(A)(A)

And if we replace it by Y combinator:

_quicksort2 = lambda r: lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(A))(lambda A: A)(lambda A: LAMBDA_IF(LAMBDA_ISEMPTY(LAMBDA_CDR(A)))(A)(_quicksort(r)(A)(partition(A))))
quicksort = (lambda r: r(r)) lambda A: _quicksort2(r)(A)(A)

Mental exercise: the quicksort call is not in quicksort itself but in _quicksort2 (that is called by quicksort). Can you figure out how Y combinator is used in that situation?

You can see it here.

Expanding everything!

At this point, all the values, data structures and ifs are functions. Also, those functions and all the others are values that can be written in a single expression.

Our work here is, basically, replace all the constants by their values so that quicksort can be a single expression. This can be done using the text replacement tool of a text editor.

Finally we have this awful thing:

quicksort = (lambda r: r(r))(lambda r: lambda A: (lambda r: lambda A: (lambda c: lambda t: lambda e: c(t)(e))((lambda l: l(lambda h: lambda t: lambda d: (lambda a: lambda b: b))((lambda a: lambda b: a)))(A))(lambda A: A)(lambda A: (lambda c: lambda t: lambda e: c(t)(e))((lambda l: l(lambda h: lambda t: lambda d: (lambda a: lambda b: b))((lambda a: lambda b: a)))((lambda p: p(lambda a: lambda b: b))(A)))(A)((lambda r: lambda A: lambda LR: (lambda c: lambda t: lambda e: c(t)(e))((lambda l: l(lambda h: lambda t: lambda d: (lambda a: lambda b: b))((lambda a: lambda b: a)))(r(r)((lambda p: p(lambda a: lambda b: a))(LR))))((lambda a: lambda b: lambda l: l(a)(b))((lambda p: p(lambda a: lambda b: a))((lambda p: p(lambda a: lambda b: b))(LR)))(r(r)((lambda p: p(lambda a: lambda b: b))((lambda p: p(lambda a: lambda b: b))(LR)))))(((lambda r: r(r)) (lambda r: lambda l1: (lambda c: lambda t: lambda e: c(t)(e))((lambda l: l(lambda h: lambda t: lambda d: (lambda a: lambda b: b))((lambda a: lambda b: a)))((lambda p: p(lambda a: lambda b: b))(l1)))(lambda l2: (lambda a: lambda b: lambda l: l(a)(b))((lambda p: p(lambda a: lambda b: a))(l1))(l2))((lambda r: lambda l2: (lambda a: lambda b: lambda l: l(a)(b))((lambda p: p(lambda a: lambda b: a))(l1))(r(r)((lambda p: p(lambda a: lambda b: b))(l1))(l2)))(r))))(r(r)((lambda p: p(lambda a: lambda b: a))(LR)))((lambda a: lambda b: lambda l: l(a)(b))((lambda p: p(lambda a: lambda b: a))((lambda p: p(lambda a: lambda b: b))(LR)))(r(r)((lambda p: p(lambda a: lambda b: b))((lambda p: p(lambda a: lambda b: b))(LR)))))))(r)(A)((lambda A:((lambda A: lambda LR: (lambda a: lambda b: lambda l: l(a)(b))((lambda p: p(lambda a: lambda b: a))(LR))((lambda a: lambda b: lambda l: l(a)(b))((lambda p: p(lambda a: lambda b: a))(A))((lambda p: p(lambda a: lambda b: b))(LR)))))(A)(((lambda r: r(r))(lambda r: lambda S: (lambda c: lambda t: lambda e: c(t)(e))((lambda l: l(lambda h: lambda t: lambda d: (lambda a: lambda b: b))((lambda a: lambda b: a)))(S))(lambda L: lambda R: lambda p: (lambda a: lambda b: lambda l: l(a)(b))(L)(R))(lambda L: lambda R: lambda p: (lambda r: lambda S: lambda LR: lambda p: r(r)((lambda p: p(lambda a: lambda b: b))(S))((lambda p: p(lambda a: lambda b: a))(LR))((lambda p: p(lambda a: lambda b: b))(LR))(p))(r)(S)((lambda x: lambda L: lambda R: lambda p: (lambda c: lambda t: lambda e: c(t)(e))((lambda m: lambda n: (lambda a: lambda b: a(b)((lambda a: lambda b: b)))((lambda m: lambda n: (lambda n: n(lambda x: (lambda a: lambda b: b))((lambda a: lambda b: a)))((lambda m: lambda n: n((lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(m))(m)(n)))(m)(n))((lambda a: a((lambda a: lambda b: b))((lambda a: lambda b: a)))((lambda m: lambda n: (lambda a: lambda b: a(b)((lambda a: lambda b: b)))((lambda m: lambda n: (lambda n: n(lambda x: (lambda a: lambda b: b))((lambda a: lambda b: a)))((lambda m: lambda n: n((lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(m))(m)(n)))(m)(n))((lambda m: lambda n: (lambda n: n(lambda x: (lambda a: lambda b: b))((lambda a: lambda b: a)))((lambda m: lambda n: n((lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(m))(m)(n)))(n)(m)))(m)(n))))(x)(p))((lambda a: lambda b: lambda l: l(a)(b))((lambda a: lambda b: lambda l: l(a)(b))(x)(L))(R))((lambda a: lambda b: lambda l: l(a)(b))(L)((lambda a: lambda b: lambda l: l(a)(b))(x)(R))))((lambda p: p(lambda a: lambda b: a))(S))(L)(R)(p))(p))))((lambda p: p(lambda a: lambda b: b))(A))((lambda a: lambda b: b))((lambda a: lambda b: b))((lambda p: p(lambda a: lambda b: a))(A))))(A)))))(r)(A)(A))

Using lambdasort

Of course we can’t use this quicksort by itself in a list as it operates in Church encoding. We’ll need a wrapper to translate the Python types to Church encoding, sort the Church list using quicksort and then translate it back to a Python list. We’re going to use the previous functions.

def quicksort_wrapper(A):
    church = pl2ll([i2l(x) for x in A])
    sorted_church = quicksort(church)
    return [l2i(x) for x in ll2pl(sorted_church)]

Now you can use quicksort_wrapper to sort your list and it will use our lambdasort as backend:

>>> from lambdasort import quicksort_wrapper
>>> x = [22, 33, 11, 55, 99, 11, 33, 77, 44]
>>> quicksort_wrapper(x)
[11, 11, 22, 33, 33, 44, 55, 77, 99]

Final thoughts

I wrote lambdasort in 2017 (my third year of university) in just two intense days, after a class by Professor Gubi about lambda calculus and Y combinator. He told us about Programming with Nothing, mentioned earlier. I found it so impressive that I wanted to do something similar, and challenged myself to write something harder then a fizzbuzz, so here we are!

Write it was really fun, and I didn’t notice at first how much I learned in only two days, and it took me years to finally write this text explaining what I did. So, thank you for reading it!

Last but not least, English is not my first language and I’m trying to make my best efforts to keep my personal page in both Portuguese and English. So, if you find something wrong about it or about anything here feel free to open a issue.