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. You will work in a team of two people for this assignment.
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 P4) 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.
You must create four artifacts:
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 P4). Your program must execute (i.e., interpret)
the Cool program described by that input.
Your main program should be a module named interpreter,
which compiles to interpreter.exe
. Thus,
the following two commands should produce the same output:
interpreter.exe file.cl-type
cool file.cl
.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.
readme.txt
describing your design decisions and choice of test cases. See
the grading rubric. A few paragraphs should suffice.
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.
test-1.cl
and test-1.cl-input
through test-N.cl
and test-N.cl-input
).
The testcases should exercise interpreter and run-time error corner cases.
P5c is a checkpoint for the larger interpreter that includes both test suite development and construction of a subset of the interpreter.
In this project, we introduce a form of test-driven development or mutation testing into our software development process and require you to construct a high-quality test suite.
The goal is to leave you with a high-quality test suite of Cool programs that you can use to evaluate your own P5 Interpreter. Writing an interpreter requires you to consider many corner cases 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 P5 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), this checkpoint provides a structured means to help you get started with the constuction of a rich test suite.
SLUGS contains 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 P5 submission.
For P5c, a test consists of a pair of text files: one syntactically
valid Cool program
and one input file
containing
the input for the program as it would be typed on the command line.
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 P5. Thus, if you make a rich test suite for P5t that reveals many defects, you can use it on your own P5 submission to reveal and fix your own bugs!
SLUGS will tell you the correct output for test cases you submit that reveal bugs in your own implementation of P5. This is the same information you can determine by comparing your output with that of the reference compiler.
Tests should include a Cool program
named test-n-XXX.cl
with a corresponding input file
named test-n-XXX.cl-input
(XXX can be anything, but must be the same for both files) where 1 ≤ n ≤ 99.
For clarity, each cool program will only be run with the input file
that the exact same number n
. If a particular test does
not require user input, provide a blank input file.
Your test files may contain no more than 2048 characters in any one file (including comments and whitspace). The cool file should pass type checking. You may submit up to 99 tests (though it is possible to get full credit with fewer). Note that the tests the autograder runs on your solution are NOT limited to 2048 characters in a file, so your solution should not impose any size limits (as long as sufficient system memory is available).
P5c is also a checkpoint for P5. The Interpreter is a large and complicated assignment; we do not want you to fall behind.
For the P5c checkpoint you will only be tested on
something akin to hello-world.cl
. If you can interpret
that, you pass the checkpoint. While it is possible to take shortcuts
on this checkpoint, this will ultimately be a disadvantage.
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.
Your final submission for P5 should be capable of interpreting all
valid cl-type
files. This includes providing
appropriate error messages for dynamic runtime check violations.
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:
class Main inherits IO {
my_void_io : IO ; -- no initializer => void value
main() : Object {
my_void_io.out_string("Hello, world.\n")
} ;
} ;
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.
You will have to handle all of the internal functions (e.g.,
IO.out_string
). These are function built into cool itself
(i.e., there is no implementation specified in the input program).
These are represented by internal
expressions in the
cl-type
file. These are an additional expression "kind"
that you did not have to handle for P3, but are produces by the type
checker.
You can do basic testing as follows:
cool --type file.cl
cool file.cl > reference-output
my-interp file.cl-type > my-output
diff my-output reference-output
Note that diff
is a command line tool for comparing
the contents of two files. You may also find Diffchecker
to be helpful as well as VSCode's built-in comparison.
This assignment is complicated (hence the checkpoint and long duration). The full interpreter took your instructor approximately nine hours to implement and debug. The resulting code was around 1000 lines. You should expect to spend some multiple of this on your own implementation (most students report that it takes 2–10 times longer). Therfore, you should try to work a little bit every day on this assignment.
The following modules in Reason are particularly helpful for this project:
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:
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:
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.
You will likely find it necessary to use some find/replace operations
based on regular expressions in your implementation. Reason's
Str
module is useful for this, but it is not included by default when compiling.
You can add a directive to your dune
file to include this
module during compilation:
(executable
(name interpreter)
(promote (until-clean))
(libraries "str")
)
You must turn in a tar.gz
file containing these files:
references.txt
: your file of citations
team.txt
: a file listing only the SLU
email IDs of both team members (see below).
interpreter.re
139ba267302516bcc9e9e23141d94ac04cd56a91
in a comment
dune
Makefile
.cl
and
corresponding .cl-input
files: Cool interpreter
testcases.
test-1-foo.cl
you may also submit test-1-foo.cl-input
, and that test
will be run with something akin to the following command.
cool --type test-1-foo.cl
cool test-1-foo.cl-type < test-1-foo.cl-input > output.txt
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.
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).
You must turn in a tar.gz
file containing these files:
readme.txt
: your README file
references.txt
: your file of citations
team.txt
: a file listing only the SLU
email IDs of both team members (see below).
interpreter.re
139ba267302516bcc9e9e23141d94ac04cd56a91
in a comment
dune
Makefile
The following directory layout is recommended for your tar.gz
file. This is the default layout generated by make
(see below) should
you following the same project structure as other projects from class.
fullsubmit.tar.gz
-- dune
-- interpreter.re
-- Makefile
-- readme.txt
-- references.txt
-- team.txt
(for P5C):
-- test-N[-xxx].cl
-- test-N[-xxx].cl-input
-- ...
make
to build this project
Note, you can use the CS-364 Makefile
to generate a
submission archive:
make fullsubmit
The Makefile
is available here.
Be sure to update the IDENTIFIER
and EXECUTABLE
variables appropriately.
If you would like to submit just your interpreter to SLUGS without test inputs (e.g., to not waste submits if your code fails to compile), you can generate a submission archive using:
make partial submit
You must 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 instructor will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment.
both team members should
submit to SLUGS. The submission should include the file
team.txt
, a two-line, two-word flat ASCII text file that
contains the email ID of both teammates. Don't include the @stlawu.edu bit. Example: If sjtime10
and
kaangs10
are working together, both kaangs10
and sjtime10
would submit
fullsubmit.tar.gz
with a team.txt
file that
contains:
kaangs10
sjtime10
Then, sjtime10
and kaangs10
will both receive the same
grade for that submission.
This seems minor, but in the past students have failed to correctly format this file. Thus you now get a point on this assignment for either formatting this file correctly.
P5 Grading (out of 100 points):
team.txt
file