1
00:00:01,969 --> 00:00:04,500
today is a special day

2
00:00:04,500 --> 00:00:07,669
biggest this is the last lecture of

3
00:00:07,669 --> 00:00:11,540
the FB 10 long axe series

4
00:00:11,540 --> 00:00:15,690
on functional programming I hope that
you enjoy it

5
00:00:15,690 --> 00:00:19,960
their rides an and that your learnt

6
00:00:19,960 --> 00:00:24,510
how to apply the ideas of your
functional programming

7
00:00:24,510 --> 00:00:28,680
and Haskell to am

8
00:00:28,680 --> 00:00:33,680
your own programming language that you
use at work there's one thing

9
00:00:33,680 --> 00:00:36,980
that we have gonna wave their hands

10
00:00:36,980 --> 00:00:40,489
about and that is lazy valuation

11
00:00:40,489 --> 00:00:44,190
and lazy evaluation is also something
that is

12
00:00:44,190 --> 00:00:49,039
can have unique to Haskell there are
other languages like Scala

13
00:00:49,039 --> 00:00:52,340
that do have some form of lazy
evaluation

14
00:00:52,340 --> 00:00:55,420
but the interesting thing about hash

15
00:00:55,420 --> 00:00:58,579
saw is dat everything

16
00:00:58,579 --> 00:01:01,989
uses lazy evaluation an unless

17
00:01:01,989 --> 00:01:05,030
unless you make think strict an

18
00:01:05,030 --> 00:01:10,409
that's the an topic of this lecture

19
00:01:10,409 --> 00:01:13,590
is to give you a little bit of an
introduction

20
00:01:13,590 --> 00:01:17,030
about the various possible evaluation
strategies

21
00:01:17,030 --> 00:01:22,270
an for functional programs okay

22
00:01:22,270 --> 00:01:26,290
so up to now we have not

23
00:01:26,290 --> 00:01:32,540
really looked at all at the details of
how expressions are evaluated

24
00:01:32,540 --> 00:01:36,570
we've done re-evaluations on the

25
00:01:36,570 --> 00:01:40,590
on the slides where we gonna be all
unfold the definitions and strong

26
00:01:40,590 --> 00:01:43,990
but we have not made distinct breach

27
00:01:43,990 --> 00:01:48,869
and an actually

28
00:01:48,869 --> 00:01:53,460
haskell expressions are evaluated with
the fairly simple strategy

29
00:01:53,460 --> 00:01:56,729
okay and the idea is dead its

30
00:01:56,729 --> 00:02:00,799
lazy and think about you being a lazy
person

31
00:02:00,799 --> 00:02:05,340
and that prototypical example is doing
the dishes

32
00:02:05,340 --> 00:02:09,879
alright I hate doing the dishes so I
want to avoid

33
00:02:09,879 --> 00:02:14,040
am unnecessary evaluation

34
00:02:14,040 --> 00:02:16,739
alright so I want to only

35
00:02:16,739 --> 00:02:20,249
washer dish when it absolutely necessary

36
00:02:20,249 --> 00:02:25,159
now doing this lazy evaluation

37
00:02:25,159 --> 00:02:29,329
allows us to program wit internet data
structures

38
00:02:29,329 --> 00:02:32,370
because we're never doing more were

39
00:02:32,370 --> 00:02:36,489
than necessary show even if you give me
an

40
00:02:36,489 --> 00:02:40,239
infinite list an infinite stack

41
00:02:40,239 --> 00:02:43,359
of dishes if I'm sufficiently lazy

42
00:02:43,359 --> 00:02:47,439
I will only wash as many as I need so
I'll

43
00:02:47,439 --> 00:02:52,239
huh you cannot catch me with that and
the other thing that we'll see

44
00:02:52,239 --> 00:02:56,260
is lazy valuation makes it easier to
compose programs

45
00:02:56,260 --> 00:03:00,040
because it there's never more work done

