## Exam Check-List: Discussion on Part 07 - State

FeG
Endlosschleifenbastler Beiträge: 182
Registriert: 6. Dez 2007 07:01

### Exam Check-List: Discussion on Part 07 - State

Hi,

here is my solution to the seventh topic of the exam check-list (-> spoiler alert...).

Best,
Felix

1. Compute the result of evaluating a program with [mutable boxes/mutable variables/call by value/call by reference].

Code: Alles auswählen

{with {b {newbox 1}}
{with {x 2}
{with {f {fun {y}
{+ {openbox b}
{seqn
{set y {+ y 8}}
y }}}}
{seqn
{setbox b 4}
{set x {+ {f x} x}}
x }}}}

Call-by-value: 16
(intermediate steps: {openbox b} = 4, y (and only y) = 10, x remains 2, sum: 16)

Call-by-reference: 24
(intermediate steps: {openbox b} = 4, y = 10 and as x is passed as reference: y==x thus also x = 10, sum: 24)
2. Explain why evaluation order is important in the presence of mutable state?

As the firstly evaluated expression might change the value of an identifier in the second expression, the overall result is possibly different, if the evaluation is switched in such a case.
3. Give an example of a program, which evaluates differently depending on the evaluation order or certain expressions.

Code: Alles auswählen

{with {x 0}
{+ x
{seqn
{set x 1}
0}}}

Result with left-to-right order: 0 (x is changed after evaluation for the + operation)
Result with right-to-left order: 1 (x is changed before evaluation for the + operation)
4. Explain the general strategy of supporting mutable state in an interpreter.

Separate identifier bindings (in environment) from now dynamically changing values (in the store). Interpreter updates environment within its calls as usual, but returns besides the result value a (possibly modified) store. This modified store is passed along to the next interpreter call in order to pass the modified state.
5. Explain what is kept in the environment and in the store of an interpreter implementing mutable state. Why we need both of them?

The environment keeps lexical bindings of identifiers to store locations, the store keeps mappings of locations to values. We need both of them, as identifiers have a limited scope (and thus will be handeled by a stack-like environment), while values have possibly infinite extent. Moreover, with static scoping, functions carrying around their definition-time environment inhibit that a possibly changed state at application time can be used by the function.
6. Explain what is meant by store-passing style.

Store-passing style describes the behavior of the interpreter, to pass along the (possibly updated) store (that an interpreter call returns besides of the result value) from one interpreter call to the subsequent one, e.g., the updated store returned by the interpreter call on the left-hand side of an addition to the interpreter call on the right-hand side of an addition.
7. Find errors in the given interpreter fragment implementing [store passing style/mutable boxes/mutable variables]. Fix them.

Code: Alles auswählen

(define (interp expr en store)
(type-case SCFWAE expr
...
(type-case Value*Store (interp l en store)
[v*s (l-value l-store)
(type-case Value*Store (interp r en store)
[v*s (r-value r-store) (v*s (num+ l-value r-value) store)])])]
...
[id (v) (v*s (env-lookup (store-lookup v store) en) store)]
...))

Correct version:

Code: Alles auswählen

(define (interp expr en store)
(type-case SCFWAE expr
...
(type-case Value*Store (interp l en store)
[v*s (l-value l-store)
(type-case Value*Store (interp r en l-store)
[v*s (r-value r-store) (v*s (num+ l-value r-value) r-store)])])]
...
[id (v) (v*s (store-lookup (env-lookup v en) store) store)]
...))

a) [add ...] clause: use l-store instead of store when interpreting the r expression and return r-store instead of store.
b) [id ...] clause: first look-up store position in environment, than look-up value in store (i.e., exchange the calls).
8. Describe the environment and the store at a certain point of the given program.

Code: Alles auswählen

{with {x 0}
{with {y 1}
{seqn
{set x 2}
{+ x y}}}}

At the point directly before evaluating "{+ x y}", the environment is

Code: Alles auswählen

  env = (
y -> store-location-B
x -> store-location-A
)

(where store-location-X is some number X chosen by the interpreter)
and the store is

Code: Alles auswählen

  store = (
A -> 2
B -> 1
A -> 0
)

(note that the second A mapping is shadowed by the first one).
9. Given an interpreter fragment tell whether it implements call-by-value or call-by-reference. Change it to the other one.

Code: Alles auswählen

(define-type SCFWAE
...
[fun (param SCFWAE?) (body SCFWAE?)]
[app (fun-expr SCFWAE?) (arg-expr SCFWAE?)]
...)

(define (parse s-expr)
(cond
...
[(list? s-expr)
(case (first s-expr)
...
[else (app (parse (first s-expr)) (parse (second s-expr)))])]))

(define (interp expr en store)
(type-case SCFWAE expr
...
[app (fun-expr arg-expr)
(type-case Value*Store (interp fun-expr en store)
[v*s (fun-value fun-store)
(type-case Value*Store (interp arg-expr en fun-store)
[v*s (arg-value arg-store)
(let ((new-loc (next-location arg-store)))
(interp
(closure-body fun-value)
(anEnv (closure-param fun-value) new-loc (closure-env fun-value))
(aSto new-loc arg-value arg-store)))])])]
...))

Implements call-by-value. Call-by-refernce version:

Code: Alles auswählen

(define-type SCFWAE
...
[fun (param symbol?) (body SCFWAE?)]
[app (fun-expr SCFWAE?) (arg-expr symbol?)]
...)

(define (parse s-expr)
(cond
...
[(list? s-expr)
(case (first s-expr)
...
[else (app (parse (first s-expr)) (second s-expr))])]))

(define (interp expr en store)
(type-case SCFWAE expr
...
[app (fun-expr arg-expr)
(type-case Value*Store (interp fun-expr en store)
[v*s (fun-value fun-store)
(let ((arg-loc (env-lookup arg-expr en)))
(interp
(closure-body fun-value)
(anEnv (closure-param fun-value) arg-loc (closure-env fun-value))
fun-store))])]
...))

Idea: Call functions with symbol, not with expression. Bind function parameter in environment to the store location of the passed symbol.
10. Explain the difference between call-by-value and call-by-reference.

Call-by-value: A copy of the argument value is passed to the function; if the function modifies its parameter identifier, this has no effect outside the function.

Call-by-reference: A "pointer" to the argument value is passed to the function; if the function modifies its parameter identifier, the argument value (outside the function) is modified, too.
11. Explain the difference between the extent of values and the scope of variables.

Scope of a variable is the lexically determined region, in which the variable is bound to a store location (and transitively, a value).

Extent of a value is the possibly infinite area in a program, at which a value is retrievable from the store, providing it's location. Due to the possiblity of modifying variables and calling by-reference, the extent of a value can be larger than the scope of the variable it was originally assigned to.
12. What is L-value? Give an example of it. What is special about its evaluation?

An L-value is a value to which another value is assigned (mostly written on the left-hand side, thus "L"-value). An example is a box, assignable by {setbox ...}. An L-value not fully evaluated but only to the point where the storage location of it's value is determined, as only the storage location is needed to update the L-value.