Является ли MapReduce одной из форм продолжения-прохождения (CPS)?

Question

Как следует из названия. Я читал Еще один фанат языка: стиль прохождения продолжения , и мне было интересно, можно ли MapReduce классифицировать как одну из форм стиля прохождения продолжения, или CPS.

Мне также интересно, как CPS может использовать более одного компьютера для выполнения сложных вычислений. Возможно, CPS облегчает работу с Актерской моделью .

Answer 1

Map-Reduction является реализацией. Интерфейс кодирования, который позволяет использовать эту реализацию, может использовать продолжения; на самом деле все зависит от того, как структура и контроль работы отделены. Рассмотрим декларативные интерфейсы для Hadoop, такие как Pig, или декларативные языки в целом, такие как SQL; механизм под интерфейсом может быть реализован многими способами.

Например, вот абстрактная реализация Python-сокращения карты:

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)

А вот та же самая реализация, использующая сопрограммы, с еще большей магической абстракцией, скрытой:

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 2

Я бы сказал, что они противоположны. MapReduce, очевидно, поддается распространению, где Map может выполнять подзадачи независимо. С помощью CPS вы пишете рекурсивную функцию, в которой каждый вызов ожидает ответа в меньшем регистре.

Я думаю, что CPS - это одна из техник программирования, которые Гай Стил описывает как вещи, которые мы должны перерасти и отучить в своем выступлении на Будущее параллели: что делать программисту?

Answer 3

И CPS, и MapReduce используют функции более высокого порядка. Это означает, что оба включают функции, которые принимают функции в качестве аргументов.

В случае CPS у вас есть функция (называемая продолжением) с аргументом, который говорит, что делать с результатом. Обычно (но не всегда) продолжение используется один раз. Это функция, которая определяет, как должны продолжаться все остальные вычисления. Это также делает его серийным. Обычно у вас есть один поток выполнения, а продолжение указывает, как оно будет продолжаться.

В случае MapReduce вы предоставляете аргументы функции, которые используются несколько раз. Эти функции аргументов на самом деле не представляют всего остального вычисления, а представляют собой небольшие строительные блоки, которые используются снова и снова. Бит «снова и снова» часто может быть распределен по нескольким машинам, что делает этот процесс параллельным.

Так что вы правы, увидев общность. Но один на самом деле не является примером другого.

Answer 4

Я бы так не сказал. MapReduce выполняет пользовательские функции, но они более известны как «обратные вызовы». Я думаю, что CPS - это очень абстрактное понятие, которое обычно используется для моделирования поведения более известных понятий, таких как функции, сопрограммы, обратные вызовы и циклы. Обычно не используется напрямую.

Опять же, я могу спутать CPS с самими продолжениями. Я не эксперт ни по одному из них.