Hacker News Reader

Comment by ts4z | Hacker News Reader

A lot of things in Lisp force the implementation of lists as cons cells. It’s probably possible to do something different, but no one has, and the result won’t be a Common Lisp.

(Consider that the detail of improper lists is enshrined in the language.)

View on HN

> A lot of things in Lisp force the implementation of lists as cons cells

This is one of the reasons that Clojure wasn’t written to be backwards compatible with CL. Rich chose to implement all of his core functions on the first/rest abstraction instead, as explained in his Clojure for Lisp Programmers talk.

https://youtu.be/nDm-QDEXGEA?t=32m47s

Common Lisp does have proper arrays as well, which can be used if the situation calls for it.

As it turns out, arrays aren't actually used that much (except for strings of course) in CL code. Most lists are just a few elements long, and regular lists are perfect for that.

I use arrays much more than lists, for the same reasons arrays are useful in any language. Plus they're dynamically resizable and you can map across them in Lisp just like lists. For many purposes arrays are a much better choice than lists in CL.

Definitely nothing wrong with that. When manipulating large sets of data, they are definitely necessary.

The structure of a list is still exposed, and that decision is baked into the essence of Lisp. If you have a list, you cannot substitute a skip list or an array. If you have a skip list, it is (I think) not a language-level sequence and so things like rest and nth won’t work on it.

Arrays, struts, all other things are possible, but the things that make Lisp Lisp mean that you may get a list where repeatedly calling cdr may result in something that is not listp (cons or nil). And that’s weird. It enables some things that are wonderful, but I think the Lisps are practically unique in conflating pairs and list elements.

I bet CL allows generalizing nth and cdr. My point is still that the list structure in Lisp is very baked into the language.

Common Lisp has a standard abstract data structure called 'sequence' and generic operations for it. Sequences are either vectors or lists. Vectors are bit vectors, strings, general vectors, ... Sequence operations are then supported for all subtypes of sequences.

http://www.lispworks.com/documentation/HyperSpec/Body/c_sequ...

There are some problems with this design. The main motivations for it were:

* basic operations in Lisp are type specific, one wanted to have some generic operations and a generic sequence abstraction over lists and vectors

* the low-level data structures like conses, arrays, tables are not object-oriented and generic

* generic operations in a dynamically typed language are slower, since there is always a runtime dispatch necessary

* to remove runtime dispatch one can use type declarations (which are optional in Common Lisp) or a JIT compiler (which is not used in most implementations, they do AOT compilation)

* the language at the type of this design had no agreed OOP extension - CLOS came some years later -> sequences are non-extensible and don't support adding new sequence types

The design of this was later improved in languages like Dylan: see the Collections of Dylan

http://lispm.de/docs/prefix-dylan/book.annotated/ch12.html

Recently some CL implementations experiment with extensible sequences.

http://www.doc.gold.ac.uk/~mas01cr/papers/ilc2007/sequences-...

Reply on news.ycombinator.com