News for hackers. Stuff that matters.
Re:“There Is No List” by sillysaurusx on Thursday October 13, 2022 @02:21PM (#33194570)
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.

Re:“There Is No List” by jjtheblunt on Thursday October 13, 2022 @02:42PM (#33194822)
Great 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)
Re:“There Is No List” by sillysaurusx on Thursday October 13, 2022 @02:46PM (#33194857)
Incidentally, 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

His Postgres FFI is the prettiest lisp FFI you’ll ever see. https://github.com/sctb/motor/blob/master/pq.l

Re:“There Is No List” by jjtheblunt on Thursday October 13, 2022 @04:40PM (#33196210)
Thanks!
Re:“There Is No List” by cnasc on Thursday October 13, 2022 @02:45PM (#33194847)
> if Lisp had been implemented using vectors and hash tables instead

Sounds a lot like Clojure

Re:“There Is No List” by User23 on Thursday October 13, 2022 @02:45PM (#33194850)
Lisp 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.

Re:“There Is No List” by sillysaurusx on Thursday October 13, 2022 @02:51PM (#33194914)
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.

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]

?
Re:“There Is No List” by User23 on Thursday October 13, 2022 @02:55PM (#33194973)
> 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

Re:“There Is No List” by sillysaurusx on Thursday October 13, 2022 @03:05PM (#33195100)
Suppose 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.

Re:“There Is No List” by User23 on Thursday October 13, 2022 @03:49PM (#33195670)
Variable 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.

Re:“There Is No List” by math-dev on Thursday October 13, 2022 @06:45PM (#33197463)
cons is a recursive data structure. it’s not discussed much here in the comments, but a lot of its useability comes from that fact - you can write elegant recursive algorithms with cons as your data structure

with vectors that doesn’t work UNLESS you add a bit of overhead (which most optimising programs may do since for many cases vectors can be more performant)

Re:“There Is No List” by User23 on Thursday October 13, 2022 @07:51PM (#33197986)
And some Lisp implementations optimize some cons lists into vectors. The technique is called CDR encoding[1]. It's my understanding that at least the latest generation of modern CPUs actually have optimized instructions for tagged 64 bit pointers too, so this can be implemented efficiently on current hardware just as it was on Lisp machines! Of note though is that mutability complicates things, as usual.

[1] https://en.wikipedia.org/wiki/CDR_coding

Re:“There Is No List” by math-dev on Friday October 14, 2022 @12:01AM (#33199496)
Thanks for sharing this link, very useful reading
Re:“There Is No List” by lispm on Friday October 14, 2022 @02:02AM (#33200126)
It's just that since decades Lisp implementations don't do this, since most implementors don't see it providing much advantage (in speed or size) and it complicates the implementation.
Re:“There Is No List” by sillysaurusx on Friday October 14, 2022 @02:34AM (#33200276)
Incidentally, that link proves the point:

> In the presence of mutable objects, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause fragmentation of the store. This problem is typically avoided by using CDR coding only on immutable data structures.

This is exactly what I've been saying. Thank you for providing a formal reference to the idea.

(I'm a bit confused how we wound up talking past each other, since my original proposal was identical to CDR coding on immutable cons cells.)

Re:“There Is No List” by f1shy on Thursday October 13, 2022 @03:02PM (#33195072)
Without 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.
Re:“There Is No List” by sillysaurusx on Thursday October 13, 2022 @03:09PM (#33195149)
No 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/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?

Re:“There Is No List” by f1shy on Friday October 14, 2022 @03:43AM (#33200688)
Not 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.

Re:“There Is No List” by creepycrawler on Thursday October 13, 2022 @03:47PM (#33195654)
It 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.