Lazy Evaluation Flashcards
describe Haskell evaluation
> avoids unnecessary evaluation
allows programs to be modular
allows programming with infinite lists
what is Haskell the only fp language to use?
Lazy Evaluation
how are expressions evaluated?
by successively expanding definitions by evaluation / reducing redexes until no further simplification is possible.
what is a redex?
a reducible expression
how do you reduce a 𝛿-redex?
by expanding a definition
e.g. square(7) -> 7*7
how do you reduce a β-redex?
(\x.b[x])(a) -> b[x]
e.g. if + = \xy. … then reducing 3 + 4 involves β-reduction
Church-Rosser theorem
if e evaluates to e1 and e2, then there exists an expression e’ such that e1 and e2 both evaluate to e’
Church-Rosser properties
the final result of evaluating an expression is independent on the evaluation order.
In Haskell, 2 different ways of evaluating the same expression will always give the same final result
What is Innermost reduction?
always selecting the innermost redex to reduce. (call by value)
What is Outermost reduction?
always selecting the outermost redex to reduce. (call by name)
what are the advantages of Outermost reduction over Innermost reduction?
outermost may give a result where innermost fails to terminate.
for any expression, if there exists and reduction sequence that terminates, then the outermost reduction will also terminate with the same result.
what are the disadvantages of outermost reduction? what is the solution?
it may require more steps.
solved using sharing.
what is sharing?
using pointers to indicate sharing of expressions during evaluation
What is Lazy Evaluation made up of?
outermost reduction + sharing
