3 ms·

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

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.

lelanthran 1y ago
> 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.
dwringer 1y ago
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.
light_hue_1 1y ago
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.
astine 1y ago
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.
- adastra22 1y ago
  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?
  - astine 1y ago
    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.collections.generic.linkedlist-1?view=net-9.0 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.
- DonaldFisk 1y ago
  > 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.
noosphr 1y ago
cons is not purely functional since set-car! and set-cdr! have existed just as long as cons had.
- DonaldFisk 1y ago
  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.
  - noosphr 1y ago
    Cons cells are mutable. Saying that cons is functional as long as you don't modify the result later is like saying that variable assignment in C is functional. There are lisp dialects that have immutable cons: https://docs.racket-lang.org/reference/pairs.html https://docs.racket-lang.org/reference/pairs.html

lelanthran 1y ago

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

dwringer 1y ago

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.

light_hue_1 1y ago

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.

astine 1y ago

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.

adastra22 1y ago
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?
- astine 1y ago
  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.collections.generic.linkedlist-1?view=net-9.0 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.
DonaldFisk 1y ago
> 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.

noosphr 1y ago

cons is not purely functional since set-car! and set-cdr! have existed just as long as cons had.

DonaldFisk 1y ago
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.
- noosphr 1y ago
  Cons cells are mutable. Saying that cons is functional as long as you don't modify the result later is like saying that variable assignment in C is functional. There are lisp dialects that have immutable cons: https://docs.racket-lang.org/reference/pairs.html https://docs.racket-lang.org/reference/pairs.html