[SOLVED] Monads and Imperative Programming

Monads and Imperative Programming
Principles of Programming Languages

Course Evaluation

Copyright By Assignmentchef assignmentchef

Please go to the link:
http://setl.hku.hk
And fill out the evaluation for the course.

Final Project
Start: 1st week of May (duration around 16 days)
Tentative dates: Start: May 8th, End: May 24th Similar in style to the assignments, but with the
following differences:
There will be an extensions part where students are count 25% of the grade.
A small report (in pdf/word) needs to be submitted.
free to define their own PL features. This part will

A Problem: Tracking Errors is Painful

Evaluating binary operators before errors:
deriving (Eq,Show)
type Env = [(String, Value)]
evaluate :: Exp ! Env ! Value Before errors
evaluate (Literal v) env = v evaluate (Unary op a) env =
unary op (evaluate a env) evaluate (Binary op a b) env =
binary op (evaluate a env) (evaluate b env)
evaluate (If a b c) env =
let BoolV test = evaluate a env in
if test then evaluate b env else evaluate c env
evaluate (Variable x) env = fromJust (lookup x env)
evaluate (Declare x exp body) env = evaluate body new where newEnv = (x , evaluate exp env ) : env

HAPTER 6. COMPUTATIONAL STRATEGIES
evaluate (Unary op a) env =
After errors
Error msg ! Error msg
Evaluating binary operators after errors:
case evaluate a env of
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
Can we make the code less messy?
w it should be clear why programmers do not always check a ause it is tedious and requires lots of code! What was original

HAPTER 6. COMPUTATIONAL STRATEGIES
evaluate (Unary op a) env =
Spotting the pattern
Error msg ! Error msg
Evaluating binary operators after errors:
case evaluate a env of
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
There seems to be a repeating pattern here.
w it should be clear why programmers do not always check a ause it is tedious and requires lots of code! What was original

