MCS-287 Lab 3: Type Checking (Spring 2006)

Due: April 26, 2006

Objective

In this lab, you will start with Tucker and Noonan's static type checker for Jay and build on it in at least two of the four ways described in the four sections that follow after the one devoted to the provided type checker. (I hope to see you achieve more than two of the improvements.) Those sections are not listed in any particular order; you can tackle them as you please.

The provided type checker

I am providing you with a file, StaticTypeCheck.java, which is essentially the same as Tucker and Noonan have on their web site from Appendix B and Chapter 3. I updated it for Java Generics and added a main so that it can be used as follows (once you compile it):

java StaticTypeCheck someInputFile.jay

Assuming the input file can successfully be parsed, a command like that should give you one line of output telling you whether the type checker found any errors. (Be sure to try it on files that are valid and on others that have type errors, redeclarations, undeclared variables, etc.)

My hope is that this will compile correctly and just work when dropped in the directory with your files from the prior lab. However, depending on how creative you were in the prior labs, there is some possibility that you may need to tinker a bit.

Adding break and continue

You can add break and continue statements to Jay. Before worrying about static checking, you'll need to make some small changes to TokenStream.java, ConcreteSyntax.java, and AbstractSyntax.java. Having done this, your main goal is to modify the static checker so that it checks that the two new kinds of statements only appear inside loop bodies. (Remember, however, that they need not be directly inside a loop; they can be inside some other statement that is inside a loop, etc.)

Before you plunge into coding, be sure to stop for a moment and consider what approach to use. I can think of at least four quite plausible designs for the checking of breaks and continues.

Adding float

You can add the float type to Jay. Before worrying about static type checking, you'll need to at least make some small changes to TokenStream.java, ConcreteSyntax.java, and AbstractSyntax.java so as to be able to declare variables with this type. (Adding a new kind of literal would be kind of nice, but is purely optional.) You should change the type checker to reflect the following rules:

Redesigning for better messages and other benefits

Instead of having two methods that operate on Expressions, namely V to check validity and typeOf to find the type of a valid expression, you can centralize all the functionality in typeOf. If presented with a valid Expression, it should return the corresponding type. If presented with an invalid Expression, it should throw an Exception, which should include a message that explains the problem. (For example, the Exception object might include the message "Undeclared variable: x".) You should create a new subclass of Exception for this purpose.

Similarly, rather than having both the typing method for Declarations and also a V method to check their validity, you can combine all the functionality into typing with an explanatory Exception if the Declarations are invalid. (While you are at it, you can also improve the efficiency so that checking requires only Θ(n) operations instead of Θ(n2).)

To complete the redesign, you can replace the V method for Program and for Statement with a check method. The difference is that rather than returning a boolean indication of whether the argument is valid, the check method should be declared with return type void, but with the ability to throw your new type of Exception. If given a valid Program or Statement, it returns normally. If given an invalid one, it throws an Exception that explains what was wrong.

You will also have to make a small change to the main method to reflect the new way of checking a program. Having made all these changes, you should find that the same judgments are made as to whether programs are valid or invalid, but that the invalid ones now result in much more useful diagnostic output.

Using the Visitor pattern or AspectJ

Rather than having a collection of methods that operate on AST nodes with lots of instanceof tests and casts, you can rewrite the static type checking to use the Visitor design pattern. Alternatively, you can use AspectJ to introduce methods into the AST classes. As of this writing, I have not installed AspectJ on the MCS lab machines. That might change, or you could install it on your own machine. Note that if you choose to use the Visitor pattern and also address the goal from the preceding section (having type checking methods throw explanatory Exceptions), you will need to modify the Visitor interface and the various accept methods to show that they can throw an Exception. Doing this well may stretch your knowledge of Java Generics; be sure to ask for help if you need it.

What you should turn in

Please turn in a printout of your final version of StaticTypeCheck.java and (if you modified it) AbstractSyntax.java, as well as any new files that you added. You need not turn in TokenStream.java or ConcreteSyntax.java, even if you modified them.


Course web site: http://www.gustavus.edu/+max/courses/S2006/MCS-287/
Instructor: Max Hailperin <max@gustavus.edu>