Assignment 4

CS 162 Programming Languages
University of California, Santa Barbara

Due 11:59:59pm Friday, February 13

The goal of this assignment is to implement parametric polymorphism for FUN, according to the rules in handout 5. Once you have a good grasp of the rules, download the code template provided here. The template contains the following key files:

1. syntax.scala: The Scala code implementing the abstract syntax tree for simply-typed FUN, along with a parser.
2. scala-parser-combinators.jar: Scala library code necessary for the aforementioned parser to work.
3. checker.scala: The actual typechecker definition, which you will define.
4. runTests.pl: A script with which you can test your code
5. basic_tests: A directory containing simple tests for basic compliance with the handout.
6. big_tests: A directory containing more complex tests, which test all sorts of interactions between typing rules.

For this assignment, you should modify only checker.scala. In checker.scala, there are a multitude of positions marked with ??? // FILL ME IN, which you must replace with concrete implementations. (Recall that ??? throws an exception at runtime, but at compile time is automatically of whatever type you desire. This will allow you to compile your code incrementally.) Each of the implementations for ??? should model something from handout 3.

For this assignment, you will need to put scala-parser-combinators.jar onto your classpath if you are on one of the CSIL machines. With this in mind, you can compile and run your code like so:

scalac -cp scala-parser-combinators.jar *.scala
scala -cp scala-parser-combinators.jar:. Checker basic_tests/good_call1.fun

For testing your code, you can run the provided runTests.pl script, like so:

./runTests.pl

Before running, make sure your code compiles. Tests which begin with “good” should typecheck, whereas tests which begin with “bad” should not typecheck. The script assumes that ill-typed programs emit the string “Illtyped”, and well-typed programs emit the string “well-typed”. As such, on error conditions the script may print UNKNOWN, or, worse yet, give incorrect results. Use the script with caution!

For ease of debugging, your code should be as close to the typing rules as possible. Code that deviates from the mathematical definition is generally difficult to reason about, since it becomes less clear where bugs are relative to the typing rules.

The vast majority of the rules can be copied over from assignment 3, without any modification. Two notable exceptions are the rules which implement constructors and pattern matching.

You must turnin all files required to compile your code. The command below should suffice:

turnin assign4@cs162 syntax.scala checker.scala