g-rh@cca.CCA.COM (Richard Harter) (07/08/88)
In article <77200036@p.cs.uiuc.edu> kenny@p.cs.uiuc.edu writes: In a previous Kenny considered the problem of printing all of the node indices of a hypercube where the number of dimensions is not fixed in advance. He started with a recursive formulation and went through a number of transformations. He presents the following as a penultimate form (always leaving room for an ultimate form). > PROGRAM 7A. >[main program still hasn't changed] >grdgen (df, nlev) > register int df; /* no. of degrees of freedom */ > register int nlev; /* no. of levels each df */ >{ > register int i; > register int j; > register int totaldfm1 = df - 1; > static int value [MAXDF]; /* to hold current values of all df's */ > > for (;;) { > while (df >= 0) /* Set up initial values */ > value [df--] = 0; > > for (j = 0; j < totaldfm1; ++j) /* Print a node */ > printf ("%d ", value [j]); > printf ("%d\n", value [j]); > > do { /* Develop another node */ > if (df >= totaldfm1) return; > i = value [++df] + 1; > } while (i >= nlev); > value [df--] = i; > } >} I must admit that I perused the original long article but did not follow it in detail. The problem piqued my interest, so I set down to solve it de novo. 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: doohickey(n,m) int n; /* No of dimensions */ int m; /* Max range on each dimension */ { int i; /* Loop index */ int w; /* Index being altered */ int *v; /* Array of indices */ int *vp; /* Ptr for print loop */ char *malloc(); /* Old faithful storage allocator*/ v = (int *)malloc(n*sizeof int); /* Get space for indices array */ for (i=n,vp=v;i>0;i--) *vp++ = 0;/* Initialize indices to zero */ for (;;) { /* Loop until all done */ for (i=n-1,vp=v;i>0;i--) printf("%d ",*vp++) /* Print n-1 v's */ printf("%d\n",*vp); /* Print last with line feed */ w = n-1; /* Point to last index */ v[w]++; /* Advance last index */ while (v[w]>=m) { /* Rollover loop */ v[w] = 0; /* Roll current index over to 0 */ w--; /* Next lower index */ if (w<0) break; /* Indices exhausted, all done */ v[w]++; /* Advance current index */ } /* End rollover loop */ if (w<0) break; /* Escape outer loop if done */ } /* End of do-all loop */ } /* End of procedure doohickey */ Initial comments: This is, I submit, clearer than Kenny's 7A. There is an immediate intuitive model of what is happening and why. In fact, I do not find 7A clear at all -- a quick reading says that you reset the value array back to zero each time, and that there is no escape from the outer loop. On a more careful reading you see that a return is used as an escape (one if in the above can be avoided by using a return as a multilevel break), and that the variable df bounces around. I don't much like this -- I like my variables to have well defined unique meanings, specified in the documentation, and there is no such specification in 7A. More to the point, it is in no way clear to me that 7A 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. On using procedures: Both the above and 7A use a procedure. For this limited problem, that is fine. However this is a general problem -- provide a coding technique for handling indexed loops with a variable number of dimensions, with an inner core of action. One does better, I think, in working out this kind of problem by not gratuituously assuming that you can put it in a procedure. 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. Another few minutes produced, for the loop logic, next: /* Loop point for next case */ ... action to be performed ... w = n-1; /* Start with last index */ rollover: /* Loop point for index push */ if ((++v[w])<m) goto next; /* Advance value, check range */ v[w--] = 0; /* Reset current index */ if (w >= 0) goto rollover; /* Next lower index is legit */ /* This is fallthru when done */ Now this is quite pretty in its way -- the logic is clear and the number of statements is a minimum. Perhaps Mr. Rubin will want to use this as an example in his campaign on behalf of the goto :-)! I will leave the translation of this code back into goto-less C as an exercise for the reader. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
chris@mimsy.UUCP (Chris Torek) (07/09/88)
In article <30563@cca.CCA.COM> g-rh@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@mimsy.umd.edu Path: uunet!mimsy!chris
djones@megatest.UUCP (Dave Jones) (07/09/88)
From article <30563@cca.CCA.COM>, by g-rh@cca.CCA.COM (Richard Harter): > In article <77200036@p.cs.uiuc.edu> kenny@p.cs.uiuc.edu writes: ... [ Code omited. ] > Now this is quite pretty in its way -- the logic is clear and the number > of statements is a minimum. Perhaps Mr. Rubin will want to use this as > an example in his campaign on behalf of the goto :-)! I will leave the > translation of this code back into goto-less C as an exercise for the > reader. If the "logic is clear and the number of statements is minimum," don't muck with it. You have better things to do than to improve clear efficient code. For example, you could be at the beach, getting your exercise for the reader from a cheap novel. -- Dave J.
g-rh@cca.CCA.COM (Richard Harter) (07/09/88)
In article <12378@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >In article <30563@cca.CCA.COM> g-rh@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.