A Poor Man's Lisp in Python

Jun 25, 2021

This is the rather impractical exercise of translating the function multirember&co introduced in chapter 8 of The Little Schemer from Lisp into Python. The function illustrates continuation-passing style programming.

Let's start with the primitive functions for working with lists in Lisp style. We imitate cons cells using lambda functions.

def cons(x, y):
    return lambda f: f(x, y)

def car(f):
    return f(lambda x, y: x)

def cdr(f):
    return f(lambda x, y: y)

Our cons returns a function which accepts another function f and returns the result of applying f to the two arguments x and y, which are captured by the closure. Now we can easily extract an individual cons part by passing a function that simply returns its first or second argument (car/cdr). To get the list (1 2 3), we write cons(1, cons(2, cons(3, None))). This is cumbersome, so I'll add a little helper function for 'consifying' any number of arguments.

def consify(*args):
    if not args:
        return None
    return cons(args[0], consify(*args[1:]))

Another unpleasantry is that printing the result of our cons function only gives us an ugly function pointer. Fortunately, implementing a recursive pretty formatter is easy.

def pretty(lat):
    if not lat:
        return
    return f'({car(lat)} {pretty(cdr(lat))})'

lat = consify(1, 2, 3)
print(pretty(l)) # -> (1 (2 (3 None)))

With these basic functions, we are already able to implement and test multirember with a collector (a continuation).

def multirember(a, lat, col):
    if not lat:
        return col(None, None)
    elif car(lat) == a:
        return multirember(a, cdr(lat),
            lambda newlat, seen: col(newlat, cons(car(lat), seen)))
    else:
        return multirember(a, cdr(lat),
            lambda newlat, seen: col(cons(car(lat), newlat), seen))

We recurse on our list of atoms lat, building a list of atoms equal a and another list of atoms not equal a via the collector function col, which gets a new layer with each recursive step.

What can we do with this? We can define a collector function that works on the final two lists and returns a result, for example, a function that pretty formats these lists into strings or a function that determines the length of these lists.

lat = consify(1, 9, 9, 3, 4)
print(multirember(9, lat, 
    lambda newlat, seen: (pretty(newlat), pretty(seen))))
# -> ('(1 (3 (4 None)))', '(9 (9 None))')

def length(l):
    if not l:
        return 0
    return 1 + length(cdr(l))

print(multirember(9, lat, 
            lambda newlat, seen: (length(newlat), length(seen))))
# -> (3, 2)

Friedman, D. P., & Felleisen, M. (1996). The Little Schemer. MIT Press.