Com Sci 221 --- Programming Languages
Assignment #3 --- Autumn 2000
Due Wednesday, 18 October

Make sure to follow the general instructions for performing and submitting homework.

1. Do problems 3.2 a, b, d and 3.3 b on page 95 of the text.



2. Do problem 3.4 parts a and c on page 95 of the text.



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

   for i := E1 to E2> do SL endfor
   

   using assignments, while-loops, and conditionals. You may assume that E1 and E2 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 E1>E2, the for-loop must be equivalent to doing nothing. And, you must never assign a value to i that is less than E1 or greater than E2, because that might cause an overflow if the loop is running right up to the limit of the range of i. This problem is based on 3.5 on page 96 of the text.
   
   Demonstrate your solution by executing programs in your favorite procedural programming language (C, C++, Pascal, Algol, ...). Fill in different possibilities for E1, E2, and SL, to show that you have satisfied the requirements. A small number of tests will suffice, but you need to find out precisely what causes integer variables to overflow.



4. In principle, all computable functions can be computed using assignments, conditionals, and while-loops. Programs involving gotos can be systematically translated into pure conditional/iterative programs. Show how to eliminate the gotos 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 gotos is or is not preserved in the translated version without gotos.
   
   

   1. SL1;
      if A then goto l;
      SL2;
      l: SL3
      

   2. SL1;
      l: SL2
      if A then goto m;
      SL3;
      if B then goto l;
      m: SL4
      

   3. SL1;
      while A do
         SL2;
         if B then goto l;
         SL3
      end while;
      SL4;
      l: SL5
      

Optional Challenge Problem

I am only interested in really well thought out and clearly presented solutions to this problem. Please don't just stab at it in the wild hopes of picking up points.

Find your own example of a flowchart that cannot be implemented using if and while, in the sense of problem 3.13 on page 99 of the text. Interpreting the ground rules for the implementation is part of the problem. You don't need to write a mathematical proof, but you must be convincing. Hint: look for a graphical property shared by all flowcharts of structured programs. A convincing argument takes 3-5 sentences.