Review
Haskell is a functional programming language Strongly typed, but with type inference
Bool
Num, Int, Integer, Fractional, Floating, Double Eq, Ord
Tuple, List, Function
Classes, type variables
List comprehension [f x | x<-list, cond x]
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(...⊕(an⊕v))) foldl ⊕ v [a1,a2,..an]=(((v⊕a1)⊕a2)⊕...)⊕an
CPSC 312 — Lecture 7 1/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
Example:
m x y = x*y
m (10-5) (m 10 5)
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
Example:
m x y = x*y
m (10-5) (m 10 5)
Call-by-value: evaluate arguments before reduction
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
Example:
m x y = x*y
m (10-5) (m 10 5)
Call-by-value: evaluate arguments before reduction: m 5 50 CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
Example:
m x y = x*y
m (10-5) (m 10 5)
Call-by-value: evaluate arguments before reduction: m 5 50 Call-by-name: reduction of function first
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
Example:
m x y = x*y
m (10-5) (m 10 5)
Call-by-value: evaluate arguments before reduction: m 5 50 Call-by-name: reduction of function first: (10-5)*(m 10 5)
CPSC 312 — Lecture 7 2/5
©D. Poole 2021
Call-by-name and Call-by-value
Call-by-value: evaluate arguments before reduction Call-by-name: reduction of function first
CPSC 312 — Lecture 7 3/5
©D. Poole 2021
Call-by-name and Call-by-value
Call-by-value: evaluate arguments before reduction Call-by-name: reduction of function first
What does the following do?
inf = 1+inf
CPSC 312 — Lecture 7 3/5
©D. Poole 2021
Call-by-name and Call-by-value
Call-by-value: evaluate arguments before reduction Call-by-name: reduction of function first
What does the following do?
inf = 1+inf
Does following halt?
inf = 1+inf
fst (x,y) = x
fst (3+2, inf)
CPSC 312 — Lecture 7 3/5
©D. Poole 2021
Call-by-name and Call-by-value
Call-by-value: evaluate arguments before reduction Call-by-name: reduction of function first
What does the following do?
inf = 1+inf
Does following halt?
inf = 1+inf
fst (x,y) = x
fst (3+2, inf)
sq x = x*x
sq (55+45)
CPSC 312 — Lecture 7 3/5
©D. Poole 2021
Call-by-name and Call-by-value
Call-by-value: evaluate arguments before reduction Call-by-name: reduction of function first
What does the following do?
inf = 1+inf
Does following halt?
inf = 1+inf
fst (x,y) = x
fst (3+2, inf)
sq x = x*x
sq (55+45)
If they both halt, they give same answer
CPSC 312 — Lecture 7 3/5
©D. Poole 2021
Lazy Evaluation
Lazy evaluation: evaluate argument only once, only if needed Evaluation Order:
Evaluation from outside in
Otherwise (if it knows both arguments need to be evaluated)
from left to right
CPSC 312 — Lecture 7 4/5
©D. Poole 2021
Lazy Evaluation
Lazy evaluation: evaluate argument only once, only if needed Evaluation Order:
Evaluation from outside in
Otherwise (if it knows both arguments need to be evaluated)
from left to right
It is possible to evaluate all arguments that need to be evaluated in parallel.
CPSC 312 — Lecture 7 4/5
©D. Poole 2021
Lazy Evaluation
Lazy evaluation: evaluate argument only once, only if needed Evaluation Order:
Evaluation from outside in
Otherwise (if it knows both arguments need to be evaluated)
from left to right
It is possible to evaluate all arguments that need to be evaluated in parallel.
One could imagine a language that memorizes the results of all previous function calls. GHC does not do that. It just caches locally.
CPSC 312 — Lecture 7 4/5
©D. Poole 2021
Lazy Evaluation
Lazy evaluation: evaluate argument only once, only if needed Evaluation Order:
Evaluation from outside in
Otherwise (if it knows both arguments need to be evaluated)
from left to right
It is possible to evaluate all arguments that need to be evaluated in parallel.
One could imagine a language that memorizes the results of all previous function calls. GHC does not do that. It just caches locally.
Lazy evaluation enables forms of programming that are not possible with call by value. E.g., definition of if-then-else
myif True then_exp else_exp = then_exp
myif False then_exp else_exp = else_exp
fac n = myif (n==0) 1 (n*fac (n-1))
CPSC 312 — Lecture 7 4/5
©D. Poole 2021
Lazy Computation Examples: finding primes (Lazy.hs)
Sieve of Eratosthenes
start with the list of all numbers ≥ 2,
when found a prime, cross off the multiples of that prime from the rest of the list
CPSC 312 — Lecture 7 5/5
©D. Poole 2021
Lazy Computation Examples: finding primes (Lazy.hs)
Sieve of Eratosthenes
start with the list of all numbers ≥ 2,
when found a prime, cross off the multiples of that prime from the rest of the list
– – sieve (p:xs) is the list of all primes from p, given all of a multiples of primes less than p have been removed.
CPSC 312 — Lecture 7 5/5
©D. Poole 2021
Lazy Computation Examples: finding primes (Lazy.hs)
Sieve of Eratosthenes
start with the list of all numbers ≥ 2,
when found a prime, cross off the multiples of that prime from the rest of the list
– – sieve (p:xs) is the list of all primes from p, given all of a multiples of primes less than p have been removed.
CPSC 312 — Lecture 7 5/5
©D. Poole 2021
©D. Poole 2021
CPSC 312 — Lecture 7 6/5