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.
You will complete this assignment using JavaScript (NodeJS) and implement the semantic analysis component of an interpreter.
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.
For this assignment you will write a semantic analyzer. Among other things, this involves traversing the abstract syntax tree and the class hierarchy. You will reject all Cool programs that do not comply with the Cool type system.
This assignment is broken into three parts (tests, checkpoint, final submission). First, you will construct a test suite for your semantic analyzer. Next, you will perform a static checks on Cool ASTs to rule out invalid programs. Because this is a rather large task, there is a checkpoint before the final submission. You should work on test suite construction and implementation in parallel.
You must create four artifacts:
A program that takes a single command-line argument (e.g.,
file.cl-ast). That argument will be an ASCII text Cool
abstract syntax tree file (as described in PA3). Your
program must either indicate that there is an error in the input
(e.g., a type error) or emit file.cl-type, a serialized
Cool abstract syntax tree, class map, implementation map, and parent
map. If your program is called checker.js, invoking
nodejs checker.js file.cl-ast should yield the same
output as cool --type file.cl. Your program
will consist of a number of JavaScript files.
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.
good.cl, bad1.cl,
bad2.cl, and bad3.cl. The first should pass
the semantic analysis stage. The remaining three should yield semantic
analysis errors.
PA4t 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 PA4t is to leave you with a high-quality test suite of Cool programs that you can use to evaluate your own PA4 type checker. Writing a type checker requires you to consider many corner cases when reading the formal and informal typing rules in the Cool Reference Manual. While you you can check for correct "positive" behavior by comparing your typechecker's output to the reference compiler's output on existing "good" Cool programs, it is comparatively harder to check for "negative" behavior (i.e., correctly reporting ill-typed Cool programs).
If you fail to construct a rich test suite of syntactically-valid but semantically-invalid programs you will face a frustrating series of "you fail held-out negative test x" reports for PA4 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 PA4t preliminary testing exercise provides a structured means to help you get started with the construction of a rich test suite.
The course staff have produced 20 variants of the reference compiler, each with a secret intentionally-introduced defect related to type-checking. 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 version. You desire a high-quality test suite to help you gain confidence in your own PA4 submission.
For PA4t, you must produce syntactically valid Cool programs (test
cases). There are 20 separate held-out seeded type-checker 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,
either a different .cl-type file or a different error
report), you win: that test has revealed that bug. For full credit your
tests must reveal at least 15 of the 20 unknown defects.
The secret defects that we have injected into the reference compiler correspond to common defects made by students in PA4. Thus, if you make a rich test suite for PA4t that reveals many defects, you can use it on your own PA4 submission to reveal and fix your own bugs!
PA4c is a checkpoint for PA4. The typechecker is a large project (and a large part of your grade), so it behooves you to start it early.
For PA4c you should turn in (electronically) an early version of PA4 that does the following:
.cl-ast file — its format was specifically chosen to make it
easy to read with just some mutually-recursive procedures. It should
take you (much) less than 150 lines to read in the .cl-ast
file. .cl-type if there are
no errors.
--class-map command-line argument to
get the reference compiler to spit out the class map after
typechecking (for comparison).
Thus you should build the class hierarchy and check everything related to that. For example:
Int (etc.). main in class Main. self and SELF_TYPE mistakes in classes
and methods. No exact list of errors is provided for this assignment. Part of your task is to think up all possible checks that do not involve expressions. If you were designing the tools for a new language, you wouldn't know the possible errors in advance; part of your job as the language designer is to consider corner cases of your language's specification. Use your tests from PA4t as a starting point.
Your final submission for PA4 will perform all of the same checks from PA4c, and it will also check expressions (method bodies).
To report an error, write the string
ERROR: line_number: Type-Check: message
to standard output and terminate the program. You may write whatever you want in the message, but it should be fairly indicative.
class Main inherits IO {
main() : Object {
out_string("Hello, world.\n" + 16777216) -- adding string + int !?
} ;
} ;
The typing rules do not directly specify the line numbers on which errors are to be reported. As of v1.11, the Cool reference compiler uses these guidelines (possibly surprising ones are italicized):
main in class
Main: always line 0
self or SELF_TYPE used in wrong place: self
(resp. SELF_TYPE) identifier (resp. type) location
while / if
subexpression(s): location of (enclosing) while or
if expression (not the location of the
conditional expression)
case expression (e.g., lub): location of
case expression
let: location of
let expression (not location of initializer)
Remember that you do not have to match the English prose of the reference compiler's error messages at all. You just have to get the line number right.
Semantic checks are unordered; if a program contains two or more errors, you may indicate whichever you like. You can infer from this that all of our test cases will contain at most one error.
If there are no errors in file.cl-ast your program should
create file.cl-type and serialize the class map,
implementation map, parent map, and annotated AST to it.
The class and implementation maps are described in the Cool Reference Manual.
A .cl-type file consists of four sections:
Simply output the four sections in order, one after the other.
We will now describe exactly what to output for the class and implementation maps. The general idea and notation (one string per line, recursive descent) are the same as in PA3.
class_map \n. no_initializer \n and then the attribute name
\n and then the type name \n. initializer \n and then the
attribute name \n and then the type name \n and then the
initializer expression. implementation_map \n. parent_map \n.Object has no parent).3+x is associated with the type
Int.
This is new to PA4. It should be done for PA4, but not for PA4c.internal \n Class.method \n
Note that you must output information about all classes and methods defined in the program as well as all base classes (and their methods). Do not just print out "classes actually used" or "methods actually called" or something like that. Output all classes and methods — no optimizations or shortcuts!
class Main inherits IO {
my_attribute : Int <- 5 ;
main() : Object {
out_string("Hello, world.\n")
} ;
} ; .cl-type class map output with comments:
class_map 6 -- number of classes Bool -- note: includes predefined base classes 0 IO 0 Int 0 Main 1 -- our Main has 1 attribute initializer my_attribute -- named "my_attribute" Int -- with type Int2 -- initializer expression line number Int -- initializer expression type (see above: this is an expression annotated with a type) -- do not emit these expression type annotations for the PA4c Checkpoint! integer -- initializer expression kind 5 -- which integer constant is it?
Object 0 String 0
.cl-type implementation map output with comments:
implementation_map 6 -- six classes Bool -- first is Bool 3 -- it has three methods abort -- first is abort() 0 -- abort has 0 formal arguments Object -- name of parent class from which Bool inherits abort()0 -- abort's body expression starts on line 0 Object -- abort's body expression has type Object internal -- abort's body is an internal kind of expression (i.e., a system call; see above) Object.abort -- extra detail on abort's body expression
copy -- second of Bool's three methods is copy() 0 -- copy has 0 formal arguments Object -- name of parent class from which Bool inherits copy()0 -- copy's body expression starts on line 0 SELF_TYPE -- copy's body expression has type SELF_TYPE internal -- copy's body is an internal kind of expression (i.e., a system call; see above) Object.copy -- extra detail on copy's body expression
... many lines skipped ...
Main -- another class is Main 8 -- it has 8 methods... many lines skipped ...
main -- one of Main's methods is main() 0 -- main has 0 formal arguments Main -- the name of the class where Main.main() is defined4 -- the body expression of Main.main starts on line 4 SELF_TYPE -- the body expression of Main.main has type SELF_TYPE self_dispatch -- the body of Main.main() is a self_dispatch kind of expression
... many lines skipped ...
.cl-type parent output with comments:
parent_map 5 -- there are five classes with parents (Object is the sixth class) Bool -- Bool's parent ... Object -- ... is Object. IO -- IO's parent ... Object -- ... is Object. Int -- Int's parent ... Object -- ... is Object. Main -- Main's parent ... IO -- ... is IO. String -- String's parent ... Object -- ... is Object.
Writing the code to output a .cl-type text file given an AST may take a bit of time but it should not be difficult; the reference implementation (OCaml) does it in 35 lines and cleaves closely to the structure given above. Reading in the AST is similarly straightforward; our reference implementation (OCaml) does it in 171 lines. (My JavaScript implementation has a similar number of lines for each task.)
You can do basic testing as follows:
You should implement all of the typing rules in the Cool Reference Manual. There are also a number of other rules and corner cases you have to check (e.g., no class can inherit from Int, you cannot redefine a class, you cannot have an attribute named self, etc.). They are sprinkled throughout the manual. Check everything you possibly can.
If you've never used JavaScript in the past, there's no need to worry. You already learned on programming language in this class (Reason), so you can learn another. While JavaScript looks something like Java, you're actually better off thinking about your programs as if you're writing Reason or Python.
Douglas Crockford (who is heavily involved in the development of JavaScript) has many helpful resources on his personal website. I also recommend watching a talk he gave at Google many years ago. Be sure to note these resources in your references.txt if you use them.
One of my favorite things about programming in JavaScript is Chrome's developer tools. You can use them with NodeJS with a couple additional flags on the command line:
$ nodejs --inspect --debug-brk main.js
Not only do the developer tools let you single-step through your program and inspect program state, but there is also an interactive shell available for you to use.
As additional assistance for getting up to speed with JavaScript, I recorded a screen cast in which I begin implementing the parsing functions to read in a Cool AST. The video contains discussion of function scoping, callbacks, higher-order functions, debugging, and JavaScript Objects. The quality of the jokes cannot be guaranteed.
Remember how OCaml has a nice Hashtbl module that is useful for symbol tables? Here is a limited version written in JavaScript:
Hint: because you can find "positive" bugs in your typechecker more
easily (e.g., by running your typechecker on the correct Cool programs
from cool-examples.zip), the PA4t exercise is strongly
biased toward "negative" bugs (i.e., the secret buggy typecheckers
usually fail to report certain semantic errors).
If you are still stuck, you can post on the forum, approach the TAs, or approach the professor.
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.
You must turn in a zip file containing these files:
.cl files: Cool typechecker test cases
cool --parse).
cool --type).
Your zip file may also contain:
team.txt — an optional file listing your other team member's UVA ID You must turn in a zip file containing these files:
main.js Your zip file may also contain:
team.txt — an optional file listing your other team member's UVA ID You must turn in a zip file containing these files:
readme.txt: your README file
references.txt: your file of citations
good.cl: a novel positive testcase
bad1.cl, bad2.cl, and bad3.cl: novel negative testcases
main.js Your zip file may also contain:
team.txt — an optional file listing your other team member's UVA ID 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 PA4 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).
The legacy server has an older version of NodeJS installed. Be careful of language features you choose to use!
PA4 Grading (out of 100 points):
team.txt file
good.cl,
bad1.cl, bad2.cl, and bad3.cl
files