46
00:03:00,040 --> 00:03:03,840
than necessary and and this

47
00:03:03,840 --> 00:03:06,969
this evaluation strategy is why

48
00:03:06,969 --> 00:03:10,060
haskell is called a lazy language

49
00:03:10,060 --> 00:03:13,359
and that should get some concrete
examples

50
00:03:13,359 --> 00:03:17,519
and and what we do to evaluate the
Haskell program

51
00:03:17,519 --> 00:03:22,319
is to take and ship expression

52
00:03:22,319 --> 00:03:25,389
if we are evaluating a big expression

53
00:03:25,389 --> 00:03:28,540
for taking a ship expression there and
we are gonna

54
00:03:28,540 --> 00:03:33,150
you know and evaluating that Sep
expression and in this case

55
00:03:33,150 --> 00:03:36,689
say that we have function definition
square and

56
00:03:36,689 --> 00:03:41,699
is and times an now if we have an
expression

57
00:03:41,699 --> 00:03:45,759
like dat square three-plus for then

58
00:03:45,759 --> 00:03:49,340
we can evaluate dish in two ways

59
00:03:49,340 --> 00:03:53,400
Wong is to first evaluate

60
00:03:53,400 --> 00:03:58,590
three press for 27 and then we used the
definition of square

61
00:03:58,590 --> 00:04:03,500
substitute 74 and then we get seven
times seven

62
00:04:03,500 --> 00:04:06,750
and then we evaluated to get forty-nine

63
00:04:06,750 --> 00:04:09,949
but another evaluation strategy

64
00:04:09,949 --> 00:04:13,400
is also DJ well we take square

65
00:04:13,400 --> 00:04:16,570
up to replace for we ship she did

66
00:04:16,570 --> 00:04:19,769
three-plus for for ensure we get three
plus for here

67
00:04:19,769 --> 00:04:22,889
and replace for here and then you know

68
00:04:22,889 --> 00:04:23,830
we

69
00:04:23,830 --> 00:04:28,189
and evaluate the results and we get

70
00:04:28,189 --> 00:04:31,310
the same value in that case

71
00:04:31,310 --> 00:04:35,280
you might think ho but now we have
evaluated

72
00:04:35,280 --> 00:04:38,879
three-plus for twice and as we will see

73
00:04:38,879 --> 00:04:41,990
ass girl has some smart wage to avoid

74
00:04:41,990 --> 00:04:45,229
duplicating dat competition

75
00:04:45,229 --> 00:04:48,699
well should get the first I am

76
00:04:48,699 --> 00:04:52,110
champ although they have the first
thread EJ showy and

77
00:04:52,110 --> 00:04:55,560
first evaluate three-plus for to get
this event

78
00:04:55,560 --> 00:04:58,690
and we substitute the definition of
square

79
00:04:58,690 --> 00:05:02,889
so and he got seven so we get seven
times seven and we get forty-nine

80
00:05:02,889 --> 00:05:06,069
now let's do it the other way around

81
00:05:06,069 --> 00:05:09,930
we take this expression we

82
00:05:09,930 --> 00:05:16,099
instantiate and red three-plus for so we
get to replace for dont replace for

83
00:05:16,099 --> 00:05:20,460
now we execute this guy 27 we execute
that guy

84
00:05:20,460 --> 00:05:23,569
27 and we get 49 K

85
00:05:23,569 --> 00:05:27,699
so in this case we have first applied
square

86
00:05:27,699 --> 00:05:31,960
before doing the addition but the nice
thing

87
00:05:31,960 --> 00:05:35,719
is that the final result is the same and

88
00:05:35,719 --> 00:05:38,930
not imagine that there were side effects

89
00:05:38,930 --> 00:05:43,449
in this God well in that case is we're
doing the valuation

90
00:05:43,449 --> 00:05:47,319
different orders this side effects might
happen in different order

