Writing a Lisp: Explicit Stack and Stacktraces | Hacker News Reader

Writing a Lisp: Explicit Stack and Stacktraces

reinvanderwoerd.nl

45 pointsreinvdwoerd11 comments

I feel like writing a LISP in a gc'ed language is taking away most of the fun of it. I wrote one in C (without a conservative garbage collector) and the most interesting aspect was what had to be done to allow garbage collection.

Garbage collection can run inside nearly all subroutines. So any temporary references stored outside of the heap need to be kept track of at all times. If gc occurs you have to able to walk the entire heap and the entire callstack to mark live data. This is obvious but I enjoyed finding it out (and subsequently rewriting everything).

> I feel like writing a LISP in a gc'ed language is taking away most of the fun of it.

Try telling Rich Hickey that. There's also Kawa and Armed Bear Common Lisp running on the JVM.

If you write your interpreter in a non-garbage-collected language (e.g. C), you should use an explicitly declared stack for arguments, and have argument-free functions. Also, for functions which might call the garbage collector, you can't store any garbage collectable data in local variables either. It might be possible to have your garbage collector access the C call stack, but I wouldn't recommend that.

Three decades ago, my first attempt at implementing a Lisp interpreter in Pascal fell foul of this problem and occasionally recycled lists which were still in use. I soon figured out what was happening. I decided to replace the interpreter with a virtual machine and a compiler (and also a source-code interpreter for bootstrapping and the REPL), and I still use a descendent of this.

One of my seminal experiences in hacking on languages was working on a VM for a garbage collected language written in C++. I wrote a Cheney style copying collector to avoid fragmentation. Meanwhile, I used C++ inheritance and vtables to implement the different kinds of objects supported by the runtime.

I thought it was a really cool system until I realized that the GC could move the object pointed to by `this` in the middle of a method. Ouch. :(

The irony of implementing Lisp in assembly is that, almost for free (sorry about that), you get precise, convenient control of the memory situation. Just put the gc root exclusively in registers.

I wrote a Lisp interpreter in assembly that dedicates 4-5 registers for the current expression, eval environment, and so on. The mark-sweep collector starts from these registers.

https://github.com/marcpaq/arpilisp

Cool project. It's much clearer than I would have thought in asm. The inline documentation is good.

No irony there. You need precise control over the machine to implement a paradigm accurately from the ground up. It's hard to do that using someone else's paradigm, living with their choices of what aspects of the machine are still revealed and which are hidden.

Back when I wanted to write a Lisp interpreter, I thought Haskell would be one of the best languages for it because of its type system. But looking at this code, although I'm sure it's probably very good, it just doesn't strike me as very intuitive or readable. Is this something you get used to over time, like reading Lisp code? Or is it just inherently harder for non-mathematically-minded people to read?

I had the same reaction. The only part of this that I could read was a little surprising:

    pop :: CallstackIO ()
    pop =
      modify popFrame
      where popFrame (_:xs) =
              xs
            popFrame xs =
              xs

Not that it's very onerous to implement, but I would expect these "pop" semantics to be imported from some more general type (or trait, or whatever Haskell uses for type composition). That said, I don't know what `modify` means.

From the documentation:

"Maps an old state to a new state inside a state monad. The old state is thrown away."

https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-M...

>Is this something you get used to over time, like reading Lisp code?

Yeah. At least for me, the thing that finally made reading Haskell and Lisp syntax was sitting down writing some.

I've been writing my own lisp (in Clojure) by following the make-a-lisp[0] process guide. So far it's been challenging and interesting. It gives clear direction without being too hand-holdy.

[0] https://github.com/kanaka/mal

Reply on news.ycombinator.com