Является ли MapReduce одной из форм Continuation-Passing Style (CPS)?

Question

Как говорится в названии. Я читал Yet Another Language Geek: Continuation-Passing Style, и мне казалось, что MapReduce можно классифицировать как одну из форм Continuation-Passing Style aka CPS.

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

Answer 1

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

Я думаю, что КПС является одним из методов программирования, Гай Стил описывает как вещи, которые мы должны вырастать и отучиться, в своей речи на The Future of Parallel: What's a Programmer to do?

Answer 2

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

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

Answer 3

Оба КПСА и MapReduce использовать функции высшего порядка. Это означает, что оба они включают функции, которые принимают функции в качестве аргументов.

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

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

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

Answer 4

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

Например, вот отведенной Python Map-Reduce реализация:

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