Thu Sep 10 13:01:50 CEST 2009

Getting rid of CONS

The point in [1] is that ordinary recursive first/rest approach is
inherently serial, and in order to make it parallizable the
decomposition should be more vector-like: split / process / append.

The interesting remark (p.68) is that for any serial program that can
be written as a composition of functions, it might be possible to
parallellize those because of associativity as long as some kind of
decoupling of intermediate functions can be found.

This reminds me of something ;)

Anyways, apparently ``parallel prefix function composition'' is
something that can be used here[2].

The conclusion seems to be that MapReduce is a big deal, and that
there are ways around the need for commutativity.

One thing that cought my eye is this[3]:

  ``If you can construct two sequential versions of a function that is
  a homomorphism on lists, one that operates left-to-right and one
  right-to-left, then there is a technique for constructing a parallel
  version automatically.''

Just derive a weak right inverse function and then apply the Third
Homomorphism Theorem[4]:

  ``A function on lists that can be computed both from left-to-right
  and from right-to-left is _necessarily_ a list homomorphism--it can
  be computed according to any parenthesization of the list.''

Some remarks.  I'm trying to relate this to constructing algebra of
recursion operators on algebraic data types in [5] on vectors.

[1] http://research.sun.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf
[2] http://wwwtcs.inf.tu-dresden.de/~voigt/popl202-voigtlaender.pdf
[3] http://www.ipl.t.u-tokyo.ac.jp/~takeichi/attachments/pldi07.pdf
[4] http://researchspace.auckland.ac.nz/bitstream/2292/3514/1/005thirdht.pdf
[5] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=