CSC324 Assignment 2: An Interpreter in Haskell
In this assignment, we will write an interpreter for a functional language in Haskell called StagShell, similar to the
interpreter that we discussed in class.
Because Haskell is a strongly typed language, implementing an interpreter in Haskell will help you better-understand
the types of objects that are being acted upon in an interpreter. This assignment is also an opportunity to work with
pattern matching, error propagation, and Haskell in general.
Before we start, remember these general guidelines for all labs and assignments:
• You may not import any libraries or modules unless explicitly told to do so.
• You may not use the function “eval” for any lab or assignment unless explicitly told otherwise.
• You may not use any iterative or mutating functionality unless explicitly allowed. Remember that a big goal of
this course is to learn about different models and styles of programming!
• You may write helper functions freely; in fact, you are encouraged to do so to keep your code easy to understand.
Breaking any of these above rules can result in a grade of 0.
• Code that cannot be imported (e.g., due to a syntax error, compilation error, or runtime error during import)
will receive a grade of zero! Please make sure to run all of your code before your final submission, and test it on
the Teaching Lab environment (which is the environment we use for testing).
• The (provide …) and module (…) where code in your files are very important. Please follow the
instructions, and don’t modify those lines of code! If you do so, your code will not be able to run and you will
receive a grade of zero.
• Do not change the default Haskell language settings (i.e. by writing an additional line of code in the first line of
your file)
Starter code
• A2.hs
• A2Types.hs
• A2StarterTests.hs
You will only be submitting A2.hs and not any of the other files. Do not make any modifications to A2Types.hs.
We’ll be supplying our own version to test your code.
The language StagShell
The language StagShell is an expression-based language that is eagerly evaluated. The language supports three
types of values: booleans (True/False), numbers, and pairs. A StagShell expression grammar is described using the
Expr abstract data type in the A2Types.hs file.
data Expr = Literal Value — literal values
| Plus Expr Expr — builtin “plus” function
| Times Expr Expr — builtin “times” function
| Equal Expr Expr — builtin checks for equality
| Cons Expr Expr — builtin “cons” function that creates a pair
| First Expr — builtin “first” function that obtains the first element of a pair
| Rest Expr — builtin “rest” function that obtains the second element of a pair
| If Expr Expr Expr — if expressions
| Var String — variable names
| Lambda [String] Expr — function definitions
| App Expr [Expr] — function applications
data Value = T | F — booleans true an dfalse
| Num Int — integers
| Pair Value Value — pairs
| Closure [String] Env Expr — closures
| Error String — errors
1
A2.hs
ATypes.hs
A2StarterTests.hs
Your task for this assignment is to write an interpreter for this language. Recall that an interpreter will take an
environment and an expression, and determine the value of the expression.
eval :: Env -> Expr -> Value
Notice that in addition to the three types of values described earlier, our definition of Value also describes two
additional value constructors Closure and Error. Here, Closure describes a closure (resulting from a function
expression), and Error describes an error when evaluating an expression.
In the rest of this handout, we will describe the behaviour of each kind of expression. Read this file carefully. We
recommend writing test cases as you go along (e.g. in the A2StarterTests.hs file). Doing so will help you engage
with the handout and stay focused, while also saving you some time down the road!
Once again, remember to trust in the recursion. Tackle each kind of expression one at a time. The order that we
provided is a fairly good way for you to get started.
Literal values
Literal values in this expression evaluate to the following:
*A2> runStag (Literal T)
T
This part of the code is written for you.
Notice that we use pattern matching to destruct a Haskell value of type Expr, so that we can get to the v inside
the Expr value (Literal v).
Plus, Times
Expressions involving Plus/Times are expected to take two subexpressions that evaluates to numbers, and produce a
number corresponding to the sum/product of the two numbers.
If either subexpression does not evaluate to a number, then return Error with an appropriate message described
towards the end of the handout.
*A2> runStag (Plus (Literal $ Num 3) (Literal $ Num 4))
Num 7
(Recall that in Haskell, the expression a $ b c is equivalent to a (b c). You can think of $ as an infix operator for
function application. If that doesn’t make sense, think of $ as a fancy way of avoiding brackets.)
We wrote some code for you to handle the Plus case, so that you can see an example of case … of … expression
in Haskell. In particular, we can pattern match the values returned from (eval env a).
You will need to write your own new patterns and bodies for the eval function from here onwards.
Equal
This expression takes two subexpressions. In most cases, use the Haskell == to check if the values of the subexpressions
are equal. If so, return the boolean value T. Otherwise, return F. (Note that if you try to return Haskell “true” and
“false” values, your interpreter will not type check!)
The only exception is if either of the subexpressions return an error. If so, return the first error encountered.
*A2> runStag (Equal (Literal $ Num 3) (Literal $ Num 4))
F
*A2> runStag (Equal (Plus (Literal $ Num 3) (Literal $ Num 4)) (Literal $ Num 7))
T
Cons, First, Rest
A Cons expression takes two subexpressions, and creates a Pair out of the resulting expressions. Again, the exception
is if either of the two sub-expressions result in an Error. If so, return the first error encountered.
2
The First and Rest expressions take one subexpression. If a pair is returned, extract either the first/second element
of the pair. Otherwise, return an error.
*A2> runStag (Cons (Literal $ T) (Literal $ F))
Pair T F
*A2> runStag (First (Cons (Literal $ T) (Literal $ F)))
T
*A2> runStag (Rest (Cons (Literal $ T) (Literal $ F)))
F
If expressions
Like in Racket, an If expression takes three subexpressions (If cond expr alt). First, the condition subexpression
cond is evaluated. If an error occurs during the evaluation of cond, propagate that error. Otherwise, we will use the
rule that if the condition subexpression evalutes exactly to T, then we will evalute expr. Otherwise, evaluate alt.
Note that in this expression, only one branch of the “If” expression should be evaluted!.
*A2> runStag (If (Literal T) (Literal $ Num 3) (Plus (Literal T) (Literal F)))
Num 3
Variable lookup
A Var identifier should evaluate to its corresponding value in the environment, similar to what we did in the previous
lab in Racket. Here, you may find the function Data.Map.lookup helpful.
One thing to note is that (Data.Map.lookup name env) does not return a Value. Instead, it returns Maybe Value,
to account for the case where the identifier name is not defined in the environment.
If the variable name does not appear in the environment, return an error.
Function expressions
A function expression takes a list of identifiers, a body expression, and evaluates to a closure like discussed in lecture.
Unlike the Lambda Calculus++ language from lecture 4, StagShell allows functions with zero or more arguments. As
examples, these are all valid expressions in StagShell, represented as a value of type Expr in Haskell:
— a function that takes 0 parameters and returns T
(Lambda [“”] (Literal T))
— a function that takes 2 parameters and returns the second one
(Lambda [“x”, “y”] (Var “y”))
— a function that takes 2 parameters adds them
(Lambda [“x”, “y”] — these are the parameter names
(Plus (Var “x”) (Var “y”)) — this is the function body
)
Here is what should happen when we evaluate an identity function in StagShell:
*A2> runStag (Lambda [“x”] (Var “x”)) — an identity function
Closure [“x”] (fromList []) (Var “x”)
Like discussed, evaluating a Lambda expression should yield a closure containing the same information as in the
function expression, plus the environment at the time to function was created. Our Closure constructor contains
• The list of parameters (e.g. [“x”] from above)
• The environment (e.g. (fromList []) from above, which is a Data.Map value)
• The body expression (e.g. (Var “x”) from above)
Note that the body expression should not be evaluated until it is called! In other words, the following expression
should not evaluate to an Error, even though evaluating (Var “y”) will fail:
3
*A2> runStag (Lambda [“x”] (Var “y”))
Closure [“x”] (fromList []) (Var “y”)
Function application
Like discussed in class, evaluating the function application (App fnExpr argExprs) involves several steps:
1. Evaluate fnExpr. This should result in a (Closure params cenv body), otherwise there is an error. At this
point, you can also check that the number of parameters is the same as the number of argument expressions,
and return an Error otherwise.
2. Evaluate each of the argExprs. If any of these argument expressions evaluates to an error, return that error
instead of continuing execution.
3. Finally, evaluate the body expression from the closure from step 1.
Pay close attention to the environment that you use (and/or construct) at this point. You may find Data.Map.insert
helpful in determining what to do with the parameter names and arguments.
*A2> runStag (App (Lambda [“x”] (Var “x”)) [Literal T])
T
Errors
The following errors should be reported:
• Error “Plus”: occurs when an expression (Plus a b) has either a or b not evaluating to a number.
• Error “Times”: occurs when an expression (Times a b) has either a or b not evaluating to a number.
• Error “First”: occurs when an expression (First e) has e not evaluating to a pair.
• Error “Rest”: occurs when an expression (Rest e) has e not evaluating to a pair.
• Error “Var”: occurs when an identifier (Var name) does not exist in the environment.
• Error “App”: occurs when an application (Apply fnExpr argExprs) has fnExpr not evaluating to a closure,
or if the list of expressions argExprs is of different length than the list of parameter names.
Moreover, we expect that the first error encounters in a left-to-right, eager evaluation order will be the one returned:
*A2> runStag (Plus (Literal $ Num 3) (Times (Literal $ Num 3) (Literal T)))
Error “Times”
*A2> runStag (App (Lambda [“x”] (Var “y”)) [Literal T])
Error “Var”
*A2> runStag (App (Lambda [“x”] (Var “y”)) [Literal T, Literal T])
Error “App”
*A2> runStag (If (Literal T) (Literal $ Num 3) (Plus (Literal T) (Literal F)))
Num 3 — no error!
Getting Started
Once again, it is normal in this course to spend a long time thinking, and relatively little time writing code. If you
begin writing code right away, you may end up writing a lot of code that serves little to no purpose. It’s okay to work
with examples for a long time. It’s okay to think for a long time about a very short piece of code. It’s also okay to
throw out large amounts of code and start over once you understand the problem better.
If you are working with a partner, we highly recommend pair coding. Pair coding is especially helpful for this course,
since it is easy to make both syntax and logical errors while coding. Handle one expression type at a time, and
expand your tests as you go along.
4
CSC324 Assignment 2: An Interpreter in Haskell
Starter code
The language StagShell
Literal values
Plus, Times
Equal
Cons, First, Rest
If expressions
Variable lookup
Function expressions
Function application
Errors
Getting Started