3 ms·

> surely a Lisp has to also keep duplicating the list or else it will get into trouble? Nope, it doesn't traditionally duplicate the list. It certainly is poss

> surely a Lisp has to also keep duplicating the list or else it will get into trouble? Nope, it doesn't traditionally duplicate the list. It certainly is possible to get into trouble in your logic, but those are the presented semantics, and debating their virtue is out of scope > why shouldn't Rust use a slice of the vector? You're gonna get into ownership-hell if you can't give a separate Rc to each list tail, because those can get passed around wherever

wizzwizz4 5y ago
That's what Cow is for, surely?
- brundolf 5y ago
  For the ownership thing? No, I don't think so. I haven't done much with Cow but my understanding is it doesn't do anything to help with cases where you have "multiple owners" of a value. It might allow you to use a slice up until it needs to be cloned, but you'll still have to clone it at that point.
  - tialaramex 5y ago
    Unlike the slice, a Cow made from that slice can be Owned. Unlike reference counting the underlying Vector, the Cow won't duplicate the slice until you modify it. This forces you to confront the reality you'd been dodging. Either you actually mutate this list in your program, and the "magic" of linked lists dissolves when it consumes all your memory, or as seems far more likely you get good performance from the better underlying data structure anyway and the "magic" of linked lists dissolves that way. You only get good performance from linked lists today on the rare occasion when their lack of data locality is outweighed by some other factor. Sprinkling the Lisp idiom over things doesn't change that. Here's an example where it's worth it: In highly concurrent systems you can't afford to use any sort of locking to protect data structures, the contention for the locks hurts too much, and you can't afford to reference count everything in those structures because even the contention on the reference counts also costs too much (everything looking at an item is storing to the reference count). So you use Hazard Pointers to avoid prematurely dropping anything. But any type of locking for your Hazard Pointers structure would have too much contention also, so you store the Hazard Pointers in a linked list, new ones can be slotted into place at the start of the list with an atomic compare-exchange. Each CPU core is writing to the Hazard Pointers it "owns" a lot, but they're deliberately too big to share with another CPU's cache, and any CPU cores that need to check the Hazard Pointers read from them all but never write so modern caches cope admirably.
    - brundolf 5y ago
      You're getting really into the weeds. All I'm saying is the OP will behave unexpectedly for people expecting "just a lisp" (a Scheme-like and/or CL-like lisp). It is not some kind of contract-preserving optimization over a naive linked-list (though those exist!). The way those languages chose to handle this stuff has well-trod advantages and disadvantages. I don't love it personally, but I get it. Certainly it's worked well enough for a whole lot of software! But I'm not commentating on it here. I'm just stating the divergence with the OP. Critiquing Lisp's 40+ year history and what parts of it should or shouldn't have been different is out of scope as far as I'm concerned. You're arguing against something that isn't being stated.
      - tialaramex 5y ago
        > All I'm saying is the OP will behave unexpectedly for people expecting "just a lisp" (a Scheme-like and/or CL-like lisp) What sort of expectations do you think will be defeated? Beyond the fact that it's only a toy and not, in fact, a Common Lisp or Scheme? Almost everything is missing, but it's a toy. You noticed the Vec but apparently didn't notice the toy language still doesn't even have Cons at the end.
tangent128 5y ago
The bytes[0] crate is a popular library in the Rust ecosystem for taking reference-counted slices of a shared byte buffer. [0]: https://docs.rs/bytes/1.0.1/bytes/struct.Bytes.html https://docs.rs/bytes/1.0.1/bytes/struct.Bytes.html

wizzwizz4 5y ago

That's what Cow is for, surely?

brundolf 5y ago
For the ownership thing? No, I don't think so. I haven't done much with Cow but my understanding is it doesn't do anything to help with cases where you have "multiple owners" of a value. It might allow you to use a slice up until it needs to be cloned, but you'll still have to clone it at that point.
- tialaramex 5y ago
  Unlike the slice, a Cow made from that slice can be Owned. Unlike reference counting the underlying Vector, the Cow won't duplicate the slice until you modify it. This forces you to confront the reality you'd been dodging. Either you actually mutate this list in your program, and the "magic" of linked lists dissolves when it consumes all your memory, or as seems far more likely you get good performance from the better underlying data structure anyway and the "magic" of linked lists dissolves that way. You only get good performance from linked lists today on the rare occasion when their lack of data locality is outweighed by some other factor. Sprinkling the Lisp idiom over things doesn't change that. Here's an example where it's worth it: In highly concurrent systems you can't afford to use any sort of locking to protect data structures, the contention for the locks hurts too much, and you can't afford to reference count everything in those structures because even the contention on the reference counts also costs too much (everything looking at an item is storing to the reference count). So you use Hazard Pointers to avoid prematurely dropping anything. But any type of locking for your Hazard Pointers structure would have too much contention also, so you store the Hazard Pointers in a linked list, new ones can be slotted into place at the start of the list with an atomic compare-exchange. Each CPU core is writing to the Hazard Pointers it "owns" a lot, but they're deliberately too big to share with another CPU's cache, and any CPU cores that need to check the Hazard Pointers read from them all but never write so modern caches cope admirably.
  - brundolf 5y ago
    You're getting really into the weeds. All I'm saying is the OP will behave unexpectedly for people expecting "just a lisp" (a Scheme-like and/or CL-like lisp). It is not some kind of contract-preserving optimization over a naive linked-list (though those exist!). The way those languages chose to handle this stuff has well-trod advantages and disadvantages. I don't love it personally, but I get it. Certainly it's worked well enough for a whole lot of software! But I'm not commentating on it here. I'm just stating the divergence with the OP. Critiquing Lisp's 40+ year history and what parts of it should or shouldn't have been different is out of scope as far as I'm concerned. You're arguing against something that isn't being stated.
    - tialaramex 5y ago
      > All I'm saying is the OP will behave unexpectedly for people expecting "just a lisp" (a Scheme-like and/or CL-like lisp) What sort of expectations do you think will be defeated? Beyond the fact that it's only a toy and not, in fact, a Common Lisp or Scheme? Almost everything is missing, but it's a toy. You noticed the Vec but apparently didn't notice the toy language still doesn't even have Cons at the end.

tangent128 5y ago

The bytes[0] crate is a popular library in the Rust ecosystem for taking reference-counted slices of a shared byte buffer. [0]: https://docs.rs/bytes/1.0.1/bytes/struct.Bytes.html https://docs.rs/bytes/1.0.1/bytes/struct.Bytes.html