Assignment 3

CS 162 Programming Languages
University of California, Santa Barbara

Due 11:59:59pm Friday, February 6

The goal of this assignment is to better understand how typechecking works. To this end, you will implement a type checker for the full simply-typed FUN, according to the rules in handout 4 (simply-typed FUN). Download the code template provided here. The template consists of the following three 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 which will run your typechecker against a provided test suite.

Additionally, there are a series of files with the extension .fun, which are all test cases that can be run like so (after compiling):

scala Checker list.fun

With the exception of doubleCase.fun and missingCase.fun, all the provided test cases should typecheck.

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

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 list.fun

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.

Be sure to turnin your typechecker. The command to turn it in is below:

turnin assign3@cs162 checker.scala syntax.scala