Final pull request for HeapVirtualMachine

[btwooton]

Alright folks, here you have it. The final implementation of the HeapVirtualMachine is now complete. All twelve of the assembly instructions have been implemented and thoroughly tested. Barring certain slight inconsistencies in the assumptions made by the Compiler spelled out in the Three Implementation Models for Scheme paper in regards to the handling lambda expressions that have multiple body expressions, this VM code is test proven to represent a sound implementation of Dybvig's Heap Based Model.

You'll notice that this pull request has a number of auxiliary commits that were needed to complement the finishing of the VM.

Closure and CallFrame were both added to shaka::Data out of necessity.

The type of the ValueRib data structure was changed from std::vector to std::deque in order to accurately reflect the semantics of being able to add arguments to the front of the value rib when the (argument ...) instruction is executed by the VM.

The functions in the core/types.hpp and core/lists.hpp were given an inline qualifier to allow Closure.cpp and HeapVirtualMachine.cpp to each include these functions without incurring linker errors, as both classes needed the functionality contained in these header files to do their work.

Finally, variadic lambda support was added to the Closure class and tested. This is to enable our system to handle lambda defined procedures like (lambda x x) that take in a variable number of arguments, as well as those that have improper parameter lists like (lambda (a b . c) ...)

Please look over this pull request at your earliest convenience, and feel free to let me know if you spot anything that looks dubious or that I might have overlooked in my testing. This turned out to be a much larger commit than I had originally foresaw, with a large number of diffs, so it is highly likely that I missed more than a few things along the way. The good news is, all of my test cases pass and the 12 instructions are complete and working properly, with lots of interoperability already proven.

[CinchBlue]

Okay, I believe we agreed during the meeting yesterday that the compiler and the VM need to be changed to handle multi-expression body lambda. I think that's what we agreed on, at least -- although I think I'm missing something.

[btwooton]

Ok. The final two test cases are fixed. Dylan and I have more or less found a solution to the problem of compiling multi expression lambdas. All expressions that are not in tail position need to be nested within (frame ret x) instructions, with the outermost body expression taking the position of the outermost ret field. This expression will have as it's next expression the (halt) instruction. This ensures that we do not propagate superfluous (return) instructions, which can be poisoned because there can be no guarantee in a system that employs TCO that there will always be a frame to return from. At the very least, the test cases intending to test the following:

(define f (lambda (k) (k 'a) 'b)) (f (lambda (x) x)) => 'b (call/cc f) => 'a

Work as expected. When we invoke the procedure f on a continuation closure, we place symbol 'a in the accumulator and return control to the frame that was the top of the call stack when the continuation was created, as we would expect. When we invoke f on the identity closure, we return symbol 'b and place it in the accumulator, then halt. Think of halt as a signal that says, "look in the accumulator for the result of the last computation." This is semantically correct as far as I can see based off of the design in Dybvig's paper, and represents at least a minimally viable solution to patching the deficiency in Dybvig's compiler implementation in regards to handling (lambda ...) expressions with multiple body expressions

[CinchBlue]

@Mortrax @dylannakahodo YOU DID IT!