صفحه 1:
Lazy Evaluation
Lecture 11 Lazy Evaluation,
Lambda Calculus
صفحه 2:
Haskell is a lazy functional programming language.
This means that
FoRSURG BS PE SURGE MRS BE AAA GLATUALP AN ey
are nee
snd (fact 10, fact 3)
er or argument first evaluation (or call by value)
snd (fact 10, fact 3)
= snd (3628800,fact 3)
snd (3628800,6)
=6
y or function first evaluation (or call by name)
snd (fact 10, fact 3)
= fact 3
8 Lecture 11 Lazy Evaluation, 2
Py Lambda Calculus
صفحه 3:
Although the results returned using lazy or eager
evaluation are the same, the amount of work done is
different. In the example below, the first argument is
SHeveinevAlugsed due to lazyness of Hugs.
Another example:
Fact> head [fact 1,fact 10,fact 100, fact 1000, fact
10000]
1
(57 reductions, 91 aells) 1: nendydhe, first element inthe
list is evaluated Lambda Calculus
صفحه 4:
In the previous example, the only element that is
evaluated from the list is the first item.
Lazy evaluation has made the use of infinite lists
slude> head [1..]
slude> take 10 [1..]
2,3,4,5,6,7,8,9,10]
2lude> zip [1..] ["Mike","Gary","Larry"]
L,"Mike"), (2,"Gary"), (3,"Larry")] :: [Unteger,[Char])]
alude > take 5[a%2]a <- [1..]]
4,9,16,25]
slude > fst ( head ['a','b','c','d'], [1..] )
slude> snd (head ['a','b','c','d'], [1..])
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
iterrupted! }
Lecture 11 Lazy Evaluation,
Lambda Calculus
صفحه 5:
Prelude> [True|a <- [1..10]]
[True, True, True, True, True, True, True, True, True, True] :
: [Bool]
Prelude> True && and [True| x <- [1..] ]
{Interrupted! }
which has resuited in an infinite thop but look at this:
Prelude> False && and [True| a <- [1..] ]
False
The reason is that the left side of the && operator isa
False and Hugs does not evaluate the right argument.
Many languages do similarly. An dxample is Modula 2.
<-[1..]]
False Lecture 11 Lazy Evaluation, 5
Lambda Calculus
Ne Tee Be a hee ie | AON dierent و 2007 ال ل ا eR a eee ol EE AE ens aE.
صفحه 6:
llowing function will run forever or cause 20 611۲0۲ 0۷
ated due to stack overflow.
forever::Int -> Int
forever n = n + forever (n+1)
But look at the way it has been used in the following
expression without any problems. This is because the
second element in the pair is never evaluated thanks
er 5)
This would definitly 1 result into error in an eager
11 Lazy Evaluation,
language. 5 Onc
صفحه 7:
efample 2 <ظ 7
The second argument above is never evaluated because
it is not needed for calculating the right hand side.
examplea b=al|t+a
In the example above the second argument is never
evaluated and
the first is only evaluated once.
Lecture 11 Lazy Evaluation, 7
Lambda Calculus
صفحه 8:
A “where clause” (local definition) is only evaluated if
and when the
value is needed and the system can tell if and when it
needs tn evaliate thinas
exampleFunction a b
Ja <b = [(a,1),(a,2)]
ja== = [(b,1),(b,2)]
| otherwise = list
where list = zip [1,3..]
194 1
in> exampleFunction 2 3
1),(2,2)] :: [Unteger,Integer)]
in> exampleFunction 5 2
2), (3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20), (21,22),
24),(25,26),(27,28),(29,30),(31,32),(33,34),(35,36),(37,38),(39,40),(41,42),
44),(45,46),(47,48),(49,50),(51,52),(53,54),(55,56),(57,58),(59,60),(61,62),
64),(65,66),(67,68),(69,70),(71,72),(73,74),(75,76),(77,78),(79,80),(81,82),
terrupted!}
Lecture 11 Lazy Evaluation, 8
Lambda Calculus
صفحه 9:
Lambda Calculus
A fairly simple
system for
representing
The BEEP RSped
functional programming
languages such as ML and
هه
Lambda Calculus
صفحه 10:
In 1920s Moses Schonfinkel developed
a theory of functions called
The theorgoMambdesalculus was
developed by Alonzo Church as a
foundation for mathematics in 1930s,
years before computers were invented.
In the 1930s Haskell Curry
rediscovered Schonfinkel’s theory
and showed that it was equivalent to
lambda calculus
50-0 11 Lazy Evaluation, 10
la Calculus
صفحه 11:
In the 1950s John
McCarthy inspired by
the lambda calculus
invented the
programming language
لك
صفحه 12:
During the 19/U's 0
and Morris wrote some
influentional papers discussing
the advantages of functional
programming for software
engineering.
In the 1980s several groups
started working on
architectures to support
functional. programming. 2
صفحه 13:
Example
¢ Squaring function in lambda
calculus
AX.X*x
Ax means that we take a value x and
the rest of the definition says that
we multiply x by itself. The A is
called lambda abstraction.
50-0 11 Lazy Evaluation, 13
la Calculus
صفحه 14:
Lambda has one parameter. If we
wanted to take two numbers,
double the first and add it to
the second we would write:
Ax Ay.2*x+y
Lecture 11 Lazy Evaluation, 14
Lambda Calculus
Lazy Evaluation
Lecture 11 Lazy Evaluation,
Lambda Calculus
1
Haskell is a lazy functional programming language.
This means that
arguments
of functions
not evaluated
until
they
e following
expression
may are
be evaluated
in two
ways:
are needed.
snd (fact 10, fact 3)
ger or argument first evaluation (or call by value)
snd (fact 10, fact 3)
= snd (3628800,fact 3)
= snd (3628800,6)
=6
y or function first evaluation (or call by name)
snd (fact 10, fact 3)
= fact 3
Lecture 11 Lazy Evaluation,
=6
Lambda Calculus
2
Although the results returned using lazy or eager
evaluation are the same, the amount of work done is
different. In the example below, the first argument is
never
evaluated
So,
using
Hugs: due to lazyness of Hugs.
Fact> snd ( fact 10, fact 3)
6
(99 reductions, 155 cells)
Fact> snd ( fact 3, fact 10)
3628800
(246 reductions, 388 cells)
Another example:
Fact> head [fact 1,fact 10,fact 100, fact 1000, fact
10000]
1
(57 reductions, 91 cells)
the first element in 3the
Lecture 11 --only
Lazy Evaluation,
Lambda Calculus
list is evaluated
In the previous example, the only element that is
evaluated from the list is the first item.
Lazy evaluation has made the use of infinite lists
possible.
elude>
head [1..]
elude> take 10 [1..]
,2,3,4,5,6,7,8,9,10]
elude> zip [1..] ["Mike","Gary","Larry"]
1,"Mike"), (2,"Gary"), (3,"Larry")] :: [(Integer,[Char])]
elude > take 5 [ a^2| a <- [1..] ]
,4,9,16,25]
elude > fst ( head ['a','b','c','d'], [1..] )
elude> snd ( head ['a','b','c','d'], [1..] )
,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
nterrupted!}
Lecture 11 Lazy Evaluation,
Lambda Calculus
4
Prelude> [True|a <- [1..10]]
[True,True,True,True,True,True,True,True,True,True] :
: [Bool]
Prelude> True && and [True| x <- [1..] ]
{Interrupted!}
which has resulted in an infinite loop but look at this:
Prelude> False && and [True| a <- [1..] ]
False
The reason is that the left side of the && operator is a
False and Hugs does not evaluate the right argument.
Many languages do similarly. An example is Modula 2.
Prelude> True && and [False| a <- [1..]]
False
Lecture 11 Lazy Evaluation,
Lambda Calculus
5
ollowing function will run forever or cause an error message
ated due to stack overflow.
forever::Int -> Int
forever n = n + forever (n+1)
But look at the way it has been used in the following
expression without any problems. This is because the
second element in the pair is never evaluated thanks
to Haskell’s laziness.
Main> fst (2^3, forever 5)
8
This would definitly result into error in an eager
Lecture 11 Lazy Evaluation,
language.
Lambda Calculus
6
example a b = a^2
Main> example 3 (4*5^9)
9
The second argument above is never evaluated because
it is not needed for calculating the right hand side.
example a b = a + a
Main> example (2+3) (3*45^58)
10
In the example above the second argument is never
evaluated and
the first is only evaluated once.
Lecture 11 Lazy Evaluation,
Lambda Calculus
7
A “where clause” (local definition) is only evaluated if
and when the
value is needed and the system can tell if and when it
needs to evaluate things.
exampleFunction a b
|a <b
= [(a,1),(a,2)]
|a==b
= [( b,1),(b,2)]
| otherwise = list
where list = zip [1,3..]
[2,4..]
ain> exampleFunction 2 3
,1),(2,2)] :: [(Integer,Integer)]
ain> exampleFunction 5 2
2),(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),
,24),(25,26),(27,28),(29,30),(31,32),(33,34),(35,36),(37,38),(39,40),(41,42),
,44),(45,46),(47,48),(49,50),(51,52),(53,54),(55,56),(57,58),(59,60),(61,62),
,64),(65,66),(67,68),(69,70),(71,72),(73,74),(75,76),(77,78),(79,80),(81,82),
nterrupted!}
Lecture 11 Lazy Evaluation,
Lambda Calculus
8
Lambda Calculus
A fairly simple
system for
representing
functions
The base of typed
functional programming
languages such as ML and
Haskell
Lecture 11 Lazy Evaluation,
Lambda Calculus
9
In 1920s Moses Schonfinkel developed
a theory of functions called
The theorycombinators.
of lambda calculus was
developed by Alonzo Church as a
foundation for mathematics in 1930s,
years before computers were invented.
In the 1930s Haskell Curry
rediscovered Schonfinkel’s theory
and showed that it was equivalent to
lambda calculus
Lecture 11 Lazy Evaluation,
Lambda Calculus
10
In the 1950s John
McCarthy inspired by
the lambda calculus
invented the
programming language
Lisp.
Lecture 11 Lazy Evaluation,
Lambda Calculus
11
During the 1970’s Henderson
and Morris wrote some
influentional papers discussing
the advantages of functional
programming for software
engineering.
In the 1980s several groups
started working on
architectures to support
functional programming.
Lecture 11 Lazy Evaluation,
Lambda Calculus
12
Example
• Squaring function in lambda calculus
λx.x*x
λx means that we take a value x and the
rest of the definition says that we
multiply x by itself. The λ is called
lambda abstraction.
Lecture 11 Lazy Evaluation,
Lambda Calculus
13
Lambda has one parameter. If we
wanted to take two numbers,
double the first and add it to the
second we would write:
λx λy.2*x+y
Lecture 11 Lazy Evaluation,
Lambda Calculus
14