# A Poor Man's Lisp in Python

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.