5 ms·

>lists are an excellent data structure for representing any kind of heterogeneous and/or hierarchical data I found this a really curious statement. Linked list

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

terminalcommand 4y ago
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.
- openfuture 4y ago
  Forth is also homoiconic (arguably more so than lisp) and it can be thought of as being purely vectors.
  - terminalcommand 4y ago
    Forth's homoiconicity seems to be disputed: https://wiki.c2.com/?HomoiconicityClassification https://wiki.c2.com/?HomoiconicityClassification
    - openfuture 4y ago
      You could see forth as just netstrings recursively. You evaluate the outermost netstring by unquoting and then doing a forth over the netstrings it contains.
dragontamer 4y ago
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.
- openfuture 4y ago
  Universal in the sense of structure, but vectors are pretty faithful to the machine memory.. which also makes them universal but more in terms of content. Therefore we should use canonical S-expressions as a universal data interchange format. When you build metaprogramming on top of it then you can do some cool things I think (check out datalisp.is).
- xdavidliu 4y ago
  > Pointers to TWO pointers (first pointer is named car, and the 2nd pointer is named cdr). This is not true; only cdr is a pointer to a pointer. car is a pointer to a value. For example, if x is (1 2), then (car x) is a pointer to the value 1, while (cdr x) is a pointer to the list (2), so only the latter is "to a pointer". > convert your C code into a vector or a hash-map. nit: C has neither vectors nor hash-maps, neither builtin nor part of any standard library.
