Description
In this assignment, you will implement an interpreter and type checker for a subset of MiniHaskell, which is itself a subset of of Haskell. You will make changes only to the Eval and
Ty modules.
The code provided to you requires a parser library, Parsec. When using Hugs, you will
probably need to supply the -98 command-line directive in order to run the code. You can
check whether you are able to run the skeleton code simply by loading the Main module and
attempting to run parseEval “tests0.mhs”. This should evaluate to a message indicating
that the evaluation function is not yet implemented.
Note that you are not allowed to modify any of the existing data type definitions unless a
problem states otherwise or explicitly directs you to change a definition. There are, however,
crude show functions for expressions, and you may want to use them at times when debugging
(think about returning a subexpressions as a string in an error message).
Note: All function definitions at top level must have explicit type annotations. Unless
otherwise specified, your solutions may utilize functions from the standard prelude as well as
material from the lecture notes and textbook. You may not use any other materials without
explicit citation.
Problem 1. (30 pts)
In this problem, you will implement an interpreter for expressions without variables or let
bindings. Because the parsed code is not being type checked before being interpreted, errors
may occur during evaluation, so you will need to use Error Val as the return type for the
various evaluation functions. Familiarize yourselves with the Exp data structure in the Exp
module (Exp.hs) that represents the abstract syntax of the language. The Val data structure
found in the Val module (Val.hs) represents evaluated expressions.
(a) In the Eval module, implement the body of the function appOp::Oper -> Val ->
Error Val that takes an operator and a value, and when the operator is defined on
that value, returns the result.
1
If the operator is binary, take advantage of the Partial::Oper -> Val -> Val constructor, which can represent a partially applied built-in function. For example, appOp
might return a value like Partial Plus (N 4) if it must apply the binary operator
Plus to the single value N 4.
If the operator is not defined on that value, the function should return an error. Be
careful with list operators such as Head, as they are not defined on empty lists. When
in doubt, you can use the real Haskell interpreter to determine how this function should
behave.
(b) In the Eval module, implement the body of the appBinOp::Oper -> Val -> Val ->
Error Val function, which takes an operator and two values, and returns the resulting
value if it is defined. Otherwise, it returns an error.
You may assume that Equal is defined only on integers. You are not required to
implement equality on boolean, list, and tuple values, but you may do so for extra
credit as part of your solution to Problem #4 below.
(c) In the Eval module, implement the body of the appVals::Val -> Val -> Error Val
function, which takes a pair of values where the first value is either a unary operator,
a binary operator, or a partially applied binary operator. You should not need to use
any functions other than those you defined in parts (a) and (b).
(d) In the Eval module, implement the body of the ev0::Exp -> Error Val function.
This function should handle all expressions that do not contain let bindings or variables. Thus, it should evaluate all base cases (such as operators, booleans, integers,
tuples, and the empty list) as well as if statements and applications. For all other
cases, ev0 may return an error. In evaluating tuples, you may find it convenient to use
the mapError::(a -> Error b) -> [a] -> Error [b] function, available in the Err
module.
Note: You should not evaluate both branches of an if statement, and this is tested in
the file tests1.mhs.
You should now be able to test the interpreter on some input. When using Hugs, it should
be sufficient to load the Main module, and to run parseEval “tests0.mhs” and parseEval
“tests1.mhs”. You may, of course, write and try evaluating your own test programs.
Problem 2. (30 pts)
In the module Env, you will find an implementation of an environment data structure which
can be used to store the values (and types) of variables. You will use this data structure
to represent evaluation and type checking contexts. You will now implement an interpreter
that can handle variables and let bindings.
(a) Implement the body of the ev::Env Val -> Exp -> Error Val function, which can
handle expressions that contain let bindings and variables. You only need to handle
2
let bindings with a single variable (that is, cases where the list of strings under the
Let constructor has exactly one element). You may extend your code to handle let
bindings with tuples for extra credit as part of your solution to Problem #4 below.
The base cases should be similar to those of ev0, except for the case of a variable. A
variable evaluates to the value with which it is associated in the environment. If it is
not found in the environment, it is not bound, and an error should be returned. When
encountering lambda abstractions, remember to store the current environment inside
them.
(b) Modify the evalExp::Exp -> Error Val function in the Eval module to call ev instead of ev0.
You should now be able to test your interpreter using tests2.mhs.
Problem 3. (40 pts)
You will now implement a type checker for a subset of Mini-Haskell. Familiarize yourself
with the abstract syntax for types in the Ty module.
(a) Implement a function tyOp::Oper -> Ty which returns the type of an operator. You
may assume that (==) can only be applied to integers, and that only integer lists can
be constructed (which means, for example, that the type of [] should indicate that it
is an integer list).
(b) Implement a function ty0::Exp -> Error Ty that can successfully type check all primitives (operators, integers, and booleans), tuples, if statements, and applications.
Since there are no type variables, you may use derived equality (==) on types. Remember that both branches of an if statement must have the same type, and that
an if condition must have a boolean type. For application, you may need to pattern
match on the type of the function in order to check that its type matches the type of
its argument.
Your solution should be able to type check tests0.mhs successfully, and should reject
tests1.mhs, as it is not well-typed.
(c) Implement the body of the ty1::Env Ty -> Exp -> Error Ty function. This function
can handle expressions that contain let bindings and variables. You only need to
handle let bindings with a single variable (that is, cases where the list of strings under
the Let constructor has exactly one element). You may extend your code to handle let
bindings with tuples for extra credit as part of your solution to Problem #4 below.
(d) Modify the typeCheck::Exp -> Error Ty function in the Ty module to call ty1 instead of ty0.
Your type checker should now be able to handle tests2.mhs.
3
Problem 4. (
∗40 extra credit pts)
(a) In the Eval module, modify the definition of appBinOp::Oper -> Val -> Val ->
Error Val so that equality is also defined on boolean, integer, tuple, and list values. Two tuples are equivalent only if they are of the same length (including the case
where both are of length zero); two lists are equivalent only if they are of the same
length and each of the corresponding values in the two lists are equivalent.
(b) In the Eval module, modify the definition of ev::Env Val -> Exp -> Error Val so
that it can handle let bindings with tuples. You should first evaluate the expression
that must be bound to the variables. If the let binding is for a tuple, this expression
must evaluate to a tuple of the same length. Otherwise, ev should return an error.
Once the value tuple is obtained, it is only necessary to take the current environment
and bind each element of the tuple to the corresponding variables. You may want
to use the updEnvL::[(String, a)] -> Env a -> Env a function, found in the Env
module, to accomplish this. Then, the body of the let binding can be evaluated under
the new environment.
(c) In the Ty module, modify the definition of ty1::Env Ty -> Exp -> Error Ty so that
when the equality operator is applied to booleans, integers, tuples, or list values, type
checking succeeds as long as both values are of the same type (you may ignore the case
in which the operator is applied partially to only a single value).
(d) In the Ty module, modify the definition of ty1::Env Ty -> Exp -> Error Ty so that
lists of any type can be constructed and expressions will still type check (you will need
to handle the list operators in a special way, as you did with equality in part (c) above).
(e) In the Ty module, modify the definition of ty1::Env Ty -> Exp -> Error Ty so that
it can handle let bindings with tuples.
A complete type inference algorithm for Mini-Haskell that can handle variables, let bindings,
lambda abstractions, and polymorphic functions and values (such as [] and (==)) can only
be defined with the help of unification. To solve the following parts, you will need to import
the Unify module from the previous assignment into the Ty module. These functions will be
used on the next assignment to define a full type-checking algorithm.
(f) Write an instance declaration in the Ty module that makes Ty a member of the
Substitutable type class.
(g) Write an instance declaration in the Ty module that makes Ty a member of the
Unifiable type class.
(h) Notice the type definition type FreshVars = [Ty]. Define a value freshTyVars::FreshVars,
an infinite list of type variables in which no type variable is ever repeated.
4