Test 1 Review B: Questions

R1b.1.

Give a lambda expression representing the composition function. That is, the function represented by your expression should take two functions f and g as arguments and return the composition of the two functions — i.e., a function h where h(x)=f(g(x)) for any x.

R1b.2.

Give a lambda expression representing the function that takes a value v and returns the projection function for v. That is, given v, it should return a function that will take any other function f and return f v.

R1b.3.

Give an example of a lambda expression that does not reduce to normal form using applicative evaluation order (also called eager evaluation), but which does reduce to normal form using normal evaluation order.

R1b.4.

Reduce the following lambda expression to irreducible form, showing every intermediate step. It should reduce to a number.

(((λf.λg.g f) (λx.10 − x)) (λy.λx.y (y x))) 4

R1b.5.

Reduce the following lambda expression to irreducible, showing every intermediate step. It should reduce to a number.

(λf.λa.f (a + 3) − (f a) − (f 3)) (λx.x × x)) 7

R1b.6.

Using normal evaluation order, reduce the following lambda expression to irreducible form, showing every intermediate step. It should reduce to a number.

(λa.λb.λc.a c c) (λd.λe.d − e) (2 − 3) (5 − 8)

R1b.7.

Using normal evaluation order, reduce the following lambda expression to irreducible form, showing every intermediate step. It should reduce to a number.

(λa.λb.a (b + 1) − a b) (λx.x × x × x) 2

R1b.8.

How is normal evaluation different from lazy evaluation?

R1b.9.

Explain the “lazy parameter penalty.”

R1b.10.

Explain the significance of strictness analysis to compiling Haskell programs into efficient code.

R1b.11.

What makes infinite-size data structures possible in languages implemented on finite-memory computers?

R1b.12.

Write Haskell code to define a list allPoints including all two-dimensional points where both coordinates are positive integers. To do this, you would want to list them in order by the sum of the two coordinates.

[(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4)…]

You can see that this will eventually hit all positive-integer points, without hitting any of them twice.

R1b.13.

List two advantages of eager evaluation over lazy evaluation.

R1b.14.

List two advantages of lazy evaluation over eager evaluation.

R1b.15.

Which of the parameters of the following Haskell function are strict?

mystery f b y = if b then y else f y

R1b.16.

Which parameters for the following function are strict?

multAll n nums = if null nums

                   then []

                   else (n * head nums) : (multAll n (tail nums))

R1b.17.

Suppose we have the Y combinator (i.e., the fixed-point combinator) defined.

Y = λf.(λx.f (x x)) (λx.f (x x))

Suppose, moreover, than we have infix operators for subtraction, addition, and comparison (=, < and ≤), as well as if–then–else expressions. Give a lambda expression to compute the nth Fibonacci number, recalling that the 0th Fibonacci is 0 and the 1st Fibonacci is 1.

Test 1 Review B: Solutions

R1b.1.

λf.λg.(λx.f (g x)) [The parentheses are unnecessary here, but they make the intention clearer.]

R1b.2.

λv.(λf.f v)

R1b.3.

(λy.(λz.z)) ((λx.x x) (λx.x x)) [It reduces to λz.z under normal evaluation order, but it does not change at all when attempting to reduce using applicative evaluation order.]

R1b.4.

(((λ`f`.λ`g`.`g` `f`) (λ`x`.10 − `x`)) (λ`y`.λ`x`.`y` (`y` `x`))) 4	⇒	((λ`g`.`g` (λ`x`.10 − `x`)) (λ`y`.λ`x`.`y` (`y` `x`))) 4
	⇒	((λ`y`.λ`x`.`y` (`y` `x`)) (λ`x`.10 − `x`)) 4
	⇒	(λ`x`.(λ`x`.10 − `x`) ((λ`x`.10 − `x`) `x`)) 4
	⇒	(λ`x`.10 − `x`) ((λ`x`.10 − `x`) 4)
	⇒	10 − ((λ`x`.10 − `x`) 4)
	⇒	10 − (10 − 4)
	⇒	10 − 6
	⇒	4

R1b.5.

(λ`f`.λ`a`.`f`(`a` + 3) − (`f` `a`) − (`f` 3)) (λ`x`.`x` × `x`)) 7	⇒	(λ`a`.(λ`x`.`x` × `x`) (`a` + 3) − (λ`x`.`x` × `x`) `a` − (λ`x`.`x` × `x`) 3) 7
	⇒	(λ`x`.`x` × `x`) (7 + 3) − (λ`x`.`x` × `x`) 7 − (λ`x`.`x` × `x`) 3
	⇒	(7 + 3) × (7 + 3) − (λ`x`.`x` × `x`) 7 − (λ`x`.`x` × `x`) 3
	⇒	(7 + 3) × (7 + 3) − 7 × 7 − (λ`x`.`x` × `x`) 3
	⇒	(7 + 3) × (7 + 3) − 7 × 7 − 3 × 3
	⇒	10 × (7 + 3) − 7 × 7 − 3 × 3
	⇒	10 × 10 − 7 × 7 − 3 × 3
	⇒	100 − 7 × 7 − 3 × 3
	⇒	100 − 49 − 3 × 3
	⇒	51 − 3 × 3
	⇒	51 − 9
	⇒	42

