MapReduce est-il une forme de Continuation-Passing Style (CPS)?

Question

Comme le titre le dit. Je lisais Yet Another Language Geek: Continuation-Passing Style et je me demandais si MapReduce pouvait être catégorisée comme une forme de Continuation-Passing Style aka CPS.

Je me demande également comment CPS peut utiliser plus d'un ordinateur pour effectuer des calculs complexes. Peut-être que CPS le rend plus facile à travailler avec Actor model.

Answer 1

Je dirais qu'ils sont opposés. MapReduce se prête évidemment à la distribution, où Map peut effectuer des sous-tâches indépendamment. Avec CPS, vous écrivez une fonction récursive où chaque appel attend sur un cas plus petit pour revenir.

Je pense que CPS est l'une des techniques de programmation que Guy Steele décrit comme des choses dont nous avons besoin pour devenir trop grand et désapprendre, dans son discours sur The Future of Parallel: What's a Programmer to do?

Answer 2

Je ne le dirais pas. MapReduce exécute des fonctions définies par l'utilisateur, mais celles-ci sont mieux connues sous le nom de "callbacks". Je pense que CPS est un concept très abstrait qui est couramment utilisé pour modéliser le comportement de concepts mieux connus comme les fonctions, les coroutines, les rappels et les boucles. Il n'est généralement pas utilisé directement.

Ensuite, je peux confondre CPS avec des continuations eux-mêmes. Je ne suis pas un expert sur l'un ou l'autre.

Answer 3

Les deux CPS et MapReduce utilisent des fonctions d'ordre supérieur. Cela signifie que les deux impliquent des fonctions qui prennent des fonctions en tant qu'arguments.

Dans le cas de CPS vous avez une fonction (appelée une continuation) avec un argument qui dit quoi faire avec un résultat. Typiquement (mais pas toujours) la continuation est utilisée une fois. C'est une fonction qui spécifie comment l'ensemble du reste du calcul devrait continuer. Cela en fait aussi une sorte de série. Généralement, vous avez un thread d'exécution et la continuation spécifie comment cela va continuer. Dans le cas de MapReduce, vous fournissez des arguments de fonction qui sont utilisés plusieurs fois. Ces fonctions d'argument ne représentent pas vraiment l'ensemble du reste du calcul, mais seulement de petits blocs de construction qui sont utilisés encore et encore. Le bit "over-over" peut souvent être réparti sur plusieurs machines, ce qui en fait une sorte de chose parallèle.

Donc, vous avez raison de voir un point commun. Mais l'un n'est pas vraiment un exemple de l'autre.

Answer 4

Map-reduce est une implémentation. L'interface de codage qui vous permet d'utiliser cette implémentation peut utiliser des suites; c'est vraiment une question de savoir comment le cadre et le contrôle du travail sont abstraits. Considérons des interfaces déclaratives pour Hadoop telles que Pig, ou des langages déclaratifs en général tels que SQL; la machinerie située sous l'interface peut être mise en œuvre de plusieurs façons.

Par exemple, voici un Python Abstraite carte-reduce mise en œuvre:

def mapper(input_tuples): 
    "Return a generator of items with qualifying keys, keyed by item.key" 
    # we are seeing a partition of input_tuples 
    return (item.key, item) for (key, item) in input_items if key > 1) 

def reducer(input_tuples): 
    "Return a generator of items with qualifying keys" 
    # we are seeing a partition of input_tuples 
    return (item for (key, item) in input_items if key != 'foo') 

def run_mapreduce(input_tuples): 
    # partitioning is magically run across boxes 
    mapper_inputs = partition(input_tuples) 
    # each mapper is magically run on separate box 
    mapper_outputs = (mapper(input) for input in mapper_inputs) 
    # partitioning and sorting is magically run across boxes 
    reducer_inputs = partition(
     sort(mapper_output for output in mapper_outputs)) 
    # each reducer is magically run on a separate box 
    reducer_outputs = (reducer(input) for input in reducer_inputs) 

Et voici la même mise en œuvre en utilisant coroutines, avec l'abstraction encore plus magique caché:

def mapper_reducer(input_tuples): 
    # we are seeing a partition of input_tuples 
    # yield mapper output to caller, get reducer input 
    reducer_input = yield (
     item.key, item) for (key, item) in input_items if key > 1) 
    # we are seeing a partition of reducer_input tuples again, but the 
    # caller of this continuation has partitioned and sorted 
    # yield reducer output to caller 
    yield (item for (key, item) in input_items if key != 'foo')