:: Enseignements :: Master :: M2 :: 2024-2025 :: Virtual Runtime Environment (and stuff around ...) ::
[LOGO]

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 (smalljs.ebnf) describing the grammar of smalljs. The generated a lexer and a parser classes for this grammar are in the folder grammar/gen-src
  • a folder samples that contains examples of JavaScript scripts supported by smalljs.
  • a folder src/main/java that contains the following packages
    • A package fr.umlv.smalljs.ast which defines the abstract syntax tree in the class Expr.java.
    • A package fr.umlv.smalljs.rt with for the moment 2 interesting classes, JSObject that represent a JavaScript object and Failure that represent an execution error
    • A package fr.umlv.smalljs.main that contains the main class (Main) able to execute all the interpreters
    • The packages fr.umlv.smalljs.astinterp, fr.umlv.smalljs.stackinterp and fr.umlv.smalljs.jvminterp that respectively represent the AST interpreter, the Stack based interpreter and the JVM based interpreter.

The command mvn package compile and create a JAR executable smalljs.jar in the folder target that can be used to test different scripts
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 --class-path lib/tatoo-runtime.jar:target/smalljs.jar ast samples/hello.js
and with the Nashorn Javascript engine 
  /usr/local/apps/java11/bin/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.

  1. Before starting, explain to yourself how "switch on types" in the method visit of ASTInterpreter.java works ?
    How to "return" a value from a case ?
    How to call it, how to do a recursive call ?
  2. 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 ?
  3. Extend your implementation to allow support int literal and verify that the test marked Q3 pass.
  4. 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.
  5. 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.
  6. 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 "qualifier" component 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.
  7. Verify that print still work by verifying that the test marked Q7 pass.
  8. 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.
  9. Modify the code to throw a Failure if the same local variable is declared twice
    What is the behavior of JavaScript if someone 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.
  10. 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 that name is not inserted in the environment
  11. Add the support of the if and verify that all the tests marked Q11 pass.
  12. 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 ?
  13. 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.
  14. 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.
  15. 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.
  16. 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.
© Université de Marne-la-Vallée