λCS162 Programming languages piazza

Description

By the time you have completed this work, you should be able to:

• Write well-typed code in Poly-Typed SimpleScala
• Write tests for a typechecker for Poly-Typed SimpleScala
• Read and understand the rules in Handout 4, implementing a typechecker for Poly-Typed SimpleScala in the process

Download the template code below. There are two files you need to modify in the template code:

1. lists.simplescala
2. typechecker.scala

In lists.simplescala, you will need to implement a number of list operations in Poly-Typed SimpleScala. The biggest change from Simply-Typed SimpleScala (for which you wrote list operations in Assignment 3) is that Poly-Typed SimpleScala contains generics and parametric polymorphism. In other words, type variables are now used, and this has been fully exploited in the provided template code. The code you write must be well-typed according to Poly-Typed SimpleScala, or else the interpreter will not be run on it. lists.simplescala contains more relevant information.

In typechecker.scala, you will need to implement the typing rules for Poly-Typed SimpleScala, which are defined in Handout 4. You will also need to define the helpers related to type replacement. Altogether, all the code you write should be restricted to the following methods, which all currently have an implementation of ???:

• typeReplace
• typeReplaceHelper
• typeReplaceHelperList
• typeof

The provided test suite for typechecker.scala is very weak. In particular, it lacks almost any tests for ill-typed programs. To that end, you will need to write at least 10 tests for full credit. More details are in the next section.

Running, Compiling, and Testing

We have provided two .jar files containing reference solution components:

• interpreter.jar: Contains a reference interpreter, and only the interpreter
• reference.jar: Contains a complete reference solution, including both the intepreter and the typechecker

Neither of these .jar files contain any actual code, only compiled .class files. There are multiple reasons why these files have been provided:

1. This assignment concerns only the typechecker, so a (hopefully!) correct interpreter has been provided for you
2. You can play around with Poly-Typed SimpleScala directly, without having to first implement you own typechecker
3. You can test your lists.simplescala code independently from your own SimpleScala typechecker. This makes it so you can debug your lists.simplescala implementation separately from your SimpleScala typechecker.

The provided reference solution includes a REPL, which can be run like so:

scala -cp reference.jar simplescala.polytyped.Repl

From within the Repl, you can load a file full of defs like so (assuming lists.simplescala holds the defs):

:load lists.simplescala

You can declare vals and evaluate expressions in the SimpleScala REPL, just as you can with Scala's REPL. The one limitation is that inputs to the SimpleScala REPL must start and end on the same line; you cannot spread a definition across multiple lines, for instance.

We recommend getting lists.simplescala working before working on typechecker.scala. This will allow you to familiarize yourself with Poly-Typed SimpleScala before writing a typechecker for it. This way, you will have a better intuitive notion of how execution should work before you need to actually implement how execution works.

The test suite for lists.simplescala can be run like so:

scala -cp reference.jar simplescala.polytyped.MultiTester lists.simplescala list_tests

Note that this line above runs the test suite with the reference solution, which you can assume to be correct.

Once you have lists.simplescala working, move on to preparing to test the typechecker you will write. The provided typechecker tests are very shallow, and they lack almost any tests checking for ill-typed programs. To this end, you must write some tests which check for different kinds of ill-typed programs. In order to do this, you will need to run the test suite on the reference solution's typechecker, like so:

scala -cp reference.jar simplescala.polytyped.SingleTester tests

The last line of the output reads as such:

NUM UNIQUE ILL-TYPED IN TYPEOF OR TYPE REPLACEMENT: 0

This records the number of unique type errors which occurred in the reference solution's typeof or type replacement methods, which collectively contain the actual typechecker implementation. Your goal is to get this number to at least 10 by adding tests which should be ill-typed to the tests directory. This means you will have to write 10 tests which all are ill-typed, but in unique ways. The file tests/access_illtyped.simplescala contains an ill-typed program, which serves as an example for the sort of tests you will need to write (where ;;; separates the program from the expected result, namely ILLTYPED in this circumstance). Note that tests/access_illtyped.simplescala does not count towards the 10 unique ways to get ill-typed programs, because the type error it exposes is not contained in the reference solution's typeof or type replacement methods.

You may find it easier to write the tests concurrently with your own typechecker implementation in typechecker.scala. You can compile typechecker.scala like so:

scalac -cp interpreter.jar:. *.scala

You can run the test suite for typechecker.scala like so:

scala -cp interpreter.jar:. simplescala.polytyped.SingleTester tests

Once that test suite is passing (which should include any of your own tests written in the tests directory), you can do more in-depth testing by running the test suite for lists.simplescala directly on your own typechecker, like so:

scala -cp interpreter.jar:. simplescala.polytyped.MultiTester lists.simplescala list_tests

Be advised that none of the provided test suites are particularly good for testing your code in typechecker.scala. You are strongly encouraged to write your own tests, even beyond the tests we are requiring you to write for full credit. These tests can be added to the tests and list_tests directories, corresponding to tests for the typechecker and tests for the lists.simplescala implementation, respectively.

Grading

A breakdown of the grade follows (out of 100 points):

• +20Implementing the missing routines in lists.simplescala
• +10Writing tests that expose ten unique ways to get ill-typed in our reference typechecker
• +70Implementing the typing rules in typechecker.scala

Downloads

Deliverables

You must use turnin to turn in all of your code. The command below will work for this purpose:

turnin assign5@cs162 lists.simplescala typechecker.scala tests

Note

As a reminder: with typechecker.scala, you may not use any mutable state. This is to encourage you to think in a functional way, rather than to write Java/Python with a new syntax.