I've found the documentation for Janet to be fairly adequate. What are some parts where the documentation could be better?
If you need to explain image-based to people unfamiliar, that's not a bad analogy.
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.
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.
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.
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”.
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
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.
This seems to just complain that cons is hard to understand or something, without actually saying what makes it hard or unintuitive.
--------
Cons is fundamentally a linked list. The "pair" is a (value+pointer), and sometimes "value" can itself be a pointer. So when you have (pointer, pointer), you now can create trees.
As such, "Cons" is a powerful abstraction for trees, pairs, and linked lists. That's all it is. If you need "more" than this (ie: graphs), then perhaps its insufficient.
---------
"Cons" itself is a malloc(sizeof(pair)) operation. While car/cdr depend on whatever you're doing or however you've designed the program.
If I were to criticize "Cons", its that high performance modern programming needs to use arrays because the cost of pointers has grown. Latency of memory lookups is relatively slower on modern machines (or really, latency hasn't improved in like 20 years), so you need to consolidate more members together.
But in terms of a "simple" data-structure, "cons" cells and list-programming is a thing for a reason.
This has been true of linked lists since the advent of memory caches; it’s not just the last 20 years. They’re simple to implement, but they’re usually very bad for performance; you really want better locality of reference in a primitive data structure. You almost always should be using an array of some kind instead.
There's a reason why the Linux Kernel continues to use Red-Black trees today for a huge number of its data-structures. When you need reliable performance on all operations (insert, delete, reorderings, reallocations), its hard to beat a tree (or "cons" for that matter).
If you can use an array, then use an array. But making the tree a "good default" seems like the right move. Lisp does that with cons/cdr/car and (a . b), or (a b c d e) syntax.
Turning (a b c d e) into (a b b1 c d e), especially for larger sizes, will likely be faster than arrays (which innately needs to memcpy ~half the array on the average).
In Lisp you'd pretty much have to ship your module with its own tree-construction logic, or use some common (but importantly, not technically standard) implementation, and document that's what you did, so people know how to structure the data they pass to you.
In C++, you simply take a std::map, which implements a red-black tree for you, and being part of the standard library it is accepted and commonly used nearly everywhere.
I think OP wishes Lisp had something like std::map.
> To be clear, I'm steal manning his argument as I'm not sure I agree with it. But I think the point is summarized best with an example: "Here's an API that takes a red-black tree as an argument." Okaaay, what format is the red-black tree? How do I construct one?
If the API calls for taking a red-black tree as an argument, it will also provide either the specific red-black tree implementation itself or it will refer you to an existing package to include as a dependency. This is not dissimilar from C++. In C++ if something takes a std::map, you use a std::map. If it takes another data structure that's not in the STL, then it will provide it or tell you how to obtain it as a dependency.
BTW: steel, not steal, manning.
Which like Quicksort (nearly the same analysis btw), has exceptional average case performance (even faster than RB trees on the average !!!!) but the downside of horrific O(n^2) performance on the worst case.
RBTrees or AVL trees all help at improving those worst cases (AVL strangely has its best case be the worst case of unbalanced trees lol).
In any case, there's a lot of tree flavors. Lisp is certainly sufficient and simple when it's exploring these different details.
Unbalanced trees, in any case, is actually a reasonably sane default. RB Tree or AVL is probably a better default but don't knock the unbalanced tree before you try it!!
------------
I've heard of highly optimized lisps where the typical list is turned into an array or at least a rope in the average case btw.
What is "modern"? How far back do we have to go to "pre-modern" such that dependent loads through pointers are not a performance issue?
Pointers don't always imply trees. Any Lisp object that won't directly fit in half a cons cell gets allocated separately and a pointer to it is placed in that half of the cons cell. Examples: Strings, symbols, bignums, etc.
> If you need "more" than this (ie: graphs), then perhaps its insufficient.
You can certainly represent cyclic graphs with cons cells. The *print-circle* mechanism in Common Lisp handles printing them, for example.
Lisp is not, nor has it ever been, a functional programming language. It had lambda decades before other languages figured out it was a good idea, but it had set! for just as long.
It is also not a list based language, but a tree based one. The fundamental point of lisps is that you can manipulate the abstract syntax tree directly since it's pretty much the same thing as the parse tree.
>Deep Nesting is Rare
>The lisp's cons [...] works just fine when data structure used is simple. [...] vast majority of list usage is just simple flat list, sometimes 2 level of nesting [...] 3 levels of nesting is seldom used [...] 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.
I guess the author has never used lisp to implement a DSL in lisp. Writing a lisp interpreted in lisp is the first real program you write if you take a lisp course at university and you need to handle arbitrarily nested expressions.
Real world usage also involves writing a specialist language to solve your problem for anything more complex than a utility script, e.g. Emacs is a text editing DSL implemented in elisp.
The LISP I manual describes the program feature as being "like a FORTRAN program with LISP statements", but that's not the same as saying it is there to appeal to Fortran programmers.
https://www.mirrorservice.org/sites/www.bitsavers.org/pdf/mi...
Oh look, it says so right near the top: 2008.
The key difference between the C primitive and the Lisp primitive is that the Lisp primitive does not require anything to be mapped onto integers whereas C does. You have to be able to increment and decrement pointers in C. You can have a fully functional Lisp with no numbers at all. In fact, this was the whole point of Lisp when it was invented: providing a model for computing on symbolic expressions rather than numbers. There is a reason that the original Lisp paper was called, "Recursive functions of symbolic expressions and their computation by machine" rather than "Cons cells: a new computational primitive".
All of the "problems" with cons cells are not problems with cons cells at all, they are problems with punning cons cells, i.e. using cons cells to implement higher-level abstractions without properly hiding the fact that the underlying implementation is a cons cell. The exact same thing happens in C when you run off the end of an array or cast a pointer to (void *). These are not problems with pointers per se, they are problems with using pointers to implement higher level abstractions (like finite arrays) without properly hiding the underlying implementation.
Punning cons cells and abusing pointers have similar consequences: segfaults in the case of C, and (typically) "NIL is not a valid argument to..." errors in Lisp. Both of these are the result of bad abstraction discipline, not a problem with the primitives.
---
[1] The author is Xah Lee, who is pretty well known in the Lisp community. He is widely considered a troll, an opinion which I personally share. I've tried to make my assessment of this post as dispassionate as I can, but I thought I should disclose the fact that I have a pretty strong bias.
$ txr
This is the TXR Lisp interactive listener of TXR 300.
Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
TXR is written, directed and produced by, not to mention starring, Kaz.
1> [mapcar chr-toupper "abc"]
"ABC"
2> (nullify "")
nil
3> (cdr "a")
nil
4> (car "abc")
#\a
5> (car "a")
#\a
6> (cdr "a")
nil
7> (car "ab")
#\a
8> (cadr "ab")
#\b
9> (cddr "ab")
nil
10> (defstruct kons ()
bling blong
(:method car (me) me.bling)
(:method cdr (me) me.blong)
(:method rplaca (me splat) (set me.bling splat))
(:method rplacd (me plonk) (set me.blong plonk)))
#<struct-type kons>
11> (new kons bling 1 blong 2)
#S(kons bling 1 blong 2)
12> (car *11)
1
13> (cdr *11)
2
14> (rplaca *11 42)
#S(kons bling 42 blong 2)
This is not the only way to make an object which serves as a sequence; you can instead (or in addition!) implement array-like indexing via the lambda and lambda-set methods to have it vector-like rather than list-like.
The empty function and nullify are almost inverses; anyway they are implemented in the same spot of a 16000+ line file. The difference is that empty errors out on objects that are not iterable, whereas nullify takes objects of all types:
val nullify(val obj)
{
val self = lit("nullify");
seq_info_t si = seq_info(obj);
if (seq_iterable(si))
{
seq_iter_t iter;
val elem;
seq_iter_init_with_info(self, &iter, si);
return if2(seq_peek(&iter, &elem), obj);
}
return si.obj;
}
val empty(val seq)
{
val self = lit("empty");
val elem;
seq_iter_t iter;
seq_iter_init(self, &iter, seq);
return tnil(!seq_peek(&iter, &elem));
}
alphazard•3h ago
The problem is everything is boxed, and the indirection mechanism is conflated with the concatenation mechanism. What you really want is the ability to compose a value (concatenate 2 things together), but store it contiguously in memory. If cons did that then you could create true products of values, without any indirection.
Then you need a different method for creating indirection. A function for each of C's malloc and '*' respectively. That would give you the control needed to create trees with arbitrary branching factors.
Jtsummers•3h ago
johnisgood•3h ago