هسکل (۲)

هسکل (۲)

اسلاید 1: Lecture 11 Lazy Evaluation, Lambda Calculus1Lazy Evaluation

اسلاید 2: Lecture 11 Lazy Evaluation, Lambda Calculus2The following expression may be evaluated in two ways:snd (fact 10, fact 3)Eager or argument first evaluation (or call by value)snd (fact 10, fact 3)= snd (3628800,fact 3)= snd (3628800,6)= 6Lazy or function first evaluation (or call by name)snd (fact 10, fact 3)= fact 3= 6Haskell is a lazy functional programming language. This means that arguments of functions are not evaluated until they are needed.

اسلاید 3: Lecture 11 Lazy Evaluation, Lambda Calculus3Fact> snd ( fact 10, fact 3)6(99 reductions, 155 cells)Fact> snd ( fact 3, fact 10)3628800(246 reductions, 388 cells)So, using Hugs:Another example:Fact> head [fact 1,fact 10,fact 100, fact 1000, fact 10000]1(57 reductions, 91 cells) --only the first element in the list is evaluatedAlthough 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 due to lazyness of Hugs.

اسلاید 4: Lecture 11 Lazy Evaluation, Lambda Calculus4In 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.Prelude> head [1..]1 Prelude> take 10 [1..][1,2,3,4,5,6,7,8,9,10]Prelude> zip [1..] [Mike,Gary,Larry][ (1,Mike), (2,Gary), (3,Larry)] :: [(Integer,[Char])]Prelude > take 5 [ a^2| a <- [1..] ][1,4,9,16,25]Prelude > fst ( head [a,b,c,d], [1..] )a Prelude> snd ( head [a,b,c,d], [1..] )[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20{Interrupted!}

اسلاید 5: Lecture 11 Lazy Evaluation, Lambda Calculus5Prelude> [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..]]FalseOnly the first element in the list is evaluated by “ and” which returns False

اسلاید 6: Lecture 11 Lazy Evaluation, Lambda Calculus6forever::Int -> Intforever 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 language.The following function will run forever or cause an error message to be generated due to stack overflow.

اسلاید 7: Lecture 11 Lazy Evaluation, Lambda Calculus7example a b = a^2Main> 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 + aMain> example (2+3) (3*45^58) 10 In the example above the second argument is never evaluated and the first is only evaluated once.

اسلاید 8: Lecture 11 Lazy Evaluation, Lambda Calculus8A “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..]Main> exampleFunction 2 3[(2,1),(2,2)] :: [(Integer,Integer)]Main> exampleFunction 5 2[(1,2),(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),(23,24),(25,26),(27,28),(29,30),(31,32),(33,34),(35,36),(37,38),(39,40),(41,42),(43,44),(45,46),(47,48),(49,50),(51,52),(53,54),(55,56),(57,58),(59,60),(61,62),(63,64),(65,66),(67,68),(69,70),(71,72),(73,74),(75,76),(77,78),(79,80),(81,82),{Interrupted!}

اسلاید 9: Lecture 11 Lazy Evaluation, Lambda Calculus9Lambda Calculus A fairly simple system for representing functionsThe base of typed functional programming languages such as ML and Haskell

اسلاید 10: Lecture 11 Lazy Evaluation, Lambda Calculus10The theory of lambda calculus was developed by Alonzo Church as a foundation for mathematics in 1930s, years before computers were invented.In 1920s Moses Schonfinkel developed a theory of functions called combinators.In the 1930s Haskell Curry rediscovered Schonfinkel’s theory and showed that it was equivalent to lambda calculus

اسلاید 11: Lecture 11 Lazy Evaluation, Lambda Calculus11In the 1950s John McCarthy inspired by the lambda calculus invented the programming language Lisp.

اسلاید 12: Lecture 11 Lazy Evaluation, Lambda Calculus12During 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.

اسلاید 13: Lecture 11 Lazy Evaluation, Lambda Calculus13ExampleSquaring 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.

اسلاید 14: Lecture 11 Lazy Evaluation, Lambda Calculus14Lambda 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