They Called It LISP for a Reason: List Processing (2005)

I jest a little bit, but that's really the fundamental thing about list-processing. For most code, you don't really care about runtime, and you really just need "a data structure that probably can solve the problem", and the (cons) based list of car and cdr solves it.

List processing itself is an elegant technique: a garbage collector tuned for exactly (cons) (2-element "items" that have a car-and-cdr, and the cdr is usually a pointer to another cons), is small, simple, elegant to implement, and works for almost any problem imaginable.

Maybe not as fast as a properly designed specific data-structure, but it will work. On top of that, Lisp has all kinds of shortcuts to make list processing easier to type.

---------

Getting a basic implementation of whatever project you're doing in cars-and-cdrs in (cons) is more important anyway for learning about your problem. Choosing a data-structure too early can hamper your understanding and bias you towards a possibly inefficient solution.

Knuth tries to explain the topic in his "binary trees representation of trees" subject, and notes that pointers to (two pointers) elegantly solves a wide variety of problems. Whether you wanna see them as binary trees, Lisp-lists, or graphs or even collections of malloc'd() nodes, it doesn't really matter. Its the flexibility of this data-structure that is incredible.

EX: the "left" child is "down a level", and the "right" child is "next sibling". Therefore, binary trees can represent any tree, and if allowed to loop, I'm sure the cons / binary tree node can be forced into working with graphs.

I found this a really curious statement. Linked lists made sense given the limitations in compute when LISP was invented (~1958) but how are vectors not a superior solution in every way, when available?

Vectors give you fast random access and fast append plus the same first/next semantics and performance as lists and the same ability to form trees. Pretty much the only thing lists are better at is prepend (which in my experience is much less useful than append).

Then for truly heterogeneous data you probably want hash maps as well, which, if you want something associative rather than sequential, are in a class all their own.

What am I missing?

I tried searching on YouTube but didn't find anything particularly unique.

FWIW I feel like RelationalAI, in their "Rel" language, has done for n-ary (database) relations what Lisp&Scheme did for lists. Something I had pondered myself for years and kind of grasped at but never really got, and I think they've done it. It's really quite elegant, worth checking out:

https://docs.relational.ai/rel/intro/overview

E.g.

"The constants true and false are also relations, of arity 0. There are only two of these: false is {} (the empty relation with arity 0), and true is {()}, that is, the relation with one empty tuple (arity 0 and cardinality 1)."

and

"In Rel, a single elements is identified with a relation of arity 1 and cardinality 1. For example, the number 7 is the same as the relation {(7)}"

This lets them do clever things like use relational cross-product ("," operator) kind of like Lisp's `cons` to build tuples, so:

  (1, 2, 3) 

  {(1,2,3)} from {(1)}, {(2)}, {(3)}. 

  def myelements = 1; 2; 3; 4; 5; 6; 7; 8; 9
  def output(x) = myelements(x), x > 3, x < 7 

And it also works as a pure cross-product operator, of course, for when you need that.

It's the same kind of elegant composability you get from Lisp, but with a maybe semantically richer datatype and a richer set of (relational algebraic) operations.

— ⁂ —

