Project Overview

You may do this assignment in OCaml, Haskell, JavaScript, Python or Ruby. You must use a different language for each of PA2 - PA5.

You may work in a team of two 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 teammate. The course staff are not responsible for finding you a willing teammate. However, you must still satisfy the language breadth requirement (i.e., you must be graded on a different language for each of PA2 - PA5).

Goal

You will also write additional code to unserialize the class and implementation maps produced by the semantic analyzer and the parse tree produced by the parser.

The Specification

1. A program that takes a single command-line argument (e.g., file.cl-type). That argument will be an ASCII text Cool class map, implementation map, and AST file (as described in PA4). Your program must execute (i.e., interpret) the Cool program described by that input. If your program is called interp, invoking interp file.cl-type should yield the same output as cool file.cl. Your program will consist of a number of OCaml files, a number of Python files, or a number of Ruby files.
   • You will only be given .cl-type files from programs that pass the semantic analysis phase of the reference interpreter. You are not responsible for correctly handling (1+"hello") programs.
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. Testcases test1.cl, test2.cl, test3.cl and test4.cl. The testcases should exercise interpreter and run-time error corner cases.

Error Reporting

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

Example error report output:

ERROR: 4: Exception: dispatch on void

Commentary

You can do basic testing as follows:

• $ cool --type file.cl  
  $ cool file.cl >& reference-output
  $ my-interp file.cl-ast >& my-output
  $ diff my-output reference-output
  

Note that this time, whitespace and newlines matter for normal output. This is because you are specifically being asked to implement IO and substring functions.

You should implement all of the operational semantics rules in the Reference Manual. You will also have to implement all of the built-in functions on the five Basic Classes.

What To Turn In For PA5t

The goal of PA5t is to leave you with a high-quality test suite of Cool programs that you can use to evaluate your own PA5 Interpreter. Writing an interpreter requires you to consider many corner cases (perhaps even more than in PA4!) when reading the formal operational semantics rules in the Cool Reference Manual. While you you can check for correct "positive" behavior by comparing your interpreter's output to the reference interpreters's output on the usual "good" Cool programs, it is comparatively harder to check for "corner case" behavior.

If you fail to construct a rich test suite of semantically-valid tricky programs you will face a frustrating series of "you fail held-out negative test x" reports for PA5 proper, which can turn into unproductive guessing games. Because students often report that this is frustrating (even though it is, shall we say, infinitely more realistic than making all of the post-deployment tests visible in advance), the PA5t preliminary testing exercise provides a structured means to help you get started with the constuction of a rich test suite.

The course staff have produced 22 variants of the reference compiler, each with a secret intentionally-introduced defect related to Interpretation. A high-quality test suite is one that reveals each introduced defect by showing a difference between the behavior of the true reference compiler and the corresponding buggy verison. You desire a high-quality test suite to help you gain confidence in your own PA5 submission.

For PA5t, you must produce syntactically valid Cool programs (test cases). There are 22 separate held-out seeded interpreter bugs waiting on the grading server. For each bug, if one of your tests causes the reference and the buggy version to produce difference output (that is different stdout/stderr), you win: that test has revealed that bug. For full credit your tests must reveal at least 17 of the 22 unknown defects.

The secret defects that we have injected into the reference compiler correspond to common defects made by students in PA5. Thus, if you make a rich test suite for PA5t that reveals many defects, you can use it on your own PA5 submission to reveal and fix your own bugs!

For PA5t you should turn in (electronically):