91
00:05:47,319 --> 00:05:51,039
and the result might be different but
century here

92
00:05:51,039 --> 00:05:54,569
in the bureau world it doesn't matter in
WAT

93
00:05:54,569 --> 00:05:59,099
order you do these reductions K

94
00:05:59,099 --> 00:06:02,169
so thats a fact

95
00:06:02,169 --> 00:06:06,990
about haskell that if there are two
different ways

96
00:06:06,990 --> 00:06:10,699
that bodes terminate to evaluate

97
00:06:10,699 --> 00:06:14,409
the same expression then these will
always give

98
00:06:14,409 --> 00:06:18,279
the same final result and that makes it
all so easy to

99
00:06:18,279 --> 00:06:22,389
got every factor has school programs
because you can again you can always

100
00:06:22,389 --> 00:06:26,389
assisted you don't miss our state's
independent

101
00:06:26,389 --> 00:06:30,180
of where they appear and thats because
of this

102
00:06:30,180 --> 00:06:34,960
property

103
00:06:34,960 --> 00:06:36,590
now we've seen to

104
00:06:36,590 --> 00:06:40,290
strategies to reduce our program and

105
00:06:40,290 --> 00:06:43,500
let's talk about that anymore

106
00:06:43,500 --> 00:06:46,650
and general sense so what we do

107
00:06:46,650 --> 00:06:51,760
is when we're evaluating expression
there might be many choices

108
00:06:51,760 --> 00:06:55,430
up some expressions that we can re jus

109
00:06:55,430 --> 00:06:59,850
and we have seen in this very small
example we've seen is already

110
00:06:59,850 --> 00:07:03,120
be good either first applied the
definition of square

111
00:07:03,120 --> 00:07:06,910
or we could first an do the arithmetic

112
00:07:06,910 --> 00:07:09,940
on the arguments K so

113
00:07:09,940 --> 00:07:13,090
there are two basic strategies

114
00:07:13,090 --> 00:07:16,620
to decide rich of the expres

115
00:07:16,620 --> 00:07:20,890
of all possible expressions to choose
and the wrong

116
00:07:20,890 --> 00:07:25,440
is in our most reduction which as

117
00:07:25,440 --> 00:07:29,590
the innermost expression that can be
reduced as always

118
00:07:29,590 --> 00:07:34,550
be reduced and then there's the how to
Russ reduction where you take

119
00:07:34,550 --> 00:07:39,430
the outermost expression to be reduced
and of course you can say

120
00:07:39,430 --> 00:07:44,780
since this rule we can also do random
execution we can bake

121
00:07:44,780 --> 00:07:47,830
Andy expression to be reduced

122
00:07:47,830 --> 00:07:52,070
but that's not very systematic right and
that makes a guy now

123
00:07:52,070 --> 00:07:55,669
heart to re yeah it's got nice

124
00:07:55,669 --> 00:07:59,230
to have it fixed strategy such that we
can reason about

125
00:07:59,230 --> 00:08:03,210
its properties and that's a look

126
00:08:03,210 --> 00:08:07,650
at am this example here where we have a
weird

127
00:08:07,650 --> 00:08:10,970
recursive definitions we define

128
00:08:10,970 --> 00:08:14,919
nope to take detail up from nope

129
00:08:14,919 --> 00:08:18,720
now what does that mean well first a
ball

130
00:08:18,720 --> 00:08:21,990
image that loop must have typed list

131
00:08:21,990 --> 00:08:27,460
all right and I'm sure we take detail of
the less so this is a list that chases

132
00:08:27,460 --> 00:08:28,370
its own tail

133
00:08:28,370 --> 00:08:32,400
and thats evaluate the expression

134
00:08:32,400 --> 00:08:35,719
give me the first of the bear

135
00:08:35,719 --> 00:08:39,010
Wong and loop and lets

136
00:08:39,010 --> 00:08:42,849
compare and contrast the STU reduction
strategies

