A coding exercise

[Richard Harter]

In article <12378 at mimsy.UUCP> chris at mimsy.UUCP (Chris Torek) writes:
>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.

	Hey, I like this.  I think of it as the "what's really going on
here?" approach.  A simple example of this kind of thing is setting up a
loop.  A loop usually looks something like this

	initialize
	loop 
	   process case
	   determine next case
	   exit if no next case
	   end loop

Now the important thing about a loop is -- what is the thing that is to be
done in a single pass through the loop, i.e. what constitutes a case.  Until
that has been clarified the issue of determining the next case is *obscure*.
In the present instance the 'case' may be

(a)	an single distinct set of index values, or
(b)	a primitive action, i.e. altering an index, a 'carry' operation, or
	a action on the set of index values.

The first choice leads to one of the cited programs, the second to a state
machine implementation.

>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.

Quite true.  I was impressed. 

Re the final goto using version, and the hand optimization used to get
to it, Chris remarks

>Actually, many optimising compilers do this internally, too.

This is an important point, which I didn't mention.  If the compiler is
good, an 'optimized' version using goto's may actually compile into less
efficient code.

One final point is that there is a real optimization for this problem,
which is to use an analog of gray code.  For those who aren't familiar
with it, gray code is a way of stepping through the binary integers such
that only one bit changes at each increment.  Example:

	000
	001
	011
	010
	110
	111
	101
	100

(Gray code is quite often used in A/D converters.)  When nlev>2 the numbers
in each column march up and then down with a modification direction rule.
Working this out is a fun problem which I won't spoil for anyone by posting
the code :-).
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.