4 ms·

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

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.
- dragontamer 4y ago
  (car [(This example) of a list]) == (This example), which is a pointer.
  - xdavidliu 4y ago
    that's an example, sure, but the original claim was that "lisp lists have two pointers to pointers", which certainly is not always true.
- dreamcompiler 4y ago
  > only cdr is a pointer to a pointer. This isn't really true either. Either half of a cons could contain a pointer or a direct value. Lisp makes the decision about pointers based on whether the value you're trying to store is small enough to fit there directly or not. And crucially, Lisp can tell the difference between a pointer and a value at runtime which means it will always do the right thing with whatever it finds. This is why it gets dicey talking about pointers in Lisp: Pointers exist all over the place in Lisp but you have no direct control over them. That's the garbage collector's job. Nothing in Lisp requires pointers in either half of a cons cell. There is a convention followed by the Lisp reader and printer that lists are represented with their head in the car and their remainder in the cdr of a cons cell, but the cons cells themselves don't care. Cons cells themselves know nothing about lists. They're just dumb 2-tuples with a car half and a cdr half. You're free to stick anything you want in either side. Each side holds 64 bits, and if you want to stick a string containing the Gettysburg address in the car [or cdr], Lisp will let you. (More specifically if you create this string Lisp will allocate a pointer for it, and it will then stick that pointer in the car.)
  - xdavidliu 4y ago
    > Nothing in Lisp requires pointers in either half of a cons cell. You are definitely right about that, but the initial claim was made about "Lisp list", for which cdr is certainly a pointer. I would expect that when we refer to "Lisp lists", we certainly don't include things like (cons 1 2)

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.

dragontamer 4y ago
(car [(This example) of a list]) == (This example), which is a pointer.
- xdavidliu 4y ago
  that's an example, sure, but the original claim was that "lisp lists have two pointers to pointers", which certainly is not always true.
dreamcompiler 4y ago
> only cdr is a pointer to a pointer. This isn't really true either. Either half of a cons could contain a pointer or a direct value. Lisp makes the decision about pointers based on whether the value you're trying to store is small enough to fit there directly or not. And crucially, Lisp can tell the difference between a pointer and a value at runtime which means it will always do the right thing with whatever it finds. This is why it gets dicey talking about pointers in Lisp: Pointers exist all over the place in Lisp but you have no direct control over them. That's the garbage collector's job. Nothing in Lisp requires pointers in either half of a cons cell. There is a convention followed by the Lisp reader and printer that lists are represented with their head in the car and their remainder in the cdr of a cons cell, but the cons cells themselves don't care. Cons cells themselves know nothing about lists. They're just dumb 2-tuples with a car half and a cdr half. You're free to stick anything you want in either side. Each side holds 64 bits, and if you want to stick a string containing the Gettysburg address in the car [or cdr], Lisp will let you. (More specifically if you create this string Lisp will allocate a pointer for it, and it will then stick that pointer in the car.)
- xdavidliu 4y ago
  > Nothing in Lisp requires pointers in either half of a cons cell. You are definitely right about that, but the initial claim was made about "Lisp list", for which cdr is certainly a pointer. I would expect that when we refer to "Lisp lists", we certainly don't include things like (cons 1 2)