Due Date

Due 11:59:59pm Wednesday, March 8

Description

The goal of this assignment is to better understand how programming language semantics work. To this end, you will implement a small-step interpreter for the full Simply-Typed FUN (simpleFUN), according to the rules in handout 7. 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. interpreter.scala: The actual interpreter definition, which you will define.
  4. runTests.sh: A bash script which will automatically run some provided tests. The script assumes your code compiled correctly.

For this assignment, you should modify only interpreter.scala. In interpreter.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 7.

If you encounter a point in the implementation where you encounter behavior that is not specified in handout 7, you should throw a StuckException to indicate that the interpreter got stuck. For example, a StuckException should ultimately get thrown on the following program, which contains a type error: 

1 + true

To be clear, your code should not perform any sort of typechecking. Our test suite intentionally contains programs which are ill-typed but do not get stuck, so a typechecker will not be very useful in determining the program's correct behavior.

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

You can also compile and run your code using sbt like so, where again, list.fun is a valid, well-typed simply-typed FUN program: 

sbt compile
sbt "run-main Interpreter list.fun"

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

./runTests.sh
Before running the test script, make sure you succesfully compile your code using scalac. Use the script with caution!

For ease of debugging, your code should be as close to the small-step transition 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 transition rules.

Deliverables

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

turnin assign5@cs162 interpreter.scala