Emulating lisp cons cells in Python

Question

A list in lisp is a series of cons cells, but in Python, a native list is a different kind of object. For translating code from lisp to Python, one might simply take lisp lists and translate them to Python native lists. However, this runs into trouble with side effecting cons cells not coming across to the Python code. For example, consider this code in lisp:

(setq a (list 1 2 3 4))
(let ((b a)
      (a (cddr a)))
  (declare (special a b))
  (setf (cadr b) ‘b)
  (setf (cadr a) ‘d)
  (print a))
(print a)

;; Results in:
(3 d)
(1 b 3 d)

Is there a Python package that would provide a better emulation of lisp lists in Python? Does such package offer easy conversion to regular Python lists?

What might the above code look like in Python using such package?

Answer 1

## SICP exercise, Alonzo Church Pairs - Lambda Calculus
def cons(x, y):
    return lambda m: m(x, y)

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

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


>>> p = cons(2, 3)
>>> car(p)
2
>>> cdr(p)
3
>>> 

Check out my answer on What is your favourite cleverly written functional code? for more details.

You can also read What Is Meant by Data? from Structure and Interpretation of Computer Programs.

Answer 2

Because of some arbitrary restrictions on the use of lambda, you can't make a full simulation of mutable Lisp pairs using the λ-calculus like you could in e.g. Ruby. Fortunately, objects and lexical closures are equipotent, so the solution is to switch gears and define a class, and optionally some convenience functions:

class cons:
    def __init__(self, addr, decr):
        self.addr = addr
        self.decr = decr

    def car(self):
        return self.addr

    def cdr(self):
        return self.decr

    def rplaca(self, n):
        self.addr = n

    def rplacd(self, n):
        self.decr = n


def car(z):
    if z is None:
        return None
    else:
        return z.car()

def cdr(z):
    if z is None:
        return None
    else:
        return z.cdr()

def rplaca(z, n):
    z.rplaca(n)

def rplacd(z, n):
    z.rplacd(n)

Here is a simple demonstration that we've achieved mutability:

>>>x = cons(10,20)
>>>print car(x)
10
>>>print cdr(x)
20
>>>rplaca(x, 100)
>>>rplacd(x, 200)
>>>print car(x)
100
>>>print cdr(x)
200

Also on account of Python's dynamic typing, cons objects have the closure property, so you can create lists a la Lisp, too:

one_to_four = cons(1, cons(2, cons(3, cons(4, None))))