Move through instructions instead of pushing/ popping

[marcusklaas]

The current approach works OK, but it has drawbacks.

Firstly, the instruction stack grows very large for deeply recursive calls. This is because we now push the instructions for both branches of a condition.

Further, we clone a vector onto the instruction stack for each function call. Since instructions are not Copy, this is pretty expensive.

It's not immediately clear what the ideal solution here is. We cannot precompile the bytecode for all functions and add them to a large vector since new functions can (only!) be made during runtime. Just pushing to a big vector whenever a function is created at runtime may work, but this may overflow when many one-shot functions are created, for example in (map (lambda (x) (lambda (y) (list x y))) (range 1 10000)).

Ideally, we don't ever clone instructions and yet throw away that which we know won't run any more. One way we may do this is by introducing (another!) stack with an Rc<Vec<Instr>> and usize, where the usize points to current instruction in the instruction vector. Instead of creating two more vectors, these values should probably be combined with the value stack pointer stack into one vector of structs, containing instruction pointer, value pointer and current instruction vector.

[marcusklaas]

This is mostly implemented now. Instruction vectors are now Rc<RefCell<Vec<Instr>>>, which is a bit inefficient since it may be as many as three indirections to get a vector and some runtime checking (because of the RefCell). We should probably introduce a new type which combines the properties of Rc, RefCell and Vec. It should be possible to have only a single level of indirection and no runtime checks other than the bounds check.

[marcusklaas]

Closing this and creating a new issue for the instruction store.