[HN Gopher] They Called It LISP for a Reason: List Processing (2...
       ___________________________________________________________________
        
       They Called It LISP for a Reason: List Processing (2005)
        
       Author : susam
       Score  : 97 points
       Date   : 2022-10-11 12:02 UTC (2 days ago)
        
 (HTM) web link (gigamonkeys.com)
 (TXT) w3m dump (gigamonkeys.com)
        
       | pjmlp wrote:
       | It might be as it started, however since 1970 that the various
       | dialects support all common data structures.
        
         | WJW wrote:
         | I wonder what the minimal set of data structures is that you
         | can build all others out of. For example binary trees can be
         | built with lists, SEXPs are proof of that. You can of course
         | also make a (boxed) linked list out of an array of 2 pointers,
         | with one element pointing to the value and the other to the
         | next element. You can make arrays with just pointer arithmetic,
         | sooooo... just pointers is enough? (I guess this can also be
         | shown from the "other" direction, by pointing out that assembly
         | has nothing but arithmetic and pointers)
         | 
         | You would also need various arithmetic operations, possibly up
         | to hashing algorithms for hash tables/sets/bloom filters/etc. I
         | would love to know if anyone can point me to an article or
         | something describing the minimal set of operations needed to
         | construct any data structure.
        
           | tmtvl wrote:
           | NAND gates?
           | 
           | For those who haven't checked either nandgame or nand2tetris
           | out, I would recommend them as fun little diversions in
           | boolean logic and computer architecture.
        
         | taeric wrote:
         | I think the point to take home here is that LISP has a rich set
         | of functions and building blocks around lists. Indeed, if you
         | have something you want to do to a list, that function probably
         | already exists.
         | 
         | Contrasted with many other languages that are catching up, but
         | sometimes have surprising amount of boilerplate to process
         | data.
        
       | dragontamer wrote:
       | The real elegance of Lisp is that malloc() has been renamed to
       | (cons) and everyone feels smarter about it.
       | 
       | 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.
        
         | terminalcommand wrote:
         | Nah, I don't agree with this. Lisp is inherently dynamic, there
         | is much more going on than just automatic garbage collection.
         | 
         | To achieve the same-level of expressiveness in C you need to
         | craft an interpreter, dynamic memory allocation doesn't cut it.
         | 
         | I once wrote a simple linked list library in C to achieve lisp
         | like functions, things got complex very quickly. I still dream
         | of writing a garbage collector for it and evolve it to a lisp
         | like state.
         | 
         | Like Greenspun said, I believe any sufficiently complicated C
         | or Fortran program contains an ad hoc, informally-specified,
         | bug-ridden, slow implementation of half of Common Lisp.
        
           | pyinstallwoes wrote:
           | Forth solves this.
        
             | terminalcommand wrote:
             | Forth is still interpreted. Forth's genius is that it's
             | interpreter is so tiny that it fits as a runtime.
        
               | pyinstallwoes wrote:
               | This is wrong.
               | 
               | Because of the way pointers are used, Forth is both
               | compiled and not compiled.
               | 
               | > After the fetch and store operations are redefined for
               | the code space, the compiler, assembler, etc. are
               | recompiled using the new definitions of fetch and store.
               | This effectively reuses all the code of the compiler and
               | interpreter. Then, the Forth system's code is compiled,
               | but this version is stored in the buffer. The buffer in
               | memory is written to disk, and ways are provided to load
               | it temporarily into memory for testing. When the new
               | version appears to work, it is written over the previous
               | version.
        
               | terminalcommand wrote:
               | What is the difference between a runtime and an
               | interpreter? I still believe forth is interpreted. Forth
               | uses a small set of functions in assembly as its
               | runtime/interpeter.
               | 
               | Your quote looks like its about bootstrapping the Forth
               | ecosystem. After writing fetch and store operations in
               | native assembly, you can bootstrap the forth system that
               | is logical. This is the way Chuck Moore first used Forth
               | anyways. He had no interpreter/compiler back than, he
               | wrote some functions to aid him circumvent assembly and
               | make his code portable. It is genius, but I think it's
               | still interpreted.
               | 
               | You can compile python to bytecode and run it in python's
               | vm, does this mean your python code is compiled. IMHO no,
               | it is compiled for the python vm and python vm interprets
               | it. Same thing applies to Forth.
               | 
               | Forth is interpreted, even if you compile and package it
               | in a standalone executable binary.
        
               | Jtsummers wrote:
               | An interpreter interprets, typically either a byte code
               | or textual representation version of a program or some
               | other intermediate form (for instance, parsing to an AST
               | and then evaluating/interpreting that versus line-by-line
               | or token-by-token). A runtime could include an
               | interpreter, but doesn't have to. Go includes its own
               | runtime which handles things like scheduling goroutines
               | and garbage collection, but it is not interpreted nor
               | does it include an interpreter.
        
               | dragontamer wrote:
               | There are many lisps that are not interpreted, but are
               | instead compiled.
               | 
               | The beauty of the lisp language is that it doesn't care
               | about interpreted vs compiled vs whatever. Its just the
               | true elegance of "everything is a (lisp) list" (which is
               | probably the wrong word. The truth of the matter is that
               | "everything is a graph" and lisp-lists are really just a
               | universal building block that can represent arbitrary
               | graphs).
               | 
               | The important gadgets are:
               | 
               | 1. Universal garbage collection (allowing you to ignore
               | free() issues and simplify code)
               | 
               | 2. Pointer to (two pointers). That is, car-and-cdr.
               | 
               | That's it. Everything else flows from these two things.
        
               | terminalcommand wrote:
               | That is true, but some sort of a runtime bordering on
               | being an interpreter needs to exist doesn't it. Because
               | my brain cannot comprehend how you can do metaprogramming
               | with macros etc. with static code.
               | 
               | My opinion was that the compiled lisps precompile as much
               | as possible (calculations etc.) into assembly and leave
               | bits they can't compile intact, that's what make them
               | fast.
        
             | 7thaccount wrote:
             | Yeah. It seems to get overlooked a lot. Forth clicked for
             | me easier than Lisp. It still requires you to build out a
             | lot unless you build it on top of higher level languages.
             | 
             | Great username btw.
        
         | dkarl wrote:
         | I think building everything out of conses held Lisp back. It
         | was possible, and it was deemed to be elegant, so people went
         | too far with it. YMMV since my adventures with Lisp were around
         | twenty years ago, but reading code, you'd see somebody
         | constructing a list with a bunch of nested lists inside it, or
         | some other complicated structure with conses, and you'd have no
         | idea what it was or how they intended to use it, and you'd just
         | have to read the code until you figured it out. It's much
         | easier to read code that uses named data structures.
         | 
         | Of course in Lisp your code _can_ and _should_ have clearly
         | named functions that encapsulate your use of conses to build
         | data structures, but casually violating that encapsulation, or
         | better yet doing without encapsulation at all, just playing
         | with conses, was the cool way to do it, the way you programmed
         | if you had even a little bit of swagger. That was fun as long
         | as feeling smart about the fact that I could do it outweighed
         | feeling annoyed at everyone else doing it, but in the end, the
         | feeling of smartness faded and the feeling of annoyance
         | remained.
        
       | sillysaurusx wrote:
       | Shared structure is overrated. The cases where you need a tree-
       | like _mutable_ structure are vanishingly small in modern times.
       | Mostly it boils down to  "just use hash tables."
       | 
       | 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"']
       | 
       | Presto, now you have car, cdr, and join (cons) in Python.
       | 
       | 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.
        
         | reikonomusha wrote:
         | I fail to see why mutable cons cells has anything to do with
         | the difficulty of implementing Lisp.
         | @dataclass         class Cons:             car: Any
         | cdr: Any
         | 
         | You can define a nice printer or reader for it if you want, but
         | mutability doesn't seem to be a hindrance in implementation.
        
           | sillysaurusx wrote:
           | You can, but then none of the Python libraries that expect
           | Python lists can use your Cons as a list.
           | 
           | I tried. It sucks. The conversion becomes a problem all over
           | the place.
           | 
           | isinstance(Cons(nil, nil), list) will fail, for example.
           | 
           | I posted a more thorough answer here:
           | https://news.ycombinator.com/item?id=33194570
        
             | Turing_Machine wrote:
             | Python...Python...Python...
             | 
             | I think I see where your problem actually is.
        
             | phoe-krk wrote:
             | This isn't a case of Lisp being hard to implement, this is
             | a case of trying to make your Lisp work with Python
             | language idiosyncrasies. These two issues have close to
             | nothing to do with one another.
        
         | lispm wrote:
         | > It's the heart of why Lisp is so hard to implement.
         | 
         | Lisp is hard to implement? The list processing core is very
         | small and relatively easy to implement.
        
         | mrkeen wrote:
         | > Shared structure is overrated. The cases where you need a
         | tree-like mutable structure are vanishingly small in modern
         | times. Mostly it boils down to "just use hash tables."
         | 
         | So confused by this. Shared, tree-like, and mutable seem pretty
         | orthogonal to me.
         | 
         | Sure, I'll forgo mutable structure. And since I don't mutate, I
         | can safely share structure. But I don't want O(n) update
         | operations, so I'd better make my hash tables use a tree-shaped
         | data structure:
         | 
         | https://en.wikipedia.org/wiki/Hash_array_mapped_trie
        
         | taeric wrote:
         | Shared mutable state is an odd focus here. The point isn't that
         | a cons cell is some magical thing. The point is that LISP gives
         | you a ton of things that it already knows how to do.
         | 
         | Other languages have started catching up with massive standard
         | libraries. But... LISP has been there for a long time.
        
         | jjtheblunt wrote:
         | > Shared structure is overrated.
         | 
         | Every MMU running a Unix with mmap probably disagrees!
        
           | sillysaurusx wrote:
           | You're right, I was imprecise. I meant specifically shared
           | list structure in Lisp contexts, not shared structures in
           | general.
           | 
           | There's a fascination in the Lisp world for cons cells.
           | Specifically the cell aspect. If you represent lists as:
           | l = [x, [y, [z]]]
           | 
           | Then you can implement car as l[0] and cdr as l[1].
           | 
           | If you require mutable cons cells, that's pretty much the
           | only way to do it. Because if you want to set the car of
           | cdr(l), how do you do it? You can just do
           | cdr(l)[0] = t
           | 
           | Because that's the same as                  l[1][0] = t
           | 
           | Which of course makes the list become                  l =
           | [x, [t, [z]]]
           | 
           | But this sucks. It's always sucked, and Lispers go out of
           | their way to ignore the fact that it sucks. I wince at having
           | such a dismissive attitude here, but it's been the source of
           | _years_ of frustrations.
           | 
           | It's a frustration because if Lisp had been implemented using
           | vectors and hash tables instead, it'd be in a far stronger
           | position today. Everyone uses vectors. Vectors are [1, 2, 3,
           | 4] ... Plain old arrays! In fact, I used vectors in the above
           | examples, and didn't even have to explain what they were.
           | Everyone knows and understands arrays.
           | 
           | Lisp can work fine with vectors, _if_ you drop the
           | requirement of mutable cons cells. Because l becomes:
           | l = [x, y, z]
           | 
           | And cdr(l) becomes l[1:], so cdr(l) returns [y, z] -- an
           | entirely new vector containing y and z.
           | 
           | This might seem like nonsense, but in practice it's not. In
           | practice, you're rarely building lists containing hundreds of
           | thousands of elements. Usually it's much smaller lists
           | contained in other structures, like hash tables.
           | 
           | And when the lists are small, you really don't care about
           | creating new lists. The fact that cdr(l) returns a copy of l
           | minus the first element is inconsequential. You'll ~never
           | experience a slowdown.
           | 
           | And the gains are massive. You get to interface with all your
           | native libraries _using lisp algorithms_. You don 't have to
           | convert from "lisp lists" to "python lists" or "javascript
           | lists" or anything else. They're just arrays.
        
             | f1shy wrote:
             | Without having any idea of this, right now I'm facing the
             | problem of making a PDDL compiler (which is basically Lisp)
             | in C++ , and this was the way I took. Lists are just
             | std::vectors<std::variant>> and the variant can be a
             | function, number (literal) or a variable.
        
               | sillysaurusx wrote:
               | No way! Is the code available anywhere? I was messing
               | around with this idea too but didn't have the time.
               | That's fantastic. :)
               | 
               | std::variant is really tricky, mostly because of C++'s
               | type system. I went with std::any. My attempt is here: ht
               | tps://gist.github.com/shawwn/63e0f010479efd95ebffdf210864
               | 5...
               | 
               | I'd love to see your code and compare notes! Mine is
               | pretty crummy; I'm not sure there are any worthwhile
               | ideas in it. Did you have much trouble with the
               | std::variant route?
        
             | jjtheblunt wrote:
             | Great write-up (and that's from someone first doing Lisp in
             | 1987, then lots of Scheme and tons of Mathematica, as well
             | as all the compiled things)
        
               | sillysaurusx wrote:
               | Incidentally, it wasn't my idea. It was Scott Bell's. I'm
               | not sure if he thought of it or got it from somewhere
               | else, but it's wonderfully effective.
               | 
               | If you want to try it out for yourself, give Lumen a
               | spin: https://github.com/sctb/lumen
               | 
               | His Postgres FFI is the prettiest lisp FFI you'll ever
               | see. https://github.com/sctb/motor/blob/master/pq.l
        
               | jjtheblunt wrote:
               | Thanks!
        
             | cnasc wrote:
             | > if Lisp had been implemented using vectors and hash
             | tables instead
             | 
             | Sounds a lot like Clojure
        
             | User23 wrote:
             | Lisp has had vectors and hash tables considerably longer
             | than Python has existed.
             | 
             | It's a general purpose language, and any competent Lisper
             | uses the right data structure for the job. As it happens,
             | the cons tree (not a list, a tree!) is the right data
             | structure for representing Lisp code. It's not necessarily
             | the right data structure for representing other non-code
             | data that Lisp code is working with.
        
               | sillysaurusx wrote:
               | Yes, but cdr(vector(1, 2, 3)) throws an error in almost
               | all lisp implementations. Which means you can't use the
               | classic algorithms on them, like map.
               | 
               | It's worth considering carefully why you feel cons cells
               | are so important for lisp code. Nested vectors are trees.
               | Why not represent                 (define (foo x) x)
               | 
               | as                 [define, [foo, x], x]          ?
        
               | User23 wrote:
               | > Yes, but cdr(vector(1, 2, 3)) throws an error in almost
               | all lisp implementations. Which means you can't use the
               | classic algorithms on them, like map.
               | 
               | What? MAP[1] works just fine with vectors and other
               | sequence types. Are you somehow surprised that MAPCAR
               | doesn't? The name makes it pretty obvious I'd think. I'm
               | starting to think you just lack familiarity with the
               | language that you're criticizing.
               | 
               | [1] http://clhs.lisp.se/Body/f_map.htm
        
               | sillysaurusx wrote:
               | Suppose Lisp were forced to abandon cons cells and could
               | only use vectors to represent code. What's the
               | disadvantage?
               | 
               | My retort to you would be "I'm starting to think you like
               | complexity for the sake of it," but debates are much more
               | fun when we're both genuinely interested in the other's
               | perspective.
        
               | User23 wrote:
               | Variable length vectors are observably more complex than
               | 2-tuples. And forgive me, but you are giving me the
               | impression that you are trolling rather than debating.
               | 
               | Suppose Lisp were forced to abandon cons cells and could
               | only use SQL tables to represent code. What's the
               | disadvantage?
               | 
               | Anyhow, by all means write your Python vector based Lisp
               | dialect. It's no skin off my teeth. Maybe it really is
               | superior and you'll be the next Rich Hickey.
        
               | math-dev wrote:
               | cons is a recursive data structure. it's not discussed
               | much here in the comments, but a lot of its useability
               | comes from that fact - you can write elegant recursive
               | algorithms with cons as your data structure
               | 
               | with vectors that doesn't work UNLESS you add a bit of
               | overhead (which most optimising programs may do since for
               | many cases vectors can be more performant)
        
             | creepycrawler wrote:
             | It seems you're suggesting making CDR into an O(N)
             | operation. So for example ordinary list processing
             | algorithms that take O(N) will now be O(N^2).
             | 
             | Anyway, these kind of weird arguments from people who don't
             | get it have been proposed and shot down a million times
             | before, and I'm not sure there's any value reiterating. I
             | suggest anyone interested in Lisp (or any programming
             | language, really) ignore weird HN critiques and just read a
             | book, like the one linked here.
        
       | georgeoliver wrote:
       | One of the best programming books (for any language) ever written
       | IMO. Seibel has a knack for clear, readable but still technical
       | prose that's all too rare unfortunately.
        
         | cepher wrote:
         | I've been meaning to read Practical Common Lisp for some time.
         | Would you recommend this even for complete beginners to Lisp?
        
           | georgeoliver wrote:
           | Yes I would! I think it was the first complete book I read
           | while learning CL.
        
           | scottomyers wrote:
           | Practical Common Lisp is a fantastic read, but Common Lisp: A
           | Gentle Introduction to Symbolic Computation gets my vote as
           | the best book for Common Lisp beginners. Working through it
           | was a joy.
        
           | G3rn0ti wrote:
           | Two prehensile toes up! ;)
        
           | abudabi123 wrote:
           | I recommend the gentle introduction to Lisp book for the
           | complete beginner.
           | 
           | The chapter on files in the Practical Common Lisp book wasn't
           | complete enough for me to read a one line file of 800MB which
           | is part of the Harvard Library Open Metadata archived set.
        
             | parenthesis wrote:
             | I'm assuming you mean Touretzky's _Common Lisp: A Gentle
             | Introduction to Symbolic Computation_ --
             | 
             | http://www.cs.cmu.edu/~dst/LispBook/index.html
             | 
             | -- which, yes, is a wonderful book for a complete beginner.
        
           | f1shy wrote:
           | That is THE book I would recommend for beginners.
        
           | dan-robertson wrote:
           | I read it around 10 years ago without knowing any lisp and
           | got on ok.
        
           | User23 wrote:
           | It's a fine first book. I'd certainly recommend it.
           | 
           | I don't recall if it has instructions on getting a dev env up
           | and running, but if it does I imagine they're out of date.
           | Emacs with Sly or SLIME is what I've used, but I believe
           | there are viable options for proper interactive development
           | in vim and vs code among others.
           | 
           | If you just use a basic editor and paste code into a repl in
           | a terminal you won't be getting the experience most Lispers
           | do.
        
       | ducktective wrote:
       | Can anyone link a screencast of doing Common Lisp with all its
       | cool interactive features? (REPL-driven, SLY/SLIME, restarts,
       | etc) and I mean doing _real_ small projects not just simply
       | touting how cool lisp is or talking about (+ 2 3) and C-c C-c
       | 
       | I tried searching on YouTube but didn't find anything
       | particularly unique.
        
         | johan_felisaz wrote:
         | I would recommend this:
         | https://m.youtube.com/user/CBaggers/featured
         | 
         | This is a _real_ project, this guy wrote a compiler, to convert
         | common lisp to GLSL (I 'm not talking about a simple DSL with
         | code generation, but also type checking and so on).
         | 
         | In his Livestreams, he usually try to implement a specific 3D
         | feature (like triplanar mapping, the Phong of lighting, ...).
         | 
         | Everything is done in a single window, with the program being
         | recompiled while running, pure lisp style.
         | 
         | He is on a hiatus right now though with livestreams, but there
         | is plenty of material already to watch ...
        
         | gaul_praham wrote:
         | I remember https://adeht.org/casts/new-project.html
         | 
         | For larger projects I remember youtube videos for Diablo and
         | Minecraft clones.
        
       | cmrdporcupine wrote:
       | Yes, this is the lovely elegance that comes out of building out
       | of a nice re-composable underlying concept. I still find it hard
       | all these years later to fully wrap my head around building
       | programs in this style, but I adore the fact that it exists.
       | 
       | 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)
       | 
       | builds the relation                 {(1,2,3)} from {(1)}, {(2)},
       | {(3)}.
       | 
       | And also the same operator can be used for filtering because
       | "false" and "true" likewise evaluate to relations, so
       | crossproducting them acts like a "where" clause, so:
       | def myelements = 1; 2; 3; 4; 5; 6; 7; 8; 9       def output(x) =
       | myelements(x), x > 3, x < 7
       | 
       | ^ "filters" myelements to return the values in the relation that
       | are greater than 3 and less than 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.
        
       | eduction wrote:
       | >lists are an excellent data structure for representing any kind
       | of heterogeneous and/or hierarchical data
       | 
       | 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?
        
         | dragontamer wrote:
         | Lisp lists aren't linked lists. Pointers to TWO pointers (first
         | pointer is named car, and the 2nd pointer is named cdr).
         | 
         | The realization that (cons) / Lisp-lists / car-and-cdr give is
         | that you can represent arbitrary graphs (!!!) with car / cdr /
         | cons, leading to a truly universal data-structure.
         | 
         | Not necessarily an _efficient_ datastructure mind you, but a
         | universal one.
         | 
         | ------
         | 
         | So really, Lisp-lists are just the "try to represent your
         | problem as a graph" and it really works 99% of the time,
         | because graphs are just so flexible of a concept.
         | 
         | For example, take the HTML of this webpage. <DOCTYPE> <blah
         | blah blah> and all that. Its pretty obvious how to convert it
         | into an equivalent (DOCTYPE (blah blah blah) (p) ...) kind of
         | structure.
         | 
         | Now try to do the same with vectors and hashmaps. You can't.
         | You need to create a concept of vectors-of-vectors and
         | hashmaps-of-hashmaps with arbitrary amount of depth.
         | 
         | -----------                   Example HTML to think about
         | <div>          <p> Start of a paragraph </p>         <p> Second
         | paragraph <b> but some of it is bold</b> </p>         </div>
         | (div (p "Start of a paragraph") (p "Second paragraph" (b " but
         | some of it is bold")))
         | 
         | Lisp itself is written in the form of Lisp-lists. The entirety
         | of your programming code _IS_ a list, proving how truly
         | universal this data-structure is.
         | 
         | You can't convert your C code into a vector or a hash-map. It
         | just doesn't make sense. Meanwhile, all of lisp is a list,
         | including the code.
        
         | terminalcommand wrote:
         | In homoiconic languages like lisp I think you'd need more
         | flexibility than vectors.
         | 
         | What if you need to remove an item for example, do you need to
         | shift all remaining items to keep order or mark the removed
         | section with Xs so that the cursor jumps to the next data item.
         | 
         | You need to be able to randomly access bits and pieces to form
         | a network.
        
       ___________________________________________________________________
       (page generated 2022-10-13 23:00 UTC)