Test 1 Review B

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]

Problem 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.

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

Problem 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.

λv.(λf.f v)

Problem 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.

(λ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.]

Problem 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

(((λ`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

Problem 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

(λ`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

Problem 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)

(λ`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

Problem 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

(λ`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

Problem R1b.8.

How is normal evaluation different from lazy evaluation?

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.

Problem R1b.9.

Explain the “lazy parameter penalty.”

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.”

Problem R1b.10.

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

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.

Problem R1b.11.

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

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).

Problem 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.

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

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



allPoints = pointsFrom 1 1

Problem R1b.13.

List two advantages of eager evaluation over lazy evaluation.

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.)

Problem R1b.14.

List two advantages of lazy evaluation over eager evaluation.

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).

Problem R1b.15.

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

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

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).]

Problem 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))

The nums parameter is strict.

Problem 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.

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