There were some mainframe implementations that would just allocate until there was no more memory left.
# At this point all objects are in the "white" set. We don't know if they're reachable (in which case they're garbage)
# Mark roots
push_registers_to_stack
stack.each {|ob| grey.append(ob) } # You need to do this to any other roots as well, e.g. any pointers from bss.
# Iteratively scan every object, moving unscanned objects into the "grey" set (reachable but unscanned)
grey.each {|ob|
ob.referenced_objects.each {|ref| grey.append(ref) }
# "ob" has now been scanned, so moving it into the black set (reachable *and* scanned)
grey.delete(ob)
black.append(ob)
}
# What remains in the "white" set is now the garbage, so free it. You can also, if you want, move this aside and free it lazily.
white.each {|ob| ob.free }
white = black
The mruby gc is a good place to see a more realistic tricolor mark and sweep that is also incremental and also includes a generational collection mode. It's about 1830 lines of verbose and well commented C including about 300 lines of test cases and a Ruby extension to interact with it. A simpler one like the above could certainly be much smaller even in C.
- Pushing registers onto the stack
- Iterating over the stack
- Appending to a linked list
- Popping the first entry off a linked list
- Iterating over a linked list
- Calling a function/method ("free") to release the memory. In it's most naive form this would mean appending it to a linked list of free memory.
The two first requires dipping into assembler in a lot of languages. The rest will be tiny in most languages, including Forth, but my Forth knowledge is very rudimentary hence why I didn't try.
Seems unlikely. Forth isn't garbage collected, is untyped, etc etc. So you'd have to add those things in "a few lines".
Though I guess it depends what you mean by "a few". I was thinking a couple of dozen. Looks like someone's done it in 500 (though without GC -- is that still Lisp?): https://forums.parallax.com/discussion/160027/lisp-technical...