In “GOTO Considered Harmful” Considered Harmful (a response to Dijkstra’s famous letter), Frank Rubin gives an example of a very simple problem which he claims is best solved with the judicious use of a GOTO statement (*gasp*):
Let X be an N×N matrix of integers. Write a program that will print the number of the first all-zero row of X, if any.
The reason why this is (supposedly) hard without GOTO is that it involves breaking/continuing out of a nested loop; most structured languages only support breaking/continuing the smallest loop a statement is contained in. So, all Rubin does with his GOTO is simulate a labelled continue statement. Personally, I think labelled break/continue statements are a very natural feature for a structured language to have*, and I am thoroughly unconvinced by Rubin’s claim that this is somehow a general defense of GOTO.
But Dijkstra’s response takes a different, more conceptual approach. Dijkstra claims that the problem’s statement immediately calls for a “bounded linear search” inside of a “bounded linear search”. Since it is well-understood how to construct a loop to perform a bounded linear search, a GOTO-less solution becomes apparent.
Well, at least in the abstract. I realized I didn’t really know how to implement this in Python. One important ingredient was a for-loop which only keeps running as long as some condition is satisfied (and its iterator hasn’t run out). I didn’t want to do this by putting a conditional “break” at the end of the loop: that would replace loop semantics with tangled procedural flow. And I certainly didn’t want to use a while loop and iterate the iterator by hand: that’s just ugly. But I realized that I should be able to make an iterator which “filters” another iterator by a condition. Turns out it already exists, as itertools.takewhile. With that, we have:
from itertools import takewhile
def first_zero_row(arr):
row_found = False
for i, row in enumerate(takewhile(lambda x: not row_found, arr)):
cell_found = False
for cell in takewhile(lambda x: not cell_found, row):
if cell != 0: cell_found = True
if not cell_found: row_found = True
return i if row_found else -1
Honestly, though, any time you see something like lambda x: not row_found you know you’re being a bit too clever for your own good. Also, although this is a straightforward translation of the solution Dijkstra presents, it obfuscates the underlying concept, of the “nested bounded linear search”. We have the luxury of functional programming in Python; we can encode things very, very cleanly:
def BLS(iter, cond):
for i, item in enumerate(iter):
if cond(item):
return i
return -1
def first_zero_row(arr):
return BLS(arr,
lambda row: -1 == BLS(row,
lambda cell: cell != 0))
first_zero_row‘s a one-liner! An inscrutable, nested-lambda’d one-liner, but these are the sacrifices we make for conceptual purity.
Of course, if I were actually solving this problem for non-academic reasons, I’d just say:
def first_zero_row(arr):
zero_rows = [i for i, row in enumerate(arr)
if all(cell == 0 for cell in row)]
return zero_rows[0] if zero_rows else -1
But where’s the fun in that?
* – Although, regrettably, Python doesn’t support them; see Guido’s rejection to the relevant PEP.
