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

Lab 1 - AST walker

The aim of this first lab is to write an AST interpreter for the language smalljs which is a small subset of the language JavaScript.
The AST (abstract syntax tree) is a tree representing a script that can be used to interpret the script by walking the tree and executing for each kind of expression a specific code.
To associate a code to execute to a specific kind of expression, we use a visitor that associate to an expression class a lambda representing the code to execute.

In order to help you to write the AST interpreter, here is a git project containing a get-started code (a lexer, a parser and classes defining the AST)
write_your_dynamic_language_runtime
The git project contains

a folder grammar that contains the file (minijs.ebnf) describing the grammar of smalljs and an ANT script (build.xml) that generates a lexer and a parser for this grammar in the folder grammar/gen-src
a folder src that contains the Java classes that define the abstract syntax tree and two classes Failure and JSObject that represent respectively an error in the script and a JavaScript object.
a folder samples that contains examples of JavaScript scripts supported by smalljs.
a folder lab1/src that contains a main class ASTInterpreterMain and two classes ReturnError that will be detailed below and ASTInterpreter which is the class that must be modified to implement the interpreter.

The command ant compile and create a JAR executable smalljs.jar that can be used to test different sample script (see the folder samples).
Moreover, Java 11 also provide a full-featured JavaScript engine, named Nashorn, that can be used to compare if the result of your interpreter is correct.
To execute by example hello.js with your interpreter use

  java -jar smalljs.jar ast samples/hello.js

and with the Nashorn Javascript engine

  jjs samples/hello.js

Exercice 1 - AST interpreter

The aim of this exercise is to just complete the file ASTInterpreter.java and you should not have to write or modify any other files.

Before starting, explain to yourself how the visitor in ASTInterpreter.java works ?
how to call it, how to do a recursive call ?
What does the second parameter of the lambdas (env) mean ?
The file ASTInterpreterTest contains several unit tests for all the following questions.
Now, we want to implement the AST interpreter when there is a constant String (a literal).
What is the class of the corresponding node in the AST (you can take a look to the file smalljs.md for a summary).
How to implement it ?
Is it enough to make test marked Q2 pass ? what other node should be implemented too ?
Extend your implementation to allow support int literal and verify that the test marked Q3 pass.
We now want to print something.
What is the class of the node in the AST to implement ?
For now, we will suppose that the only function is the print function. How to find the function "print" which is registered in the global environment ? How to call it ?
Add the code to support the function print and verify that the test marked Q4 pass.
What is the return value of the function print in JavaScript ?
Make sure your interpreter behave accordingly and verify that the test marked Q5 pass.
We now want to support other functions than just print.
Where all the builtin functions are defined ?
How to modify the code to support all builtin functions ? What is the "qualified" attribute represent ?
Is the visit of a function call enough to implement the support of a function call ? What is the method in the environment env to look for a value associated to a name ?
What is the class that represent a function at runtime ?
Modify the code and verify that the test marked Q6 pass.
Verify that print still work by verifying that the test marked Q7 pass.
We now want to be able to declare or assign a local variable.
What is the class of the node in the AST corresponding to a local variable assignment ?
Implement the interpreter part and verify that all the tests marked Q8 pass.
Modify the code to throw a Failure if the same local variable is declared twice
What is the behavior of JavaScript if somone try to access to a local variable before the declaration of this variable ? Modify the code of the interpreter to have the same semantics.
Verify that the tests marked Q9 pass.
We want to support the declaration of user defined function. What is the name of the class of the AST node that correspond to a function declaration.
How to create a new function (JSObject) at runtime ?
Why a new environment must be created to represent the environment inside the function ? What will happen if we re-use the current environment ?
What is the value of the hidden parameter "this" ?
How to implement the return knowing there is a class ReturnError ?
Note: a failure should be thrown is the number of parameter and the number of argument are not the same.
Note2: if a function doesn't have a name, the name of the JSObject is "lambda" for debugging but the name is not inserted in the environment
Add the support of the if and verify that all the tests marked Q11 pass.
Verify that your code support recursive function by running the test marked Q12.
What if the maximum value of n when running the function fact ? Why ?
We now want to add the support of the creation of object instance using the JavaScript JSON like notation.
What is the class of the corresponding AST node ?
How to create a JSObject at runtime ?
Implement the corresponding interpreter part and verify that the tests marked Q13 and Q14 pass.
We want to implement the read of an instance field.
What is the class of the corresponding AST node ?
What if the value is not an instance of a class but a primitive type ?
What should be done if the field doesn't exist for that instance ?
Implement the corresponding interpreter part and verify that the tests marked Q15 pass.
We want to implement the write of an instance field.
What is the class of the corresponding AST node ?
What if the value is not an instance of a class but a primitive type ?
What should be done if the field doesn't exist for that instance ?
Implement the corresponding interpreter part and verify that the tests marked Q16 pass.
We want to implement the method call.
What is the class of the corresponding AST node ?
What the difference between a function call and a method call
Implement the corresponding interpreter part and verify that the tests marked Q17 pass.