Com Sci 221 — Programming Languages Assignment #6 — Winter 1994 Due Friday, 18 February

1. Do problems 3.13 and 3.14 on p. 114 of the text, in the programming language of your choice. Write a very brief essay (perhaps 1 page) comparing the structure of the loops for the two problems, and the invariants for those loops. It is important to do both problems iteratively, but I am not particularly interested in the use of the break command, so I recommend that you use while–loops in both cases. At any rate, make the two versions of the program as structurally similar as possible.

2. Do problems 3.4, 3.5, 3.6 on pp. 111–112 of the text.

3. Show how to implement a for-loop of the form

for i := E_{1} to E_{2} do SL

using assignments, while-loops, and conditionals. You may assume that E_{1} and E_{2} are pure integer expressions with no side effects, and that SL does not change the value of i. But, you must insure that your code will execute successfully under all reasonable circumstances. In particular, if E_{1} > E_{2}, the for-loop must be equivalent to doing nothing. And, you must never assign a value to i that is less than E_{1} or greater than E_{2}, because that might cause an overflow if the loop is running right up to the limits of the range of i. This problem is taken from problem 3.8 on p. 112 of the text, but you need not use Modula-2 in the solution. No program execution is required, just paperwork.

4. In principle, all computable functions can be computed using assignments, conditionals, and while–loops. Programs involving go-tos can be systematically translated into pure conditional/iterative programs. Show how to eliminate the go-tos in the following schematic program fragments. You will need to introduce new variables in some cases. Comment briefly in each case on the extent to which the structure of the original program with go-tos is or is not preserved in the translated version without go-tos.

(a) α; If A then go to l; β; l: γ

(b) α; l: β; If A then go to m; γ; If B then go to l; m δ

(c) α;

While A do β; If B then go to l; γ

end while; δ; l: ϵ