PA5 — Compiler/Code Generator

Project Overview

PA5 is due 4/2 at 11:50PM. Alternatively, you can submit PA5 by 4/16 at 11:50pm, but you will not be eligible for extra credit (rubric below).

You may do this assignment in OCaml, Haskell, JavaScript, Python, or Ruby. If you are comfortable with functional languages, OCaml and Haskell are likely the best choices. However, Python is the most popular choice.

You may work in a team of up to four people for this assignment. You may work in a team for any or all subsequent programming assignments. You do not need to keep the same team. The course staff are not responsible for finding you a willing team.

Goal

For this assignment, you will write a program that takes a Cool abstract syntax tree and produces either Cool Assembly or x86-64 assembly. You will be given a Cool Annotated Abstract Syntax Tree (see PA4 specification for details). From this annotated AST, you must generate ASM code.

You do not have to worry about malformed input because the semantic analyzer (from PA4) has already ruled out bad programs. You will track enough information to generate legitimate run-time errors (e.g., dispatch on void). Among other things, this assignment involves implementing the operational semantics specification of Cool.

The Specification

You must create three artifacts:

  1. A program that takes a single command-line argument (e.g., file.cl-type). That argument will be a Cool Annotated Abstract Syntax Tree file coresponding to one or more classes and methods. The cl-type file will always be well-formed (i.e., there will be no errors in the cl-type file). That is, every test case you receive can be compiled successfully. Your program must emit either Cool Assembly Language (file.cl-asm) or x86-64 Assembly Language (file.s). Your program will consist of a number of source files.
  2. A plain ASCII text file called readme.txt describing your design decisions and choice of test cases. See the grading rubric. A few paragraphs should suffice.
  3. Test cases test1.cl, test2.cl, test3.cl, and test4.cl. These test cases should exercise compiler and run-time error corner cases.
  4. If you are in a team, you must include a file called team.txt that contains the UMich Uniqid's of all team members on separate lines.

Error Reporting

You are guaranteed that the file.cl-type input file will be correctly formed and will correspond to a well-typed Cool program. Thus, there will not be any direct static errors in the input. Those were all caught by the semantic analyzer earlier.

However, you must generate file.cl-asm (or file.s) so that it checks for and reports run-time errors. When your file.{cl-asm,s} program detects an error, it should use the Syscall IO.out_string and Syscall exit assembly instructions to cause an error string to be printed to the screen.

To report an error, write the string ERROR: line_number: Exception: message (for example, using Syscall IO.out_string) and terminate the program with Syscall exit. You may generate your file.{cl-asm,s} so that it writes whatever you want in the message, but it should be fairly indicative. Example erroneous input: 

class Main inherits IO {
  my_void_io : IO ; -- no initializer =\> void value
  main() : Object {
    my_void_io.out_string("Hello, world.\n")
  } ;
} ;

For such an input, you must generate a well-formed file.{cl-asm,s} assmebly language file. However, when that file is executed (either in a Cool CPU Simulator or on an x86-64 machine), it will produce output such as: 

ERROR: 4: Exception: dispatch on void

To put this another way, rather than actually checking for errors directly, you must generate assembly code that will later check for and report errors.

Line Number Error Reporting

The typing rules do not directly specify the line numbers on which errors are to be reported. As of v1.25, the Cool reference compiler uses these guidelines:

Note that the reference interpreter uses different line numbers in some cases; you must match the reference compiler.

Video Guides

NOTE: Some of these video guides are from a previous offering of a similar course at the University of Virginia. The assignment for this semester has changed slightly (and, in this case, was named differently). While they are still relevant, you are responsible for completing the assignment according to this course's grading rubric.

A Video Guide is provided to help you get started on this assignment on your own. The Video Guides are a walkthrough in which the instructor manually completes and narrates, in real time, the first part of this assignment. It includes coding, testing and debugging elements.

If you are still stuck, you can post on the forum, approach the TAs, or approach the professor. The use of online instructional content outside of class weakly approximates a flipped classroom model. Click on a video guide to begin, at which point you can watch it fullscreen or via Youtube if desired.

Code Generation
Debugging
PA5 Overview
Python - VTables, Constructors
Python - Code generation
Entry point, debugging

What To Turn In For PA5

You must turn in a zip file containing these files:

  1. readme.txt — your README file
  2. source_files — including
    • main.rb or
    • main.py or
    • main.js or
    • main.hs or
    • main.ml
  3. 4 test cases

Your zip file may also contain:

Submit the file to the course autograding website.

Autograding

We will use scripts to run your program on various testcases. The testcases will come from the test1.cl-type and test2.cl-type files you and your classsmates submit as well as held-out testcases used only for grading. Your programs cannot use any special libraries (aside from the OCaml unix and str libraries, which are not necessary for this assignment). We will use (loosely) the following commands to execute them:

You may thus have as many source files as you like (generally, students supply 4-5 source files, including separate handling of the deserialization of input, traversing the AST, generating relevant IR, and generating final assembly)

In each case we will then compare your output to the correct answer. If your compiler changes the meaning of the program, you will get 0 points for that testcase. Otherwise, you get 1 point for that test case.

You do not need to create any temporary files. We will run your submission in a special "jail" or "sandbox".

Grading Rubric