🚀 go-pugleaf

In article <51123@iuvax.cs.indiana.edu> jashley@silver.ucs.indiana.edu (J. Michael Ashley) writes:
>A little while ago I asked why array comprehensions are not parallel.  In
>particular, why does an array comprehension like this:
>
>	{ array (1, n) | [i] = f i || i <- 1 to n }
>
>not evaluate the (f i)'s concurrently?  Well, it turns out that the i's get
>generated sequentially as a list (a list in the data structure sense, mind
>you).

This index list is intermediate and an optimizing compiler can eliminate it 
using loop fusion.

Assum you have 

  FUN .. : nat ** nat -> seq[nat] 
  DEF i..n == IF i>n  THEN <>
	      IF i<=n THEN i::((i+1)..n) ELSE <> FI

and

  FUN init: array[alpha] ** (nat -> alpha) ** seq[nat] -> array[alpha] 
  DEF init(A,f,S) == IF <>?(S) THEN A 
		     IF ::?(S) THEN init(update(A,hd(S),f(hd(S))),f,tl(S)) FI

and somewhere the expression

  ...  init(array(1,n),f,1..n) ...

as a low level representation of the array comprehension. 

Now the compiler may derive the new function:

  FUN init1: array[alpha] ** (nat -> alpha) ** nat ** nat -> array[alpha]

  DEF init1(A,f,i,n) == IF <>?(i..n) THEN A
			IF ::?(i..n) THEN init(update(A,hd(i..n),f(hd(i..n))),
					       tl(i..n)) FI

and the rule:

  LAW init(A,f,i..n) == init1(A,f,i,n)


Unfolding .. once in init1 and simplification yields:

  DEF init1(A,f,i,n) == IF i>n  THEN A
			IF i<=n THEN init(update(A,hd(i::((i+1)..n)),
						   f(hd(i::((i+1)..n)))),
					  tl(i::((i+1)..n))) FI

			...
			IF i<=n THEN init(update(A,i,f(i)),(i+1)..n) 

Using the above rule you get finaly:

  DEF init1(A,f,i,n) == IF i>n  THEN A
			IF i<=n THEN init1(update(A,i,f(i)),i+1,n) FI

(A compiler will probably not use this fold/unfold method,
because it depends to much on "eureka" steps. Furthermore, the view 
is based on the assumption that update is O(1). Such an update
can be established by a sharing analysis for the given example).

Regarding to concurrent initialization assume simplisticaly that init1
is not strict in its first argument.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Wolfgang Grieskamp       
wg@opal.cs.tu-berlin.de        tub!tubopal!wg         wg%opal@DB0TUI11.BITNET