Deadline#

Your work should be committed and pushed to your forked gitlab repo by 11:59pm on 24 April 2023.

This project is worth 10% of total course mark.

Description#

Implement translation from MoJo abstract syntax to intermediate code trees using the provided framework.

Getting Started#

Before starting this project, familiarize yourself with Chapters 6, 7, and 14 of the textbook and review the lecture notes on translation.

To get started fork the Project 4 repository on gitlab.

This project includes new source code that implements an intermediate code form based on trees, similar to the Appel book. Remember that the link between Project 3 and Project 4 is the semantic analysis of programs, which computes bindings for types, fields, methods, and local variables.

  • The framework for building the AST and printing out the results is the same as before, in src/mojo/Absyn.java.
  • You do not need to edit src/mojo/Absyn.java.

This project includes new source code that implements scaffolding for the semantic analysis phase of the compiler. Remember that the link between the Project 2 and Project 3 is the correct construction of AST nodes from Absyn.java.

  • The framework for building the AST and printing out the results is the same as before, in src/mojo/Absyn.java, with slight modifications to add fields for the types of expressions.
  • You do not need to edit src/mojo/Absyn.java.

Provided Semantic Analysis Solution#

The Project repo also includes binaries that implement both a complete parser and semantic analyzer in bin/mojo/*.class. You may choose to base your Project 4 work on the provided solution, or continue using your own solution. It is expected that you do not try to reverse engineer the class files of the provided solution to improve your score on Project 3, although you may run them to understand why your solution might be broken.

You can use your own Project 2 and 3 solution(s) by copying your files from Projects 2 & 3 into src/mojo. The grading script will work with either solution as long as you put its source in the proper place.

Where to Add Your Code#

All the action in this project is in src/mojo/Translate.java, which already contains much of the implementation. Your tasks will familiarise you with this stage of compilation. The class src/mojo/Translate includes the driver for running translation.

  • You should only need to edit src/mojo/Translate.java to complete this project.
  • You task is to complete the various methods marked with TODO comments. Some comments give a little explanation. Others you will need to infer based on context (make sure to look for clues in the other translation code that we have already provided).
  • Use the command make to build the project.

Once compiled, you can run the driver with:

java -cp bin mojo.Translate <input_file.mj>

Running the driver outputs a dump of the new tree code IR from your translation.

There is Lots of Code to Help You Here#

The provided framework provides the target IR, including a representation of the tree code from the Appel book and frames. You need only implement the translation from AST to IR.

Types#

A set of classes representing semantic types is provided, as for the 4last project.

Frames#

The src/Translate/Frame.java class provides an abstract representation of stack frames. It has a concrete subclass in src/x64 that is target-specific for Intel x86-64. This is the default machine target for our project.

Stack-Allocated Data#

The translation solution allocates local variables in each stack frame. This is done through the Frame interface using the allocLocal methods. Each local variable is associated with its allocated storage using the map accesses.

Statically-Allocated Data#

Your translation solution will need to implement various constructs that require statically-allocated data. In particular, we must generate allocations for:

  • Strings
  • Virtual Method Dispatch Tables
  • Global Variables

This is done through the Frame interface using the string, vtable, and record methods, respectively.

Code#

You will translate the ASTs into Tree code from src/Translate/Tree.java, grouping it into fragments.

Run-Time Tests#

For null pointer checks and array index bounds checks the Frame classes have methods badPtr and badSub that return labels to which your code can jump on dereferencing a null pointer or indexing an array with an out of bounds subscript.

Interpreter#

This project includes generating not only an IR, but also provides an interpreter for that IR, implemented in package interp (src/interp/Interpreter.java and src/interp/Frame.java). It simulates a flat word-based memory, the execution stack, and a small number of registers:

  • %ra : the first argument / return register
  • %sp : the stack pointer register
  • %fp : the frame pointer register
  • %fl : the frame link (aka static link/lexical link) used for nested procedures to access variables from outer lexical scopes, which are stored in the stack frame of the outer scope

The interpreter automatically adjusts %sp and %fp upon call and return; we don’t need to generate code to do this.

The src/interp/Interpreter machine has these builtin “external” functions, which have the same semantics as their C library counterparts:

  • void *malloc(int size): We use this to allocate heap objects in implementing New. You shouldn’t really call this from a mojo program directly as it is unsafe!
  • int putchar(int): You can define this in mojo as def putchar(i: int): int; and use it directly from mojo.
  • int getchar(void): You can define this in mojo as def getchar(): int; and use it directly from mojo programs.
  • void exit(int status): You can define this in mojo as def exit(status: int);. Our implementation of exit in the interpreter also prints the status value to standard output.

[Ultimately, we will link our compiled programs to the standard C libary to obtain these functions.]

You can “run” your translated programs using the interpreter as follows:

java -cp bin mojo.Translate -main -target=interp <input_file.mj>

The -main flag tells mojo.Translate to generate code for the “main” function which will call the procedure emitted as the main body of the compilation unit input_file.mj. The -target=interp flag tells mojo.Translate to use interp.Frame as the target (instead of the default x64.Frame which implements x86-64). Using the interp target will also invoke the interpreter after translation to interpret your program.

For example, consider the following program:

def exit(status: int);

{
  exit(3);
}

Running with the interpreter will produce the value 3 to standard output.

You can see the translated code (in linearized form) followed by the steps of the interpreter as it runs with the -trace flag. For the program above you should see something like the following output (skipping over badPtr and badSub where the … appears):

example (linearized):
0: 
EXP(
 CALL(
  NAME exit,
  CONST 0,
  CONST 3))

main (linearized):
0: 
EXP(
 CALL(
  NAME example,
  CONST 0))

...

  => main() frameSize=0, sp=1048576, fp=1048576
  NAME(example) = -10
  CONST(0)
  CALL(func=-10, link=0)
    addrToCode(-10) = example
    => example() frameSize=1, sp=1048572, fp=1048576
    NAME(exit) = -7
    CONST(0)
    CONST(3)
    CALL(func=-7, link=0, 3)
    => exit(status=3)
3

Expected Output#

The class mojo.Translate contains a main method that loads files, invokes the parser, runs the semantic analysis phase, and then invokes your translation solution. Your solution will be graded on correctnes, not code quality.

Make sure your program does not add any extraneous output to standard output. Make sure to run against the provided tests. Feel free to request or suggest additional tests (we will also add some more). You can still add debugging output to standard error. The grading script just greps for any expected semantic error in standard error. Make sure to use the provided error methods, as they give good error messages, and the script actually checks their text!

Turn In and Grading#

  • Like previous projects, you should fork the project repo to get started.
  • Like before, you don’t need to turn anything in.
  • We will pull from your repo’s master branch at the deadline.
  • We will rebuild your submission from source with your Makefile.
  • We will run the grading script on your code with additional test inputs that are not included in the repo.
  • We will provide the additional test inputs along with your score after the deadline.
bars search times arrow-up