🚀 go-pugleaf

iain@sgi.com (Iain McClatchie) writes:

>I don't know and wonder how single assignment languages handle these three
>kinds of iteration, especially the last:
>
>1) Loops where you know over what you iterate at compile time.
>   for (i = 0; i < 20; i++) ...
>
>2) Loops where you know over what you iterate before you begin the loop.
>   for (i = a; i < b; i++) {expressions not involving a,b, or i}
>
>3) Loop where you discover over what you iterate as you iterate
>   for (i = 0; abs(z) < 2.; i = i + 1) z = z*z + c;
>
>My examples are coded in something like C, in which an array which is
>iterated over by i is allocated by the programmer beforehand, and it is
>his responsibility to get the size right.
>
>In a single assignment language, I would think that the values taken on
>by z must go into some array z, so that the individual values are
>seperately addressable.  Supposing the compiler cannot optimize away the
>array, how does it know what size it is?  Better yet, how is this third
>loop written in a single assignment language?

Single assignment languages normally use recursion instead of interation.
(The compilers will generally compile the recursive code into iterative
machine code, though - this is known as "tail-recursion optimization").

The first loop would be written in Prolog as
	loop :- loop(0).
	loop(I) :-
		(I >= 20 ->		% if I >= 20
			true		% then finish the loop
		;
			whatever(I),	% otherwise perform body of loop,
			I1 is I + 1,	% increment I,
			loop(I1)	% and recursively call loop
		).

The third loop might be written in Haskell as

	mandel::int -> complex -> (int, complex)
	mandel i z =
		if abs(z) >= 2.0 then
			(i,z)		-- return i and z
		else
			mandel (i+1) (z*z + c)
					-- recursively call mandel with
					-- new values of i and z

(If c was not a constant, then you would have to pass it as a parameter
as well as i and z).

-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
This .signature virus is a self-referential statement that is true - but 
you will only be able to consistently believe it if you copy it to your own
.signature file!