mapreduce - MapReduce 是延续传递风格 (CPS) 的一种形式吗？

Question

正如标题所说。我正在阅读另一种语言极客：延续传递风格，我有点想知道 MapReduce 是否可以归类为延续传递风格的一种形式，即 CPS。

我也想知道 CPS 如何利用多台计算机来执行复杂的计算。也许 CPS 可以更轻松地使用Actor 模型。

Answer 1

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

Answer 2

我不会这么说的。MapReduce 确实执行用户定义的函数，但这些函数更好地称为“回调”。我认为 CPS 是一个非常抽象的概念，通常用于对更知名的概念（如函数、协程、回调和循环）的行为进行建模。一般不直接使用。

再说一次，我可能将 CPS 与延续本身混淆了。我不是任何一个方面的专家。

Answer 3

我会说他们是对立的。MapReduce 显然适用于分布式，其中 Map 可以独立执行子任务。使用 CPS，您可以编写一个递归函数，其中每个调用都在等待较小的情况下返回。

我认为 CPS 是 Guy Steele 在他关于并行的未来的演讲中描述为我们需要超越和忘却的编程技术之一：程序员该做什么？

Answer 4

CPS 和 MapReduce 都使用高阶函数。这意味着两者都涉及将函数作为参数的函数。

在 CPS 的情况下，您有一个带有参数的函数（称为延续），该参数说明如何处理结果。通常（但不总是）延续使用一次。它是一个函数，它指定整个其余计算应该如何继续。这也使它成为一种连续的事情。通常，您有一个执行线程，而延续指定它将如何继续。

在 MapReduce 的情况下，您提供了多次使用的函数参数。这些参数函数并不真正代表整个其余的计算，而只是反复使用的小构建块。“一遍又一遍”位通常可以分布在多台机器上，这使得这是一种并行的事情。

所以你看到一个共同点是对的。但其中一个并不是另一个的真正例子。