MapReduceは、継続パススタイル（CPS）の1つの形式ですか？

Question

タイトルが言うように。読んでいた さらに別の言語オタク：継続パススタイル そして、私はMapReduceをCPSと呼ばれる1つの形式の継続パススタイルとして分類できるかどうかを疑問に思っていました。

また、CPSが複雑な計算を実行するために複数のコンピューターをどのように利用できるか疑問に思っています。たぶん、CPSにより作業が容易になる可能性があります 俳優モデル.

Answer 1

彼らは反対だと思います。 MapReduceは明らかに、MAPが独立してサブタスクを実行できる分布に役立ちます。 CPSを使用すると、各コールが小さいケースを待って戻るのを待っている再帰関数を書きます。

CPSは、Guy Steeleが私たちが成長し、学習する必要があるものとして説明しているプログラミングテクニックの1つであると思います。 並列の未来：プログラマーは何をすべきか？

Answer 2

私はそうは言いません。 MapReduceはユーザー定義の機能を実行しますが、これらは「コールバック」としてよく知られています。 CPSは、機能、コルーチン、コールバック、ループなどのよく知られている概念の動作をモデル化するために一般的に使用される非常に抽象的な概念だと思います。通常、直接使用されません。

繰り返しになりますが、CPSを継続自体と混同している可能性があります。私はどちらの専門家ではありません。

Answer 3

CPSとMapReduceの両方が高次関数を使用します。これは、両方が関数を引数として取る機能を含むことを意味します。

CPSの場合、結果をどうするかを示す引数を持つ関数（継続と呼ばれます）があります。通常、（常にではない）継続は一度使用されます。これは、計算の残りの部分全体がどのように続くべきかを指定する関数です。これはまた、シリアルなものになります。通常、実行のスレッドが1つあり、継続はそれがどのように続くかを指定します。

MapReduceの場合、複数回使用される関数引数を提供しています。これらの引数関数は、実際には計算の残りの部分全体を表していませんが、何度も何度も使用されるビルディングブロックはほとんどありません。 「繰り返し」ビットは、多くの場合、複数のマシンに分布することができ、これを並行したものにします。

ですから、あなたは共通性を見るのが正しいです。しかし、1つは実際には他の例ではありません。

Answer 4

Map-Reduceは実装です。その実装を使用できるコーディングインターフェイスでは、継続を使用できます。フレームワークとジョブコントロールがどのように抽象化されているかの問題です。豚などのHadoopの宣言的インターフェイス、または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')