[skissane]

> Building lists out of pairs and then using them as your intermediate format creates a lot of garbage.

I wonder if a Lisp-like language which used vectors rather than pairs as its fundamental data structure might be a better fit for severely memory-constrained systems? On average, vectors take up half the memory consumption of lists.

Such a language would end up looking rather different to Lisp though. Cons cells encourage CAR/CDR and recursion. A vector-centric language would naturally lead to a more iterative programming style.

[pjmlp]

Since the mid-70's that Lisps support vectors....

[skissane]

I know that, but that wasn't my point. Yes, all major Lisps support vectors; but they all use lists a lot more than they use vectors. One of Lisp's major features is "code as data", but that code is almost all lists of lists (as opposed to vectors of vectors). I was talking about a Lisp-like language in which vectors, not lists, are the primary data structure. Possibly even one which doesn't have cons cells at all, only vectors. I am suggesting such a language might possibly work better in severely memory poor environments than a more traditional Lisp would.

[pjmlp]

Then you're also aware that one of the beautiful things of Lisp is how it allows to abstract the hardware beyond the core primitives, there is nothing that prevents an optimizing Lisp compiler to map what looks like lists to vectors at the machine code level.

One reason why such optimization isn't common is most likely due to the current usage of Lisp across the industry, and the commercial implementations being a niche product.

[jhgb]

How would you save memory using vectors for example relative to using CDR-coding?

[skissane]

In principle, you can save the same amount of memory with CDR-coding.

In practice though, you run into some issues (1) RPLACD/set-car! makes CDR-coding much more complicated (I suppose you can just ban it – in Racket, pairs are immutable by default, although there is also a separate mutable pair type); (2) CDR-coding generally only works if you construct the list up-front, the existence of CONS can encourage a coding style in which you don't do that; (3) to fix (2), you can force the list to be CDR-coded by duplicating it, but you have to remember to do that at right points – if you don't do it, you'll miss out on the benefits of CDR-coding, but if you do it when you don't have to you are unnecessarily harming performance; (4) since CDR-coded and non-CDR-coded lists are the same type, and indistinguishable without peeling off the covers of the implementation, it makes it harder for the programmer to address (2) and (3) correctly.