CS 440 HW4
Updated 3/13 to give more specifics about substitution in problem 3 and fix a Markdown conversion error.
In this homework you will be writing a typechecker for the MiniML language, for which you wrote an interpreter on HW3. See the language spec and
Your code for this homework will go in
This assignment is to be completed individually, subject to the academic integrity policy on the course website. Make sure you read and understand these.
At the end of this assignment, we will ask you to list any students you discussed the homework with, as well as any websites or other resources (please list specific URLs when applicable) you referred to.
Important notes about grading
Your submissions will be graded automatically for correctness, as well as checked by hand. Please keep our autograder (and Xincheng, who has to run it) happy:
Recall that unification returns a substitution, which is a list of pairs (?i,τi) meaning "replace ?i with τi". For a substitution σ, we'll write [[σ]]τ to mean "τ with all the replacements in σ". So, for example,
[(?0, int); (?1, string)](?0 -> ?1) = int -> string
(?0, list(?1)); (?1, int)]?0 = int list
The OCaml definition for substitutions is given in
In that definition, ?0 is represented as just the integer 0. We also include a function
Recall the (recursive) unification algorithm from class:
Algorithm: Unify(τ1,τ2) Returns a substitution or an error.
Compile and run your code using:
This will open something similar to the OCaml toplevel, which will let you type declarations and will print out the bindings and types introduced:
You can also use the binary
This will interpret the entire file and print out the type and value of every top-level binding. We've provided some sample files in the
It's also important to make sure that, in addition to allowing well-typed programs, your type checker appropriately rejects programs with type errors. We've provided a few of these in
When you are done with your work, make sure you have compiled your code using
When you're finished, use the following commands to submit:
Please do actually use the commit message "HW4 submit" so we know when you intended to submit your homework and can also differentiate this from when you submitted HW3.
There are no additional files you need to add to the repo, just