137
00:08:42,849 --> 00:08:44,740
noticed that when we

138
00:08:44,740 --> 00:08:47,960
now reduce this guy loop

139
00:08:47,960 --> 00:08:52,880
it cost a lovely hope so let's hope she
did look so we get they lost a loved a

140
00:08:52,880 --> 00:08:53,620
love Dale

141
00:08:53,620 --> 00:08:57,220
so this action this thing actually
chases its tail

142
00:08:57,220 --> 00:09:01,250
and it will never gonna do. finds an
actual list

143
00:09:01,250 --> 00:09:05,480
again they could enjoy as well nope but

144
00:09:05,480 --> 00:09:08,990
let's look at this guy so D enormous
reduction

145
00:09:08,990 --> 00:09:12,820
takes the in our most reducible
expression

146
00:09:12,820 --> 00:09:16,110
and reduces that to end this expression
here the

147
00:09:16,110 --> 00:09:20,130
in almost three years ago expression is
nope so we

148
00:09:20,130 --> 00:09:23,290
expand

149
00:09:23,290 --> 00:09:26,740
nope and detailed nope now nope

150
00:09:26,740 --> 00:09:30,960
is again the innermost expression and
then we executed

151
00:09:30,960 --> 00:09:35,400
so this will not terminate to deceive
valuation order

152
00:09:35,400 --> 00:09:39,470
ish too strict it got a large rise to
evaluate

153
00:09:39,470 --> 00:09:42,560
the argument here of first

154
00:09:42,560 --> 00:09:46,180
it inside this dot ball and then

155
00:09:46,180 --> 00:09:49,830
that diverges and there's no chance that
we can

156
00:09:49,830 --> 00:09:56,070
take the first up this pair nah let's
look at the outermost reduction

157
00:09:56,070 --> 00:10:00,120
so in that case we take the outermost

158
00:10:00,120 --> 00:10:03,930
reducible expression thats first it
supplied

159
00:10:03,930 --> 00:10:08,280
28 up all which is have reduced by
extraction so first of

160
00:10:08,280 --> 00:10:11,310
it double a NB is a

161
00:10:11,310 --> 00:10:15,680
it's wrong and we're done alright so
this strategy

162
00:10:15,680 --> 00:10:19,540
gauges the result in one step whereas
the

163
00:10:19,540 --> 00:10:25,680
enormous reduction would never terminate
okay what r

164
00:10:25,680 --> 00:10:29,910
some facts here is dead the outermost
reduction

165
00:10:29,910 --> 00:10:33,710
may give the result when the innermost
reduction

166
00:10:33,710 --> 00:10:37,340
fails to terminate and this is what we
have seen and

167
00:10:37,340 --> 00:10:40,860
and the second fact is that

168
00:10:40,860 --> 00:10:46,050
if there's if for an expression there
exists

169
00:10:46,050 --> 00:10:49,150
a sequence that terminates then the

170
00:10:49,150 --> 00:10:53,220
out there must most reduction also
terminate okay

171
00:10:53,220 --> 00:10:56,990
and it will return with the same result
so if there

172
00:10:56,990 --> 00:11:00,490
is any reduction sequence that
terminates the

173
00:11:00,490 --> 00:11:03,950
outermost reduction will always altered
art nature dead

174
00:11:03,950 --> 00:11:07,089
your kitchen strong hint that's the

175
00:11:07,089 --> 00:11:10,709
are demolished strategy is not a bad
thing

176
00:11:10,709 --> 00:11:14,790
okay if they're is anyway did this thing
will read

177
00:11:14,790 --> 00:11:18,800
return a value an in finite time

178
00:11:18,800 --> 00:11:25,339
the outermost reduction will also
terminate now let's look at

179
00:11:25,339 --> 00:11:29,810
another a few other examples offender
most

180
00:11:29,810 --> 00:11:32,830
outermost reduction an and

