5 ms·
This article is chock-full of misinformation. > an s-expression [is] a fancy term for a list of [cons] cells No, it's not. An S-expression is a serialization
by lisper 8y ago
This article is chock-full of misinformation.
> an s-expression [is] a fancy term for a list of [cons] cells
No, it's not. An S-expression is a serialization of a (single) cons cell, whose elements might be other cells.
> We're using a vector instead [of cons cells], but the two are equivalent
No, they are not. When represented as cons cells, CDR is a non-consing O(1) operation. When represented as vectors, CDR is a copying O(n) operation (and because it necessarily makes a copy, the semantics are different if you introduce mutation).
The fact that S-expressions represent cons cells and NOT vectors is crucially important. It is the feature from which Lisp derives much of its power.
It is possible to make a Lisp-like language where the surface syntax represents vectors instead of cons cells. In fact, this makes a useful exercise. 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?
> There are three different sorts of data structure that we have so far: Strings. S-expressions, and Cells
As above, S-expressions are not a data type, they are a serialization of cons cells, i.e. they are a mapping between cons cells and strings, and this mapping has a very particular feature from which much of Lisp's power is derived, which is that it compresses a linked list of cons cells into this:
(1 2 3 4)
instead of this
(1 . (2 . (3 . (4 . nil))))
This language is missing that core feature. (It's also missing symbols, without which a language cannot rightfully call itself a Lisp. And first-class functions. And macros.)
While I don't want to discourage any attempt to make Lisp more accessible, it's important to actually get it right. What this article is describing is similar in spirit to Lisp, but it's not Lisp. It's a different (toy) language at a completely different point in the design space.
- kerkeslager 8y agoThis is the big problem with a lot of people's attempts to implement lisps to show how simple lisp is: they don't implement even a reasonable subset of lisp. A real lisp implementation will eventually require a garbage collector! Which is hardly simple. The misunderstanding, I think, comes from the fact that lisp code is typically quite terse, which is often a measure of simplicity. But part of the reason lisp code is so simple is that a lot of the heavy lifting is done behind the scenes. There's no getting around that software is complicated: the benefit of lisp is that it does a good job of managing the complicated parts while giving the programmer responsibility for a small subset of the functionality which is still powerful enough to enable the programmer to do what they need/want to do.
- giancarlostoro 8y ago> But part of the reason lisp code is so simple is that a lot of the heavy lifting is done behind the scenes. Heck, HN is powered by Arc which is (last I checked) running on Racket (or any other Lisp engine)!
- sedachv 8y ago> The misunderstanding, I think, comes from the fact that lisp code is typically quite terse, which is often a measure of simplicity. I have been programming in Lisp for a few years, and I think that Lisp programs are verbose, and not terse at all. This is because Lisp special forms and functions tend to be explicit and self-contained, which makes Lisp code more robust and easier to change and compose, than more terse notations that leave a lot of details implicit. Non-trivial programs are just shorter to write in Lisp than many other languages, partly because the Lisp primitives are better thought out, and partly because that explicitness turns out to be more concise than working around the implicit special-case rules and poor error handling of other notations, that you end up needing to do in larger programs. Things that work for one-liners may not work as well once you get past one thousand lines. You also see this in Common Lisp with DSLs like LOOP and FORMAT, which seem convenient until you run up against their limits (part of the reason why many people dislike them). The thing is that it is much easier to go from fully delimited/explicit to terse and implicit than vice-versa, if you have good primitives. Because of dynamic scoping and read macros, you can do really terse DSLs in Common Lisp in a very straightforward way (for example, Andrew Sengul did an APL subset that can be wrapped in a read macro, and I think sed would be pretty easy to do).
- agumonkey 8y agoisn't this verbosity CL only and not Lisp per se ? clojure code is often super terse (mostly because lots of funcallable and fp idioms)
- 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, ...
- tom_mellior 8y ago> If you undertake this exercise you will come to know the answer to the question: [...] We could also know the answer if you just told us. It's bad form to make readers jump through hoops for insights you could easily share. This is not school, you are not supposed to assign homework to make us learn.
- lisper 8y agoSharing this insight is not so easy. It's not a pithy aphorism that fits in an HN comment. It would take at the very least a blog post that would probably take me a couple of hours to write. Doing the exercise would take less time (do it in Python or Ruby).
- KayEss 8y agoWhat is the observable effect then? I can really only think of two: A particular performance characteristic, or that modifications of shared tails in lists are observable across lists. Is this latter that is the problem?
- lisper 8y agoVectors are a lot of work for no gain. They make everything more complicated, especially if you want an efficient CDR operation, and there's just no reason for it. Yes, your code might compile a little faster, but Lisp code is generally compiled incrementally anyway, so compile cycles tend to be measured in milliseconds already. There's just no point in speeding it up any further.
- KayEss 8y agoLOL
- tom_mellior 8y agoDon't write the blog post, only write the "conclusions" section. "Not using conses leads to more copying and more garbage being generated" or whatever.
- jdougan 8y agoAll this an no pointers to Ciel?
- lisper 8y agoI haven't worked on Ciel in such a long time I can't even remember if it's cons-based or vector based. But sure... https://github.com/rongarret/Ciel https://github.com/rongarret/Ciel