Writing a Lisp: Explicit Stack and Stacktraces
reinvanderwoerd.nl
Writing a Lisp: Explicit Stack and Stacktraces
1–10 of 12 posts
Re: Writing a Lisp: Explicit Stack and Stacktraces
#2Back 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?
Re: Writing a Lisp: Explicit Stack and Stacktraces
#3Back 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
Re: Writing a Lisp: Explicit Stack and Stacktraces
#4I 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).
Re: Writing a Lisp: Explicit Stack and Stacktraces
#5I 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…
> 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.
Re: Writing a Lisp: Explicit Stack and Stacktraces
#6I 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…
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. :(
Re: Writing a Lisp: Explicit Stack and Stacktraces
#7Back 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?
>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.
Re: Writing a Lisp: Explicit Stack and Stacktraces
#8I'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.
Re: Writing a Lisp: Explicit Stack and Stacktraces
#9Back 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...
Re: Writing a Lisp: Explicit Stack and Stacktraces
#10I 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 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.