PA5: The Interpreter (Reason)

PA5t Due: 2017-04-11 at 11:50pm

PA5c Due: 2017-04-14 at 11:50pm

PA5 Due: 2017-05-06 at 11:50pm

Programming assignments 2 through 5 will direct you to design and build an interpreter for Cool. Each assignment will cover one component of the interpreter: lexical analysis, parsing, semantic analysis, and operational semantics. Each assignment will ultimately result in a working interpreter phase which can interface with the other phases.

Programming assignments 2 through 4 involved the constructed of the front-end (lexer, parser) and gatekeeping (semantic analyzer) stages of an interpreter. In this assignment you will write the code that performs the execution and interpretation of valid programs.

This assignment must be completed in Reason (or OCaml for the legacy server).

You may work in a team of two people for this assignment. You do not need to keep the same teammate. The course staff are not responsible for finding you a willing teammate.

Goal

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

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.

Specificaton

You must create four artifacts:

  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.
    • 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. A plain ASCII text file called references.txt providing a citation for each resource you used (excluding class notes, and assigned readings) to complete the assignment. For example, if you found a Stack Overflow answer helpful, provide a link to it. Additionally, provide a brief description of how the resource helped you.
  4. Testcases test1.cl, test2.cl, test3.cl and test4.cl. The testcases should exercise interpreter and run-time error corner cases.

PA5t: Creating PA5 Tests

PA5t is a preliminary testing exercise that introduces a form of test-driven development or mutation testing into our software development process and requires you to construct a high-quality test suite.

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!

PA5c: Checkpoint

PA5c is a checkpoint for PA5. The Interpreter is a large and complicated assignment; we do not want you to fall behind.

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.

PA5

Your final submission for PA5 should be capable of interpreting all valid cl-type files. This includes providing appropriate error messages for dynamic runtime check violations.

Error Reporting

To report an error, write the string

ERROR: line_number: Exception: message

to standard output and terminate the program. You may write whatever you want in the message, but it should be fairly indicative. Example erroneous input:

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")
} ; 
} ;
Example error report output:
ERROR: 4: Exception: dispatch on void

Commentary

To make your life easier, the version of Reason on the grading server has been updated to version 1.13.3. Be sure to upgrade your development environment to match!

You will have to handle all of the internal functions (e.g., IO.out_string) that you first encountered in PA4.

You can do basic testing as follows:

Example testing
$ cool --type file.cl
$ cool file.cl >& reference-output
$ my-interp file.cl-type >& 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.

Hint

While not as painful (hopefully!) as PA4, this is still a non-trivial assignment. The checkpoint took your instructor an entire afternoon of coding (approx. 600 lines of code) to implement. Therfore, you should try to work a little bit every day on this assignment.

Building

The following command is used by the grading server to compile your submissions. You might find it helpful for your own testing:

Example compilation
$ rebuild -tag debug -ocamlc 'ocamlc unix.cma str.cma' -ocamlopt 'ocamlopt unix.cmxa str.cmxa' main.native

It might be reasonable to infer that either Unix or Str will be useful in your code.

Data Structures

OCaml's standard library Map (think dictionary) is particularly useful for representing the environment and store. Note that you can't really use a Map directly, instead, you will use a functor to generate a module with a particular type for the key.

Let's say that you'd like to have a map from integer locations to stored values (sounds like a "store", no?). You can create a LocationMap module using the Map.Make functor:

Creating a LocationMap module: 

type location = int;

module OrderedLocation = {
    type t = location;
    let compare = compare;
};

module LocationMap = Map.Make(OrderedLocation);

Making a Map, which uses strings as keys, is even more direct:

Creating a StringMap module: 

module StringMap = Map.Make(String);

Once you create a Map module, you can use any of these functions. Note that these maps are not mutable; instead a new mapping is returned with each update function.

If you are still stuck, you can post on the forum, approach the TAs, or approach the professor.

Video Guides

Wes Weimer has developed a number of Video Guides that you might find helpful. The Video Guides are walkthroughs in which Wes manually completes and narrates, in real time, the first part of a similar assignment — including a submission to his grading server. They include coding, testing and debugging elements.

These videos are considered an outside resource for completing this assignment. Be sure to note these videos in your references.txt if you use them.

Note: Wes's videos use a different submission site from this class.

What to Submit For PA5t

You must turn in a zip file containing these files:

Your zip file may also contain:

Hint: All of the usual tactics apply (from randomly-generating programs to permuting one symbol in each operational semantics rule to reading the prose descriptions in the CRM and looking for words like "must" to digging through the reference compiler binary).

What to Submit For PA5c

You must turn in a zip file containing these files:

Your zip file may also contain:

What to Submit For PA5

You must turn in a zip file containing these files:

Your zip file may also contain:

Human Study Participation

To give you the most amount of time to participate in the debugging human study, you will have until the due date of PA5 to complete the study. If you complete the study, submit a study.txt file with your PA5 zip. In this file, give your email ID followed by your completion code. If you are working alone, this file should contain only one line. If you are working with a partner and you both complete the study, there should be two lines. Bonus points for completing the study are awarded to individuals, not groups.

Example study.txt file (assuming kaa2nx and mst3k are partners)
kaa2nx: < study completion code 1 >
mst3k: < study completion code 2 >

Working In Pairs

You may complete this assignment in a team of two. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.

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, one-word flat ASCII text file that contains the email ID of your teammate. Don't include the @virgnia.edu bit. Example: If ph4u and kaa2nx are working together, ph4u would submit ph4u-pa2.zip with a team.txt file that contains the word kaa2nx. Then ph4u and kaa2nx will both receive the same grade for that submission.

This seems minor, but in the past we've had students fail to correctly format this one word file. Thus you now get a point on this assignment for either formatting this file correctly (i.e., including only a single word that is equal to your partner's UVA email ID) or not including it (and thus not working in a pair).

Legacy Grading

The legacy server does not have Reason installed. Instead, there is an older version of OCaml. Be careful of language features you choose to use!

Grading Rubric

PA5 Grading (out of 100 points):