Due Date

Due 11:59:59pm Tuesday, February 14

Description

The goal of this assignment is to better understand how typechecking works. To this end, you will implement a typechecker for the full Simply-Typed FUN (SimpleFUN), according to the rules in handout 4. Download the code template provided here. The template consists of 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 Perl script which will automatically run some provided tests. The script assumes your code compiled correctly.

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, where list.fun is a valid simply-typed FUN program: 

scalac -cp scala-parser-combinators.jar *.scala
scala -cp scala-parser-combinators.jar:. Checker list.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 “ill-typed”, 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.

Deliverables

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

turnin assign3@cs162 checker.scala