home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / misc / 3081 < prev    next >
Encoding:
Text File  |  1992-09-15  |  2.5 KB  |  71 lines
  1. Newsgroups: comp.lang.misc
  2. Path: sparky!uunet!munnari.oz.au!cs.mu.OZ.AU!munta.cs.mu.OZ.AU!fjh
  3. From: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
  4. Subject: Re: Iteration in single assignment languages
  5. Message-ID: <9226001.12005@mulga.cs.mu.OZ.AU>
  6. Keywords: single assignment iteration
  7. Sender: news@cs.mu.OZ.AU
  8. Organization: Computer Science, University of Melbourne, Australia
  9. References: <psathc8@fido.asd.sgi.com>
  10. Date: Tue, 15 Sep 1992 15:09:09 GMT
  11. Lines: 58
  12.  
  13. iain@sgi.com (Iain McClatchie) writes:
  14.  
  15. >I don't know and wonder how single assignment languages handle these three
  16. >kinds of iteration, especially the last:
  17. >
  18. >1) Loops where you know over what you iterate at compile time.
  19. >   for (i = 0; i < 20; i++) ...
  20. >
  21. >2) Loops where you know over what you iterate before you begin the loop.
  22. >   for (i = a; i < b; i++) {expressions not involving a,b, or i}
  23. >
  24. >3) Loop where you discover over what you iterate as you iterate
  25. >   for (i = 0; abs(z) < 2.; i = i + 1) z = z*z + c;
  26. >
  27. >My examples are coded in something like C, in which an array which is
  28. >iterated over by i is allocated by the programmer beforehand, and it is
  29. >his responsibility to get the size right.
  30. >
  31. >In a single assignment language, I would think that the values taken on
  32. >by z must go into some array z, so that the individual values are
  33. >seperately addressable.  Supposing the compiler cannot optimize away the
  34. >array, how does it know what size it is?  Better yet, how is this third
  35. >loop written in a single assignment language?
  36.  
  37. Single assignment languages normally use recursion instead of interation.
  38. (The compilers will generally compile the recursive code into iterative
  39. machine code, though - this is known as "tail-recursion optimization").
  40.  
  41. The first loop would be written in Prolog as
  42.     loop :- loop(0).
  43.     loop(I) :-
  44.         (I >= 20 ->        % if I >= 20
  45.             true        % then finish the loop
  46.         ;
  47.             whatever(I),    % otherwise perform body of loop,
  48.             I1 is I + 1,    % increment I,
  49.             loop(I1)    % and recursively call loop
  50.         ).
  51.  
  52. The third loop might be written in Haskell as
  53.  
  54.     mandel::int -> complex -> (int, complex)
  55.     mandel i z =
  56.         if abs(z) >= 2.0 then
  57.             (i,z)        -- return i and z
  58.         else
  59.             mandel (i+1) (z*z + c)
  60.                     -- recursively call mandel with
  61.                     -- new values of i and z
  62.  
  63. (If c was not a constant, then you would have to pass it as a parameter
  64. as well as i and z).
  65.  
  66. -- 
  67. Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
  68. This .signature virus is a self-referential statement that is true - but 
  69. you will only be able to consistently believe it if you copy it to your own
  70. .signature file!
  71.