The University of COMP3259: Principles of Programming Languages
Tutorial 9
Yaozhu Sun Instructor
Copyright By PowCoder代写 加微信 powcoder
26 April 2022
Table of Contents
1 Introduction 3
2 An Imperative Language 4
2.1 AMonadicInterpreterforanImperativeLanguage . . . . . . . . . . . . . 5 2.2 AMonadicInterpreterwithErrorHandling …………….. 6
1 Introduction
This tutorial aims at providing students with experience in writing monadic interpreters and especially interpreters with imperative features.
2 An Imperative Language
Now that we already have experience with monads in the last tutorial, we can come back to our SNH language. Previous tutorials have been focusing on functional programming (i.e. no mutation is allowed). In this tutorial, we are going to add some imperative features to SNH. However, unlike JavaScript, we use a model where mutable variables have to be explicitly declared using the Mutable constructor. Furthermore, accessing a
mutable variable should be prefixed with @, and := is used to update a mutable variable. Here are two examples:
var mb = Mutable(true); var mi = Mutable(6); if {
mi := @mi + 1 } else {
mi := @mi – 1 }
var mx = Mutable(4); var my = Mutable(8); mx := @mx + @my;
my := @mx – @my;
mx := @mx – @my
Note that semicolons (;) now have two different meanings although the two usages are quite similar. On the first two lines, the semicolons are used to separate initial values and declaration bodies. The other usage is called sequential composition, which is a standard construct in imperative programs. It sequentializes two expressions and keeps the result of the latter.
The abstract syntax of SNH is as follows:
data Value = IntV Int | BoolV Bool
| ClosureV String Exp Env | AddressV Int — new deriving Eq
An AddressV is generated by the Mutable constructor, and it contains an address in a virtual memory.
data Exp = Lit Value
| Bin BinaryOp Exp Exp
| If Exp Exp Exp
| Var String
| Decl String Exp Exp
| Call Exp Exp
| Fun String Exp
| Mutable Exp
| Access Exp
| Assign Exp Exp
| Seq Exp Exp deriving (Eq, Show)
Sequential composition is modeled by the Seq constructor, which consists of two expres- sions. The Access and Assign constructors, as the names suggest, are used for accessing and updating mutable variables.
In an imperative language, besides environments, we also need a virtual memory and a notion of stateful values. They are modeled as follows:
type Memory = [Value]
type Stateful t = Memory -> (t, Memory)
Stateful.hs includes an incomplete evaluator for SNH. You can start with the code there and try to understand how the environment and the virtual memory interact for the case of Mutable. Your job is to finish the remaining cases, following the same idea.
Question 1. Complete the cases for Access, Assign, and Seq in the file Stateful.hs.
Hint: For Seq, evaluate the first expression, throw away the result, and then evaluate the second expression. Note that the two helper functions access and update may come in handy when interacting with the virtual memory.
2.1 A Monadic Interpreter for an Imperative Language
We are now going to implement the same language using a monadic interpreter. The code presented here is available in the file StatefulMonad.hs.
The interpreter can be monadic because Stateful is actually a monad, which can be defined as follows:
newtype Stateful t = ST (Memory -> (t, Memory))
instance Monad Stateful where return val = ST $ \m -> (val, m) ST c >>= f = ST $ \m ->
let (val, m’) = c m ST c’ = f val
The monad allows us to rewrite the evaluator such that the details of threading the state through the evaluation is encapsulated by the monadic operation >>=. The rewritten code is much simpler and cleaner.
With the Stateful monad, the type of evaluate is as follows: evaluate :: Exp -> Env -> Stateful Value
Question 2. Complete the definition of evaluate using the do-notation in the file StatefulMonad.hs.
2.2 A Monadic Interpreter with Error Handling
Since we have known that error handling is also a monadic operation, what if we combine the two monads into a single one and obtain an interpreter that both checks errors and supports mutable state?
There are at least two ways to compose the two monads Checked and Stateful. One way is:
newtype CheckedStateful1 t = CST1 (Memory -> (Checked t, Memory)) Another way is:
newtype CheckedStateful2 t = CST2 (Memory -> Checked (t, Memory))
Question 3. Fill in the missing monadic operators (return and >>=) for these two monads in the file StatefulCheckedMonad.hs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com