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 diﬀerent 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 ﬁnal 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 ﬁles 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 ﬁrst line of
You will only be submitting A2.hs and not any of the other ﬁles. Do not make any modiﬁcations 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 ﬁle.
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
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 deﬁnition 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 ﬁle carefully. We
recommend writing test cases as you go along (e.g. in the A2StarterTests.hs ﬁle). 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.