Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!fauern!tub!tubopal!wg
From: wg@tubopal.UUCP (Wolfgang Grieskamp)
Newsgroups: comp.lang.functional
Subject: Re: Id array comprehensions revisited
Message-ID: <1663@opal.tubopal.UUCP>
Date: 17 Jul 90 23:06:41 GMT
References: <51173@iuvax.cs.indiana.edu>
Reply-To: wg@tubopal.UUCP (Wolfgang Grieskamp)
Followup-To: comp.lang.functional
Organization: Technical University of Berlin, Germany
Lines: 50

In article <51173@iuvax.cs.indiana.edu> jashley@silver.ucs.indiana.edu (J. Michael Ashley) writes:
>Wolfgang Grieskamp writes:
>
>>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
>>
>> [...]

>>Regarding to concurrent initialization assume simplisticaly that init1
>>is [[not strict]] lazy in its first argument.
>
>
>This doesn't solve the problem, however.  Since we are using a dataflow
>architecture, the function f will undergo partial evaluation to the point
>where it must have it's argument.  

If I get it right, this a specific problem of dataflow architectures. init1
fires only, when *all* arguments are available, so the next recursion level
may only be reached when update(..) is available (must be something like 
this, I'am not so firm with dataflow architectures).

Anyway, array initialization is not only in FORTRAN inherently 
parallel, but also in functional languages, and that should be pointed out.
You might imagine the evaluation of init1 causes the creation of (n-i)+1 update
"processes". The result of update is not required to bound the recursion,
so init1 may terminate before any f(i) has been evaluated. The bottelneck
appears, if some f(i) is ready, and update requires the updated array of
the i+1 recursion level (this is a inherent problem (also in FORTRAN ...) 
you can only solve with some complicated analysis 
which ensures the commutativity of all performed updates).


>In the case of 
>accumulator comprehensions, the programmer will probably not be using this
>easy-to-optimize "1 to n" construct.  Instead, there will be some arbitrary
>function (probably complicated) that *must return a list*.  

Fusion in the case of the discussed array comprehensions works for *any* 
list producer with an arbitrary number of recursion and termination cases, not
only for "1 to n". However, the (conceptual) fold step can be only applied
to cases which have an outermost list constructor (so if you construct
the index list with a concatenate of two sublists, it will fail for this
case). Another problem is the compilers runtime ... so we actually need
parallel machines to write nice compilers!

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