Immutable tree-structured stack

I'm writing valeri to be a pure language. As a pure language, it needs a way to somehow do IO in a way that doesn't violate purity and doesn't lead to mutation of state or non-reproducible behavior.

One of the ways to achieve this is called "algebraic effects". You can read theory on algebraic effects in the Eff paper. In short, IO can be represented as a "continuation", where an attempt to call a function doing IO leads to saving the full state of computation and "throwing" it up the stack until it reaches the top level. The VM then performs the requested IO and calls the continuation object with the results. It looks like sort of a resumable try-catch.

The reason why systems with "algebraic effects" can be considered pure is because in a sense you invert the control. As if the program is divided into 2 pieces - the one before the IO and the one after the IO. Both of those parts are themselves pure function and you just call them sequentially.

There are multiple clever ways to implement continuations, but most of them reduce program debuggability in the same way that automatic tail-call optimizations do. Mostly because they don't preserve the call stack except for what is necessary for continuing the execution past a certain point. An attempt to print a stacktrace on exception will likely lead to nonsensical results. (or even exploring values of certain local variables in the debugger can be impossible)

So instead, I went for the most straightforward approach to saving program state. Initially I started out with having a single mutable stack backed by an array. As many regular languages do, it used a base pointer to delimit the current "frame". And now I've converted one single stack to a linked list of frames: whenever a function is called, a new frame is allocated on the heap, and it points back to the previous frame. So in theory you can return back to the previous frame and start a new "branch" from there.

The only trick here is to prevent modification of the shared parts of the stack when we throw the continuation and a function somewhere up the stack performs some computation. To achieve this, my stack data structure is immutable: all modifications of the frame actually create a new copy of the same frame, and the VM switches to that. It's not efficient, but it's a way to get a working solution. And there are ways to remove unneeded copies where we can perform direct mutation of the frame if there's nobody else who refers to the same frame.