Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!noose.ecn.purdue.edu!iuvax!silver!jashley
From: jashley@silver.ucs.indiana.edu (J. Michael Ashley)
Newsgroups: comp.lang.functional
Subject: re: Id array comprehensions revisited
Message-ID: <51369@iuvax.cs.indiana.edu>
Date: 18 Jul 90 21:56:54 GMT
Sender: news@iuvax.cs.indiana.edu
Reply-To: jashley@silver.ucs.indiana.edu (J. Michael Ashley)
Organization: Graceland
Lines: 43


Wolfgang 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.

>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
[...]
>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).

Put aside dataflow for a minute.  Just assume we have a lazy language.  Then
the question now is not whether init1 is strict in its first argument, but
whether or not update is strict in its first argument.  I think it is, so
this simple version of init1 is sequential.

using dataflow, it is certainly sequential!

it's an easy optimization to make init1 run O(log n) using a divide and
conquer algorithm.  this can be done since i-structures are being used to
represent arrays.  no analysis is necessary.

>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).

constructing the index list by concatenating sublists is usually what happens,
so the analysis won't work.  at any rate, even if it could theoretically work,
i bet it would take forever to do the analysis on real codes.

mike ashley
jashley@lanl.gov