Is `goto' still harmful?

Jan 26 04:27 UTC 2007

Almost 20 years ago, Remmers entered an item in M-Net's programming
conference about structured programming and the use of goto.  He quoted a
letter to the editor of the Communications of the ACM that took exception to
the idea that the `goto' statement should be banned outright as a matter of
course in programming (and, in a larger sense, computer science) education.
The assertion of the letter was that judicious use of goto could enhance
clarity and readability of programs, and in some cases, correctness.

The letter stated that its author gave the following task to a group of 12
or so "expert programmers" (however that was decided):

"Let X be an N by N matrix of integers.  Write a program that will print
 the number of the first all-zero row of X, if any."

(Most of the solutions offered in the thread generalized to an M by N
matrix, where M and N might differ.  This should not materially affect
the answer.)

Various solutions were offered; two of which were incorrect.  Three or
so used goto's.  The rest did not.

The question is: How would you implement this?  (Without cheating and
looking at the answers on M-Net!)  Would you use a goto?  Would that
improve the efficiency and/or readability of the resulting program?

What do people on grex have to say?  Do we still believe the dogma that
goto is only ever harmful, or are there cases where it is acceptable?
Bearing in mind that the major languages of the time the question was
posed included FORTRAN, COBOL, Pascal and others, how have the advances
in languages changed the way we think about these problems in the last
twenty years?  Feel free to post a solution in any language you like
and let's talk about it!

response 2 of 45:

Jan 26 14:18 UTC 2007

I'm certainly NOT an expert programmer, but here is what I came up with
in Perl:


@matrix = (
   [1, 2, 3, 4],
   [0, 5, 6, 0],
   [0, 0, 0, 0],
   [7, 0, 8, 9]
   );

my ($rows, $cols) = matrix_count_rows_cols ($matrix);

my $row = 0;
my $col;
my $found;

while ( $row < $rows ) {
        $col = 0;
        while ( $col < $cols ) {
                $found = $row + 1;              
            if ( $matrix[$row][$col] != 0 ) {
                        $col = $cols;
                        $found = 0;
                }
                $col++;
        }
        if ( $found != 0 ) {
                $row = $rows;
        }
        $row++;
}

if ( $found != 0 ) {
        print "The first all-zero row is row number $found.\n";
}
else {
        print "No all-zero rows found.\n";
}

response 6 of 45:

Jan 26 18:23 UTC 2007

That's closer to what I was thinking about, but still not optimal.  In
particular, once you hit a non-zero element in some column, why do you keep
going?  You know that row is not all-zero at that point: is there a way to
avoid looking at the rest of the row?  And do you actually need $rowsum?

response 8 of 45:

Jan 26 18:49 UTC 2007

Okay, can you spot the bug?

response 10 of 45:

Jan 26 19:13 UTC 2007

Consider the case where a row is all zero.  Then the inner for loop will
terminate naturally, and $j will be equal to $n.  But arrays in Perl are
origin 0, meaning that their indicies range from 0 ... ($n - 1).  In your if
statement, you index $a[$i][$j], but on an all-zero row, $a[$i][$j] is
actually one element beyond the end of array that represents the row; a
classic off by one error.  I could be mistaken, I'm fairly certain there's
no guarantee in Perl that going one past the end of the array always yields
a zero and that this is, in fact, an error.

You could do a test on $j instead of looking at the array to do essentially
the same thing, but then you're doing an extra comparison in the outter loop
that you could avoid in the goto case.  There is another solution using the
facilities of Perl, anyone know what it is?

response 12 of 45:

Jan 26 19:46 UTC 2007

Both.

response 16 of 45:

Jan 26 20:14 UTC 2007

Regarding #14; Interesting.  Nice way to generalize to a totally unexpected
problem domain.  I wonder if you can't avoid the left join by using a
subselect, however...

response 18 of 45:

Jan 26 20:18 UTC 2007

I'm not exactly sure if this gives you the correct answer. But I put the
join in there because MySQL does not allow aggregate functions in the
WHERE expression. 

response 20 of 45:

Jan 26 20:39 UTC 2007

Interesting.  What about exception handling?  If I understand your prohibition
about jumping *out* of the middle of a block, that would rule out jumping out
of nested loops, no?  I actually think that should be allowed, since the
alternatives often involve flag variables and lots of additional checks.  Ick!

response 22 of 45:

Jan 26 22:26 UTC 2007

Excellent.  That is very similar the to method that Remmers used on M-Net,
(20 years ago, in Pascal).  Here is his solution:

From Remmers (excerpt copied without permission):
----
 Let (i,j) be the current (row,column) position.  Assume that
 all rows prior to the ith have been "rejected" (contain at least
 one non-zero element) and that in the ith row, all columns
 after the jth have been "accepted" (are all zero).  We can
 make progress toward termination by updating i and j as follows:
 If x[i,j] = 0, then decrement j; if x[i,j] <> 0, then increment
 i and set j to n.  Termination occurs when we accept an entire
 row (j = 0) or reject the nth row.  (If we use j = -1 to flag
 this, the loop test is simply "j > 0".)

 This leads directly to the algorithm:

        i := 1; j := n;
        while j > 0 do
            if x[i,j] = 0 then j := j-1
            else if i = n then j := -1
            else begin i := i+1; j := n end;
        if j = 0 then writeln('1st all-zero row is ',i)
----

Whereas he tested against the column index, here you test against the
row index, but the idea is the same.  You could avoid the second if
statement inside the loop by using an elif (observe that, if
matrix[row][column] != 0, then we reset column to 0 and we can never
get the case where column == n; that can only happen after we increment
column, and we needn't increment column column if that's the case.  So,
we get the following modification:

def findnonzero(matrix):
         m = len (matrix)
         n = len (matrix [0])
         k = n - 1
         row = 0
         column = 0
         while (row < m):
                 if (matrix [row][column] != 0):
                         row += 1
                         column = 0
                 elif (column == k):
                         print row
                         row = m
                 else:
                         column += 1

I'm not too stokked about the appearance of the temporary k, but that is
just there to deal with the fact that Python arrays are also origin 0, and
we want to (explicitly) avoid the cost of calculating either (column + 1)
or (n - 1) in the conditional (though the python interpreter is probably
smart enough to do that for us).

I claim this code is equivalent to Remmers's.  Clearly, it operates from
the point of view (if one will) of the row instead of the column.  Whether
it will be faster, however, depends on whether non-zero elements appear
frequently in the matrix on not.

response 24 of 45:

Jan 26 23:22 UTC 2007

"error traps" are not goto's in the conventional sense - the code running at
the time of an exception didn't want to abort and wildly jump somewhere else
to execute something different.