today is a special day
biggest this is the last lecture of
the FB 10 long axe series
on functional programming I hope that you enjoy it
their rides an and that your learnt
how to apply the ideas of your functional programming
and Haskell to am
your own programming language that you use at work there's one thing
that we have gonna wave their hands
about and that is lazy valuation
and lazy evaluation is also something that is
can have unique to Haskell there are other languages like Scala
that do have some form of lazy evaluation
but the interesting thing about hash
saw is dat everything
uses lazy evaluation an unless
unless you make think strict an
that's the an topic of this lecture
is to give you a little bit of an introduction
about the various possible evaluation strategies
an for functional programs okay
so up to now we have not
really looked at all at the details of how expressions are evaluated
we've done re-evaluations on the
on the slides where we gonna be all unfold the definitions and strong
but we have not made distinct breach
and an actually
haskell expressions are evaluated with the fairly simple strategy
okay and the idea is dead its
lazy and think about you being a lazy person
and that prototypical example is doing the dishes
alright I hate doing the dishes so I want to avoid
am unnecessary evaluation
alright so I want to only
washer dish when it absolutely necessary
now doing this lazy evaluation
allows us to program wit internet data structures
because we're never doing more were
than necessary show even if you give me an
infinite list an infinite stack
of dishes if I'm sufficiently lazy
I will only wash as many as I need so I'll
huh you cannot catch me with that and the other thing that we'll see
is lazy valuation makes it easier to compose programs
because it there's never more work done
than necessary and and this
this evaluation strategy is why
haskell is called a lazy language
and that should get some concrete examples
and and what we do to evaluate the Haskell program
is to take and ship expression
if we are evaluating a big expression
for taking a ship expression there and we are gonna
you know and evaluating that Sep expression and in this case
say that we have function definition square and
is and times an now if we have an expression
like dat square three-plus for then
we can evaluate dish in two ways
Wong is to first evaluate
three press for 27 and then we used the definition of square
substitute 74 and then we get seven times seven
and then we evaluated to get forty-nine
but another evaluation strategy
is also DJ well we take square
up to replace for we ship she did
three-plus for for ensure we get three plus for here
and replace for here and then you know
we
and evaluate the results and we get
the same value in that case
you might think ho but now we have evaluated
three-plus for twice and as we will see
ass girl has some smart wage to avoid
duplicating dat competition
well should get the first I am
champ although they have the first thread EJ showy and
first evaluate three-plus for to get this event
and we substitute the definition of square
so and he got seven so we get seven times seven and we get forty-nine
now let's do it the other way around
we take this expression we
instantiate and red three-plus for so we get to replace for dont replace for
now we execute this guy 27 we execute that guy
27 and we get 49 K
so in this case we have first applied square
before doing the addition but the nice thing
is that the final result is the same and
not imagine that there were side effects
in this God well in that case is we're doing the valuation
different orders this side effects might happen in different order
and the result might be different but century here
in the bureau world it doesn't matter in WAT
order you do these reductions K
so thats a fact
about haskell that if there are two different ways
that bodes terminate to evaluate
the same expression then these will always give
the same final result and that makes it all so easy to
got every factor has school programs because you can again you can always
assisted you don't miss our state's independent
of where they appear and thats because of this
property
now we've seen to
strategies to reduce our program and
let's talk about that anymore
and general sense so what we do
is when we're evaluating expression there might be many choices
up some expressions that we can re jus
and we have seen in this very small example we've seen is already
be good either first applied the definition of square
or we could first an do the arithmetic
on the arguments K so
there are two basic strategies
to decide rich of the expres
of all possible expressions to choose and the wrong
is in our most reduction which as
the innermost expression that can be reduced as always
be reduced and then there's the how to Russ reduction where you take
the outermost expression to be reduced and of course you can say
since this rule we can also do random execution we can bake
Andy expression to be reduced
but that's not very systematic right and that makes a guy now
heart to re yeah it's got nice
to have it fixed strategy such that we can reason about
its properties and that's a look
at am this example here where we have a weird
recursive definitions we define
nope to take detail up from nope
now what does that mean well first a ball
image that loop must have typed list
all right and I'm sure we take detail of the less so this is a list that chases
its own tail
and thats evaluate the expression
give me the first of the bear
Wong and loop and lets
compare and contrast the STU reduction strategies
noticed that when we
now reduce this guy loop
it cost a lovely hope so let's hope she did look so we get they lost a loved a
love Dale
so this action this thing actually chases its tail
and it will never gonna do. finds an actual list
again they could enjoy as well nope but
let's look at this guy so D enormous reduction
takes the in our most reducible expression
and reduces that to end this expression here the
in almost three years ago expression is nope so we
expand
nope and detailed nope now nope
is again the innermost expression and then we executed
so this will not terminate to deceive valuation order
ish too strict it got a large rise to evaluate
the argument here of first
it inside this dot ball and then
that diverges and there's no chance that we can
take the first up this pair nah let's look at the outermost reduction
so in that case we take the outermost
reducible expression thats first it supplied
28 up all which is have reduced by extraction so first of
it double a NB is a
it's wrong and we're done alright so this strategy
gauges the result in one step whereas the
enormous reduction would never terminate okay what r
some facts here is dead the outermost reduction
may give the result when the innermost reduction
fails to terminate and this is what we have seen and
and the second fact is that
if there's if for an expression there exists
a sequence that terminates then the
out there must most reduction also terminate okay
and it will return with the same result so if there
is any reduction sequence that terminates the
outermost reduction will always altered art nature dead
your kitchen strong hint that's the
are demolished strategy is not a bad thing
okay if they're is anyway did this thing will read
return a value an in finite time
the outermost reduction will also terminate now let's look at
another a few other examples offender most
outermost reduction an and
maybe we gonna be a that will a.m.
throw some docs on the an
outermost reduction and this is our familiar example
an which where if we do the innermost reduction
we do three plus for 7 seven times seven
49 so this is done in now
Wong to three steps but if we do the outermost reduction
weird duplicating that reducible expression three bills for
so we're doing the work twice okay
so that's a fact
that outermost reduction may require more steps
then enormous reduction but as we have seen sometimes
enormous reduction will not terminate yes the crucial question
is their way to have our cake
and he did too and it turns out that
Darrius and their way
we solve this problem is by using sharing
so and when we Sep said you'd
three-plus for into the definition of square
we don't just copy that expression to replace for
but we share it show we have pointers
do that expression said shit when we reduces once
reader 27 and now the results are shared
and then we get 49
alright and at shirt lazy evaluation s
lazy evaluation is outermost reduction
love sharing so lazy evaluation
it's like having your cake and eating it too
and Haskell uses lazy
valuation here's another example of
an that shows the advantages up lazy evaluation
am by the finding am a
recursive type of list rigors of value
I should say of Leicester this is of course a recursive type but we're
looking here
as a recursive value so read the find a listing
infinite list of in once as
wong's owns wants so that unfold the recurve a couple of time so we see that
launches ones guam's launch
and fold it again so we get loans goes wrong gone wrong
et cetera et cetera so wont
is and list of what now let's look at:
evaluation of had of one's okay
and what we want to do as we want to compare and contrast
in our March devaluation with lazy evaluation and you can already guess
what will happen when we use in a marked reduction this is again the same example
with loop so we are taking the in the most reusable expression which is once
be unfolded we unfolded be unfolded
so we never get around to taking the head
of that list whereas this list is already
in the shape where we can take it okay sure does internet
wears every year lazy evaluation Heather once
well that's still not reduce ball so we have to unfold this guy so we get Wong
homes once nah we can do this
and we're done okay to end this case
the result ish 1
general let the slogan up lazy evaluation
think of doing the dishes is we're doing
just enough work as required
to and for jews the final result
K as a really when we say that wong's
isn't infinite list are gonna lying because once is not an infinite lest
is a potentially infinite list only when
you know it's gonna I'll X bomb that on the mom and has not
exponent eagerly to an infinitely show it's just the rest should be
to create an infinite list and if you would do dish
in a strict language what typically happens issue which day
this Wong is defiant using some form
of at sunk show you put in a unit arrow somewhere
to stop the valuation be guessed that French unit arrow
is already value now let's look at the next example here
be mentioned that and lazy evaluation makes code
more modular and the region is dead it's because
it does just enough evaluation to gonna
are make the next step so let's look at
take five once that
will return a list of 5 once
okay and once is really the same
as you know this expression here the International want
and that also returns from lunch
and again the region is dead we have seen that take was defined by induction
over the structure the list so every time that you know once
better matching better matches on that list is
evaluated just enough to gonna yar
get the next value such that we nicely
terminate an here so this is the end of Part two
about lazy evaluation and see you in a few minutes