solving the “Rubin problem”

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 None

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):
    return next((x for x in iter if cond(x)), None)

def first_zero_row(arr):
    found = BLS(enumerate(arr),
                lambda (i, row): not BLS(row,
                                         lambda cell: cell != 0))
    return found[0] if found else None

first_zero_row‘s practically 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):
    return next((i for i, row in enumerate(arr)
                 if all(cell == 0 for cell in row)), None)

But where’s the fun in that?

* – Although, regrettably, Python doesn’t support them; see Guido’s rejection to the relevant PEP.