Est-MapReduce une forme de style passage de continuation (CPS)?

Question

Comme le dit le titre. Je lisais Pourtant, une autre langue Geek: de continuation passant style et j'était en quelque sorte de se demander si MapReduce peut être classé comme une forme de passage de continuation style aka CPS.

Je me demande aussi comment CPS utiliser plus d'un ordinateur pour effectuer des calculs complexes. Peut-être que CPS facilite le travail avec modèle Acteur .

Answer 1

Je leur dire que vous êtes opposés. MapReduce se prête évidemment à la distribution, où la carte peut faire indépendamment sous-tâches. Avec CPS vous écrivez une fonction récursive où chaque appel est en attente sur un petit cas pour revenir.

Je pense que CPS est l'une des techniques de programmation que Guy Steele décrit comme des choses que nous devons devenir trop grand et désapprendre, dans son discours sur

Answer 2

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

Et puis, je peux être source de confusion CPS avec continuations eux-mêmes. Je ne suis pas un expert sur l'un.

Les deux CPS et MapReduce faire usage des fonctions d'ordre supérieur. Cela signifie que les deux impliquent des fonctions qui prennent des fonctions comme arguments.

Dans le cas de CPS vous avez une fonction (appelée suite) avec un argument qui dit quoi faire avec un résultat. En général (mais pas toujours) la poursuite est utilisé une fois. Il est une fonction qui indique comment l'ensemble du reste du calcul devrait se poursuivre. Cela rend également une sorte de série de chose. En général, vous avez un thread d'exécution et la continuation spécifie comment ça va continuer.

Dans le cas de MapReduce vous fournir des arguments de fonction qui sont utilisés à plusieurs reprises. Ces fonctions d'argument ne représentent pas vraiment l'ensemble du reste du calcul, mais juste un peu de blocs de construction qui sont utilisés encore et encore. Le « plus et plus » bit peuvent souvent être répartis sur plusieurs machines ce qui en fait une sorte parallèle de chose.

Vous avez raison de voir un point commun. Mais on est pas vraiment un exemple de l'autre.

Plan-réduire est une implémentation. L'interface de codage qui vous permet d'utiliser cette mise en œuvre pourrait utiliser continuations; il est vraiment une question de la façon dont le cadre et le contrôle de l'emploi sont extraites. Tenez compte des interfaces déclaratives pour Hadoop comme le cochon, ou les langues déclaratives en général telles que SQL; l'appareil sous l'interface peut être mise en œuvre de plusieurs façons.

Par exemple, voici une carte-réduire Python Abstraite la 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')

Answer 3

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

Et puis, je peux être source de confusion CPS avec continuations eux-mêmes. Je ne suis pas un expert sur l'un.

Answer 4

Les deux CPS et MapReduce faire usage des fonctions d'ordre supérieur. Cela signifie que les deux impliquent des fonctions qui prennent des fonctions comme arguments.

Dans le cas de CPS vous avez une fonction (appelée suite) avec un argument qui dit quoi faire avec un résultat. En général (mais pas toujours) la poursuite est utilisé une fois. Il est une fonction qui indique comment l'ensemble du reste du calcul devrait se poursuivre. Cela rend également une sorte de série de chose. En général, vous avez un thread d'exécution et la continuation spécifie comment ça va continuer.

Dans le cas de MapReduce vous fournir des arguments de fonction qui sont utilisés à plusieurs reprises. Ces fonctions d'argument ne représentent pas vraiment l'ensemble du reste du calcul, mais juste un peu de blocs de construction qui sont utilisés encore et encore. Le « plus et plus » bit peuvent souvent être répartis sur plusieurs machines ce qui en fait une sorte parallèle de chose.

Vous avez raison de voir un point commun. Mais on est pas vraiment un exemple de l'autre.

Answer 5

Plan-réduire est une implémentation. L'interface de codage qui vous permet d'utiliser cette mise en œuvre pourrait utiliser continuations; il est vraiment une question de la façon dont le cadre et le contrôle de l'emploi sont extraites. Tenez compte des interfaces déclaratives pour Hadoop comme le cochon, ou les langues déclaratives en général telles que SQL; l'appareil sous l'interface peut être mise en œuvre de plusieurs façons.

Par exemple, voici une carte-réduire Python Abstraite la 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')