Com Sci 221/321 --- Programming Languages
Assignment #3 --- Autumn 1999
Due Monday, 18 October

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

Com Sci 221 and 321

1. Do problems 3.2 a-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 asssignments, 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, contionals, 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
      

Com Sci 321 only

Choose one of the following two problems. In both cases, you must interpret the ground rules for implementing one control structure in terms of others in a sensible way that makes the problem interesting. I encourage you strongly to discuss this point in the HyperNews forum.

1. Do problem 3.13 on page 99 of the text. It takes some thought to interpret the ground rules for this problem, and that interpretation is part of your assignment. I recommend this choice only if you have studied formal language theory.



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