181
00:11:32,830 --> 00:11:36,240
maybe we gonna be a that will a.m.

182
00:11:36,240 --> 00:11:39,390
throw some docs on the an

183
00:11:39,390 --> 00:11:44,490
outermost reduction and this is our
familiar example

184
00:11:44,490 --> 00:11:49,350
an which where if we do the innermost
reduction

185
00:11:49,350 --> 00:11:53,279
we do three plus for 7 seven times seven

186
00:11:53,279 --> 00:11:56,540
49 so this is done in now

187
00:11:56,540 --> 00:12:01,180
Wong to three steps but if we do the
outermost reduction

188
00:12:01,180 --> 00:12:06,440
weird duplicating that reducible
expression three bills for

189
00:12:06,440 --> 00:12:10,190
so we're doing the work twice okay

190
00:12:10,190 --> 00:12:13,550
so that's a fact

191
00:12:13,550 --> 00:12:17,920
that outermost reduction may require
more steps

192
00:12:17,920 --> 00:12:22,300
then enormous reduction but as we have
seen sometimes

193
00:12:22,300 --> 00:12:28,540
enormous reduction will not terminate
yes the crucial question

194
00:12:28,540 --> 00:12:31,810
is their way to have our cake

195
00:12:31,810 --> 00:12:35,370
and he did too and it turns out that

196
00:12:35,370 --> 00:12:38,540
Darrius and their way

197
00:12:38,540 --> 00:12:42,190
we solve this problem is by using
sharing

198
00:12:42,190 --> 00:12:45,620
so and when we Sep said you'd

199
00:12:45,620 --> 00:12:49,459
three-plus for into the definition of
square

200
00:12:49,459 --> 00:12:53,980
we don't just copy that expression to
replace for

201
00:12:53,980 --> 00:12:58,020
but we share it show we have pointers

202
00:12:58,020 --> 00:13:02,850
do that expression said shit when we
reduces once

203
00:13:02,850 --> 00:13:07,550
reader 27 and now the results are shared

204
00:13:07,550 --> 00:13:10,529
and then we get 49

205
00:13:10,529 --> 00:13:13,510
alright and at shirt lazy evaluation s

206
00:13:13,510 --> 00:13:16,960
lazy evaluation is outermost reduction

207
00:13:16,960 --> 00:13:20,070
love sharing so lazy evaluation

208
00:13:20,070 --> 00:13:24,390
it's like having your cake and eating it
too

209
00:13:24,390 --> 00:13:27,700
and Haskell uses lazy

210
00:13:27,700 --> 00:13:31,459
valuation here's another example of

211
00:13:31,459 --> 00:13:35,940
an that shows the advantages up lazy
evaluation

212
00:13:35,940 --> 00:13:39,490
am by the finding am a

213
00:13:39,490 --> 00:13:43,440
recursive type of list rigors of value

214
00:13:43,440 --> 00:13:47,010
I should say of Leicester this is of
course a recursive type but we're

215
00:13:47,010 --> 00:13:47,730
looking here

216
00:13:47,730 --> 00:13:51,930
as a recursive value so read the find a
listing

217
00:13:51,930 --> 00:13:55,000
infinite list of in once as

218
00:13:55,000 --> 00:14:00,810
wong's owns wants so that unfold the
recurve a couple of time so we see that

219
00:14:00,810 --> 00:14:02,490
launches ones guam's launch

220
00:14:02,490 --> 00:14:06,160
and fold it again so we get loans goes
wrong gone wrong

221
00:14:06,160 --> 00:14:09,320
et cetera et cetera so wont

222
00:14:09,320 --> 00:14:14,270
is and list of what now let's look at:

223
00:14:14,270 --> 00:14:18,260
evaluation of had of one's okay

224
00:14:18,260 --> 00:14:22,550
and what we want to do as we want to
compare and contrast

