home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / misc / 3496 < prev    next >
Encoding:
Text File  |  1992-11-05  |  3.8 KB  |  94 lines

  1. Newsgroups: comp.lang.misc
  2. Path: sparky!uunet!ukma!darwin.sura.net!udel!louie!ori.cis.udel.edu!carroll
  3. From: carroll@ori.cis.udel.edu (Mark C. Carroll)
  4. Subject: Re: A challenge to the anti-goto
  5. Message-ID: <1992Nov5.165716.9164@udel.edu>
  6. Sender: usenet@udel.edu (USENET News Service)
  7. Nntp-Posting-Host: ori.cis.udel.edu
  8. Organization: University of Delaware, Newark
  9. References: <1992Nov3.165005.18037@midway.uchicago.edu> <BEVAN.92Nov3211454@hippo.cs.man.ac.uk> <Bx6z1J.57r@mentor.cc.purdue.edu>
  10. Date: Thu, 5 Nov 1992 16:57:16 GMT
  11. Lines: 81
  12.  
  13. In article <Bx6z1J.57r@mentor.cc.purdue.edu> hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
  14. >In article <BEVAN.92Nov3211454@hippo.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
  15. >>In article <1992Nov3.165005.18037@midway.uchicago.edu> dave@alex.uchicago.edu (Dave Griffith) writes:
  16. >>   >   If we've known about this problem for twenty years, why don't we
  17. >>   >   have more powerful `break' instructions in our existing languages??
  18. >
  19. >>   >Code the inner loops as a function, and use 'return' as your
  20. >>   >powerful 'break'. 
  21. >
  22. >>   Well, no.  The idea is to be able to break out of multiple loops.  Making
  23. >>   functions out of your inner loops does nothing to help this.  You would have
  24. >>   to use setjmp/longjmp, with all the hideousness that entails.  
  25. >
  26. >>   It should be noted that Ada and CLU have named loops and named breaks.  They
  27. >>   are indeed quite nice for many control flow problems.
  28. >
  29. >>You could always use a variant of the function approach and have
  30. >>explicit continuations i.e. don't "return" from functions, just call
  31. >>the next function with the "result" of the current one.  I don't know
  32. >>what a C compiler would make of this, but a number of Scheme (and at
  33. >>least one Prolog) compiler transforms everything into this sort of
  34. >>code and consequently deals efficiently with it.  Of course, whether
  35. >>a continuation based program is easier to understand than one which
  36. >>uses explicit gotos is something I'll leave others to decide.
  37. >
  38. >There are two major problems with this.  For one, the stack grows with
  39. >the non-returns, and taking care of this would be at least as bad as
  40. >garbage collection, if not worse, as stack locations are, for extremely
  41. >good reasons, not globally known.  For another, this does not handle
  42. >procedures which continue the resource use of the current procedure.
  43. >
  44.  
  45. Wrong... (You know, I _really_ hate it when people criticize something
  46. out of ignorance. Why must you post a criticism of something that you
  47. know nothing about?)
  48.  
  49. First, compilation by continuations does _not_ necessarily incur stack
  50. growth. Calling a continuation is not quite a traditional function call -
  51. continuations NEVER RETURN. 
  52.  
  53. The idea of continuations is that at any point, the rest of the computation
  54. being conducted can be thought of as a function which takes as arguments
  55. the value computed by the current statement.
  56.  
  57. So, consider the following:
  58.  
  59.    A := B + C
  60.    D := A * B
  61.    E := D + 2
  62.  
  63. This can be rewritten as follows:
  64.  
  65. function step1() {
  66.    return step2(B+C)
  67. }
  68.  
  69. function step2(A:integer) {
  70.    return step3(A*B)
  71. }
  72.  
  73. function step3(D : integer) {
  74.    return D+2;
  75. }
  76.    
  77. These are all tail calls, so no stack growth is necessary. 
  78.  
  79. Compilation by using continuation passing does _not_ have any problem
  80. with procedures which continue the resource use of the current
  81. procedure.  The continuation function is the _entire_ rest of the
  82. computation, so it includes all resources that are needed by the rest
  83. of the computation.
  84.  
  85. There's a lot more to it than this; if you're really interested in it,
  86. try getting a copy of Appel's book.
  87.  
  88.     <MC>
  89. -- 
  90. || Mark Craig Carroll: <MC>     ||"I prize the cloudy, tearing sky,
  91. || Univ of Delaware, Dept of CIS|| for the thoughts that flap and fly.
  92. || Grad Student/Labstaff Hacker || For staying in and reading by.
  93. || carroll@udel.edu             || For sitting under" -Karen Peris
  94.