In addition to not technically needing a GC, a simple GC can be small if you don't care (much) about performance. One variation over a basic tricolor mark and sweep using linked lists for each "color" is basically (ruby-ish pseudocode):
# 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
A "real" implementation of the above can be done in <100 lines in many languages. Doing efficient gc gets more complex very quickly, though.
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.
It's remote in that it looks very different, but not in terms of complexity. The operations used in the pseudo code are basically just.
- 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...