Parallel collections (was Re: Exception transparency)

[Nathan Bryant]

Brian Goetz wrote:
> Could you be more concrete on how views could solve the problem of
accommodating both serial and parallel iteration in a type-safe way?

If by type-safe, you mean "in such a way that pureness can be encoded in
the type system", I suspect the answer is "no, views aren't helpful for
that" -- part of this is after all intended as a way to -avoid- exactly
that kind of type checking. "Views", the way I talk about them, are
explicitly non-strict: Iterator.par().forEach() would let you pass an
impure function.

More generally, there is the problem that forEach() itself may
manipulate shared state: it may interact with a fork-join pool. Can one
annotate it as @pure, without @SuppressWarnings("pureness"), without
introducing some weaker, more complex definition of relative purity? In
the absence of annotations, can the runtime discover pureness without
introducing that same weaker definition?

So the options?

0) redo everything with monads-eek! ;)
1) assuming checking at compile time rather than runtime: pureness
violations may only cause a compiler warning, and if overload resolution
is driven by pureness, then one may want a way to cast the pureness
annotation in or out, at a call site, or alternately, some form of
support for call site annotations. (E.g. say I have a pure function, but
I -don't- want to parallelize it, perhaps I'm already parallelizing at a
coarser level and it's just not a win at the lowest level... or more
obviously, I have an impure function which I -do- want to parallelize.)
2) Be strict everywhere... no monads... how?

I suppose it's all "workable" if one is willing to admit
@SuppressWarnings("pureness")