:: Enseignements :: ESIPE :: E5INFO :: 2019-2020 :: Machine Virtuelle (et bazar autour ...) ::
[LOGO]

Lab 2 - Stack Interpreter

This lab is split in two parts. In the first exercise, the idea is to implement an interpreter of instructions using snippet of program written by hand. In the second exercise, the idea to is write a Rewriter that takes an AST of smalljs and generates the corresponding suite of instructions.

Exercice 1 - Stack interpreter

A video of Terence Parr of the San Franscisco University about how to create a stack interpreter in Java
How to Build a Virtual Machine by Terence Parr

The aim of this exercise is to write a stack interpreter for the language smalljs.
Unit tests for this exercise are available in class StackInterpreterInstrTests.

  1. First, what is the purpose of the following classes ?
    • Code
    • Dictionary
    • Instructions
    • TagValues
    • StackInterpreter
  2. What the following code does ? 
      CONST, encodeDictObject("hello", dict),
  RET

    First modify the code of StackInterpreter so the instruction CONST is executed correctly Then verifify that the test marked "Q2" pass
    Then fix the code of RET in the interpreter to calculate the starts of the activation, and retrieve the program counter (pc) from the activation zone. The test marked "Q2" should still pass.
  3. Comparing the tests "Q2" and "Q3", what the difference between encodeDictObject("hello", dict) and encodeSmallInt(3) ?
    Verifies that the test marked "Q3" pass.
  4. We know want to print 3, for now instead of using the real "print" that requires that the instruction FUNCALL that does a function call to be implemented, we will use the instruction PRINT which execute a hardcoded print.
    Complete all the TODOs so all the tests marked "Q4" pass.
  5. We now want to implement the instruction FUNCALL if the function is a native function (native functions are the ones not defined by the user but already implemented in the environment).
    The tests marked "Q5" should pass.
  6. The code that you have written should support any native function, not only print.
    Verify that the tests marked "Q6" pass.
  7. Also verifies that print both the hardcoded version and the one using native function call both returns undefined by executing the tests marked "Q7".
  8. We want to add the support of loading and storing values into local variables. For that you have to implement the instructions LOAD and STORE.
    The tests marked "Q8" should pass.
    Note: for printSeveralAssignments to pass, you need to also to implement POP that remove the value on top of the stack.
  9. By default, in JavaScript (and in smalljs), the local variables are initialized to undefined Modify the interpreter to initialize all the local variables and verify that the test marked "Q9" pass.
  10. We now want to be able to call another function also defined by the user. First, explain the first two instructions of the test callAUserDefinedFunctionAndPrint.
    Then fix all the Todos in the instructions FUNCALL and RET.
    Verify that the tests marked "Q10" pass.
    Note: for the test callVariableFunction, you also need to implement the instruction DUP
  11. In order to support the if ... else, add the implementation of instructions JUMP_IF_FALSE and GOTO.
    Verify that the tests marked "Q11" pass.
  12. Verify that the tests marked "Q12" that test recursive user defined functions pass.

Exercice 2 - Rewriter

We now want to directly execute a smalljs script from the command line. For that, we want to complete the code of class Rewriter that transforms an AST to a Code (an array of instructions).
In order to simplify the code, the rewrite will be done when the code of a function is discovered. We will see in a later lab how to do that lazily.

  1. In the class Rewriter, what is the purpose of the VARIABLE_VISITOR ?
  2. In the Rewriter visitor, implement the support of Literal.
    Verify that the test marked "Q2" pass.
  3. Verify that the string literal are also supported by executing the test marked "Q3".
  4. Add the support of the function call by implementing the visit of FunCall.
    Verify that the test marked "Q4" pass.
    Note: When an identifier is not a local variable, a LOOKUP is emitted. Implement the visit of LocalVarAccess to add that behavior. Note2: in case the local variable exists, throw an exception, we will change that later.
  5. Verify that the test marked "Q5" pass.
  6. Verify that the return value are propagated properly so the test marked "Q6" pass.
  7. Also Verify that the test marked "Q7" pass.
  8. Add the support to rewrite the declaration of a variable and the loading of that variable by implementing respectively the visit of LocalVarAssignment and LocalVarAccess.
    Verify that the tests marked "Q8" pass.
  9. Verify that the test marked "Q9" pass.
  10. We now want to support the declaration of user defined function. For that, you have to implement the visit of the Fun and the Return ast nodes.
    Verify that the tests marked "Q10" pass.
    Note: if you don't see the shape of the generated code, you can take a look to the tests marked "Q10" in StackInterpreterInstrTests.
  11. In order to implement the if ... else, implement the visit of If ast node and verify that the tests marked "Q11" pass.
  12. Verify that the tests marked "Q12" pass.
© Université de Marne-la-Vallée