:: Enseignements :: Master :: M2 :: 2018-2019 :: Machine Virtuelle (et bazar autour ...) ::

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 minijs and generates the corresponding suite of instructions.
A ZIP archive containing a get-started code is available vm2016-lab2.zip

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 minijs.

First, what is the purpose of the following classes ?
- Code
- Dictionary
- Instructions
- TagValues
- StackInterpreter
Modify the code of Example.topLevel() to write the instructions that prints 42
Then modify the code of StackInterpreter and test by running the main of Example.
Change the instructions of the method Example.topLevel() to have something similar to the following code
```
  a = 3
  print(a)
        
```
then modify the stack interpreter in order to execute the instructions.
Verify that the following code transformed into instructions
```
  a = b = 3
  print(a)
  print(b)
        
```
works correctly.
Modify the instructions of Example.topLevel() to represent the following code
```
  a = function() { return 42; }
  print(a)
        
```
Modify the interpreter to be able to interpret that code.

Same question with the following snippet

  function foo() { return 42; }
  print(foo);

Modify Example.topLevel() and StackInterpreter to test that GOTO works !
Note: you should test a forward branch and a backward branch.
Modify the instructions to use JUMP_IF_FALSE instead and change the interpreter accordingly.
We now want to implement the function call (FUNCALL and RET).
What is the meaning of the variables BP_OFFSET, PC_OFFSET and FUN_OFFSET ?
Knowing that the argument of a function call are the parameters of the called function without copying them, how the stack has to be organized ?
Make a drawing of the stack when the function topLevel calls the function addTo to be sure.
How to know when the interpreter should stop ?
Implement the function call and return.

Exercice 2 - Rewriter

We now want to directly execute a minijs 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.

Modify the code of the Rewriter to be able to transform the following code
```
  print(42)
        
```
into an array of instructions.
Then execute it using the stack interpreter.
Modify the class Rewriter in order to be able to execute the following code
```
  function foo() {
    var a = 2
    print(a)
  }
  foo();
        
```

Same question with the following code

  function foo(a) {
    print(a)
  }
  foo(42);

Test that you can also execute an addition.
Test that you can execute the following code
```
  if (3 == 3) {
    print(1);
  } else {
    print(0);
  }
        
```
Note: minijs syntax forbids an if without an else. and then test that fibo.js is working !
The idea is to put a placeholder instead of the target of GOTO and then when the address is know to patch the placeholder.