The first thing to understand is that Lisp invented functional programming. (Seibel's chapter mentions this, of course.)

The functional-programming approach is to define your procedures recursively rather than iteratively; this began in Lisp but is now central to a number of other languages, like Haskell, OCaml, and F#. For certain fields, like symbolic algebra and compilers, this approach makes many difficult problems trivial. Even outside those fields, pervasive immutability often has many benefits, eliminating large classes of bugs, greatly simplifying problems like undo and thread-safety, and dramatically reducing the runtime cost of garbage collection. However, recursively defined linked data structures tend to use more space, and they're not very cache-friendly, and sometimes those are more important considerations.

To define your procedures recursively, it's very helpful to define your data types recursively. Recursively-defined lists (for example, "a list of Ts is either the empty list of Ts or a T followed by a list of Ts") support this recursive, immutable approach to programming.

Other kinds of recursive structures do, too; Haskell and ML dialects tend to use application-specific sum types at least as much as general-purpose lists, and I like that style better. It has most of the same advantages and disadvantages.

STL-style vectors do not support a recursive style of programming. They support an iterative, imperative approach to programming. If you use that other approach to programming exclusively, you will not understand why anyone would want to primarily use linked lists. And occasionally you will be confronted with problems that are very difficult for you to solve, problems which would have been trivial with a recursive approach, and you will not realize that you are doing a hundred times more work to solve them than you need to. SICP is full of examples.

— ⁂ —

The second thing about Lisp is that it has orthogonal serialization and deserialization: PRINT and READ. This mechanism is sometimes, though not always, adequate for debug logging, saving and loading application state, configuration files, and networking. Modern Lisps like Clojure generally extend those to arbitrary data structures, not just lists and atoms, but it's especially easy to implement if you only have lists and atoms; it's about 30 lines of Forth, for example¹. This is of course not unique to Lisp anymore; Java, Python, Tcl, Golang, and many other languages have ways to do it.

Orthogonal deserialization of lists is not really an optional extra, since you use it to parse Lisp programs, too. And you need the serialization to print lists in the REPL, anyway.

— ⁂ —

The third thing about Lisp is that it supports metaprogramming very well. This takes lots of forms; compile-time macros are a common one, and they give you enormous flexibility to extend Lisps into domain-specific languages, though they're probably used even more often to hack around inadequately optimized compilers. EVAL answers many requirements for runtime flexibility, though there are times when it is too powerful.

As with serialization and deserialization, these metaprogramming facilities mostly just fall out of the Lisp design; they require minimal or no extra code in a Lisp interpreter.

— ⁂ —

Historically speaking Lisp had a lot of other advantages: for a long time it was the only garbage-collected language, the only dynamically-typed language, the only language with EVAL, the only language with higher-order functions, and so on, and so for many years it was by far the best language for the things that you would do in JS, Python, Ruby, Lua, or OCaml today. JS, Python, Ruby, Lua, and OCaml are better for some of those things, and for many purposes they adequately support the functional, recursive, immutable approach to programming that Lisp pioneered.

Still, it might be easier to learn it in Lisp.

— ⁂ —

Lisp is sort of a minimal core of functional programming. In a decent low-level language like C or Forth, you can build a Lisp with an interactive functional programming environment with dynamic typing, orthogonal serialization and deserialization, an interactive interpreter, garbage collection, and extensive metaprogramming capabilities, in under 1000 lines of code, and the only data structure you need to do it is cons.

(It's not quite as simple as you might think from reading the "Maxwell's Equations of Software" in the Lisp 1.5 manual; those gloss over READ, PRINT, decimal conversion, arithmetic, symbol interning, the garbage collector, and user interaction, so you end up with significantly more code in a low-level language² where you have to implement those. But it's still days of work, not weeks.)

That doesn't mean Lisp is the only way to do functional programming, or even the best one. Quite apart from implementation questions, you might reasonably prefer the ML approach, with its strong static type checking; or the Haskell approach, which also features laziness; or the Clojure approach, which includes first-class persistent finite maps and integer-indexed "vectors"; or again the Clojure approach, where every operation supports ad-hoc polymorphism; or the Tcl approach, where everything is a string; or the Q approach, where your code defines term-rewriting rules rather than functions; or the Prolog approach, where you have not only list processing but lists that can contain uninstantiated logic variables; or the KANREN approach, which generalizes functional programming to full-on relational programming; or the Bicicleta approach, where you program directly in a side-effect-free ς-calculus, overriding methods instead of passing parameters; and many other approaches that haven't been thought of yet.

But if you're thinking of Forth as an alternative to Lisp, or STL vectors as an alternative to Lisp lists, and in general rather than in a particular case, you just haven't understood the Lisp approach to problem solving at all.

And when you do, it's going to be awesome.

______

¹ http://canonical.org/~kragen/sw/dev3/readprint.fs

² https://www.mail-archive.com/kragen-hacks@canonical.org/msg0...

This isn't just a dismissive observation. It's the heart of why Lisp is so hard to implement. When I ignored mutable cons cells, I realized I could just implement bel in Python by using actual Python lists.

    t = True
    nil = None

    def car(l):
        if l:
            return l[0]

    assert car(nil) == nil
    assert car([]) == nil
    assert car([1]) == 1
    assert car([[1]]) == [1]
    assert car(car([[1]])) == 1
    assert car(car([(1, 2)])) == 1

    def sequence(x):
        return isinstance(x, (list, tuple))

    def cdr(l):
        if l:
            if v := l[1:]:
                if v[0] == ".":
                    if sequence(l):
                        if len(l) == 3 and l[1] == ".":
                            return l[2]
                return v

    assert cdr(nil) == nil
    assert cdr([]) == nil
    assert cdr([1]) == nil
    assert cdr([1, ".", 2]) == 2
    assert cdr((1, 2, 3)) == (2, 3)
    assert cdr("foo") == "oo"

    def join(x=nil, y=nil):
        if sequence(y):
            return [x, *y]
        return [x, ".", y]

    assert join(nil, nil) == [nil]
    assert join(1, 2) == [1, ".", 2]
    assert join(1, '"foo"') == [1, ".", '"foo"']

This works (and works very well). You can build lists with Lisp and then pass them off to other Python libraries -- after all, they're just lists. And in the rare case where you care about mutating cons cells, you can just use a dict instead.

EDIT: See https://news.ycombinator.com/item?id=33194570 for a more thorough explanation of why mutable cons cells are problematic.