home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / arch / 10427 < prev    next >
Encoding:
Internet Message Format  |  1992-11-07  |  2.5 KB
  1. Xref: sparky comp.arch:10427 comp.lang.misc:3505
  2. Newsgroups: comp.arch,comp.lang.misc
  3. Path: sparky!uunet!ukma!darwin.sura.net!zaphod.mps.ohio-state.edu!cs.utexas.edu!bcm!rice!sabry
  4. From: sabry@rice.edu (Amr Sabry)
  5. Subject: Re: A challenge to the anti-goto
  6. Message-ID: <Bx9G9F.4E2@rice.edu>
  7. Originator: sabry@datura.cs.rice.edu
  8. Sender: news@rice.edu (News)
  9. Reply-To: sabry@rice.edu (Amr Sabry)
  10. Organization: Rice University
  11. References: <Bwznzx.Dr1@mentor.cc.purdue.edu> <Bx0BuG.s4@mentor.cc.purdue.edu> <1992Nov5.111943.21554@harlqn.co.uk> <Bx8x1y.C2@mentor.cc.purdue.edu>
  12. Date: Thu, 5 Nov 1992 20:44:02 GMT
  13. Lines: 45
  14.  
  15.  
  16. In article <Bx8x1y.C2@mentor.cc.purdue.edu>, hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
  17. |> In article <1992Nov5.111943.21554@harlqn.co.uk> daveb@harlqn.co.uk (Dave Berry) writes:
  18. |> >It's easy to get rid of these gotos.  Every goto can be replaced by a
  19. |> >tail-recursive function call.  This can be compiled into the same machine
  20. |> >code. 
  21. |>
  22. |> This is only part of the challenge.  The other part of the challenge is
  23. |> to do this in such a way that the resulting code will be at least nearly
  24. |> as efficient.  In order to accomplish this, one thing  necessary is that
  25. |> every one of the function calls be a totally-non-context switching function,
  26. |> with nothing added to the stack.  Now it matters not to me what you call
  27. |> such a beast, BUT IT IS A GOTO.
  28.  
  29. Yes, it is a goto, and this is exactly what Berry said. A function
  30. call in a "tail" position is a goto. Some languages require the
  31. compiler to recognize this and some don't. However, most descent
  32. compilers will do it anyway.
  33.  
  34. |> I have never seen ML code before.  If the above features could be added,
  35. |> I would have no problem with it.  But, as I have pointed out, these
  36. |> features are equivalent to reordering code, gotos, and dropthroughs,
  37. |> and they do not seem to be provided in the language.  Would the compiler
  38. |> do it?  If so, it meets the challenge for this code.
  39.  
  40. An example:
  41.  
  42. factorial(n, result)
  43.     if n=0 then result
  44.     else fact (n-1, result*n)
  45.  
  46. is compiled as if it was written like:
  47.  
  48. factorial(n,result)
  49. label 100: if n=0 then result
  50.        else begin      n = n-1
  51.              result = result * n 
  52.             goto 100
  53.  
  54. No context-switching, no stack, nothing, just a goto. 
  55. -- 
  56. Amr Sabry                             sabry@cs.rice.edu
  57. ---------------------------------------------------------------------
  58. Man will occasionally stumble over the truth, but most of the time he
  59. will pick himself up and continue on.-- Churchill's Commentary on Man
  60.