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.

Goal

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.

Specification

You must create four artifacts:

  1. 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.

  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 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: Creating PA4 Tests

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: Checkpoint

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:

Thus you should build the class hierarchy and check everything related to that. For example:

Note

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.

PA4

Your final submission for PA4 will perform all of the same checks from PA4c, and it will also check expressions (method bodies).

Error Reporting

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.

Example erroneous input:

class Main inherits IO { 
 main() : Object { 
   out_string("Hello, world.\n" + 16777216) -- adding string + int !? 
 } ; 
} ;
Example error report output:
ERROR: 3: Type-Check: arithmetic on String Int instead of Ints

Line Number Error Reporting

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):

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.

The .cl-type File Format

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:

  1. The class map.
  2. The implementation map.
  3. The parent map.
  4. The annotated AST.

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.

Example input:

class Main inherits IO {
  my_attribute : Int <- 5 ; 
  main() : Object { 
    out_string("Hello, world.\n") 
  } ;
} ;	
Example .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 Int

2 -- 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
Example .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 defined

4 -- 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 ...

Example .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.)

Commentary

You can do basic testing as follows:

Example testing
$ cool --parse file.cl
$ cool --out reference --type file.cl
$ my-checker file.cl-ast
$ diff -b -B -E -w file.cl-type reference.cl-type

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.

Getting Started with JavaScript

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.

Getting Started Video

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.

Symbol Tables

Remember how OCaml has a nice Hashtbl module that is useful for symbol tables? Here is a limited version written in JavaScript:

Hint

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.

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 PA4t

You must turn in a zip file containing these files:

Your zip file may also contain:

What to Submit For PA4c

You must turn in a zip file containing these files:

Your zip file may also contain:

What to Submit For PA4

You must turn in a zip file containing these files:

Your zip file may also contain:

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 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).

Legacy Grading

The legacy server has an older version of NodeJS installed. Be careful of language features you choose to use!

Grading Rubric

PA4 Grading (out of 100 points):