abecedarius 4y ago
> fast append If you're mutating it, yes. And CL/Scheme do offer that datatype. Linked lists support a functional style building shared structures without having to worry about plan interference from the mutations. Clojure can do this with immutable arrays instead of lists, but the implementation is hairier than either linked lists or mutable arrays.
openfuture 4y ago
Just use canonical S-expressions, then you've got linked lists where the atoms are vectors, best of both worlds :)
kazinator 4y ago
Lists based on cons cells avoid heap fragmentation: all allocations are of the same size. This is not true of vectors. Making different lists that share the same tail, by building at the front, is incredibly common in code that manipulates code. For instance, in many situations you have a body of forms that are to be put into some statement: (defun glue-args-and-body-making-lambda (args body) `(lambda ,args ,@body)) That lambda expression shares the args object with the caller, of course (and an array would do the same), but it also shares the body object, which an array won't do unless it's a very specialized array. The backquote expression can compile down to: (list* 'lambda args body) which allocates exactly two cons cells: one cell to hold lambda in its car; another one to hold args in its car and the body goes into the cdr of that same one. It's also incredibly common to work with the suffix of a list. In the reverse direction, we can break the lambda: (defun take-apart-lambda (lambda-expr) (destructuring-bind (lambda-sym args &rest body) lambda-expr (values args body))) This requires no memory allocation We can pull the args out of an array-based lambda expression for free; but not the body (suffix of the array). Vectors have the advantage of compact storage; a large vector's storage should be roughly the value word size times number of elements, plus small fixed overhead. Each element of a list costs us a cons cell (unless we have cdr coding, which is just little vectors in disguise). Cons cells can be compactly allocated, but not like the elements of a vector. They can be individually reclaimed though. If we cdr three steps down a list, and nothing has retained the pointer to that list, those three conses can be identified as garbage and reclaimed.
dreamcompiler 4y ago
One example is queues: Lists are superior to vectors for queues that need to grow and shrink. It's easy to build an augmented list with an extra cons cell at the beginning that contains a pointer to both the first and last cons cells of the queue. This provides O[1] prepend, append, and push and pop operations. [Popping from the far end remains slow, which is why you typically push onto the far end and pop from the near end.] Doing this with vectors is internally much messier and requires a lot of copying, which makes it slower, unless your queue is a circular buffer of fixed size.
lispm 4y ago
> the same first/next semantics and performance as lists How so? Say we have a vector #(1 2 3 4) . How do I get a vector with the first element removed? How do I get a vector with a element added? (rest #(1 2 3 4)) -> #(2 3 4) (prepend 0 #(1 2 3 4)) -> #(0 1 2 3 4) There are basically a few options to implement this: a) allocate new vectors b) implement growing/shrinking vectors c) do something very clever internally, sharing vector memory With cons cells this is simple. The possible drawbacks: a) memory is fragmented into cons cells linking each other b) lists may share memory

terminalcommand 4y ago

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.

openfuture 4y ago
Forth is also homoiconic (arguably more so than lisp) and it can be thought of as being purely vectors.
- terminalcommand 4y ago
  Forth's homoiconicity seems to be disputed: https://wiki.c2.com/?HomoiconicityClassification https://wiki.c2.com/?HomoiconicityClassification
  - openfuture 4y ago
    You could see forth as just netstrings recursively. You evaluate the outermost netstring by unquoting and then doing a forth over the netstrings it contains.

dragontamer 4y ago

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.

openfuture 4y ago
Universal in the sense of structure, but vectors are pretty faithful to the machine memory.. which also makes them universal but more in terms of content. Therefore we should use canonical S-expressions as a universal data interchange format. When you build metaprogramming on top of it then you can do some cool things I think (check out datalisp.is).
xdavidliu 4y ago
> Pointers to TWO pointers (first pointer is named car, and the 2nd pointer is named cdr). This is not true; only cdr is a pointer to a pointer. car is a pointer to a value. For example, if x is (1 2), then (car x) is a pointer to the value 1, while (cdr x) is a pointer to the list (2), so only the latter is "to a pointer". > convert your C code into a vector or a hash-map. nit: C has neither vectors nor hash-maps, neither builtin nor part of any standard library.

abecedarius 4y ago

> fast append If you're mutating it, yes. And CL/Scheme do offer that datatype. Linked lists support a functional style building shared structures without having to worry about plan interference from the mutations. Clojure can do this with immutable arrays instead of lists, but the implementation is hairier than either linked lists or mutable arrays.

openfuture 4y ago

Just use canonical S-expressions, then you've got linked lists where the atoms are vectors, best of both worlds :)

kazinator 4y ago

Lists based on cons cells avoid heap fragmentation: all allocations are of the same size. This is not true of vectors. Making different lists that share the same tail, by building at the front, is incredibly common in code that manipulates code. For instance, in many situations you have a body of forms that are to be put into some statement: (defun glue-args-and-body-making-lambda (args body) `(lambda ,args ,@body)) That lambda expression shares the args object with the caller, of course (and an array would do the same), but it also shares the body object, which an array won't do unless it's a very specialized array. The backquote expression can compile down to: (list* 'lambda args body) which allocates exactly two cons cells: one cell to hold lambda in its car; another one to hold args in its car and the body goes into the cdr of that same one. It's also incredibly common to work with the suffix of a list. In the reverse direction, we can break the lambda: (defun take-apart-lambda (lambda-expr) (destructuring-bind (lambda-sym args &rest body) lambda-expr (values args body))) This requires no memory allocation We can pull the args out of an array-based lambda expression for free; but not the body (suffix of the array). Vectors have the advantage of compact storage; a large vector's storage should be roughly the value word size times number of elements, plus small fixed overhead. Each element of a list costs us a cons cell (unless we have cdr coding, which is just little vectors in disguise). Cons cells can be compactly allocated, but not like the elements of a vector. They can be individually reclaimed though. If we cdr three steps down a list, and nothing has retained the pointer to that list, those three conses can be identified as garbage and reclaimed.

dreamcompiler 4y ago

One example is queues: Lists are superior to vectors for queues that need to grow and shrink. It's easy to build an augmented list with an extra cons cell at the beginning that contains a pointer to both the first and last cons cells of the queue. This provides O[1] prepend, append, and push and pop operations. [Popping from the far end remains slow, which is why you typically push onto the far end and pop from the near end.] Doing this with vectors is internally much messier and requires a lot of copying, which makes it slower, unless your queue is a circular buffer of fixed size.

lispm 4y ago

> the same first/next semantics and performance as lists How so? Say we have a vector #(1 2 3 4) . How do I get a vector with the first element removed? How do I get a vector with a element added? (rest #(1 2 3 4)) -> #(2 3 4) (prepend 0 #(1 2 3 4)) -> #(0 1 2 3 4) There are basically a few options to implement this: a) allocate new vectors b) implement growing/shrinking vectors c) do something very clever internally, sharing vector memory With cons cells this is simple. The possible drawbacks: a) memory is fragmented into cons cells linking each other b) lists may share memory