Id array comprehensions revisited

Thread View: comp.lang.functional

5 messages

[T] Back to Threads [V] Tree View [G] Group Articles

5 total messages Started by J. Michael Ashley Tue, 17 Jul 1990 00:49

#349

Author: J. Michael Ashley
Date: Tue, 17 Jul 1990 00:49

48 lines
2805 bytes

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

But there's no reason why we have to confine ourselves to using this "1 to n"
construct to generate the indices.  In fact, we can use any function we like
to generate the indices.  For example, we can rewrite the above expression as

	{ array (1, n) | [i] = f i || i <- gen 1 n }

where gen is some generator of our own creation.  But what are we going to
create?  We'd like to write something better than the O(n) generator that the
"1 to n" represents.  Unfortunately, I haven't been able to uncover a
O(1) or even O(log n) algorithm.  The difficulty is that the append
function is O(m), where m is the length of the first argument, so the best
I've been able to do is O(m).  This is no good.

Thorsten von Eiken suggested the following trick.  Instead of using one
generator to create the indices, use two!  I'm ignoring the bounds problem,
but this is the idea:

	{ array (1, n) | [i] = f i || j <- 1 to n by 8 &
                                      i <- j to j+7      }

The best you can hope for with this method is O(sqrt n) where n is the
length of the array.  You can use more generators to get O(cubert n), etc...
This is a nice solution, and I don't think you can do much better without
resorting to non-functional constructs (the "make_1d_i_array" function in Id).

Though this is a nice solution, it is still a trick, and I'm not very fond
of tricks.  It seems that the root of the problem is that the generator
produces a *list* of indices.  I say this is the problem because building
a list is an O(n) job and referencing the list is an O(n) job.  A list
is the wrong data structure.

Can anybody else suggest a better definition for array comprehensions?  What
about a "set" as a new data structure?

By the way, array comprehensions are a feature of Haskell, which is
suppossed to be the new standard.  So this question is very relevent!

mike ashley 
jashley@lanl.gov

Re: Id array comprehensions revisited

#353

Author: Wolfgang Grieskamp
Date: Tue, 17 Jul 1990 11:52

70 lines
2776 bytes

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

Re: Id array comprehensions revisited

#354

Author: Wolfgang Grieskamp
Date: Tue, 17 Jul 1990 16:36

11 lines
998 bytes

In article <1661@opal.tubopal.UUCP> wg@tubopal.UUCP (Wolfgang Grieskamp) writes:
> ...
>Regarding to concurrent initialization assume simplisticaly that init1
>is not strict in its first argument.
	 ^^^^
	 NONSENS. I wanted to say "lazy".


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

Re: Id array comprehensions revisited

#360

Author: Tom Thomson
Date: Wed, 18 Jul 1990 19:30

10 lines
926 bytes

In article <51123@iuvax.cs.indiana.edu> jashley@silver.ucs.indiana.edu (J. Michael Ashley) writes:
>Can anybody else suggest a better definition for array comprehensions?  What
>about a "set" as a new data structure?
>
what's "new" about "set"?
Sets have been in Hope+ for a long time.
Perhaps the most interesting set of "set" facilities is in the
Hope+Unification variant of Hope+.

Tom Thomson

Re: Id array comprehensions revisited

#362

Author: Frank Silbermann
Date: Thu, 19 Jul 1990 12:12

18 lines
1058 bytes

J. Michael Ashley:
>>		Can anybody else suggest a better definition
>>		for array comprehensions?  What about a
>>	"set" as a new data structure?

Tom Thomson:
>	what's "new" about "set"?
>	Sets have been in Hope+ for a long time.

It was my understanding that Hope's "set" abstractions
violate the axioms of set theory.
The elements of Hope's "sets" have an implied ordering
accessible to the programmer, and are therefore
more accurately described as _list_ comprehensions,
i.e. list processing with implicit backtracking.

	Frank Silbermann	fs@rex.cs.tulane.edu
	Tulane University	New Orleans, LA  70118

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads