4 ms·

I think you’ve a trivial error in your function definitions but I don’t think it’s relevant. I think you’re right about avoiding cycles. I think the parent was

I think you’ve a trivial error in your function definitions but I don’t think it’s relevant. I think you’re right about avoiding cycles. I think the parent was talking about a let rec construction for data, e.g. in Haskell: let funky_list = 1:2:3:4:funky_list (Note that : is the cons operator). If this is allowed then you may have issues. I think the problem is perhaps that the GC won’t work if you have pointers in the opposite of the normal direction. The fix though is relatively simple: add forwarding pointers (somehow), then after copying from the ‘B’ region to the ‘C’ region you leave behind a forwarding pointer and, if you see it again in your copying, you don’t make a duplicate copy of the data. Then I think you can proceed as before. But representing forwarding pointers efficiently is hard, I suspect. Actually I think I don’t understand the GC sufficiently. Do you end up with a lot of memory usage after this or a little? ((LAMBDA (D Z) (D Z)) (QUOTE (LAMBDA (X) (COND (X ((LAMBDA (Y) (CONS Y Y)) (D (CDR X)))) ((QUOTE T) (QUOTE T))))) (QUOTE (A A A A A A A A))) This should get you a binary tree about 8 levels deep with T on every leaf, and I think it should use linear memory (in the depth of the tree) but I don’t understand how the GC avoids ending up with an exponential amount of memory being used?

jhgb 5y ago
> a let rec construction for data Is there actually any Lisp dialect where letrec works for data? I'm not aware of such, at least where it comes to major ones (CL and common implementations of Scheme).
- dan-robertson 5y ago
  Common Lisp let’s you write e.g. (list-length '#1=(1 2 3 4 . #1#)) But I think that isn’t what you mean.
- dan-robertson 5y ago
  I don’t understand how to construct cyclic references using only letrec. Do you have a concrete example?
- JonChesterfield 5y ago
  It would need a lazy data constructor and the lisp ones are (usually) strict. If you make cons et al lazy then letrec on data works as it does in other languages. Alternatively, make letrec wrap the values in thunks. The resulting cyclic structures are then moderately annoying to work with.
  - jhgb 5y ago
    Oh, I forgot lazy Lisps. But those would probably not be considered "major". > Alternatively, make letrec wrap the values in thunks. Aaaand of course I forgot that as well. My bad. So basically full lexical scoping and the presence of lambda should be enough to create cyclic structures, even in the absence of mutability.
MaxBarraclough 5y ago
> I think the parent was talking about a let rec construction for data You know more Haskell than I do ;-) What I had in mind were recursive and mutually recursive functions, defined with letrec, as examples of reference-cycles in functional programming.
jart 5y ago
Ah yes I missed that that when posting my earlier comment. As for your example, it uses exponential memory because your example produces exponential data. The only thing I'd need to show is that SectorLISP's ABC garbage collector doesn't grow at a large rate as the input size increases. According to the simulator's "heap" statistic, your example needs 449 doublewords of memory to compute a data structure that's 266 double words in size. That seems linear, but it's not, because if you add a few A's then the gap narrows. The cool thing about your example is that even though it's generating exponential data, that data structure doesn't require an exponential amount of memory to be stored internally. Currently the SectorLISP simulator only does things like de-duplication for DEFINEs which the simulator reports as "code" size in doublewords. However that's a friendly branch feature and the rest of the time SectorLISP just does plain "what you see is what you get" evaluation. I'm sure much more advanced techniques have been discovered since McCarthy wrote his original paper.
- dan-robertson 5y ago
  To be clear, my understanding of the GC is that what I wrote would use a linear amount of storage before the gc and potentially an exponential amount after. But maybe the gc runs in more places than I’d realised and so it never gets to only be linear.
  - jart 5y ago
    I've recorded a screencast of your algorithm running in Blinkenlights. That might help intuitively explain what the ABC Garbage Collector is doing: https://justine.lol/sectorlisp2/binarytree2.mp4 https://justine.lol/sectorlisp2/binarytree2.mp4
    - deleted 5y ago
      [deleted]

jhgb 5y ago

> a let rec construction for data Is there actually any Lisp dialect where letrec works for data? I'm not aware of such, at least where it comes to major ones (CL and common implementations of Scheme).

dan-robertson 5y ago
Common Lisp let’s you write e.g. (list-length '#1=(1 2 3 4 . #1#)) But I think that isn’t what you mean.
dan-robertson 5y ago
I don’t understand how to construct cyclic references using only letrec. Do you have a concrete example?
JonChesterfield 5y ago
It would need a lazy data constructor and the lisp ones are (usually) strict. If you make cons et al lazy then letrec on data works as it does in other languages. Alternatively, make letrec wrap the values in thunks. The resulting cyclic structures are then moderately annoying to work with.
- jhgb 5y ago
  Oh, I forgot lazy Lisps. But those would probably not be considered "major". > Alternatively, make letrec wrap the values in thunks. Aaaand of course I forgot that as well. My bad. So basically full lexical scoping and the presence of lambda should be enough to create cyclic structures, even in the absence of mutability.

MaxBarraclough 5y ago

> I think the parent was talking about a let rec construction for data You know more Haskell than I do ;-) What I had in mind were recursive and mutually recursive functions, defined with letrec, as examples of reference-cycles in functional programming.

jart 5y ago

Ah yes I missed that that when posting my earlier comment. As for your example, it uses exponential memory because your example produces exponential data. The only thing I'd need to show is that SectorLISP's ABC garbage collector doesn't grow at a large rate as the input size increases. According to the simulator's "heap" statistic, your example needs 449 doublewords of memory to compute a data structure that's 266 double words in size. That seems linear, but it's not, because if you add a few A's then the gap narrows. The cool thing about your example is that even though it's generating exponential data, that data structure doesn't require an exponential amount of memory to be stored internally. Currently the SectorLISP simulator only does things like de-duplication for DEFINEs which the simulator reports as "code" size in doublewords. However that's a friendly branch feature and the rest of the time SectorLISP just does plain "what you see is what you get" evaluation. I'm sure much more advanced techniques have been discovered since McCarthy wrote his original paper.

dan-robertson 5y ago
To be clear, my understanding of the GC is that what I wrote would use a linear amount of storage before the gc and potentially an exponential amount after. But maybe the gc runs in more places than I’d realised and so it never gets to only be linear.
- jart 5y ago
  I've recorded a screencast of your algorithm running in Blinkenlights. That might help intuitively explain what the ABC Garbage Collector is doing: https://justine.lol/sectorlisp2/binarytree2.mp4 https://justine.lol/sectorlisp2/binarytree2.mp4
  - deleted 5y ago
    [deleted]