and updating memory) and then evaluating the second ex l
updating memory as appropriate). They both have a simi with the evaluation of a and b. Factoring out the commo
mem let (v , m next-part
Spotting the pattern
part, the core of the pattern is:
We seem to have something like this:
case first-part of
Error msg ! Error msg Good v ! next-part v
This first-part corresponds to evaluate a env or evaluat versions. The second-part represents the remainder of everything that appears after the main pattern, but wit explicit. For the Checked case, the only variable need
How to capture this pattern as reusable code?

These patterns can be made explicit as a special operator t t
where the second part is a function with the appropria concrete, these parts are converted into explicit variables
Use a higher-order function!
Spotting the pattern
and the second-part, which is a function, is named F :
A BS F = mem let (
A BC F = case A of
Error msg ! Error msg Good v ! F v
These generic operators for Checked BC and Stateful BS the core pattern composing two Checked or Stateful co operators are called bind operators, because they bind

Revising the Implementation

Creating auxiliary definitions
The higher-order function capturing error propagation:
(>>=) :: Checked a -> (a -> Checked b) -> Checked b
Error msg -> Error msg
Good v -> f v
A function that creates checked values:
return :: a -> Checked a
return v = Good v
We will call this function bind (since it binds a value v)

Rewriting Evaluation
Here is the new version (4 cases) of evaluation:
evaluateM (Literal v) env = return v
evaluateM (Variable x) env =
case lookup x env of
Nothing -> Error (Variable ++ x ++
undefined)
Just v -> return v
evaluateM (Unary op a) env =
evaluateM a env >>= checked_unary op
evaluateM (Binary op a b) env =
evaluateM a env >>=
v1 -> evaluateM b env >>=
v2 -> checked_binary op v1 v2

Propagating errors
evaluateM (Binary op a b) env =
evaluateM a env >>=
v1 -> evaluateM b env >>=
v2 -> checked_binary op v1 v2

HAPTER 6. COMPUTATIONAL STRATEGIES
evaluate (Unary op a) env = Propagating errors
Error msg ! Error msg with
case evaluate a env of
Good av ! checked_unary op av evaluate (Binary op a b) env =
case evaluate a env of Error msg ! Error msg Good av !
case evaluate b env of Error msg ! Error msg Good bv !
checked_binary op av bv
This code is definitely longer.
w it should be clear why programmers do not always check a ause it is tedious and requires lots of code! What was original

Propagating errors
evaluateM (Binary op a b) env =
evaluateM a env >>=
v1 -> evaluateM b env >>=
v2 -> checked_binary op v1 v2
Still, the use of bind may not immediately intuitive.

Monads are a structure composed of two basic operations (bind and return), which capture a common pattern that occurs in many types.
Monads in are implemented using type
class Monad m where
(>>=) ::ma->(a->mb)->mb return :: a -> m a

Checked as a Monad
Because Checked can implement return and bind it can be made an instance of Monad
instance Monad Checked where
return v = Good v
Error msg -> Error msg
Good v -> f v

Rewriting Code Again
Using bind and return from the Monad class does
not affect the code:
evaluateM (Binary op a b) env =
evaluateM a env >>=
v1 -> evaluateM b env >>=
v2 -> checked_binary op v1 v2

Rewriting Code Again
However, because monads are so pervasive, Haskell notation).
supports a special notation for monads (called the do-
With the do-notation we can re-write the program as
evaluateM (Binary op a b) env =
do v1 <- evaluate a env v2 <- evaluate b env checked_binary op v1 v2 Do-notationIn Haskell, code using the do-notation, such as:do pattern <- exp morelinesIs converted to code using bind:exp >>= (pattern -> do morelines)

Monads, Functional Programming and Interpreters
Monads were introduced to Functional Programming by
See the paper below, which motivates monads through interpreters (much like the interpreters in the class)
The essence of Functional Programming,, 1992

Imperative Programming

Lecture covers:
Chapter 6 of Anatomy of Programming
Languages
http://www.cs.utexas.edu/~wcook/anatomy/ anatomy.htm

Interpreter so far
Our current JavaScript-like interpreter already
supports a number of features:
basic expressions (arithmetic & conditionals) variable declarations
function definitions & first-class functions recursion
Error Handling

Imperative Programming
Imperative Programming is characterized by mutable variables
a programming style that uses mutation and
iteration (loops) to implement algorithms
for (i = 2; i <= 5; i = i + 1) {x = x * i; }Imperative LanguagesMost languages support Imperative Programming Classic Languages: Algol, C, OO Languages: C++, Java, C# Scripting Languages: Javascript, Python, Languages: ML, OCaml, ScalaDifferent designs are possible:Mutable StateMutation by default: Make everything mutable byAdopted by most languages: Java, C, C#, Mutation: Make mutation explicitSome languages, such as ML, adopt this Explicit MutationIn a design with explicit mutation, variables need tobe declared to be mutable:x = Mutable(1);for (i = Mutable(2); @i <= 5; i := @i + 1) {x := @x * @i; }We are going to adopt this design. We are going to use addresses to model mutation:Mutable(e)Creates a mutable cell with an initial value given by eAccesses the contents stored at address aUpdates the contents at address a to be the value of expression e Implementing Mutable StateAddresses are a new kind of valuedata Value = IntV Int | BoolV Bool | ClosureV String Exp Env| AddressV Int — new deriving (Eq, Show)The current value of all mutable cells used in aprogram is called memory.Logically, a memory is a map or association ofaddresses to values.Since addresses are integers, one naturalrepresentation is as a list or array of valuestype Memory = [Value]Memory OperationsTwo important operations on Memory: Access: accesses the value stored in the memory address.access i mem = mem !! iUpdate: updates the value stored in the memoryupdate :: Int -> Value -> Memory -> Memory
update addr val mem =
let (before, _:after) = splitAt addr mem in before ++ [val] ++ after

Monads Again!

Stateful Monad

Evaluating binary operators before state:
deriving (Eq,Show)
type Env = [(String, Value)]
evaluate :: Exp ! Env ! Value Before state
evaluate (Literal v) env = v evaluate (Unary op a) env =
unary op (evaluate a env) evaluate (Binary op a b) env =
binary op (evaluate a env) (evaluate b env)
evaluate (If a b c) env =
let BoolV test = evaluate a env in
if test then evaluate b env else evaluate c env
evaluate (Variable x) env = fromJust (lookup x env)
evaluate (Declare x exp body) env = evaluate body new where newEnv = (x , evaluate exp env ) : env

After State
Evaluating binary operators after state:
evaluate (Binary op a b) env mem =
let (av, mem) = evaluate a env mem in
let (bv, mem) = evaluate b env mem in
(binary op av bv, mem)
the state around makes code messy! Can we do better?

Spotting the pattern
Evaluating binary operators after errors:
evaluate (Binary op a b) env mem =
(binary op av bv, mem)
There seems to be a repeating pattern here.
let (av, mem) = evaluate a env mem in
let (bv, mem) = evaluate b env mem in

Monads to the Rescue!
We can capture the essence of threading the state around using a Monad!
data 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 f = f val

Rewriting code
Using the do-notation for Monads we can rewrite the code as follows:
evaluate (Binary op a b) env = do
av <- evaluate a envbv <- evaluate b envreturn (binary op av bv) CS: assignmentchef QQ: 1823890830 Email: [email protected]