• A zip file containing a set of .cl (and possibly corresponding .cl-input) files: Cool interpreter testcases.
  • Each testcase you submit must be semantically valid (i.e., must pass cool --type).
  • Each testcase you submit may have a corresponding input file. For example, if you submit wes.cl you may also submit wes.cl-input, and that test will be run with a command like cool wes.cl-type < wes.cl-input >& output.txt.
  • Each testcase you submit must be at most 2048 characters (i.e., wc -c yourtest.cl says 2048 or less). You want each of your testcases to be meaningful so that it helps you narrow down a bug later (cf. Delta Debugging).
    • Q: Ha ha! I will get around this edict by removing comments and compressing whitespace and variable names.
    • A: Remember, the point of PA5t is not to make me happy, but to provide you with a high quality test suite. You're only hurting yourself later by making low-quality tests now. When your interpreter fails one of your own tests later you'll end up shrinking the test down as part of debugging, so you're not actually saving yourself any time.
  • Each testcase you submit may run to completion or it may trigger some run-time error. None of the seeded defects you are trying to uncover are intentionally related to infinite loops. Do not spam our server.
    • Clarification: Similarly, none of the errors are related to large memory allocations or exhausting the heap at run-time (e.g., by making arbitrarily large strings, etc.).
  • No testcase should be named bug... or ref... because the testing server uses those prefices internally. If you submit a test case with such a name it will be ignored. (Limited course resources can either be spent making better lectures, grading your assignments, etc., or ironing out wrinkles such as these from grading scripts. We have chosen to focus on pedagogy.)

• team.txt -- an optional file listing your other team member (see below -- if you are not working in a team, do not include this file)

What To Turn In For PA5c

For the PA5c checkpoint you will only be tested on something akin to hello-world.cl. If you can interpret that, you pass the checkpoint. (You can "cheat" the checkpoint by hard-coding output for that single test case, but you're ultimately only hurting yourself!) The goal of the checkpoint is not to do the minimal amount of work possible for this program, but instead to do the greatest amount possible now so that you have plenty of time for the rest of the features later.

You must turn in a zip file containing these files:

1. source_files -- your implementation, including
   • main.rb or
   • main.py or
   • main.js or
   • main.hs or
   • main.ml

• team.txt -- an optional file listing your other team member (see below -- if you are not working in a team, do not include this file)

What To Turn In For PA5

1. readme.txt -- your README file
2. test1.cl -- a testcase
3. test2.cl -- a testcase
4. test3.cl -- a testcase
5. test4.cl -- a testcase
6. source_files -- your implementation, including
   • main.rb or
   • main.py or
   • main.js or
   • main.hs or
   • main.ml

• team.txt -- an optional file listing your other team member (see below -- if you are not working in a team, do not include this file)

Working In Pairs

Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each programming assignment; each member receives the same grade for the assignment. If a partnership is not going well, the teaching assistants will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment.

If you are working in a team, exactly one team member should submit a PA5 zipfile. That submission should include the file team.txt, a one-line flat ASCII text file that contains exactly and only the email address of your teammate. Don't include the @virgnia.edu bit. Example: If ph4u and wrw6y are working together, ph4u would submit ph4u-pa5.zip with a team.txt file that contains the word wrw6y. Then ph4u and wrw6y will both receive the same grade for that submission.

Autograding

In each case we will then compare your output to the correct answer:

• diff testcase.out correct-answer.out

For error messages and negative testcases we will compare your output but not the particular error message. Basically, your interpreter need only correctly identify that there is an error on line X. You do not have to faithfully duplicate our English error messages. Many people choose to (because it makes testing easier) -- but it's not required.

We will perform the autograding on some unspecified test system. It is likely to be Solaris/UltraSPARC, Cygwin/x86 or Linux/x86. However, your submissions must officialy be platform-independent (not that hard with a scripting language). You cannot depend on running on any particular platform.

There is more to your grade than autograder results. See the Programming Assignment page for a point breakdown.

Language Hints

I was performing the computation 4 / -59. In a very strange turn of events, this computation returns 0 in a simple C program (and, apparently, in OCaml), but -1 in Python. Bwah?

Python's division truncation works differently from C's. This is more than a little annoying, and certainly a "gotcha".

I seem to have solved the problem by adding

from __future__ import division

to the top of my file, which makes the / operator always return a floating-point result, then casting the result of a/b to an integer via the int() constructor.