Comment by sillysaurusx

Shared structure is overrated. The cases where you need a tree-like mutable structure are vanishingly small in modern times. Mostly it boils down to "just use hash tables."

This isn't just a dismissive observation. It's the heart of why Lisp is so hard to implement. When I ignored mutable cons cells, I realized I could just implement bel in Python by using actual Python lists.

    t = True
    nil = None

    def car(l):
        if l:
            return l[0]

    assert car(nil) == nil
    assert car([]) == nil
    assert car([1]) == 1
    assert car([[1]]) == [1]
    assert car(car([[1]])) == 1
    assert car(car([(1, 2)])) == 1

    def sequence(x):
        return isinstance(x, (list, tuple))

    def cdr(l):
        if l:
            if v := l[1:]:
                if v[0] == ".":
                    if sequence(l):
                        if len(l) == 3 and l[1] == ".":
                            return l[2]
                return v

    assert cdr(nil) == nil
    assert cdr([]) == nil
    assert cdr([1]) == nil
    assert cdr([1, ".", 2]) == 2
    assert cdr((1, 2, 3)) == (2, 3)
    assert cdr("foo") == "oo"

    def join(x=nil, y=nil):
        if sequence(y):
            return [x, *y]
        return [x, ".", y]

    assert join(nil, nil) == [nil]
    assert join(1, 2) == [1, ".", 2]
    assert join(1, '"foo"') == [1, ".", '"foo"']

Presto, now you have car, cdr, and join (cons) in Python.

This works (and works very well). You can build lists with Lisp and then pass them off to other Python libraries -- after all, they're just lists. And in the rare case where you care about mutating cons cells, you can just use a dict instead.

EDIT: See https://news.ycombinator.com/item?id=33194570 for a more thorough explanation of why mutable cons cells are problematic.