Hacker News Reader

This 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.

> 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)!

> 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).

isn't this verbosity CL only and not Lisp per se ?

clojure code is often super terse (mostly because lots of funcallable and fp idioms)

> 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.

Sharing 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).

What 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?

Vectors 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.

LOL

Don't write the blog post, only write the "conclusions" section. "Not using conses leads to more copying and more garbage being generated" or whatever.

Conclusions: Lisp is invariably implemented in terms of conses rather than vectors for a wide variety of reasons, which were discussed in detail in the preceding post. No one of these multiple reasons stands out as the "killer advantage". Vectors just turn out to be the death of a thousand complexities, whereas conses are simple, extremely flexible, and sufficiently efficient for the purpose. A great deal of additional insight can be gained by actually implementing Lisp both ways and experiencing the differences first hand.

All this an no pointers to Ciel?

I 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

> 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).

Typically, 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

Lisps do not "typically" use this relatively obscure data structure. Can you name one Lisps that use it? If so, how about two more?

It's also fascinating that none of the 'benchmarks' in the paper practically matter (today) in a native Lisp implementation: creating, copying, appending, mapping, ...

The 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.

That would be surprising. Typically Lisp implements lists in terms of cons cells and the empty list.

> 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.

There 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.

So are you asserting that Clojure is not a Lisp, or that Clojure indeed uses cons cells, contrary to the comment mentioned above?

How would Clojure be a Lisp, given that it runs zero Lisp code?

The 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).

> 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.

Languages that don't share code cannot be called dialects, QED. According to the most common linguistic definition of "dialect", they lack "mutual intelligibility".

> Like ML was derived from Lisp

Like English was derived from Latin, French and Scots (among other things), yet is not Latin or French or Scots.

Like Romantic music was derived from Baroque, yet is not Baroque; or rock was derived from blues but isn't blues.

Etc.

To say "Swahili speakers don't understand English" is already to assume that Swahili is not a dialect of English, and therefore a circular argument. Or else you would have to admit that Swahili speakers do understand an English dialect: their own!

Take someone who is trained in Clojure programming and nothing else; which Lisp's code can they understand that is not derived from Clojure, like ClojureScript?

Basically, the criterion for a "dialect" is mutual intelligibility. A language which is an island isn't a dialect of anything. Two languages that are not mutually intelligible are not dialects.

Lisps are dialects which share a mutual intelligibility formed by the core that comes from the ancient Lisp. They are based on the same or very similar core concepts and use the same names for them.

>To say "Swahili speakers don't understand English" is already to assume that Swahili is not a dialect of English, and therefore a circular argument. Or else you would have to admit that Swahili speakers do understand an English dialect: their own!

That's not really a counter-argument by absurdity to my argument, as it's also valid.

To say "Swahili speakers don't understand English" indeed already assumes that Swahili is not a dialect of English. When one says "Swahili speakers don't understand English" they don't make an argument -- they make a statement of fact.

Now, one could argue that the fact that Swahili is different than English is well established, and needs no further arguments (as people will already be familiar with it and accept it).

But regarding whether Clojure is or is not a dialect of Lisp, I don't think that's the case.

> as it's also valid.

Possibly so, but it isn't sound.

What about it is not sound? I wrote an extended explanation of why it's not an argument, but a statement (that needs to be evaluated as such).

'(zero) ?

'(zero . nil)

Which Lisp code are you asserting it can not run? Scheme? CommonLisp? Racket? Emacs Lisp?

Furthermore which of those Lisp dialects can or cannot run each other’s code? Is your definition of “Lisp code” a primordial core of which a set of languages descend? If so, what is that primordial core?

To my mind the defining characteristic of a Lisp is that code is represented as a first-class data structure, one that can be produced by parsing text, but that has more structure than text. In the case of most Lisp's that first-class structure is a cons cell, and I think that is by far the best choice, but I don't think that using a different structure should be disqualifying by definition. If you're really going to be that strict about it, then Scheme is not a Lisp because its standard does not actually specify the data structure that is used. It only specifies that code can be represented "as data" but it doesn't say what kind of data that is. It could be a string and still conform to the standard.

> 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.