NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/arch/10409

Internet Message Format | 1992-11-04 | 4.5 KB

Xref: sparky comp.arch:10409 comp.lang.misc:3492
Newsgroups: comp.arch,comp.lang.misc
Path: sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!news.nd.edu!mentor.cc.purdue.edu!pop.stat.purdue.edu!hrubin
From: [e-mail] (Herman Rubin)
Subject: Re: A challenge to the anti-goto
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET News)
Organization: Purdue University Statistics Department
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Thu, 5 Nov 1992 13:49:09 GMT
Lines: 162

In article <[e-mail]> [e-mail] (Dave Berry) writes:
>It's easy to get rid of these gotos.  Every goto can be replaced by a
>tail-recursive function call.  This can be compiled into the same machine
>code.  Here is Herman's example, gratuitously rewritten in ML.

>(Note: I decided not to make the program functional, for clarity.  Also
>for clarity I left out all occurrences of the dereference operator.  I
>don't know if an existing ML compiler would produce code as efficient as
>the original C - they aren't usually optimised for this sort of work.
>But that's not the point - you could write this in C if your compiler
>optimises tail-recursion.)

This is only part of the challenge.  The other part of the challenge is
to do this in such a way that the resulting code will be at least nearly
as efficient.  In order to accomplish this, one thing  necessary is that
every one of the function calls be a totally-non-context switching function,
with nothing added to the stack.  Now it matters not to me what you call
such a beast, BUT IT IS A GOTO.

Another explicit inefficiency is that dropthroughs do not seem to occur.
add() should dropthrough to start(), and the numbered labels should drop-
through to the next lower number.  These are essentially costless
efficiencies in the object code.

I have never seen ML code before.  If the above features could be added,
I would have no problem with it.  But, as I have pointed out, these
features are equivalent to reordering code, gotos, and dropthroughs,
and they do not seem to be provided in the language.  Would the compiler
do it?  If so, it meets the challenge for this code.

>(Another note: In both ML and C it would be possible (and possibly
>advisable) to use other features of the language to structure some
>parts of this program.)


>let
>  val n = ref 0
>  val m = ref 0
>  val b = ref B

>  fun start() =
>  ( g := ...;
>    body()
>  )

>  fun body() =
>    case g of
>      1 => add()
>    | 2 => ()
>    | 3 => start()
>    | 4 => label2()
>    | 5 => start()
>    | 6 => start()
>    | 7 => (g4 := 1; label3())
>    | 8 => ( h := ...;
>             g4 := h>>1;
>             if h&1 then
>             ( g4+=2;
>           label3()
>             )
>             else
>               label4()
>           )
>    | _ => if g > 8 andalso g <= 12 then
>             start()
>           else
>           ( g16 := (g-9)>>4;
>             g &= 3;
>             if g=1 then
>           label5()
>             else if g=2 orelse g=3 then
>           start()
>             else
>             ( h := ...;
>           g4 := (h+1)>>1;
>           if h&1 then
>           ( j := 6;
>             labelh()
>           )
>           else
>           ( j := 7;
>             g := ...;
>             if g mod 3 <> 2 then start() else loop()
>           )
>             )
>           )

>  fun add() = (n += 1; start ())

>  fun loop() =
>    if bit then
>      labelh ()
>    else
>    ( j += 1;
>      g := ...;
>      if (2<<(g-1)/j)&1 = 0 then
>    start()
>      else
>    loop ();
>    )

>  fun labelh() =
>  ( i := C(j);
>    b >>= 1;
>    if i=j orelse i=0 then
>      labelh()
>    else
>    ( m |= b;
>      case i of
>    1 => ()
>      | 2 => label2()
>      | 3 => label3()
>      | 4 => label4()
>      | _ => label5()
>    )
>  )

>  fun label5 () =
>  ( b >>= g16;
>    m |= b;
>    g := ...;
>    if bit then
>      if g&1 then label2() else ()
>    else
>    ( g4 := (g+1)>>1;
>      if g&1 then label3() else label4()
>    )
>  )

>  fun label4() =
>  ( g := ...;
>    if g4 < g then
>    ( m |= (b>>g4 | b>>g);
>      ()
>    ) else
>    ( m |= b>>g;
>      if bit then () else (b >>= 1; label3())
>    )
>  )

>  fun label3() =
>  ( b >>= g4;
>    m |= b;
>    b <<= 1;
>    label2()
>  )

>  fun label2() =
>  ( g = ...;
>    m |= (b>>g);
>    ()
>  )
>in
>  start()
>end;


--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: [phone]
[e-mail] (Internet, bitnet)
{purdue,pur-ee}!pop.stat!hrubin(UUCP)