Programming Assignment 4 - The Semantic Analyzer

Project Overview

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

You may do this assignment in OCaml, Python, JavaScript, Haskell or Ruby. You must use be graded on a different language for each of PA2 - PA5.

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. However, you must still satisfy the language breadth requirement (i.e., you must be graded on a different language for each of PA2 - PA5).

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.

You will also write additional code to unserialize 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.

The Specification

You must create three 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, invoking checker file.cl-ast should yield the same output as cool --type file.cl. Your program will consist of a number of OCaml files, a number of Python 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 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.

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.

That's it for the output specification. Here's some 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 interger 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 o 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 map 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 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.

Commentary

You can do basic testing as follows: When you attempt to submit your PA4c or PA4 assignment, the server will automatically run your program on some held-out test cases and report the results.

You should implement all of the typing rules in the 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.

Because PA4 involves spitting out parts of the AST in a similar format to PA3, there is a slight synergy to doing PA3 and PA4 in the same language. It's not major, though, and the vast majority of your effort in PA4 will be centered on type checking (rather than output formatting).

What To Turn In For PA4t

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!

For PA4t you should turn in (electronically):

Your zip file may also contain: 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).

What To Turn In For PA4c

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:

You must turn in a zip file containing these files:

  1. source_files -- your implementation, including
Your zip file may also contain: Submit the file electronically (as with PA1-PA3).

What To Turn In For PA4

You must turn in a zip file containing these files:
  1. readme.txt -- your README file
  2. good.cl -- a positive testcase
  3. bad1.cl -- a negative testcase
  4. bad2.cl -- a negative testcase
  5. bad3.cl -- a negative testcase
  6. source_files -- including
Your zip file may also contain: Submit the file as you did for PA1.

Working In Pairs

You may complete this project 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 flat ASCII text file that contains exactly and only the email address of your teammate. Don't include the @virgnia.edu bit. Example: If ph4u and wrw6y are working together, ph4u would submit ph4u-pa4.zip with a team.txt file that contains the word wrw6y. Then ph4u and wrw6y will both receive the same grade for that submission.

Autograding

We will use scripts to run your program on various testcases. The testcases will come from the good.cl and bad.cl files you and your classsmates submit as well as held-out testcases used only for grading. Your programs cannot use any special libraries (aside from the OCaml unix and str libraries, which are not necessary for this assignment). We will use (loosely) the following commands to execute them: You may thus have as many source files as you like (although two or three should suffice) -- they will be passed to your language compiler in alphabetical order (if it matters).

In each case we will then compare your output to the correct answer:

If your answer is not the same as the reference answer you get 0 points for that testcase. Otherwise you get 1 point for that testcase.

For error messages and negative testcases we will compare your output but not the particular error message. Basically, your semantic analyzer need only correctly identify that there is an error on line X. You do not have to faithfully duplicate our English error messages. Many people choose to (because it makes testing easier) -- but it's not required.

We will perform the autograding on some unspecified test system. It is likely to be Solaris/UltraSPARC, Cygwin/x86 or Linux/x86. However, your submissions must officialy be platform-independent (not that hard with a scripting language). You cannot depend on running on any particular platform.

There is more to your grade than autograder results. See the Programming Assignment page for a point breakdown.

Your submission may not create any temporary files. Your submission may not read or write any files beyond its input and output. We may test your submission in a special "jail" or "sandbox".