Exam Check-List: Discussion on Part 04 - Lazy Evaluation

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

Exam Check-List: Discussion on Part 04 - Lazy Evaluation

Hi,

below my solution to the fourth topic of the exam check-list (-> spoiler alert...).

Best,
Felix

1. What is the difference between call-by-name and call-by need?

Call-by-name: Argument expression provided to a function is evaluated within the function whenever it is needed (possibly multiple times).

Call-by-need: Argument expression provided to a function is evaluated at most once, and then the result is cached for further uses.
2. Explain the implementation strategy of lazy evaluation. How does it solve the efﬁciency problems of lazy substitution?

Only evaluate expressions at pre-defined strict points and use expression closures to carry the define-time environment along with the later-to-be-evaluated expressions. Solve efficiency of lazy substitution by substitution caches that remember (via mutable values, e.g., boxes) the value of an expression, once computed.
3. Given two programs (with erroneous subexpressions), tell which of them fail under a lazy and eager evaluation regime, respectively.

a)

Code: Alles auswählen

{with {x y} {if0 0 1 x}}

Fails with eager evaluation (as y is undefined), but returns 1 with lazy evaluation (as x's bound expression is never evaluated).

b)

Code: Alles auswählen

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

Fails with lazy evaluation, as y is calculated with x set to 0, but returns 2 with eager evalution (as division is performed immediately while x = 1.
4. Give an example program where lazy evaluation is more efﬁcient than eager evaluation (evaluates in less steps). Explain why.

Code: Alles auswählen

{with {x {+ 1 1}} 1}

With lazy evaluation, the value of x is never computed (as never used), so it save one step for the addition.
5. Given a program, tell what is it computational complexity under a lazy and eager evaluation regime, respectively.

Code: Alles auswählen

{with {x {+ 1 1}} 1}

Lazy evaluation: 2 steps (process with, output 1)

Eager evaluation: 3 steps (process with, therefor evaluate named expression "{+ 1 1}", output 1)
6. Explain the difference between lazy evaluation and memoization.

Lazy evaluation caches the evaluated value of some expression currently bound in the environment.

Memoization remembers the result of a function for a specific (set of) argument(s) (e.g., in a hash table), even between function calls in unrelated sub-expressions.
7. Explain the problems of using lazy evaluation in combination with mutable state.

With mutable state, the value of some expression may change between definition and usage, thus lazy evaluation leads here to a changed (and thus incorrect) value, as mutable values are evaluated at usage time, not at definition time (as with eager evaluation).
8. Given a fragment of an interpreter tell whether it implements lazy or eager evaluation. How do you recognize it?

Code: Alles auswählen

(define (interp expr en)
(type-case CFWAE/L expr
...
[with (bound-id named-expr bound-body)
(interp
bound-body (anEnv bound-id (eclosure named-expr en) en))]
...
[app (fun-expr arg-expr)
(local ([define fun-value (interp fun-expr en)])
(interp
(fclosure-body fun-value)
(anEnv
(fclosure-param fun-value)
(eclosure arg-expr en)
(fclosure-env fun-value))))]))

Interpreter implements lazy evaluation, as the binding in [with ...] clause is stored in an expression closure, where the named-expr is not directly evaluated, but kept for later, lazy evaluation. Similarly, on function application, the arg-expr is not interpreted but passed as-is in an expression closure.
9. Given an interpreter fragment implementing lazy evaluation, ﬁnd an error and ﬁx it.

Code: Alles auswählen

; cached lazy evaluation
(define (interp expr en)
(type-case CFWAE/L expr
[num (n) (numb n)]
[add (l r) (numb (+ (numb-n (strict (interp l en))) (numb-n (strict (interp r en)))))]
[sub (l r) (numb (- (numb-n (strict (interp l en))) (numb-n (strict (interp r en)))))]
[with (bound-id named-expr bound-body)
(interp
bound-body (anEnv bound-id (eclosure (strict (interp named-expr en)) en (box false)) en))]
[id (v) (strict (lookup v en))]
[fun (arg body) (fclosure arg body en)]
[if0 (test-expr then-expr else-expr)
(if (zero? (numb-n (interp test-expr en)))
(interp then-expr en)
(interp else-expr en))]
[app (fun-expr arg-expr)
(local ([define fun-value (strict (interp fun-expr en))])
(interp
(fclosure-body fun-value)
(anEnv
(fclosure-param fun-value)
(eclosure arg-expr en (box false))
(fclosure-env fun-value))))]))

a) [with ...] clause: named-expr should not be strictly evaluated here, but kept as-is for later lazy evaluation, if needed
b) [if0 ...] clause: strict evaluation of test-expr is needed.
10. What is stored in expression closures? Why they are necessary?

An expression closure stores (beside the expression) the environment in which the expression shall be evaluted, i.e., the definition-time environment. This is needed, as the environment possibly has changed where the expression is needed, but it should not be evaluated in the new, changed environment, but in the environment at definition time.
11. Describe the environment (including function and expression closures) at certain points in the given program, assuming an interpreter with lazy evaluation.

Code: Alles auswählen

{with {x {+ 1 2}} {with {f {fun {y} {+ x y}}} {f 0}}}

Directly before evaluation of "{f 0}", the environment looks like this:

Code: Alles auswählen

  env = (
x -> (eclosure: expr={+ 1 2}, env=emptyEnv),
f -> (fclosure: param=y, body={+ x y}, env=( x -> (eclosure: expr={+ 1 2}, env=emptyEnv) ) )
)

