Re: MapReduce engine for recursion

Russ,

My apologies in advance for not reading through your message fully (so the applicability of my comments may be questionable), but... i suspect that you might get a lot out of a continuation-passing-style (CPS). Specifically, you might look at transformations of the form

Program |-> CPS(Program) |-> MapReduce(CPS(Program))

The reason is that continuation is sort of the smallest unit of control. If you want to mix and match control structures, the continuation is like the Bohr atom(ic model) for this. It should also provide an intermediate representation from which you can do various forms of dependency analysis to see when MR is a win.

My guess is that there's a couple of monad transformers that would provide you a higher-level set of structuring tools. You might look at LogicT, for example -- as a place to begin -- not for immediate applicability.

Best wishes,

--greg

P.S. Process calculi -- like π-calculus -- can be seen as an explicit CPS model. In a reflective version (where channels are the codes of processes) you can transform programs into a continuation-saturated form in which the continuation of each action is passed to a meta-level executor that gets to decide whether the code is run. This makes back-tracking, undo, transactions, etc. a cinch; at the cost of pretty space growth for simple control structures.

On Fri, Dec 12, 2008 at 9:22 PM, Russ Abbott <russ.abbott@gmail.com> wrote:

That was probably an overly broad claim. The structure allows one to simulate a Turing Machine. So it is Turing complete, and hence capable of computing any computable function.

In terms of parallelization, do you have some interesting examples of functions that don't fit this model?

Also, I'll admit that I do not understand why Map/Reduce leads to trivial parallelization. In most cases the Map step is parallizable, but I don't see how the Reduce step is. Even when considering the Map step, parallelization is not necessaily trival. If the problem can be expressed in advance as a tree structure of sub-computations, then certainly one could apply map in parallel to each node in the tree. But as the QuickSort example illustrates, one doesn't always know the tree in advance. It is often computed as part of the computation. So I'm not clear why even the Map part leads to trivial parallelization.

-- Russ

On Fri, Dec 12, 2008 at 7:28 AM, David MacIver <david.maciver@gmail.com> wrote:

On Fri, Dec 12, 2008 at 7:21 AM, Russ Abbott <russ.abbott@gmail.com> wrote:

The basic idea is that every recursive function can be understood in terms of a mapping function and a reduce function.

This is simply not true. Many interesting classes of recursive functions can be, but if it were true that all recursive functions could be  then every problem would be trivially parallelisable.

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com