Re:Show HN: Lisp with GC in 436 Bytes
by dan-robertson on Tuesday December 21, 2021 @06:22AM
(#29636286)
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.
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
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.