3 ms·
You'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
by sillysaurusx 4y ago
You'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] ?
- User23 4y ago> Yes, 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. What? MAP[1] works just fine with vectors and other sequence types. Are you somehow surprised that MAPCAR doesn't? The name makes it pretty obvious I'd think. I'm starting to think you just lack familiarity with the language that you're criticizing. [1] http://clhs.lisp.se/Body/f_map.htm http://clhs.lisp.se/Body/f_map.htm
- sillysaurusx 4y agoSuppose Lisp were forced to abandon cons cells and could only use vectors to represent code. What's the disadvantage? My retort to you would be "I'm starting to think you like complexity for the sake of it," but debates are much more fun when we're both genuinely interested in the other's perspective.
- User23 4y agoVariable length vectors are observably more complex than 2-tuples. And forgive me, but you are giving me the impression that you are trolling rather than debating. Suppose Lisp were forced to abandon cons cells and could only use SQL tables to represent code. What's the disadvantage? Anyhow, by all means write your Python vector based Lisp dialect. It's no skin off my teeth. Maybe it really is superior and you'll be the next Rich Hickey.
- f1shy 4y agoWithout having any idea of this, right now I'm facing the problem of making a PDDL compiler (which is basically Lisp) in C++ , and this was the way I took. Lists are just std::vectors<std::variant>> and the variant can be a function, number (literal) or a variable.
- sillysaurusx 4y agoNo way! Is the code available anywhere? I was messing around with this idea too but didn't have the time. That's fantastic. :) std::variant is really tricky, mostly because of C++'s type system. I went with std::any. My attempt is here: https://gist.github.com/shawwn/63e0f010479efd95ebffdf2108645ad3#file-runtime-h-L428-L448 https://gist.github.com/shawwn/63e0f010479efd95ebffdf2108645... I'd love to see your code and compare notes! Mine is pretty crummy; I'm not sure there are any worthwhile ideas in it. Did you have much trouble with the std::variant route?
- f1shy 4y agoNot jet. I'm working with a friend. Even though the code is in github, is still private, until we have a first working version. What I'm doing is an extremely simple evaluator, which can do what is required for PDDL: basic arithmetic, logic operators and IF.
- creepycrawler 4y agoIt seems you're suggesting making CDR into an O(N) operation. So for example ordinary list processing algorithms that take O(N) will now be O(N^2). Anyway, these kind of weird arguments from people who don't get it have been proposed and shot down a million times before, and I'm not sure there's any value reiterating. I suggest anyone interested in Lisp (or any programming language, really) ignore weird HN critiques and just read a book, like the one linked here.