MJS prompted reconsidering Lisp's core compound data-structuring element, conses/lists. The main point was roughly that conses/lists are too crude, and too concrete (although their typing weakness will not be addressed here).
So, first a view of why and how they are overly primitive. Then a sketch of a reasonable possible replacement idea (as Scheme).
Conses/lists seem like a mismatch in the language. They are more rudimentary than they should be compared to their context. They are also a little weak compared to common programming equivalents.
The grounds of the opinion is a sense of data-structure/algorithm symmetry – that the basic algorithmic means should balance with the basic data-structuring means. This is not very well-founded, it just has an immediately reasonable appeal.
Seemingly, conses/lists presume to be the lambda of data structures. Do they merit that position? Yes they do, in a way, But the problem is that is not what we want. They should really be equivalent to procedures/functions, which are a notch more developed for programming than lambdas.
Lambdas, in lambda-calculus world, assemble in a currying way: they do not have parameter lists, but chain calls of single parameters. This matches conses/lists.
But Lisp does not really have lambdas, it has procedures/functions – calls are not currying and parameters are arrays, each addressed by name. So, to match, Lisp should not have conses/lists, but instead the slightly higher level equivalent to procedures: dictionary-trees. A ‘dictionary-tree’ being: a tree-like structure, with items at each node addressed by name – like a JavaScript/Lua object.
Replace ’pair
’ (in Scheme) with an alternative data structuring building-block, ’branch
’:
branch
This is like pair
except generalised and easified:
And this generalised structure is simpler than pair
: pair
's having two items is like a special constant, ad hoc (but for what good reason now?).
Branchs/trees are a superset of pairs/lists, so could straightforwardly support all list operations. A pair is just a branch with two items, named ‘car’ and ‘cdr’. Nil is perhaps redundant, since the tail end of a list could simply have only one item. But nil can be explicitly represented by a branch with zero items.
Operations on branchs/trees can be quite easily adapted from Scheme's operations on pairs/lists:
(branch?
<arg>)
(tree?
<arg>)
– is not some other graph shape(null?
<arg>)
– is zero-size branch(branch
[(name-value
<name> <value>)
...])
– like cons and list(append
<branch> (name-value
<name> <value>)
...)
– add at leaf end(reverse
<branch>)
– reverse branch (index) ordering
(item
<branch> <name|index> [<name|index> ...])
– read a value, optionally recursively(branch-size
<branch>)
– item count (not including branchs?)(tree-size
<branch>)
– recursive(item-set!
<branch> <name|index> <value>)
(item-add!
<branch> <name|index> <value>)
(item-del!
<branch> <name|index>)
(tree->vector
<branch> [<order>])
It is not entirely convincing, yet there is something to it. (And of course, it would no longer be Lisp: it would be Trep.)