4 ms·

I'll bite: cdr gets expensive? You could represent a list as a naked array of lisp pointers, but then cons gets expensive. And good luck garbage collecting the

I'll bite: cdr gets expensive? You could represent a list as a naked array of lisp pointers, but then cons gets expensive. And good luck garbage collecting the vectors.

lisper 15y ago
> cdr gets expensive Yes, that's one thing. But do you really need CDR? > You could represent a list as a naked array of lisp pointers, but then cons gets expensive. Actually, it's much worse than that. CONS actually becomes impossible. (Think about it.) But maybe there's something else that you can use instead of CONS? > And good luck garbage collecting the vectors Why would that be a problem? Extant Lisps collect vectors just fine.
- akkartik 15y ago
  "Extant Lisps collect vectors just fine." But they don't permit pointers inside the vectors, do they? I think if you permit internal pointers so you can have copyless cdr, computing reachability would get really expensive.
  - lisper 15y ago
    The phrase "permit pointers inside the vectors" doesn't really make sense. Vectors are just ordered collections of objects. They don't have insides and outsides, except insofar as the objects contained by the vector could be (but usually aren't) considered "inside" the vector. Lisp vectors are usually implemented as arrays of pointers, so in that sense pointers are "permitted" inside vectors. But I'm guessing that's not what you meant. (I have no idea what you actually meant.)
    - akkartik 15y ago
      (a (b (c . nil)) ^ ^ | | | | A B If you implement lists as vectors with car/cdr (I'm still thinking about your other questions) and choose to have cdr not copy results out of the original cell, you can end up in the (rope-like) situation above with pointer B (value (b c)) in addition to pointer A (value (a b c)). But that makes GC inefficient. For a vector to be GC'd you have to know what internal pointers it has, and then you have to make the choice to copy them out if they're 'toward the end', or to leave the vector uncollected. (ignore pointers to a, b, and c.)
      - lisper 15y ago
        Ah. What you are calling a "pointer to the inside of a vector" is actually called a displaced vector. It's a standard Common Lisp feature, and no problem for modern GCs.
        akkartik 15y ago
        Interesting! Thanks.
        ori_b 15y ago
        It does mean that you are potentially keeping around masses of data when you only care about one or two elements. Normally not an issue, but normally internal pointers ("displaced arrays") aren't a central organizational concept in a language.

I'll bite: cdr gets expensive? You could represent a list as a naked array of lisp pointers, but then cons gets expensive. And good luck garbage collecting the vectors.

lisper 15y ago

> cdr gets expensive Yes, that's one thing. But do you really need CDR? > You could represent a list as a naked array of lisp pointers, but then cons gets expensive. Actually, it's much worse than that. CONS actually becomes impossible. (Think about it.) But maybe there's something else that you can use instead of CONS? > And good luck garbage collecting the vectors Why would that be a problem? Extant Lisps collect vectors just fine.

akkartik 15y ago
"Extant Lisps collect vectors just fine." But they don't permit pointers inside the vectors, do they? I think if you permit internal pointers so you can have copyless cdr, computing reachability would get really expensive.
- lisper 15y ago
  The phrase "permit pointers inside the vectors" doesn't really make sense. Vectors are just ordered collections of objects. They don't have insides and outsides, except insofar as the objects contained by the vector could be (but usually aren't) considered "inside" the vector. Lisp vectors are usually implemented as arrays of pointers, so in that sense pointers are "permitted" inside vectors. But I'm guessing that's not what you meant. (I have no idea what you actually meant.)
  - akkartik 15y ago
    (a (b (c . nil)) ^ ^ | | | | A B If you implement lists as vectors with car/cdr (I'm still thinking about your other questions) and choose to have cdr not copy results out of the original cell, you can end up in the (rope-like) situation above with pointer B (value (b c)) in addition to pointer A (value (a b c)). But that makes GC inefficient. For a vector to be GC'd you have to know what internal pointers it has, and then you have to make the choice to copy them out if they're 'toward the end', or to leave the vector uncollected. (ignore pointers to a, b, and c.)
    - lisper 15y ago
      Ah. What you are calling a "pointer to the inside of a vector" is actually called a displaced vector. It's a standard Common Lisp feature, and no problem for modern GCs.
      - akkartik 15y ago
        Interesting! Thanks.
      - ori_b 15y ago
        It does mean that you are potentially keeping around masses of data when you only care about one or two elements. Normally not an issue, but normally internal pointers ("displaced arrays") aren't a central organizational concept in a language.