A coding exercise

[Chris Torek]

In article <30563 at cca.CCA.COM> g-rh at cca.CCA.COM (Richard Harter)
transforms Kevin Kenny's `penultimate grdgen()' by the method I usually
use (as opposed to essentially mechanical transforms): decide what it
does, then decide how to do that.

>... My first thought was not, how can I set this up as a simple
>recursion, but rather what is this problem like?  And the answer
>immediately sprang to mind -- this is like an odometer turning over the
>miles.  With this in mind I wrote the following in about 5 minutes:

[odometer version deleted]
While it does not matter for the original problem (generate a grid),
this version does not have identical behaviour: in particular, the
original one `ran the odometer dyslexically'.  That is, it counted

  0 0 0 / 1 0 0 / 2 0 0 / ... / 0 1 0 / 1 1 0 / 2 1 0 / ...

while the replacement counts in the `usual' direction,

  0 0 0 / 0 0 1 / 0 0 2 / ... / 0 1 0 / 0 1 1 / 0 1 2 / ...

Fortunately, this is quite easy to change.

>More to the point, it is in no way clear to me that [the `penultimate'
>version] is correct!  I assume that it is, since it was produced
>by a series of transformations from an originally correct program.  But
>if I saw it as original code I would have to work throught it very
>carefully to have confidence in it.

I thought it was fairly obvious, although a comment like `this counts
like a ``df''-digit odometer in base ``nlev'', but with the low order
digits on the left' might have been nice.  Something that is important
is that it *was* a series of mechanical transformations, and one that
is suitable for embedding within a compiler.  Given the level at which
the problem was presented, reaching 7A from the original recursive
version is rather a fair accomplishment.

>Radical simplification:  When I wrote down the above, I was not much
>satisfied with it, because there are several duplications in it.  I
>suspected there must be a simpler way.  One way to look for such things
>is to translate all the logic into goto's, simplify, and translate back
>into structured code. ...

Actually, many optimising compilers do this internally, too.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris