3 ms·

This is cool. I wrote a similar Lisp but got stuck debugging my copying GC. The interaction between the Lisp environment chain and the C stack is tricky. I pre

by blt 8y ago

This is cool. I wrote a similar Lisp but got stuck debugging my copying GC. The interaction between the Lisp environment chain and the C stack is tricky. I prefer something like this over Norvig's Lisp interpreter written in Python. Norvig's is good for understanding environments and eval/apply, but IMO it's cheating to use the host language's GC for allocations. I would add integers, even if it costs a few lines of code... using `itos` and re-parsing the string when evaluating an int is just too painful for me.

mpirstitz 8y ago
Here's my own attempt at implementing a somewhat readable copying GC in C - https://github.com/matp/tiny-lisp/blob/master/tiny-lisp.c#L101 https://github.com/matp/tiny-lisp/blob/master/tiny-lisp.c#L1...
- krig 8y ago
  Cool, that's an interesting solution! I tried hard to keep the GC implementation as straight-forward as possible, as a teaching aid, but I'll admit that debugging the GC was a bit of a struggle when roots weren't clearly indicated as such.
krig 8y ago
I felt the same way about Norvigs version which was one reason to do this. I feel like the recursive lisp interpreter-on-an-interpreter thing is not as clear when so much of the host language is relied on. Oh, and I hear you about integers as strings. This choice was in part for compactness and in part inspired by the first LISP papers where there are only symbols and no other types.
slaymaker1907 8y ago
To be fair to Norvig, malloc is also a relatively hefty abstraction comparable to a GC on a systems level.
- krig 8y ago
  That is certainly a good point. The problem I felt with dropping below malloc is that the code becomes very platform-dependent.
- blt 8y ago
  but copying GC can be easily implemented with sbrk, or on the bare metal if no MMU is present. mpirstitz's GC uses mmap but could easily be replaced with sbrk. the main challenge of dynamic memory management is fragmentation, which is completely handled by using a copying GC. an implementation on top of malloc is not leaning on malloc's fragmentation handling at all.

by blt 8y ago

mpirstitz 8y ago

Here's my own attempt at implementing a somewhat readable copying GC in C - https://github.com/matp/tiny-lisp/blob/master/tiny-lisp.c#L101 https://github.com/matp/tiny-lisp/blob/master/tiny-lisp.c#L1...

krig 8y ago
Cool, that's an interesting solution! I tried hard to keep the GC implementation as straight-forward as possible, as a teaching aid, but I'll admit that debugging the GC was a bit of a struggle when roots weren't clearly indicated as such.

krig 8y ago

I felt the same way about Norvigs version which was one reason to do this. I feel like the recursive lisp interpreter-on-an-interpreter thing is not as clear when so much of the host language is relied on. Oh, and I hear you about integers as strings. This choice was in part for compactness and in part inspired by the first LISP papers where there are only symbols and no other types.

slaymaker1907 8y ago

To be fair to Norvig, malloc is also a relatively hefty abstraction comparable to a GC on a systems level.

krig 8y ago
That is certainly a good point. The problem I felt with dropping below malloc is that the code becomes very platform-dependent.
blt 8y ago
but copying GC can be easily implemented with sbrk, or on the bare metal if no MMU is present. mpirstitz's GC uses mmap but could easily be replaced with sbrk. the main challenge of dynamic memory management is fragmentation, which is completely handled by using a copying GC. an implementation on top of malloc is not leaning on malloc's fragmentation handling at all.