🚀 go-pugleaf

In article <Bx0BuG.s4@mentor.cc.purdue.edu> hrubin@mentor.cc.purdue.edu (Herman Rubin) writes:
>To try to clarify the program, I am writing it with ONLY gotos for transfer of
>control.  This should enable those who have difficulty following the pattern to
>see what it is doing.
>
   [ code and other stuff deleted ]
>
>The challenge still stands; code this in a HLL without using gotos, and
>try to get as fast code.

O.K., here's my first cut at improving the code.  By ``improved'', I mean
``more structured'' and ``probably faster''.  I don't want to get into an
argument about whether it's more readable, since that's more subjective,
and also not strictly part of the challenge.  Some comments follow after
the code; please read them before replying!


extern B;
n = 0;
m = 0;
b = B;
start:
    g = ...;
    switch ( g ) {
        case 1:
            n += 1;
            goto start;
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 11:
        case 12:
            goto start;
        case 2:
            return;
        case 4:
            g = ...;
            m |= ( b>>g );
            return;
        case 7:
            g4 = 1;		/* probably could be eliminated		*/
            m |= ( b>>1 );
            g = ...;
            m |= ( b>>g );
            return;
        case 8:
            h = ...;
            g4 = h>>1;
            if ( h & 1 ) {
                g4 += 2;
                b >>= g4;
                m |= b;
                b <<= 1;
                g = ...;
                m |= ( b>>g );
                return;
            }
            goto label4;
        default:
            g16 = ( g - 9 )>>4;
            g &= 3;
            if ( g == 1 ) goto label5;
            if ( g != 0 ) goto start;
            h = ...;
            g4 = ( h + 1 )>>1;
            if ( h & 1 ) {
                j = 6;
            } else {
                g = ...;
                if ( g & 3 != 2 ) goto start;
                j = 7;
                while ( ! ..bit.. ) {
                    j += 1;
                    g = ...;
                    if ( ( 2<<( g - 1 )/j ) & 1 == 0 ) goto start;
                }
            }
            do {
                i = C( j );
                b >>= 1;
            } while ( i == j || i == 0 );
            m |= b;
            switch ( i ) {
                case 1:
                default:
                    return;
                case 2:
                    g = ...;
                    m |= ( b>>g );
                    return;
                case 3:
                    b >>= g4;
                    m |= b;
                    b <<= 1;
                    g = ...;
                    m |= ( b>>g );
                    return;
                case 4:
                    goto label4;
                case 5:
                    break;
            }
    }
label5:
    b >>= g16;
    m |= b;
    g = ...;
    if ( ..bit.. ) {
        if ( g & 1 ) {
            g = ...;
            m |= ( b>>g );
        }
        return;
    }
    g4 = ( g + 1 )>>1;
    if ( g & 1 ) {
        b >>= g4;
        m |= b;
        b <<= 1;
        g = ...;
        m |= ( b>>g );
        return;
    }
label4:
    g = ...;
    if ( g4 < g ) {
        m |= ( b>>g4 | b>>g );
        return;
    }
    m |= b>>g;
    if ( ! ..bit.. ) {
        b >>= ( g4 + 1 );
        m |= b;
        g = ...;
        m |= ( b>>g );
    }


If you've gotten this far, I'm sure you've noticed I haven't eliminated all
the gotos.  Three labels remain:  `start', `label3', and `label4'.  The last
two could be eliminated easily, either at a minor cost in speed, or by
ballooning the code uncomfortably.  Herman, if you're interested, I can show
you the code that avoids these.  However, to everyone who's decided to take
up the Herman challenge, I don't believe the control constructs of C are
powerful enough to make removing the `start' label feasible.  I make the
following claim:

	When coded in C, Herman's algorithm cannot be efficiently
	implemented without at least one label (`start'), and
	corresponding `goto's.

(I look forward to seeing this claim refuted!)

Actually, lest anyone wonder about my claim, I should mention that it's
well known that the structured control constructs of most ``Pascal-like''
languages are not sufficient to handle all of the ``interesting''
algorithms, if we assume algorithms like Herman's count as being interesting.

``Well now, this sounds like a problem,'' you might say.  ``Can't we do
something about it?''  To which the answer is:  ``Yes and no.''

If we define ``interesting'' to mean ``any possible control flow graph is
allowed,'' then it's easy to argue that you have to have some kind of
`goto'.  So the situation on the one hand could be viewed as hopeless.
However, it turns out that if we instead define ``interesting'' to mean
``all algorithms whose control flow graphs don't have multiple entries into
a loop''---and this obviously includes Herman's code---it's been shown
(sorry, I don't have a reference handy) that all that's lacking from most
languages is a good, general-purpose way of exiting arbitrarily-nested
control constructs.  In other words, what we need here is a more powerful
`break' instruction.  (I leave it as an exercise to figure out how that
would help on Herman's code.)

Moreover, it's widely suspected that loops with multiple entries are a real
rarity, even when `goto's are available.  So one could claim that a general-
purpose `break' is all we're really missing out of our existing repertoire
of control constructs!

(However, before everyone rushes out to invent new `break' constructs,
you might first want to look at all the ideas that were proposed in the
Seventies, some of which should be perfectly acceptable.  A particularly
good starting point, in my opinion, would be a proposal made by Zahn in 1974:

	Charles T. Zahn, Jr.  A control statement for natural top-down
	structured programming.  Programming Symposium:  Proceedings,
	Colloque sur la Programmation (April 9--11, 1974).  Edited by
	B. Robinet.  Lecture Notes in Computer Science 19.  Springer-Verlag
	(1974).  pp. 170--180.  )

In any event, all of this sort of begs the question:

	If we've known about this problem for twenty years, why don't we
	have more powerful `break' instructions in our existing languages??

Beats me.

----------------------------------------------------------------------------
Boycott redwood.  Boycott Louisiana-Pacific.  Keep the forests.  YYYYYYYYYYY
John Hauser---jhauser@cs.berkeley.edu  YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY