Homework 5
Note: the prelude for this exercise is quite long. However, we will point you
to the useful functions in the prelude when relevant, so you shouldn’t try to
read it all at once.
Copyright By PowCoder代写 加微信 powcoder
Note: you must not use references / assignment (“=”) throughout the
entire homework.
A DIY programming language: MiniCAML
In this homework, you will implement a programming language called
MiniCAML, in OCaml. The goal is to explore concepts such as free
variables, substitution, evaluation, type checking, and type inference.
MiniCAML is very similar to the language you have seen in class, and also
it is quite similar to OCaml. Compared to the language described in class,
MiniCAM adds nary function abstraction and application, and recursion.
Compared to OCaml, MiniCAML lacks pattern matching, user-defined
datatypes, exceptions, and modules.
The grammar of MiniCAML is the following.
= int | bool| T1 … Tr > T
Expression .- .. | rec (f:r) > el fun (21: TI,…, 2n: Tn) = e | eer..
If you are not sure how to read this, please refer to the course notes:
chapter 9, section 9.1.
For this assignment, we have extended the syntactic category for
expressions with nary unction abstractions, nary function applications,
and recursion:
Using these inference rules, write tests for and fill in the missing cases of
infer: context
-> tp. The type of a context is defined for you
in the prelude; we also provide the functions extend: context
* tp) -> context and extend _list: context -> (name * tp) list
-> context for extending a given context with one or several type
ascriptions. If you encounter a type error during type inference, you should
raise the exception TypeError with the appropriate value of type
type_error as defined in the prelude. For the missing cases of infer,
you will need to raise the tollowing type errors:
• If the function expression of Apply has type t
an Arrow type, you should raise the exception TypeError
(Apply_non_arrow t’).
• If you encounter a type mismatch (expected something of type t, but
instead found something of type t’ ), vou should raise the exception
TypeError (Type_mismatch t t’). We have defined a helper
function type_mismatch in the prelude for this. Note: be mindful of
the order of arguments to type_mismatch! The first argument
should be the expected type, and the second should be the actual type
encountered.
As before, you should not write tests for error cases, but test them on your
own; and you are only required to write test cases for Rec, Fn, and
Question 5: Unification
We take the first steps towards extending MiniCAML to support full type
inference, like in OCaml. Remember that in OCaml, it isn’t necessary to
write type annotations anywhere: the compiler can figure out the types of
all variables for you based on how you define and use them. The upshot of
adding full type inference to MiniCAML is that we can remove the type
annotations on the Fn and Rec constructors for exp.
The key algorithm we need to implement type inference is unification,
which checks if two types can be made syntactically equal by substituting
types for type variables. For example, if asked to unify a with Int-›Int,
then the solution is simply fo = Int > Intl; if asked to unify a > B
with Int-›Bool, then the solution is {a = Int, B = Bool}. These
solutions are called unifiers, and are representated in the template as an
immutable mapping from variable names to types as up UTVarMap.t
with module UTVarMap = Map.Make (String) defined in the prelude.
To support variables such as o and B in types, we extend the datatype tp
(the new extended type is called up, and we have prefixed all old
constructors with U.so that Int is now UInt. etc.) with the constructor
UTVar of string: we model type variables using variable names as
Unification fails in two situations.
In sum, the unification algorithm for variable a with the type t is the
following.
If a occurs in t, then raise an appropriate exception.
• Otherwise, check whether a substitution is already defined for a.
o If there is already a type
” to substitute in for a, then unify t
• If not, then set t as the type to substitute in for a.
Note that the substitution of a type for a type variable is not propagated
throughout the data structure for the unifier. This has the consequence
that programs using one such unifier have to be context-dependent, as is
the case with the string of utp : utp UTVarMap.t-> utp and
string _of_substitution : up UTVarMap.t -> string functions
defined in the prelude.
Your task is to complete the implementation of the function unify : utp
-> utp -> utp UTVarMap.t which takes two types t1 and t2 and
constructs a unifier such that applying it to t1 and t2 produces
structurally equal types. If the two types are not unifiable, you should raise
the exception UnifError as defined for you in the prelude.
In the template, the cases for the local unify function are given, with a
missing implementation for the arrow type case. It is your task to fill in the
missing case, and to provide the complete implementation of unifyVar
tollowing the algorithm description above.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com