Sections 2.3 and 2.4

Question 1

A redex that can’t be reduced further is in ____ form.

Answer 1

normal

Question 2

True or False: For a given lambda expression reducible to a normal form, every reduction terminates.

Answer 2

False

Question 3

A non-terminating reduction sequence is like a ____ in an imperative program.

Answer 3

infinite loop

Question 4

True or False: The normal form, if it exists, is unique.

Answer 4

True

Question 5

If a lambda expression E is reducible to both E1 and E2, what is true about E1 and E2?

Answer 5

E1 and E2 are reducible to E3.

Question 6

The previous property is known as ____

Answer 6

The Church-Rosser Theorem

Question 7

Normal order reduction reduces the ____ redex first.

Answer 7

leftmost outermost

Question 8

Using normal order reduction, the next redex to reduce in z (((λx. x x) u) ((λy. y) v)) is ____.

Answer 8

(λx. x x) u

Question 9

True or False: Normal order reduction of an expression will reduce it to normal form, if it exists.

Answer 9

True

Question 10

True or False: Normal order reduction produces the fewest number of reductions.

Answer 10

False

Question 11

The lambda calculus provides no facility for ____ expressions.

Answer 11

naming

Question 12

In the equality FAC = H FAC, FAC is a ____ of H.

Answer 12

fixed point

Question 13

True or False: The fixed point of a function is unique

Answer 13

False

Question 14

True or False: The equality in the equation FAC = H FAC is syntactic equality.

Answer 14

False

Question 15

Y produces the ____ fixed-point of a function.

Answer 15

least