225
00:14:22,550 --> 00:14:27,760
in our March devaluation with lazy
evaluation and you can already guess

226
00:14:27,760 --> 00:14:33,430
what will happen when we use in a marked
reduction this is again the same example

227
00:14:33,430 --> 00:14:38,930
with loop so we are taking the in the
most reusable expression which is once

228
00:14:38,930 --> 00:14:42,480
be unfolded we unfolded be unfolded

229
00:14:42,480 --> 00:14:46,089
so we never get around to taking the
head

230
00:14:46,089 --> 00:14:50,670
of that list whereas this list is
already

231
00:14:50,670 --> 00:14:56,370
in the shape where we can take it okay
sure does internet

232
00:14:56,370 --> 00:15:00,370
wears every year lazy evaluation Heather
once

233
00:15:00,370 --> 00:15:06,560
well that's still not reduce ball so we
have to unfold this guy so we get Wong

234
00:15:06,560 --> 00:15:09,890
homes once nah we can do this

235
00:15:09,890 --> 00:15:13,630
and we're done okay to end this case

236
00:15:13,630 --> 00:15:18,920
the result ish 1

237
00:15:18,920 --> 00:15:22,320
general let the slogan up lazy
evaluation

238
00:15:22,320 --> 00:15:25,970
think of doing the dishes is we're doing

239
00:15:25,970 --> 00:15:29,110
just enough work as required

240
00:15:29,110 --> 00:15:32,270
to and for jews the final result

241
00:15:32,270 --> 00:15:36,090
K as a really when we say that wong's

242
00:15:36,090 --> 00:15:41,250
isn't infinite list are gonna lying
because once is not an infinite lest

243
00:15:41,250 --> 00:15:45,410
is a potentially infinite list only when

244
00:15:45,410 --> 00:15:49,710
you know it's gonna I'll X bomb that on
the mom and has not

245
00:15:49,710 --> 00:15:53,940
exponent eagerly to an infinitely show
it's just the rest should be

246
00:15:53,940 --> 00:15:58,740
to create an infinite list and if you
would do dish

247
00:15:58,740 --> 00:16:03,230
in a strict language what typically
happens issue which day

248
00:16:03,230 --> 00:16:07,540
this Wong is defiant using some form

249
00:16:07,540 --> 00:16:12,130
of at sunk show you put in a unit arrow
somewhere

250
00:16:12,130 --> 00:16:15,890
to stop the valuation be guessed that
French unit arrow

251
00:16:15,890 --> 00:16:22,360
is already value now let's look at the
next example here

252
00:16:22,360 --> 00:16:27,020
be mentioned that and lazy evaluation
makes code

253
00:16:27,020 --> 00:16:31,090
more modular and the region is dead it's
because

254
00:16:31,090 --> 00:16:34,320
it does just enough evaluation to gonna

255
00:16:34,320 --> 00:16:37,430
are make the next step so let's look at

256
00:16:37,430 --> 00:16:41,120
take five once that

257
00:16:41,120 --> 00:16:44,460
will return a list of 5 once

258
00:16:44,460 --> 00:16:48,900
okay and once is really the same

259
00:16:48,900 --> 00:16:52,670
as you know this expression here the
International want

260
00:16:52,670 --> 00:16:55,720
and that also returns from lunch

261
00:16:55,720 --> 00:17:01,490
and again the region is dead we have
seen that take was defined by induction

262
00:17:01,490 --> 00:17:06,610
over the structure the list so every
time that you know once

263
00:17:06,610 --> 00:17:09,970
better matching better matches on that
list is

264
00:17:09,970 --> 00:17:13,340
evaluated just enough to gonna yar

265
00:17:13,340 --> 00:17:16,860
get the next value such that we nicely

266
00:17:16,860 --> 00:17:22,120
terminate an here so this is the end of
Part two

267
00:17:22,120 --> 00:17:25,820
about lazy evaluation and see you in a
few minutes