Fundamental Problems of LISP, the Cons Cell
(this essay is originally written around 2008)
The Cons Business The other fundamental problem in the language is its cons cells as its list construction primitive. Lisp at core is based on functional programing on lists. This is a powerful paradigm. However, for historical reasons, lisp's list is based on the hardware concept of “cons” cell. From a mathematical, functional, API point of view, what this means is that lisp's “list” is limited to a max of 2 elements. If you want a longer list, you must nest it and interpret it in a special way. (i.e. effectively creating a mini-protocol, known as “proper list”.) The cons fundamentally crippled the development of list processing. Lisp being historically based the cons for about 4 decades. The cons and the associated {car cdr cadr caadr caddr caaar cdddr …} are fundamentally rooted in the lisp langs, is thus not something that can be easily mended. This is unfortunate. However, this situation could be improved. By, for example: Create a standard that all list data structures must be proper lists. (this would also mean re-implement association lists to be based on proper lists)
Expose only higher-level list manipulation functions (i.e. interfaces to cons) in all new literature.
Even mark cons related constructs as obsolete. One of the myth that is quickly injected into budding lispers, is that cons is powerful. It is powerful in the sense assembly lang is powerful. Lisp's cons is perhaps the greatest fuck up in the history of computer languages. Racket Lisp described the cons problem well: Racket Doc on Lisp Cons Problem For some concrete examples of problems caused by the cons, see: Guy Steele Says: Don't Iterate, Recurse, and Get rid of lisp cons!
Why Lisp Not Have a Generic Copy-List Function?
Lisp List Problem
Frequently Asked Questions If you don't like cons, lisp has arrays and hashmaps, too. Suppose there's a lang called gisp. In gisp, there's cons but also fons. Fons is just like cons except it has 3 cells with 3 accessors: car, cbr, cdr. Now, gisp is a old lang, the fons are deeply rooted in the lang. Every some 100 lines of code you'll see a use of fons with its extra accessor cbr, or any one of the cbaar, cdabr, cbbar, cbbbar, etc. You got annoyed by this. You complain that fons is bad. But then some gisp fanatics retorts: “If you don't like fons, gisp has cons, too!”. You see, by “having something too”, does not solve the problem of pollution. I like the cons concept. Even in functional languages like Haskell it is popular, for example, when matching in the form of (x:xs), which is the same like car/cdr in Lisp. Languages that have a list data type implemented as linked list, with First, Rest accessors, do not expose it as API in the same way lisp does with explicit cons. Lisp's cons forces programer to think of list in a low-level nested of 2-item construction, with explicit functions like “cddr”, “cadaar” etc, and even a special notation “(A . B)”. This hinders the development tree functions. For example, one might write a function that extracts the leafs of a binary tree. But due to cons, there is no single data structure to implement a binary tree. You can have the whole structure made of cons, or cons only for ending branches, or whole structure made of “proper list”. Consequently, what's considered a leaf depends on your implementation, and the code to traverse the tree also depends on how you used cons. Worse, any proper list can have improper list as elements. So, you can have a list of cons, or cons of lists, cons of cons, list of lists, or any mix. The overall effect of the cons is that it prevents lisp to have a uniform high level treatment of lists, with the result that development of functions that work on tree are inconsistent and few. 2009-07-21 Addendum : there was actually a lang with “fons” of 3 cells. {Haines, E. C., The TREET List Processing Language. M.S. Thesis, MIT, Cambridge, Mass., August 1964. Also SR-133, The MITRE Corporation, Bedford, Mass., April 1965.} Thanks to Richard Fateman for alerting me to this.
Why Lisp's Cons Problem Never Got Fixed? Now, a little speculation. We might wonder, why lisp has the cons problem and was never addressed in Common Lisp or Scheme Lisp? Historical Necessity I guess at the time, 1960s and 1970s, the very fact that you could have a concept like a list in a lang and manipulate it as a unit, is a very advanced concept. The list, being built up by hardware cons, is just something that is necessary for implementation for practical considerations. (think for a moment what computers are like in the 1960s.) Having data as a single manipulable object (list) didn't really become popular until the 1990s. (notably due to Perl) And today, it is THE most important feature of high-level languages. (e.g. Perl Python Ruby PHP JavaScript) Deep Nesting is Rare The lisp's cons, as a underlying primitive that builds lists, even though a bit cumbersome, but works just fine when data structure used is simple. Even today, with all the Perl, Python, PHP, JavaScript etc langs that deal with lists, vast majority of list usage is just simple flat list, sometimes 2 level of nesting (list of list, list of hash, hash of list). 3 levels of nesting is seldom used, unless it is 3D matrices used mostly in computer graphics or linear algebra applications. Greater than 3 level is rarely seen. Systematic manipulation and exploitation of nested list, such as mapping to leafs, to particular level, transposition by permutation on level, or list structure pattern matching in today's functional langs, etc is hardly ever to be seen. (These are common idioms in so-called array languages. For example, APL, MATLAB, Mathematica.) So, in general, when you just deal with simple lists, the cumbersomeness of using {cons, car, cdr, caardr, …} for list doesn't really surface. Further, the cons is fundamentally rooted in the language. It's not something that can be easily changed except creating a new language. When there is a specific need in a application, there is a haphazard collection of functions that deal with lists at a higher level. Today, with list manipulation being mainstream, especially with the Proliferation of Programing Languages, and with JavaScript arose JSON , the lisp's cons historical baggage becomes more apparent and painful. Summary of Reasons: Lisp's list being cons as part of the language was necessary for practical implementation in 1960, 1970s.
List as a unit in programing languages did not became popular until 1990s.
By then, the cons as a lang element is deeply rooted in lisp and it is hard to change other then as a new lang.
Most use of lists in programing tasks are just flat lists. Nesting of more than 3 levels is rarely used for typical programing tasks. So, the problem of cons did not surface.
Clojure Fixed the Lisp Cons Problem cons , first and rest manipulate sequence abstractions, not concrete cons cells from: ❰2014-11-04 http://clojure.org/lisps ❱