3 ms·

> You can write a lisp in a few lines of Forth. Seems unlikely. Forth isn't garbage collected, is untyped, etc etc. So you'd have to add those things in "a few

> You can write a lisp in a few lines of Forth. 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-technically-scheme-written-in-forth https://forums.parallax.com/discussion/160027/lisp-technical...

pjmlp 8y ago
Not all Lisps had GC in the early days. There were some mainframe implementations that would just allocate until there was no more memory left.
vidarh 8y ago
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.
- kazinator 8y ago
  Ruby-ish pseudo code is somewhat remote from working Forth.
  - vidarh 8y ago
    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.
tgvaughan 8y ago
This is actually a random side project of mine! https://github.com/tgvaughan/scheme.forth.jl https://github.com/tgvaughan/scheme.forth.jl

pjmlp 8y ago

Not all Lisps had GC in the early days. There were some mainframe implementations that would just allocate until there was no more memory left.

vidarh 8y ago

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.

kazinator 8y ago
Ruby-ish pseudo code is somewhat remote from working Forth.
- vidarh 8y ago
  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.

tgvaughan 8y ago

This is actually a random side project of mine! https://github.com/tgvaughan/scheme.forth.jl https://github.com/tgvaughan/scheme.forth.jl