Com Sci 221 — Programming Languages Assignment #5 — Winter 1994 Due Wednesday, February 9

1. Suppose that you are designing a language of boolean expressions using the binary infix operators & (and) and ⇒ (implies). Notice that it is very common to express assertions of the form, “A and B and C and D imply E.” Also notice that (A&B&C&D) ⇒ E is equivalent to A ⇒ (B ⇒ (C ⇒ (D ⇒ E))).

(a) In order to make the particular form above most convenient to express, while accommodating other forms reasonably as well, fill in the following rules about precedence and associativity:

i. highest precedence should be assigned to (&, ⇒, doesn’t matter); ii. & should be (left-associative, right-associative, doesn’t matter); iii. ⇒ should be (left-associative, right-associative, doesn’t matter).

In each case, justify your choice in a couple of sentences.

(b) Suppose now that you must eliminate the &, and use the equivalence mentioned above. Would you change the associativity of ⇒? Very briefly, why or why not?

2. Briefly discuss the relations between the set-theoretic types

A + B + C + (A × B × C)

and

(A + {nil}) × (B + {nil}) × (C + {nil})

Are they equivalent? Nearly equivalent? Does one represent the other?