4 ms·

Writing a Lisp: Explicit Stack and Stacktraces

45 points by reinvdwoerd 9y ago

penpapersw 9y ago
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?
- gavinpc 9y ago
  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.
  - reinvdwoerd 9y ago
    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-Monad-State-Lazy.html https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-M...
- ubercow 9y ago
  >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.
rrmm 9y ago
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).
- DonaldFisk 9y ago
  > 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.
- munificent 9y ago
  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. :(
- marcpaq 9y ago
  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 https://github.com/marcpaq/arpilisp
mbil 9y ago
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 https://github.com/kanaka/mal

45 points by reinvdwoerd 9y ago

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?

gavinpc 9y ago
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.
- reinvdwoerd 9y ago
  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-Monad-State-Lazy.html https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-M...
ubercow 9y ago
>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.

rrmm 9y ago

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).

DonaldFisk 9y ago
> 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.
munificent 9y ago
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. :(
marcpaq 9y ago
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 https://github.com/marcpaq/arpilisp

mbil 9y ago

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 https://github.com/kanaka/mal