Extra Credit Programming Assignment 5xc: Type Reconsruction

Points: 100

Files

Some Simple Test Inputs

Overview

Preparation   Create a programs/5xc directory within your comp411 directory. All of your files for this assignment should be stored in the programs/5xc subdirectory.

Teamwork   You are encouraged to do this assignment and all other programming assignments using pair programming. When you submit your assignment, indicate the composition of your team (names, student ids, and email addresses) in your README file.

Task   Your task is to write a type checker for essentially the same language as Assignment 5, without at type specified for the input program and with no type qualifiers on the binding occurrences of variables nor on {\tt empty} constants. You type reconstruction engine will infer the most general type for specified expression in the specified environment, which will be a type scheme if the type of the program is polymorphic. Of course, every constant that appears in the expression has a specific type either simple or polymorphic (a type scheme]. Moreover, in the world of structural typing, {\em there are no subtypes} so the argument types in every application of a program operation must exactly match the type of the inputs to the operation. These constraints can all be expressed by equations which type reconstruction solves using the unification algorithm.

We suggest that you use your solution to Assignment 5 as a starting point The most important change that you must make to this code are (i) generating the set of equations corresponding to the constraints imposed by applications; and (ii) solving this set of constraints using unification. This process is used in every implementation of every language in the ML famliy, so it is discussed in great detail on the internet.

Testing   As usual, you are expected to write unit tests for all of your non-trivial methods or functions and submit your test code as part of your program. For more information, refer back to Assignment 1.

The extra credit part of this assignment is a complete extra assignment with the identifying project name 5xc. Solutions must be submitted using the project name 5xc rather than 5. As preparation for the extra credit part, create a programs/5xc directory within your comp411 directory. The extra credit assignment is not a substitute for the regular assignment!

The input language to the extra credit assignment is the same as for Assignment 4 except for the elimination of the primitives list?, number?, function?, ref?, and arity (which were also eliminated in Assignment 5). Note that the other changes in input syntax for Assignment 5 do not apply to the extra credit assignment.

The public interface supported by the interpreter is the same as for Assignment 5 except for the fact that input programs do not have type annotations.

Your assignment is to implement a type checker that performs Hindley-Milner type inference using unification. The types for variables are determined by this inference process rather than program annotations. Type errors may be manifested as unification failures.

Note that some programs that are not typeable in Typed Jam (5) are typeable in Implicitly Polymorphic Jam (5xc).

Testing and Submitting Your Program

The directory tests contains the test file Assign4xcTest.java with some very simple unit tests for your program. These tests are far from comprehensive.

Your program directory should only contain the files that you want to submit. We will subsequently provide you with test scripts similar to the ones we provided for Assignment 3. Running these scripts will alert you to any problems with your directory configuration. We will also place a few addtional test programs in the directory tests.

Make sure that your program passes the sample unit tests and works with our grading script before submitting it. Create a README file in the your directory program/4xc that

• contains nothing but the user names of the team members in lines 1 and 2 and a blank line as line 3,
• outlines the organization of your program, and
• specifies what testing process you used to confirm the correctness of your program.

We have provided a sample README for your reference. Make sure that your README file is structured correctly:

1. It has to be named README (all upper case, no .txt or anything)
2. It has to be in the assignment's "root directory", e.g. ~/comp411/programs/4xc
3. The first two lines should only contain your usernames and nothing else. The third line should be blank (if you're working alone, leave lines 2 and 3 blank), e.g.:
   

   mgricken dmp This is where the readme text starts.

Any test data files for your program must be stored in the programs/4xc directory. Please make sure you submit your unit tests! You cannot get credit for parts not submitted!

Each procedure or method in your program should include a short comment stating precisely what it does. For routines that parse a particular form of program phrase, give grammar rules describing that form.

Please make sure to remove or disable all debug output before submitting. Excessive use of print statements considerably slows your interpreter and thus testing your project down. If your interpreter generates a timeout error because debug output slows it down, you may not get credit for the test cases that took too long.

To confirm that your program supports the API that will be tested by the grading suite, we suggest that you either test your program using {\tt Assign5Test.java} or submit your program to our test engine (formerly oar program submission engine as well) by (i) placing all of the files that you plan to submit is located in the directory comp411/programs/5xc on CLE@R and (ii) typing the command

~comp411/bin/turnin411 5xc

from within your comp411/programs directory.

The command will inform you whether or not your submission passes the test in Assign5xcest.java confirming that your support the correct API and works for some very simple inputs. To submit your program, convert the same file tree to a zip flie and upload as your solution to Assignment 5xc on Canvas.