PA4 — The Semantic Analyzer

You may complete this assignment in OCaml, Python, JavaScript, Haskell or Ruby.

You may work in a team of up to four 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 teammates. The course staff are not responsible for finding you a willing team.


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.

You will also write additional code to deserialize the AST produced by the parser stage and to serialize the class map, implementation map, parent map, and annotated AST produced by your semantic analysis.


You must create three artifacts:

  1. A program that takes a single command-line argument (e.g., 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, a serialized Cool abstract syntax tree, class map, implementation map, and parent map. If your program is called checker, invoking checker should yield the same output as cool --type Your program will consist of a number of OCaml files, a number of Python files, a number of JavaScript files, a number of Haskell files, or a number of Ruby 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. Testcases,, and The first should pass the semantic analysis stage. The remaining three should yield semantic analysis errors.

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 your program should create 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.

Detailed .cl-type Example

Now that we've formally defined the output specification, we can present a worked example. Here's the example input we will consider:

class Main inherits IO {
  my_attribute : Int <- 5 ;
  main() : Object {
    out_string("Hello, world.\n")
  } ;
} ;

Resulting .cl-type class map output with comments:

.cl-type class map comment
6 number of classes
Bool note: includes predefined base classes
1 our Main has 1 attribute
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?

Resulting .cl-type implementation map output with comments:

.cl-type implementation map comment
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 ...

Finally, the resulting .cl-type parent map output with comments:

.cl-type parent map comment
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 rote code to output a .cl-type text file given an AST may take a bit of time but it should not be difficult; our reference implementation does it in 35 lines and cleaves closely to the structure given above. Reading in the AST is similarly straightforward; our reference implementation does it in 171 lines.


You can do basic testing as follows:

$ cool --parse
$ cool --out reference --type
$ my-checker
$ diff -b -B -E -w

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.

Video Guides

NOTE: Some of these video guides are from a previous offering of a similar course at the University of Virginia. The assignment for this semester has changed slightly. While they are still relevant, you are responsible for completing the assignment according to this course's grading rubric.

A number of Video Guides are provided to help you get started on this assignment on your own. The Video Guides are walkthroughs in which the instructor manually completes and narrates, in real time, the first part of this assignment — including a submission to the grading server. They include coding, testing and debugging elements.

If you are still stuck, you can post on the forum, approach the TAs, or approach the professor. The use of online instructional content outside of class weakly approximates a flipped classroom model. Click on a video guide to begin, at which point you can watch it fullscreen or via Youtube if desired.

PA4c — Checkpoint
PA4 — Expressions
PA4 Primer
PA4 Python Deserialization
PA4 Python Examples

PA4c — Checkpoint

PA4c is a checkpoint for PA4 to encourage you to start 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:

Q: What's the exact list of errors I have to check for in PA4c?

A: No such list is provided! Part of the assignment is thinking up all possible checks that do not involve expressions.

What to Turn In For PA4c

You must turn in a zip file containing these files:

  1. source_files — your implementation, including
    • main.rb or
    • or
    • main.hs or
    • main.js or

Your zip file may also contain:

What to Turn In For PA4

You must turn in a zip file containing these files:

  1. readme.txt — your README file
  2. — a novel positive testcase
  3. — a novel negative testcase
  4. — a novel negative testcase
  5. — a novel negative testcase
  6. source_files — including
    • main.rb or
    • or
    • main.js or
    • main.hs or
Your zip file may also contain:

Grading Rubric

PA4 Grading (out of 100 points):