R1b.6.

(λ`a`.λ`b`.λ`c`.`a` `c` `c`) (λ`d`.λ`e`.`d` − `e`) (2 − 3) (5 − 8)	⇒	(λ`b`.λ`c`.(λ`d`.λ`e`.`d` − `e`) `c` `c`) (2 − 3) (5 − 8)
	⇒	(λ`c`.(λ`d`.λ`e`.`d` − `e`) `c` `c`) (5 − 8)
	⇒	(λ`d`.λ`e`.`d` − `e`) (5 − 8) (5 − 8)
	⇒	(λ`e`.(5 − 8) − `e`) (5 − 8)
	⇒	(5 − 8) − (5 − 8)
	⇒	−3 − (5 − 8)
	⇒	−3 − −3
	⇒	0

R1b.7.

(λ`a`.λ`b`.`a` (`b` + 1) − `a` `b`) (λ`x`.`x` × `x` × `x`) 2	⇒	(λ`b`.(λ`x`.`x` × `x` × `x`) (`b` + 1) − (λ`x`.`x` × `x` × `x`) `b`) 2
	⇒	(λ`x`.`x` × `x` × `x`) (2 + 1) − (λ`x`.`x` × `x` × `x`) 2
	⇒	(2 + 1) × (2 + 1) × (2 + 1) − (λ`x`.`x` × `x` × `x`) 2
	⇒	3 × (2 + 1) × (2 + 1) − (λ`x`.`x` × `x` × `x`) 2
	⇒	3 × 3 × (2 + 1) − (λ`x`.`x` × `x` × `x`) 2
	⇒	9 × (2 + 1) − (λ`x`.`x` × `x` × `x`) 2
	⇒	9 × 3 − (λ`x`.`x` × `x` × `x`) 2
	⇒	27 − (λ`x`.`x` × `x` × `x`) 2
	⇒	27 − 2 × 2 × 2
	⇒	27 − 4 × 2
	⇒	27 − 8
	⇒	19

R1b.8.

Both evaluation orders involve the same basic concept — arguments are sent into functions unevaluated. With normal evaluation, this may lead to arguments being computed within the function multiple times. But with lazy evaluation, care is taken that after the first computation of an argument completes, that value is saved so that subsequent accesses to the same argument need not involve recomputation.

R1b.9.

Each time a function that accepts a lazy parameter tries to access the argument value, it must first ensure that the argument has already been computed before actually retrieving the argument value. The process of ensuring that the argument is already computed has a cost that is not necessary with eager parameters, where the value is passed already-computed into the function. That additional cost is the “lazy parameter penalty.”

R1b.10.

In a straightforward implementation of a lazy language such as Haskell, each reference to a parameter identifier must be first checked to see whether it is a thunk and reduced if so, before the value can be used. This checking process is quite inefficient. Through analyzing whether a function is strict, the compiler can identify identifiers that it is sure will be eventually referenced, and these parameters can be thawed from their thunk form immediately so that generated machine code for later references can avoid checks to see whether the thunk is thawed yet.

R1b.11.

In a language with lazy evaluation, while the data structure may be theoretically infinite, a program would actually only generate that portion of the data structure that is actually used by the program, saving the uncomputed portion of the structure simply as code that can generate more of the structure when necessary (and it may never be necessary).

R1b.12.

pointsFrom x y | y == 1    = (x, y) : pointsFrom 1 (x + 1)

               | otherwise = (x, y) : pointsFrom (x + 1) (y - 1)



allPoints = pointsFrom 1 1

R1b.13.

It is simpler to implement.
Users tend to find the evaluation order much more intuitive. This is essential when the language includes any non-functional features, such as variable assignments or input/output operations. (It is not important at all if the language is purely functional.)

R1b.14.

Programs written using eager evaluation are more likely to end up performing computation that turns out to be in fact unnecessary to the final result, since all arguments are evaluated before being passed to a function, even when they turn out to be useless.
Lazy evaluation is mathematically sound, which allows compilers to perform code reordering for optimization that would otherwise not be feasible because of the potential for accidentally entering infinite computation.
It enriches the expressiveness of the base language to permit infinite data structures (as well as to remove the need for if-then or short-circuit Boolean operators within the core language).

R1b.15.

The only strict parameter is b. [You may be tempted to say that y is strict. It is not, however, since if b is false, and f turns out to ignore its parameter, then y's value is never necessary. An example of this is mystery False (sqrt (-1)) (\x -> 1).]

R1b.16.

The nums parameter is strict.

R1b.17.

Y (λf.λn.if n ≤ 1 then n else f (n − 1) + f (n − 2)