4 ms·
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 h
by sillysaurusx 4y ago
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 https://news.ycombinator.com/item?id=33194570 for a more thorough explanation of why mutable cons cells are problematic.
- jjtheblunt 4y ago> Shared structure is overrated. Every MMU running a Unix with mmap probably disagrees!
- sillysaurusx 4y agoYou're right, I was imprecise. I meant specifically shared list structure in Lisp contexts, not shared structures in general. There's a fascination in the Lisp world for cons cells. Specifically the cell aspect. If you represent lists as: l = [x, [y, [z]]] Then you can implement car as l[0] and cdr as l[1]. If you require mutable cons cells, that's pretty much the only way to do it. Because if you want to set the car of cdr(l), how do you do it? You can just do cdr(l)[0] = t Because that's the same as l[1][0] = t Which of course makes the list become l = [x, [t, [z]]] But this sucks. It's always sucked, and Lispers go out of their way to ignore the fact that it sucks. I wince at having such a dismissive attitude here, but it's been the source of years of frustrations. It's a frustration because if Lisp had been implemented using vectors and hash tables instead, it'd be in a far stronger position today. Everyone uses vectors. Vectors are [1, 2, 3, 4] ... Plain old arrays! In fact, I used vectors in the above examples, and didn't even have to explain what they were. Everyone knows and understands arrays. Lisp can work fine with vectors, if you drop the requirement of mutable cons cells. Because l becomes: l = [x, y, z] And cdr(l) becomes l[1:], so cdr(l) returns [y, z] -- an entirely new vector containing y and z. This might seem like nonsense, but in practice it's not. In practice, you're rarely building lists containing hundreds of thousands of elements. Usually it's much smaller lists contained in other structures, like hash tables. And when the lists are small, you really don't care about creating new lists. The fact that cdr(l) returns a copy of l minus the first element is inconsequential. You'll ~never experience a slowdown. And the gains are massive. You get to interface with all your native libraries using lisp algorithms. You don't have to convert from "lisp lists" to "python lists" or "javascript lists" or anything else. They're just arrays.
- jjtheblunt 4y agoGreat write-up (and that's from someone first doing Lisp in 1987, then lots of Scheme and tons of Mathematica, as well as all the compiled things)
- sillysaurusx 4y agoIncidentally, it wasn’t my idea. It was Scott Bell’s. I’m not sure if he thought of it or got it from somewhere else, but it’s wonderfully effective. If you want to try it out for yourself, give Lumen a spin: https://github.com/sctb/lumen https://github.com/sctb/lumen His Postgres FFI is the prettiest lisp FFI you’ll ever see. https://github.com/sctb/motor/blob/master/pq.l https://github.com/sctb/motor/blob/master/pq.l
- jjtheblunt 4y agoThanks!
- cnasc 4y ago> if Lisp had been implemented using vectors and hash tables instead Sounds a lot like Clojure
- User23 4y agoLisp has had vectors and hash tables considerably longer than Python has existed. It's a general purpose language, and any competent Lisper uses the right data structure for the job. As it happens, the cons tree (not a list, a tree!) is the right data structure for representing Lisp code. It's not necessarily the right data structure for representing other non-code data that Lisp code is working with.
- sillysaurusx 4y agoYes, but cdr(vector(1, 2, 3)) throws an error in almost all lisp implementations. Which means you can’t use the classic algorithms on them, like map. It’s worth considering carefully why you feel cons cells are so important for lisp code. Nested vectors are trees. Why not represent (define (foo x) x) as [define, [foo, x], x] ?
- reikonomusha 4y agoI fail to see why mutable cons cells has anything to do with the difficulty of implementing Lisp. @dataclass class Cons: car: Any cdr: Any You can define a nice printer or reader for it if you want, but mutability doesn't seem to be a hindrance in implementation.
- sillysaurusx 4y agoYou can, but then none of the Python libraries that expect Python lists can use your Cons as a list. I tried. It sucks. The conversion becomes a problem all over the place. isinstance(Cons(nil, nil), list) will fail, for example. I posted a more thorough answer here: https://news.ycombinator.com/item?id=33194570 https://news.ycombinator.com/item?id=33194570
- phoe-krk 4y agoThis isn't a case of Lisp being hard to implement, this is a case of trying to make your Lisp work with Python language idiosyncrasies. These two issues have close to nothing to do with one another.
- Turing_Machine 4y agoPython...Python...Python... I think I see where your problem actually is.
- taeric 4y agoShared mutable state is an odd focus here. The point isn't that a cons cell is some magical thing. The point is that LISP gives you a ton of things that it already knows how to do. Other languages have started catching up with massive standard libraries. But... LISP has been there for a long time.
- lispm 4y ago> It's the heart of why Lisp is so hard to implement. Lisp is hard to implement? The list processing core is very small and relatively easy to implement.
- mrkeen 4y ago> 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." So confused by this. Shared, tree-like, and mutable seem pretty orthogonal to me. Sure, I'll forgo mutable structure. And since I don't mutate, I can safely share structure. But I don't want O(n) update operations, so I'd better make my hash tables use a tree-shaped data structure: https://en.wikipedia.org/wiki/Hash_array_mapped_trie https://en.wikipedia.org/wiki/Hash_array_mapped_trie