As promised here are my notes from class covering mutable state through the end of the semester. I have not edited or otherwise tried to clean them up, but they do represent what we covered in class. For other topics the online text is far better prepared and much preferable.
There are a few topics - sums and products, errors, loops - that I removed from the end of these notes. Those topics are not on the exam. The exam topics end where these notes end.
The big difference between Haskell and C
... x=x+3 ; y=x++ ...
“;” do?"=" do?bind x=(f a) in
(g 3)
== ((lambda _ in (g 3)) (f a))
What’s happening besides substitution?
do { l’ <- eval l ;
r’ <- eval r ;
return (op l’ r’) }
What’s happening besides binding?
Order!
We tend to think of two programming paradigms:
What’s happening in this sequence? Where does x get a value?
x := 1; x := x + 1; x := x + 1; ...
:= (the walrus) is an assignment that updates a variable in the next state
x := x+1 == x’ = x+1
x is the current x plus 1How is state different than environment?
Seq sequence operatorstoreeval to maintain state in addition to environmentNew concrete syntax: t ; t
New abstract syntax: Seq::FBAE->FBAE->FBAE
Define sequence by elaboration: Seq l r == (App (Lambda x r) l)
eval e s Seq l r = do { s' <- eval e s l; eval e s' r }
Is state updated differently than environment?
Interesting syntax!
We’re being sloppy anyway, we’ll skip typing for now.
FBAE := new FBAE | deref FBAE | set loc FBAE
loc - new type of value for locations - where’s loc in the syntax?new t - creates a new location, puts eval t there, returns the locationderef l - retrieves a value from l and returns itset l t - stores eval t in location l and returns lderef (new 5)
== 5
deref (set (new 5) 6)
== 6
bind l = new 2+3 in deref l [(l,->5)]
== (deref l) [(l,->5)]
== (deref ->5)
== 5
bind l = new 2+3 in [(l,->5)]
set l ((deref l) + 1) ; (deref l) [(l,->5)]
== (set l 6) ; (deref l)
== (deref l) [(l,->6)]
== 6
:= (sort of)?l := r == (set l (deref r))
l := l + 1
bind m = new 5 in [(m,->5)]
bind n = m in [(n,->^)]
set m 6 ; deref n [()]
== 6
bind m = new 5 in
bind n = m in
bind n = new 5 in
set m 6 ; deref n
== 5
bind inc = (lambda l in (set l ((deref l) + 1)))
bind n = new 5
inc n ; deref n
==
Store as a function with location as a number
We could use an array or a sequence, but let’s try a technique commonly used in formal modeling.
type Sto = Loc -> Maybe FBAEVal
type Loc = Int
Sto is the store and is a function from Loc to Maybe FBAEVal.
Why a Maybe?
Just x - a good location is accessed.Nothing - a bad location is accessed.What are good and bad memory locations?
What does this have to do with language design?
Memory contains FBAEVal. What does this imply?
What does this have to do with language design?
Dereferencing is just using the store as a function:
derefSto s l = (s l)
The initial store is a store with nothing in it.
initSto :: Sto
initSto x = Nothing
initSto 3?initSto for any value?Updating the store is a bit trickier…
m0 = \l -> if l=3 then 1 else (initSto l)m0 is the new store using if
(m0 3) = 1 using then when l=3Return initSto l using else when l<>3
m0 at location 1:
m1 = \l -> if l=1 then 2 else (m0 l)m1 is the new store again using if
(m1 1) = 2 using then when l=1(m0 l) using else when l<>1(m1 3)?What is (m1 2)?
m2 = \l -> if l=2 then 0 else (m1 l)m2 is the new store yet again using if
(m2 2) = 0 using then when l=2(m1 l) using else when l<>2(m1 3)?What is (m1 2)?
m3 = \l -> if l=3 then 4 else (m2 l)m3 is the new store yet again using if
(m3 3) = 4 using then when l=3(m2 l) using else when l<>3(m1 3)?What happened to the old (m1 3)
… if it walks like a duck and quacks like a duck …
setSto :: Sto -> Loc -> FBAEVal -> Sto
setSto s l v = \m -> if m==l then (Just v) else (s m)
\x -> t is lambda x in t in HaskellThe store becomes a collection of nested if statements. Not the most efficient, but it does what it’s supposed to for our purposes.
Putting things together to model memory:
type Store (Loc,Sto)
A location, store pair.
loc is the next memory elementsto is the current memoryderefStore (_,s) l = (s l)
Dereferencing is accessing the memory location
initStore = (0,initSto)
Initialize memory is the initial, empty memory with a next value of 0.
setStore (m,s) l v = (m,setSto s l v)
Storing a new value
newStore (l,s) = (l+1,s)
Uh, we’re not storing anything are we?
Allocating memory location.
l is forHow does store differ from environment?
Let’s add a constructor for locations
data FBAEVal =
...
Loc :: Int -> FBAEVal
And a constructor in FBAE?
Seems simple enough
eval can return a locationOur choices are important. Even the tiny ones.
How to implement mutability of Store??
Start with a new return value:
type Retval = (FBAEVal,Store)
Retval is the return value for our interpreter
What’s this for??
eval :: Env -> Store -> FBAE -> Maybe Retval
eval now takes an environment and a store.
Env - identifiers and values in scopeStore - contents and current location in memory.What should an initial call to eval look like?
x:=x+1 ; x:=x+1
eval e s (Seq l r) = do {(v,s') <- (eval e s l) ;
(v',s'') <- (eval e s' r) ;
return (v',s'')}
v is doingeval e s (Set l t) = do {(v,s') <- (eval e s t) ;
(setStore s' l v)}
All that work finally pays off - Set calls setStore
What is the pattern matching in the do clause doing?
eval e s (Plus l r) = do {((NumV l'),s') <- (eval e s l) ;
((NumV r'),s'') <- (eval e s' r) ;
return ((NumV l'+r'),s'')}
This passing of state is the new idiom:
eval e s (Deref t) = do {((Loc l'),s') <- (eval e s t) ;
(derefStore (Loc l') s'}
Let’s unpack New and figure out what’s going on:
eval e s (New t) = do { (v’,(l,s’)) <- eval e s t ;
return ((Loc l+1),(setStore (newStore (l,s’)) s' v’)) }
Wow. What the heck?
(v',(l,s')) - v' value to be stored in s' at location l+1(Loc l+1) - next location after l the location value is the return value.(newStore (l,s')) - new store with l allocated(setStore ...) - stores v'
`
Let’s do this together…
What is the difference between a variable and an identifier?
We have utilities for mutable store that we should be able to use.
What things do we need to define?
We want to control the way that memory gets accessed.
set, deref, newvar x:=t1 in t2 == bind x=new t1 in t2
var x:=0 in
var y:=1 in
var z:=3 in x+y+z
x, y and z in a style like OCamlx+1 rather than `(deref x) + 1x is a variable?(deref (lookup x e) s) - value stored in the location stored in x
lookupderef`x := v == (set x v)
v not general termsx?Asn :: string -> FBAE -> FBAE
For example:
x := x+y+z
x(set x v)
set works if x is a location and v is a value resulting from evaluating the right side.In many languages we will remove all location manipulating functions and just use var and assignment. Any reason for that?