The cons is integral to Lisp, and is used to construct the list, which is a purely functional data structure. Other languages also have lists, e.g. Prolog and Haskell (as well as similar pure functional languages).
Saying that they're a fundamental problem in Lisp is like saying that objects are a fundamental problem in Smalltalk or that arrays are a fundamental problem in APL.
If Xah doesn't like cons cells, there are other languages he can use instead. Lisp (as well as Prolog, Haskell, ML, etc.) programmers won't be persuaded to abandon cons cells or lists as they find them extremely useful.
Not only has Haskell "abandoned" cons cells, its lists were never cons cells at all. The type system forbids (a . 1) entirely.
In Haskell there's a movement to get rid of much of the special syntax for lists. And a lot of code has moved on from lists. Many people never use them, I don't.
What killed lists is the reality of their horrific performance. They were great 40 years ago. But memory and CPU speed have scaled with different factors that make lists almost always the wrong choice.
> Lisp (as well as Prolog, Haskell, ML, etc.) programmers won't be persuaded to abandon cons cells or lists as they find them extremely useful.
Who said anything about abandoning lists? The argument appears to be that lists don't need to be built up out of two-element cells (i.e cons cells), and that Lisp, by enforcing `cons` cells as a way to construct lists, is seeing some limitations.
TBH, I agree a little that that PoV - there is no need for exposing the implementation of the list to the programmer, much less forcing the programmer into using the implementation.
The other problem with enforcing lists to be constructed of cons cells is one of performance; the default list in Lisp is a cache-invalidating monster.
Also to be fair to Common Lisp, it has lots of support for sequences that aren't functional lists. Cons cells just happen to be convenient for representing things like the source code so they are prevalent. They're hardly a requirement for any algorithm's logical implementation.
Xah's complaint appears to be that cons cells are too low level a construct to expose to the user. He seems fine with lists in general but just dislikes how they are implemented in Lisp. If I were to implement a list in a non-Lisp language (like C or whatever,) it would likely internally include a struct called "Node" that filled the same purpose as cons cells do in Lisp. However, users of this hypothetical 'list' usually wouldn't directly interact with these "Nodes"; they would mostly be an implementation detail, as appears to be the case for most list implementations other than Lisp's. I think that Xah is wishing that was the case for Lisp as well.
> Xah's complaint appears to be that cons cells are too low level a construct to expose to the user
On his web page, he writes:
> Lisp's cons forces programer (sic) 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)”.
Except, most of the time, it doesn't. For example, I think (a b c) is a list of three elements. If I want c, I call (third '(a b c)), not (caddr '(a b c)). I know it's stored as (a . (b . (c . NIL))) and that third is just an alias for caddr, but I'm not forced to think that way.
So why not just think in terms of lists, which can be nested, rather than cons-cells, which are only rarely used for anything other than to construct lists? The cons function itself would still be needed, as adding a value to a list without modifying the original list is extremely useful. Or you could think in terms of the more abstract data structures (parse trees, Lisp functions, etc.) you construct from lists.
When learning and using a language, it's important to think in that language.
So why not just think in terms of lists, which can be nested, rather than cons-cells, which are only rarely used for anything other than to construct lists?
Because, as he continues:
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.
In other words, the fact that the implementation details for lists are so exposed means that you have to be careful when interacting with 'lists' that turn out not to be actual lists. There is no type information, either at compile or runtime, that ensures that what you're dealing with is actually a list and not something else. So you can't _actually_ think in terms of lists; you have to think in terms of cons cells which are probably lists but might not actually be so.
> So why not just think in terms of lists, which can be nested, rather than cons-cells, which are only rarely used for anything other than to construct lists?
Cons cells are used to construct other higher-level data structures, like trees, not just lists.
But this whole discussion seems to just be a version of the usually static vs. dynamic typing discussion, where the “you have to think in terms of cons not lists” side is the static typing side saying that without handcuffs making it statically impossible to do the wrong thing you can't ever stop thinking about the things that could be done even if you aren't doing them and the “you can think in terms of lists without a problem” is the dynamic typing side saying “no, we actually don’t need to think about other possibilities unless we actively choose to use them”.
I’m confused as to what that would look like though. If you implement a linked list in C/C++, it ends up looking like cons. What is Xah imagining it would be otherwise?
You'll have an equivalent of a cons cell in any linked list implementation, but you won't necessarily interact with it as a user. Look at the standard library implementation of a linked list in C# for example (https://learn.microsoft.com/en-us/dotnet/api/system.collecti...). You see methods for looping over a list, for accessing elements, for insertions and removals, but not much for directly accessing a list's nodes and manually constructing a list out of those nodes. That part is abstracted away.
You mean Lisp isn't purely functional, as it has rarely used functions which destructively modify cons cells and lists. The cons function itself has no side effects, so is purely functional. As long as you avoid list-modifying functions, the cons data structure and any lists built from it are purely functional data structures (i.e. their contents never change), just like in Prolog and Haskell.
Saying that they're a fundamental problem in Lisp is like saying that objects are a fundamental problem in Smalltalk or that arrays are a fundamental problem in APL.
If Xah doesn't like cons cells, there are other languages he can use instead. Lisp (as well as Prolog, Haskell, ML, etc.) programmers won't be persuaded to abandon cons cells or lists as they find them extremely useful.