12. Given a deﬁnition of an inﬁnite list, compute its ﬁrst n elements. What sequence does it implement? What is the program’s computational complexity?

Code: Alles auswählen

foo = 2 : zipWith (*) foo foo

Implements the sequence (a_i) with a_0 = 2 and a_i+1 = a_i^2. Complexity is linear.
13. Implement an inﬁnite list according the given speciﬁcation.

Implement an infinit fibonacci list.

Code: Alles auswählen

fib = 0 : 1 : zipWith (+) fib (tail fib)

14. Given a function implementation, explain why it would not work with inﬁnite lists. Fix it.

Code: Alles auswählen

fun [] = []
fun (x:y:rest) = (x+1) : (y+1) : (fun rest)

bar = 1 : (fun bar)

Now "bar" doesn't work as infinite list, because "fun" needs the first two elements to compute it's result, but the second element of "bar" first has to be computed by "fun" -- so we have an infinite cycle resulting to, e.g., "take" queries to "bar" never terminating.

Can be fixed like this:

Code: Alles auswählen

fun [] = []
fun (x:rest) = (x+1) : (fun rest)

15. Given a function implementation (e.g., from list to list, or to string to string), ﬁx it so that it produces the output incrementally.

@Andreas: I don't understand this task (maybe it's too late... ), could you provide an example?
Zuletzt geändert von FeG am 23. Aug 2012 15:43, insgesamt 1-mal geändert.

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: Exam Check-List: Discussion on Part 04 - Lazy Evaluation

FeG hat geschrieben:2. Explain the implementation strategy of lazy evaluation. How does it solve the efﬁciency problems of lazy substitution?

Only evaluate expressions at pre-defined strict points and use expression closures to carry the define-time environment along with the later-to-be-evaluated expressions. Solve efficiency of lazy substitution by substitution caches that remember (via mutable values, e.g., boxes) the value of an expression, once computed.
Please don't confuse substitution caches (a synonym for environments used in the first lectures, prior to the introduction of closures) with an expression closure's cache.

Also (not directly related to the above question), think about the difference between function closures (fclosures) and expression closures (eclosures). Which cases in the interpreter (num, add, fun, app, etc.) return which kind of closure? Which kind of closure keeps previously computed values in the case of caching and which closure keeps them in the case of memoization? And how many values are kept per fclosure and eclosure, respectively?

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: Exam Check-List: Discussion on Part 04 - Lazy Evaluation

FeG hat geschrieben:15. Given a function implementation (e.g., from list to list, or to string to string), ﬁx it so that it produces the output incrementally.

@Andreas: I don't understand this task (maybe it's too late... ), could you provide an example?
OK, what you want to do is being able to issue a call like head (f xs) without computing the entire result list (f xs) just to get at its first element. In some cases like f = reverse this is not possible, but in other cases it is.

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

Re: Exam Check-List: Discussion on Part 04 - Lazy Evaluation

sewe hat geschrieben:OK, what you want to do is being able to issue a call like head (f xs) without computing the entire result list (f xs) just to get at its first element. In some cases like f = reverse this is not possible, but in other cases it is.
Well, I understood what's meant, however only rather contrived examples come to my mind (except for the combine vs. combine2 task 5 from ex. 2012-05-11), e.g., this one:

Code: Alles auswählen

fun :: (Num a) => [a] -> [a] -> [a]
fun [] _ = []
fun _ [] = []
fun (x1:x2:xs) (y1:y2:ys) = (x1+y1) : (x2+y2) : (fun xs ys)

Fixed (doesn't need to evaluate 2 elements of xs and ys for a head (fun xs ys) call:

Code: Alles auswählen

fun :: (Num a) => [a] -> [a] -> [a]
fun [] _ = []
fun _ [] = []
fun (x:xs) (y:ys) = (x+y) : (fun xs ys)


sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: Exam Check-List: Discussion on Part 04 - Lazy Evaluation

FeG hat geschrieben:Well, I understood what's meant, however only rather contrived examples come to my mind (except for the combine vs. combine2 task 5 from ex. 2012-05-11)
I admit that it's not trivial to come up examples. One way to construct one would be a version of the function that requires length l to be known and another that doesn't, but again that's rather contrived.

AlexanderF
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Exam Check-List: Discussion on Part 04 - Lazy Evaluation

FeG hat geschrieben:
b)

Code: Alles auswählen

  {with {x {newbox 1}} {with {y {/ 2 x}} {seqn {set x 0} y}}}

Fails with lazy evaluation, as y is calculated with x set to 0, but returns 2 with eager evalution (as division is performed immediately while x = 1.
I think you mixes mutating via container and direct mutating of identifier.

I think you should write

Code: Alles auswählen

{with {x 1} {with {y {/ 2 x}} {seqn {set x 0} y}}}
or

Code: Alles auswählen

{with {x {newbox 1}} {with {y {/ 2 {openbox x}}} {seqn {setbox x 0} y}}}

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

Re: Exam Check-List: Discussion on Part 04 - Lazy Evaluation

AlexanderF hat geschrieben:I think you mixes mutating via container and direct mutating of identifier.
You're right. Both of your variants do the job I wanted to illustrate. For shortness I chose the first one using variables and changed my first post. Thanks.

AlexanderF
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

no problem