|
|
| Author |
Message |
cross
|
|
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!
|
| 45 responses total. |
remmers
|
|
response 1 of 45:
|
Jan 26 12:56 UTC 2007 |
(It would be cheating for me to post my solution, but I await others'
with interest.)
|
nharmon
|
|
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";
}
|
cross
|
|
response 3 of 45:
|
Jan 26 17:00 UTC 2007 |
Hmm, that will work, but there are better solutions. Early on in the thread,
Remmers posted the letter's author's solution, which looked something like
this (in Pascal, slightly reformated):
for i := 1 to n
do begin
for j := 1 to n do
if x[i,j] <> 0
then goto reject;
writeln('1st all-zero row is ',i);
break;
reject:
end
In C, we'd rewrite this as:
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
if (x[i][j] != 0)
goto reject;
printf("1st all-zero row is %d\n", i);
break;
reject:
}
Nate, you gave a go in Perl: how would you recast this code directly
into Perl, without using goto? (Hint: look at loop control statements.)
|
nharmon
|
|
response 4 of 45:
|
Jan 26 18:09 UTC 2007 |
This response has been erased.
|
nharmon
|
|
response 5 of 45:
|
Jan 26 18:13 UTC 2007 |
Woops
Make that:
for ($i = 0; $i < $n; $i++) {
$rowsum = 0;
for ($j = 0; $j < $n; $j++) {
$rowsum = $rowsum + $matrix[$i][$j];
}
if ( $rowsum != 0 ) {
next;
}
print "1st all-zero row is ".($i+1)."\n";
last;
}
|
cross
|
|
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?
|
nharmon
|
|
response 7 of 45:
|
Jan 26 18:35 UTC 2007 |
I see what you mean, Dan.
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
if ( $matrix[$i][$j] != 0 ) {
last;
}
}
if ( $matrix[$i][$j] == 0 ) {
print "1st all-zero row is ".($i+1)."\n";
last;
}
}
|
cross
|
|
response 8 of 45:
|
Jan 26 18:49 UTC 2007 |
Okay, can you spot the bug?
|
nharmon
|
|
response 9 of 45:
|
Jan 26 19:02 UTC 2007 |
It seems to test okay with real data. Maybe you can clue me in? :)
|
cross
|
|
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?
|