4 ms·
> If you undertake this exercise you will come to know the answer to the question: why has this idea (a vector-based Lisp) not gained more wide-spread adoption?
by bitwize 8y ago
> If you undertake this exercise you will come to know the answer to the question: why has this idea (a vector-based Lisp) not gained more wide-spread adoption?
It's gained incredibly widespread adoption. Clojure doesn't use cons cells at all; lists are trees of vectors internally, and vectors and maps enjoy first-class status, even as syntactic elements, right alongside lists. Clojure enjoys far more business interest than Common Lisp or any other Lisp dialect, meaning that non-cons-cell based Lisp has won.
Furthermore, the C++ programmers, being performance minded, have learned something the Lisp guys still don't seem to grok: on modern architectures where cache is fast and RAM is slow, the big-O inefficiency of using vectors vs. linked lists is usually more than made up for by the speed gains of cache locality, to the extent that for real-world data structures it almost never makes sense to use a linked list rather than a vector.
Anyway, if you represent a list as a slice of an underlying vector, cdr is still O(1).
- sparkie 8y agoTypically, lisps will implement their lists internally in terms of a VList[1] or similar data structure, which has some of the benefits of both linked lists and vectors, and the downsides of each are minimized. VLists are [O(1) cons, car, cdr, index average] and [O(log N) length, index worst case], making them a pretty good all-rounder. There is also improved cache locality as compared to a linked-list. [1]:http://lampwww.epfl.ch/papers/techlists.pdf http://lampwww.epfl.ch/papers/techlists.pdf
- kazinator 8y agoLisps do not "typically" use this relatively obscure data structure. Can you name one Lisps that use it? If so, how about two more?
- lispm 8y agoIt's also fascinating that none of the 'benchmarks' in the paper practically matter (today) in a native Lisp implementation: creating, copying, appending, mapping, ...
- kazinator 8y agoThe paper is annoyingly undated; the highest year that occurs among the citations is 1999, so I'm taking that to be its date. The discussion on garbage collection of these vlists is noteworthy. The paper admits that their aggregation causes retention of garbage ("Large parts of the unused list structure may not be garbage collected."), and since they have heterogeneous sizes, fragmentation also. But, oh, that's totally okay, because all you have to do is make your collector copying to compact these things and you're good! cons cells cause no fragmentation whatsoever (they can be placed in a dedicated cons heap in which everything is a cons of the same size), and an unreachable cons cell is always reclaimable.
- lispm 8y agoThat would be surprising. Typically Lisp implements lists in terms of cons cells and the empty list.
- lisper 8y ago> non-cons-cell based Lisp has won In terms of usage, yes. Not in terms of adoption as an implementation technique. If you want a non-cons-cell-based Lisp (and no one actually wants this -- that code is vectors is not the reason people use Clojure) you have only one option. > vectors and maps enjoy first-class status, They do in Common Lisp as well. > even as syntactic elements Vectors have a standard surface syntax in Common Lisp, and it's trivial to define a reader macro for maps if you want one. But anything you would do with a static map is probably better done with a CASE form. > the big-O inefficiency of using vectors vs. linked lists is usually more than made up for by the speed gains of cache locality All of this only matters when processing code, which is usually a tiny fraction of the CPU time. When processing data, Lisp has vectors, and Lisp programmers can and do use them. > if you represent a list as a slice of an underlying vector, cdr is still O(1). Yes, but then you still have to allocate memory to store the result.
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- kazinator 8y agoThere is no such thing as a non-cons-cell-based Lisp. Just like there is no non-H2O water. Well, there are isotopes: D2O is "heavy water". Similarly, not all Lisps have exactly the same cons representation down to the sub-atomic level; there are various isotopes.
- Dangeranger 8y agoSo are you asserting that Clojure is not a Lisp, or that Clojure indeed uses cons cells, contrary to the comment mentioned above?
- lispm 8y agoHow would Clojure be a Lisp, given that it runs zero Lisp code?
- coldtea 8y agoThe argument you made is cyclical -- it assumes what it's asked to prove. To say "Clojure doesn't run Lisp code" is to already assume Clojure is not a Lisp (else you would have to admit that it does run Lisp code: its own).
- lispm 8y ago> The argument you made is cyclical It's not. Lisp code existed before Clojure. If it can only run its own code, then it is no Lisp. Lisps share code. I have a zillion lines of Lisp code. Then Clojure appears. It runs none of my zillion lines of Lisp and none will be directly translated to it (because it uses different data structures, has different operators, has different semantics, has different pragmatics). -> it's no Lisp It's derived from or influenced by Lisp, that's it. Like ML was derived from Lisp (it was originally even implemented in Lisp) and does not run any Lisp code. It's also no Lisp.
- kazinator 8y ago
- lispm 8y ago> Furthermore, the C++ programmers, being performance minded, have learned something the Lisp guys still don't seem to grok: on modern architectures where cache is fast and RAM is slow, the big-O inefficiency of using vectors vs. linked lists is usually more than made up for by the speed gains of cache locality, to the extent that for real-world data structures it almost never makes sense to use a linked list rather than a vector. Contrary to your claim, that's nothing new. Memory hierarchies have existed decades ago, too. Lisp users have found that linked lists as a primitive data structure were fast enough for many applications. Other native data structures like vectors, multi-dimensional arrays, hash-tables, etc. have been supported in Lisp for decades.