CS 3721 Recitation 1: Nogoto Recitation

CS 3721
Programming Languages
Spring 2013

Recitation 1. No GOTO

Week 1: Jan 14-18

Submit following directions at: submissions and rules at: rules. Deadlines are:

2013-01-22 23:59:59 (that's Tue, 22 Jan 2013, 11:59:59 pm) for full credit.
2013-01-25 23:59:59 (that's Fri, 25 Jan 2013, 11:59:59 pm) for 75% credit.

List of names of students submitting, final list: Rec1 Submissions.

1. Overview: This recitation is concerned with the goto statement, which is a part of most languages, with the notable exception of Java. More than 40 years ago, computer scientists recognized that programs written with gotos were often much more difficult to comprehend than those without gotos. This was part of the structured programming revolution, initiated in 1968 by E. Dijkstra, a Dutch computer scientist: Dijkstra's original article. For these and other reasons the use of the goto statement has been discouraged, to the point where the statement is often not even taught to beginning C or C++ programmers.

Dijkstra later made clear that the goto itself was not necessarily bad if it was used for an orderly termination of a loop (as with a break statement).

The Java language has no goto, but it has a break statement to break out of a loop (as with C and C++), and the more complicated labeled break which lets one break out of multiple nested loops. Java also has a continue statement which lets one skip the remainder of a loop and start over at the header.

Some sophisticated Java books (such as those by Horstmann) never use break or continue and discourage its use. Horstmann also never uses the Java switch statement, mainly because it's too error prone (if you leave off a break from a switch clause, execution of that clause will fall through and execute the next clause).

One issue that might bother students is: what if you had a program written with gotos whose logic was so complicated that you could not understand it. It turns out that there are powerful theoretical results which show that one can always rewrite to get a gotoless program. It's also possible to do without break and continue, but we won't discuss that further here.

Any program written using gotos can be rewritten without gotos
so that it carries out exactly the same computation.
It is not necessary to understand the program in order to rewrite it.

This recitation illustrates the above result starting with a moderately confusing initial program with gotos. The whole idea is not to unravel the logic of this weird program, but to see that it can be transformed to a program without gotos, and without understanding how the program works.

The structure of the resulting transformed program is at least as confusing as the original program, even though the new program has no gotos. This shows that the structured programming revolution was not really about making programs free of gotos, but was concerned with creating programs whose control structure could be understood.

Several examples below occur in Fortran and in Pascal. It is not necessary to understand either Fortran or Pascal in order to understand these examples.

2. Initial example: On the left below is an obscure Fortran program with gotos that translates an integer to Roman numerals, while on the right is an equivalent Pascal program without gotos. The Fortran program uses only GOTOs and IFs followed by a GOTO. It works for integers less than 4000. (The line numbers in yellow at the right of lines of the Fortran program have nothing to do with the program itself.) Note that this is intended to be an obscure program, whose mechanism may not be clear.

The Pascal program below on the right uses a simple method to carry out the actions of the original program without using goto statements. It illustrates a general strategy for translating any program using gotos into an equivalent program without gotos. ("Equivalent" means that the new program carries out exactly the same computation.) Thus in a sense it shows that the simple-minded approach to structured programming ("Get rid of all gotos") can always be achieved.

Here the variable LINE keeps track of which of the original 18 lines are executing. The Pascal "case" statement is like a "switch" statement in C/C++/Java. Each case (1-18) corresponds to a line number. After executing a case, the program either increments LINE to the next line number (in case control in the original program went on to the next line), or else changes LINE to a different line number altogether, corresponding to a goto statement.

Do you think the program on the right below is better or simpler or easier to understand because it has no goto statements?

Fortran Program With GOTOs

Equivalent Pascal Program Without GOTOs

% cat rom.for
* Fortran program:
*   translate to Roman numerals
*   uses GOTOs extensively
      PROGRAM ROMAN
      
      INTEGER ROM, I, L, N, K
      CHARACTER*1 S(15), R(7)
      

      DATA R/'I','V','X','L','C','D','M'/
      

      
      ROM = 3947                  Line 1
      I = 1                       Line 2
      L = 1000                    Line 3
      N = 13                      Line 4
20    IF (MOD(N,4) .NE. 1) GOTO 30Line 5
      
      K = L                       Line 6
      L = K/10                    Line 7
30    K = K - L*(MOD(N,4)-1)**2   Line 8

40    IF (ROM .LT. K) GOTO 60     Line 9
      ROM = ROM - K               Line 10
      IF (MOD(N,2) .NE. 0) GOTO 50Line 11
      
      S(I) = R(((N-2)/4)*2 + 1)   Line 12
      
      I = I + 1                   Line 13
50    S(I) = R((N+2)/2)           Line 14
      I = I + 1                   Line 15
      GOTO 40                     Line 16
60    N = N - 1                   Line 17
      IF (N .GE. 1) GOTO 20       Line 18
      PRINT *, S
      STOP
      END
% f77 -o rom_for rom.for
rom.for:
 MAIN:
% rom_for
 MMMCMXLVII

% cat rom.pas
(* Transformed Pascal version of the   *)
(*   original Fortran program          *)
(* No goto statements in this program  *)
program ROMAN;
var
  ROM, I, L, N, K, LINE: integer;
  S: array[1..15] of char;
  R: array[1..7] of char;
begin
  R := 'IVXLCDM';
  LINE := 1;
  while LINE <> 19 do
  case LINE of
   1: begin ROM := 3947; LINE := LINE + 1 end;
   2: begin I := 1; LINE := LINE + 1 end;
   3: begin L := 1000; LINE := LINE + 1 end;
   4: begin N := 13; LINE := LINE + 1 end;
   5: if (N mod 4) <> 1 then LINE := 8
         else LINE := LINE + 1;
   6: begin K := L; LINE := LINE + 1 end;
   7: begin L := K div 10; LINE := LINE + 1 end;
   8: begin K := K-L*((N mod 4)-1)*((N mod 4)-1);
         LINE := LINE + 1 end;
   9: if ROM < K then LINE := 17
         else LINE:=LINE + 1;
  10: begin ROM := ROM - K; LINE := LINE + 1 end;
  11: if (N mod 2) <> 0 then LINE := 14
         else LINE := LINE + 1;
  12: begin S[I] := R[((N-2)div 4)*2 + 1];
         LINE := LINE + 1 end;
  13: begin I := I + 1; LINE := LINE + 1 end;
  14: begin S[I] := R[(N+2)div 2];
         LINE:=LINE + 1 end;
  15: begin I := I + 1; LINE := LINE + 1 end;
  16: LINE := 9;
  17: begin N := N - 1; LINE := LINE + 1 end;
  18: if N >= 1 then LINE := 5
         else LINE := LINE + 1
  end; (* case  and  while*)
  writeln(S)
end.
% pc -o rom_pas rom.pas
% rom_pas
MMMCMXLVII

3. A second way to eliminate GOTOS: For a second, slightly different method to eliminate GOTOs, consider the Pascal program below on the left, which is an almost exact copy of the original Fortram program, rendered in Pascal.

The Pascal program below on the right (that includes no goto statements in it) uses a different strategy to translate a program with gotos into an equivalent program without goto statements. Here each block of statements corresponding to the target of a goto is treated as a unit, rather than focusing on the individual lines.

Pascal Program With GOTOs

Equivalent Pascal Program Without GOTOs

% cat rom3.pas
(* Pascal program exactly equivalent    *)
(*   to the original Fortran program    *)
(*                                      *)
(*   Uses GOTOs                         *)
program ROMAN;
var
    ROM, I, L, N, K: integer;
    S: array[1..15] of char;
    R: array[1..7] of char;
label
    L1, L2, L3, L4, L5, L6;
begin

L1: R := 'IVXLCDM';
    ROM := 3947;
    I := 1;
    L := 1000;
    N := 13;



L2: if (N mod 4) <> 1 then goto L3;
    
    K := L;
    L := K div 10;




L3: K := K - L*((N mod 4)-1)*((N mod 4)-1);



L4: if ROM < K then goto L6;
    
    ROM := ROM - K;
    if (N mod 2) <> 0 then goto L5;
    
    S[I] := R[((N-2)div 4)*2 + 1];
    I := I + 1;





L5: S[I] := R[(N+2)div 2];
    I := I + 1;
    goto L4;


L6: N := N - 1;
    if N >= 1 then goto L2;

    


    writeln(S)
end.
% pc -o rom3_pas rom3.pas
% rom3_pas
MMMCMXLVII

% cat rom4.pas
(* Equivalent Pascal version of the    *)
(*   original Fortran program          *)
(* Shows another translation strategy  *)
(* No goto statements in this program  *)
program ROMAN;
var
  ROM, I, L, N, K, LABEL: integer;
  S: array[1..15] of char;
  R: array[1..7] of char;
begin
  LABEL := 1;
  while LABEL <> 0 do
  case LABEL of
1:begin
    R := 'IVXLCDM';
    ROM := 3947;
    I := 1;
    L := 1000;
    N := 13;
    LABEL := 2
  end;
2:begin
    if (N mod 4) <> 1 then LABEL := 3 else
    begin
      K := L;
      L := K div 10;
      LABEL := 3
    end
  end;
3:begin
    K := K - L*((N mod 4)-1)*((N mod 4)-1);
    LABEL := 4
  end;
4:begin
    if ROM < K then LABEL := 6 else
    begin
      ROM := ROM - K;
      if (N mod 2) <> 0 then LABEL := 5 else
      begin
        S[I] := R[((N-2)div 4)*2 + 1];
        I := I + 1;
        LABEL := 5
      end
    end
  end;
5:begin
    S[I] := R[(N+2)div 2];
    I := I + 1;
    LABEL := 4;
  end;
6:begin
    N := N - 1;
    if N >= 1 then LABEL := 2
    else LABEL := 0;
  end
  end; (* case and while *)
  writeln(S)
end.
% pc -o rom4_pas rom4.pas
% rom4_pas
MMMCMXLVII

4. C version of the original Fortran program. Here is the C version. Notice that it would not be possible to write this program directly in the Java language, because Java has no goto statement. Source file is: rom.c.

C Program With GOTOs

% cat rom.c
/* C version of program */
#include <stdio.h>
int rom, i, l, n, k;
char s[15];
/* initial blank below due to 
 *   C's 0-based arrays */
char r[8]= " ivxlcdm";
int main() {
    rom = 3947;
    s[0] = ' ';
    i = 1;
    l = 1000;
    n = 13;
L2: if ((n%4) != 1) goto L3;
    k = l;
    l = k/10;
L3: k = k - l*((n%4) - 1)*((n%4) - 1);
L4: if (rom < k) goto L6;
    rom = rom - k;
    if ((n%2) != 0) goto L5;
    s[i] = r[((n-2)/4)*2 + 1];
    i = i + 1;
L5: s[i] = r[(n+2)/2];
    i = i + 1;
    goto L4;
L6: n = n - 1;
    if (n >= 1) goto L2;
    s[i] = '\0';
    printf("%s\n", s);
}
% cc -o rom rom.c
% rom
 mmmcmxlvii

5. "Mystery" Program in C. Here is an even more obscure program written in C, a "mystery" program completely different from the previous ones (and more complicated). Source file is: mystery.c.

"Mystery" C Program With GOTOs

% cat mystery.c
#include <stdio.h>
#define N 100
int k[N+1];

int main() {
     int n = 9973, i, j, y, c, K, P;
     int f = 0, g = 1, h = 1;
     int M, I, p, q, t, r;

     i = 1;
L1:  if (i > N) goto L2;
     n = (n*15551) % 19993;
     k[i] = n;
     i++;
     goto L1;
L2:  i = 2;
L3:  if (i > N) goto L16;
     y = k[i];
     K = k[i]; P = i-1;
L4:  if (h - 1 >= P) goto L5;
     f = g;
     g = h;
     h = f + g;
     goto L4;
L5:  M = h - 1 - P;
     I = g - M;
     p = f;
     q = g - f;
L6:  if ( I > 0 && K <= k[I]) goto L8;
     if (p != 1) goto L7;
     r = -I;
     goto L12;
L7:  I = I + q;
     p = p - q;
     q = q - p;
     goto L6;
L8:  if (K != k[I]) goto L9;
     r = I;
     goto L12;
L9:  if (K >= k[I]) goto L11;
     if (q != 0) goto L10;
     r = -(I - 1);
     goto L12;
     /* continue in next column */

L10: I = I - q;
     t = p;
     p = q;
     q = t - q;
     goto L6;
L11: goto L6;
L12: c = r;
     if (c >= 0) goto L13;
     c = -c;
L13: j = i - 1;
L14: if (j < c + 1) goto L15;
     k[j+1] = k[j];
     j--;
     goto L14;
L15: k[c+1] = y;
     i++;
     goto L3;
L16: P = N;
     printf("  ");
     i = 1;
L17: if (i > 10) goto L18;
     printf("%i\t", i);
     i++;
     goto L17;
L18: printf("\n +");
     i = 1;
L19: if (i > 9) goto L20;
     printf("--------");
     i++;
     goto L19;
L20: printf("\n");
     i = 1;
L21: if (i > P) goto L24;
     if (i%10 != 1) goto L22;
     printf("%i|", i/10);
L22: printf("%i\t", k[i]);
     if (i%10 != 0) goto L23;
     printf("\n");
L23: i++;
     goto L21;
L24: printf("\n\n");
     return 0;
}
% cc -o mystery mystery.c
% mystery

Output of "Mystery" C Program

  1     2       3       4       5       6       7       8       9       10
 +------------------------------------------------------------------------
0|182   532     814     865     914     969     1452    1655    1668    2092
1|2407  2432    2435    2479    2736    2864    2945    3078    3222    4042
2|4081  4197    4361    4416    4422    4425    4531    4968    5203    5207
3|5288  5574    5589    5620    5849    5914    5949    6249    6959    6990
4|7217  7955    8147    8357    8461    8623    8804    9642    9893    10142
5|10165 10328   10395   10595   10858   10894   11257   11269   11514   11619
6|11630 11873   11905   12136   12200   12219   12350   12862   13009   13269
7|13278 13458   13653   13725   13785   14190   15235   15344   16023   16319
8|16408 16899   17016   17254   17262   17293   17593   18082   18349   18459
9|18467 18584   18627   18892   18933   19143   19468   19542   19901   19936

6. Recitation work: For this recitation, you are to practice translating two programs with GOTOs into equivalent programs without GOTOs. Specifically, you are to translate the two C programs in sections 4 and 5 above into Java (preferably) or C programs (C without gotos) using one of the two strategies illustrated in sections 2 and 3 above. (You do not need complicated Java -- everything can even be in a single main function.) For the initial work, you should not translate to a structured version of the program even if you could figure out how to make it structured. In other words, you should initially not try to uncover the loops within the program and translate them to actual loops. The second part of this recitation has you discovering such loops.

7. What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item letters: a, b, c, etc.

Contents of email submission for this recitation:
Last Name, First Name; CS 3723; Recitation Number.
Last Name, First Name (of second person, if two are working together).

Java or C source program that translates the C program in Section 4 above: (.java or .c file). This program should have the organization of one of the programs on the right in Sections 2 or 3. Specifically, it should have a single while and inside that a single switch statement. It should have no goto statements. (Of course you may use an extended if-then-else instead of a switch.)

Log of a run of the program in 1, including the output.

Java or C source program that translates the C program in Section 5 above (the "mystery" program). The same remarks apply as for item 1.

Log of a run of the program in 3, including the output.

Java or C source program that recovers the hidden loops and the structure of the C program in Section 4. This recitation has not taught any specific techniques for this, but the presence of loops and if statements should be fairly clear.

Log of a run of the program in 5, including the output.

(Much Harder) For this part, you are to write a Java or C source program that recovers the hidden loops and the structure of the C program in Section 5 (the "mystery" program). This is much harder than the example in Section 4. This example is partly to demonstrate just how difficult it can be to deal with gotos. If you don't eliminate all gotos, you should submit a program representing how far you got.
[Hint: One way to proceed is to start with the given program that compiles (hopefully) and has a given output. At each stage, you can make small changes, recovering first the most obvious loops one at a time, and repeatedly checking that it still compiles with the same output. If you think about it properly, you'll see that at the core there is a function call and a function definition.]

(Also hard) The algorithm used in the program in section 5 (the "mystery" program) is intricate, but its general approach is fairly straightforward. Roughly what is it doing?

9. Key idea: It always possible to mechanically translate a program with GOTOs into an equivalent program without GOTOs, without necessarily understanding the logic of the program. This will work no matter how complicated the original program is. However, eliminating the GOTOs in this way will not make the structure of the resulting program easier to understand than the original program.

Revision date: 2012-12-30. (Please use ISO 8601, the International Standard.)