MapReduce es una forma de pasar Continuación-Style (CPS)?

Question

Como dice el título. Estaba leyendo Sin embargo, otro friki Idioma: Continuation- pasando Estilo y yo era una especie de preguntarse si MapReduce puede ser categorizado como una forma de pasar Continuación-Estilo aka CPS.

También me pregunto cómo pueden CPS utilizar más de un ordenador para realizar cálculos complejos. Tal vez CPS hace que sea más fácil trabajar con modelo Actor .

Answer 1

Yo diría que son opuestos. MapReduce, obviamente, se presta a la distribución, donde Mapa puede hacer subtareas independiente. Con CPS se escribe una función recursiva que cada llamada esperando en una caja más pequeña para volver.

Creo CPS es una de las técnicas de programación que Guy Steele describe como cosas que tenemos que superar y desaprender, en su conversación sobre El futuro del paralelo:? ¿Qué es un programador que hacer

Answer 2

Yo no diría eso. MapReduce hace ejecutar funciones definidas por el usuario, pero estos son más conocidos como "devoluciones de llamada". Creo CPS es un concepto muy abstracto que se utiliza comúnmente para modelar el comportamiento de los conceptos más conocidos como funciones, co-rutinas, las devoluciones de llamada y bucles. Por lo general, no se utiliza directamente.

A continuación, de nuevo, puede ser confuso CPS con los propios continuaciones. No soy un experto en cualquiera de ellos.

Answer 3

Tanto CPS y el uso de MapReduce marca de funciones de orden superior. Esto significa que ambos implican funciones que toman funciones como argumentos.

En el caso de CPS que tiene una función (llamada una continuación) con un argumento que dice qué hacer con el resultado. Típicamente (pero no siempre) la continuación se utiliza una vez. Es una función que especifica cómo el conjunto del resto de la computación deben continuar. Esto también hace que sea una especie de serie de cosas. Por lo general usted tiene un hilo de ejecución y está previsto por la continuación de la forma en que va a continuar.

En el caso de MapReduce que está proporcionando argumentos de las funciones que se utilizan varias veces. Estas funciones de argumentos no representan realmente la totalidad del resto de la computación, pero sólo un poco bloques de construcción que se utilizan una y otra vez. El bit de frecuencia se pueden distribuir "una y otra vez" a través de múltiples máquinas de fabricación de este tipo de cosas en paralelo.

Así que tienes razón para ver algo en común. Pero uno no es realmente un ejemplo de la otra.

Answer 4

Mapa-a reducir es una implementación. La interfaz de codificación que le permite usar que la aplicación podría utilizar continuaciones; en realidad es una cuestión de cómo se abstraen el marco y el control de trabajos. Considere las interfaces declarativas para Hadoop como cerdo, o lenguajes declarativos en general como SQL; la maquinaria debajo de la interfaz se puede implementar de muchas maneras.

Por ejemplo, aquí hay un mapa abstraída Python-reducir la aplicación:

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)

Y aquí está la misma aplicación utilizando co-rutinas, con la abstracción aún más mágico escondido:

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')