3 of 37

Categories of Values so far

Expressed values�Possible values of expressions�Int, Bool, Closure

Denoted values�The values bound to variables�Int, Bool, Closure

4 of 37

Effects

So far: Expressions evaluate to values
New: Effects during evaluation

exp

value

effects

eval

both

5 of 37

What is an effect?

Print something on screen
Read or write a file, network device
Sending a signal on communication port
...
Alter state of memory

6 of 37

Modeling State

General concept: store (=memory)

store :: loc -> val�

Domain: "addresses" of memory cells
Range: Content of memory cells

What operations do we need on the store?

7 of 37

Operations

insert :: store -> val -> (store,loc)
update :: store -> loc -> val -> store
fetch :: store -> loc -> val

Implementation depends on meta-language.

Scala: Use a map.

8 of 37

Language extension (explicit refs)

e ::= ... | new e | deref e

| setref e e

Exp = ... | New Exp | Deref Exp

| Setref Exp Exp

Val = ... | VLoc Loc

9 of 37

Example

let x = new 1 in

let y = x in // location assignment

if deref x = deref y then // val comp.

setref x 2

else

setref y 7

(deref x) + (deref y)

eval(...) = 4

10 of 37

Categories of Values

Expressed values�Possible values of expressions�Int, Bool, Closure, Ref(ExpVal)

Denoted values�The values bound to variables�Int, Bool, Closure, Ref(ExpVal)

11 of 37

Consequences: Global change

Let is local

let x = 5 in

...

Effect is global

Can change behavior everywhere

12 of 37

Consequences: We lose purity

Always:

eval(f 42) = 10

With effects

eval(f 42) = 10
eval(f 42) = 20

Order of execution is suddenly important!

13 of 37

Order of execution

Pure (order unimportant)

(f e1 (f e2 e3))

Impure (order important)

(f e1 (f e2 e3))

14 of 37

Evaluation (1)

We need to change eval

eval :: exp -> env -> val

Adding our store

eval' :: exp -> env ->

store -> (store, val)

15 of 37

Evaluation (2) - Order important!

Change all calls from eval to eval'.

eval (Add e1 e2) env =

VNum (getNum (eval e1 env)

+ getNum (eval e2 env))

eval' (Add e1 e2) env store =

let (store',v1) = eval' e1 env store in

let (store'',v2) = eval' e2 env store' in

let res = VNum (getNum v1 + getNum v2) in

(store'', res)

16 of 37

Evaluation (3)

eval' (VLoc i) env store = (store, VLoc i)

eval' (New e) env store =

let (store',v) = eval' e env store in

let (store'',l) = insert store' v in

(store'', VLoc l)

17 of 37

Evaluation (4)

eval' (Deref e) env store =

let (store',VLoc loc) = eval' e env store in

(store',fetch store' loc)

eval' (Setref e e') env store =

let (store',VLoc loc) = eval' e env store in

let (store'',v) = eval' e' env store' in

(update store'' l v, v)

18 of 37

Refs and functions

Functions integrate without problems

let incValue = new

fun a =>

let v = deref a in

setref a (v + 1)

let _ = setref incValue (fun a => a) in

let x = new 5 in

(deref incValue) x

Can we get rid of deref, ref, setref?

19 of 37

Example

Explicit:

let x = new 1 in

let _ = setref x 5

deref x

Implicit:

let x = 1 in

x := 5;

20 of 37

Language extension (implicit refs)

e ::= ... | x := e | e;e

Exp = ... | Assign Var Exp

| Seq Exp Exp

Val = ... | VLoc Loc

Removed:

Reference creation (automatically with let)
Manual dereferencing

21 of 37

Evaluation (1)

Change signature of Environment:

put :: Map Ident Loc -> Ident -> Loc

-> Map Ident Loc

get :: Map Ident Loc -> Ident -> Loc

eval' (Let x e body) env store =

let (store',v) = eval' e env store in

let (store'', loc) = insert store' v

let env' = put env x loc in

eval' body env' store''

22 of 37

Evaluation (2)

eval' (Assign id e) env store =

let (store',v) = eval' e env store in

let loc = get env id in

(update store' loc v,v)

23 of 37

Evaluation (3)

eval' (Seq e1 e2) env store =

let (store',_) = eval' e1 env store in

eval' e2 env store'

24 of 37

Evaluation (4)

eval' (Var x) env store =

let loc = get env x in

(store, fetch store loc)

25 of 37

Explicit vs. implicit refs

Explicit refs:

Our interpreter
C++ (pointer)
C# (unsafe)
Pascal

Implicit refs:

Java
C++ references
Scala

You know any other language with explicit refs?

26 of 37

Categories of Value

Expressed values�Possible values of expressions�Int, Bool, Closure

Denoted values�The values bound to variables�Ref(ExpVal)

27 of 37

Consequences

Smaller code
Code more complex
How about functions?

fun x => x := 5

28 of 37

Function calls with implicit refs

fun x => x := 5

Functions can change arguments visible to the outside!
Strategies:

Call-by-reference
Copy parameters before call

29 of 37

Example

let x = 1 in

let addOne = fun a => x + a in

// ...

x := 11;

// ...

addOne 4

30 of 37

Call-by-* strategies

So far, we had:

Call-by-value
Call-by-name

New:

Call-by-reference
Call-by-need

31 of 37

Call-by-reference

eval' (App e1 e2) env store =

let (store', VClos x env' body) =

eval' e1 env store in

let (store'', arg) =

match e2 with

Var x => (store', get env x)

_ => let (store''', v) =

eval' arg env store' in

insert store''' v

eval' body env' store''

32 of 37

Call-by-need

Only evaluated when needed (lazy)
Mixture of call-by-name and call-by-value

General concept:

Thunk exp env

Call: Argument not evaluated -> Thunk
Use:
eval exp env store = (store', val)
update store ThunkLoc val

33 of 37

Deallocation

Only creation of references so far!

No deallocation!�Possibilities:

Manual deallocation (e.g. C++'s delete)
Automated deallocation: Garbage Collection

34 of 37

Language extension (Manual free)

e ::= ... | free e

Exp = ... | Free Exp

New operation on store:

delete :: store -> loc -> store

35 of 37

Evaluation

eval' (Free exp) env st =

let (st',VLoc loc) = eval' exp env st in

(delete st' v, v)

36 of 37

Problems

What if a cell is still referenced after free?

x := 5;

free x;

37 of 37

Garbage collection

Idea:

Automated search for dead references
Several approaches:

Mark and Sweep
Copying
Generational
...