Path: utzoo!attcan!uunet!mcsun!unido!tub!tubopal!wg
From: wg@tubopal.UUCP (Wolfgang Grieskamp)
Newsgroups: comp.lang.functional
Subject: Re: Id array comprehensions revisited
Keywords: Id, Haskell, poor array comprehensions
Message-ID: <1661@opal.tubopal.UUCP>
Date: 17 Jul 90 11:52:39 GMT
References: <51123@iuvax.cs.indiana.edu>
Reply-To: wg@tubopal.UUCP (Wolfgang Grieskamp)
Followup-To: comp.lang.functional
Organization: Technical University of Berlin, Germany
Lines: 70

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