CSCC24 2020 Summer – Assignment 4
Due: Thursday, August 13, midnight
This assignment is worth 10% of the course grade.
In this assignment, you will implement in Haskell an interpreter for a toy language.
As usual, you should also aim for reasonably efficient algorithms and reasonably organized, comprehensible code.
Trycat
Trycat is an imperative language that has mutable integer variables, integer-valued expressions, and exception throwing and catching. The detailed constructs are defined by the algebraic data types Stmt, Expr, and Exception. Here are the cases for statements in both human notation and Stmt form:
Stmt form
var := expr
try stmtList catch (exception) stmtList endtry Try stmtList exception stmtList
human notation
begin stmtList end
Compound stmtList
The cases for expressions are integer literal (can be negative), variable, addition, and division. Note: Unlike in Assignment 3, this time the operands are arbitrary expressions, recursively.
The cases for exceptions are division by zero (DivByZero) and uninitialized variable (VarUninit). Some informal points on semantics:
• Assign successfully initializes or modifies var’s value, whether or not it was initialized before.
• When looking up a variable’s value, if it was not initialized before, this throws the VarUninit
exception.
• When evaluating division, if the divisor is 0, this throws the DivByZero exception.
• When evaluating addition or division, evaluate the operands in the given order, e.g., evaluate the 1st operand first. This settles the question of which exception to throw if both operands would throw exceptions.
• Try b1 exception b2 runs b1 and catches the given exception case only, not other exception cases. When that exception case happens in b1, catch it and run b2. Example: Try b1 DivByZero b2 catches DivByZero but not VarUninit from b1.
Monad for Trycat
The following type class MonadTrycat contains methods corresponding to the important features of Trycat:
1
Assign var expr
class Monad m => MonadTrycat m where
— Init/Write a variable.
putVar :: String -> Integer -> m ()
— Read a variable. Throws VarUninit if uninit. getVar :: String -> m Integer
— Throw the given exception.
raise :: Exception -> m a
— tryCatch p eCaught handler:
— Run p, but if eCaught is caught, run handler. tryCatch :: m a -> Exception -> m a -> m a
Using these methods and the Functor, Applicative, Monad methods, an interpreter for Trycat can be implemented.
A concrete model is this combination of a state monad (for mutable variables) and an Either monad (for exceptions):
data TC a = MkTC (Map String Integer ->
(Map String Integer , Either Exception a))
The state is a Map, which has the initialized variables and their values. Note that there is always a new state, whether there is an exception or not—state changes are never lost upon exceptions.
Question 1 [8 marks]
Implement the Monad >>= method and MonadTrycat methods for TC. (The rest are already done.)
Question 2 [9 marks]
Implement the Trycat interpreter:
interp :: MonadTrycat m => Stmt -> m ()
This is polymorphic, limiting you to the MonadTrycat interface, but the benefits are that it is more focused, and it can be tested under a correct instance of MonadTrycat, in case you have trouble with Question 1.
Two functions run and runWith are included to run your interpreter using TC: run starts with no variable initialized, runWith starts with a given state.
End of questions.
2