:: Enseignements :: Master :: M2 :: 2023-2024 :: 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 verify 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. This has to be done for the first frame and each time a non nativefunction is called. 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.
© Université de Marne-la-Vallée