È una forma di MapReduce Continuazione-Passing Style (CPS)?

Question

Come dice il titolo. Stavo leggendo Yet Another Geek Lingua: Continuation- passando stile e io era una sorta di chiedersi se MapReduce può essere classificato come una forma di Continuazione-Passing Style aka CPS.

Sono anche chiedendo come possono CPS utilizzare più di un computer per eseguire calcoli complessi. Forse CPS rende più facile il lavoro con modello Attore .

Answer 1

vorrei dire che sono opposti. MapReduce si presta ovviamente alla distribuzione, dove Mappa può fare attività secondarie in modo indipendente. Con CPS si scrive una funzione ricorsiva in cui ogni chiamata è in attesa su un caso minore di tornare.

Credo CPS è una delle tecniche di programmazione che Guy Steele descrive come cose che dobbiamo superare e unlearn, nel suo intervento su Il futuro del Parallel:? Che cosa è un programmatore di fare

Answer 2

Non direi così. MapReduce fa eseguire funzioni definite dall'utente, ma questi sono meglio noti come "callback". Penso CPS è un concetto molto astratto che viene comunemente utilizzato per modellare il comportamento dei concetti più conosciute come funzioni, coroutine, callback e loop. Non è generalmente utilizzato direttamente.

Poi di nuovo, mi può essere fonte di confusione CPS con continuazioni stessi. Io non sono un esperto di uno dei due.

Answer 3

Sia CPS e l'uso MapReduce fanno di funzioni di ordine superiore. Ciò significa che entrambi coinvolgono le funzioni che accettano funzioni come argomenti.

Nel caso di CPS si dispone di una funzione (chiamata una continuazione) con un argomento che dice che cosa fare con un risultato. Tipicamente (ma non sempre) il proseguimento viene utilizzata una volta. E 'una funzione che specifica come tutto il resto del calcolo dovrebbero continuare. Questo rende anche una sorta di serie di cose. In genere si ha un thread di esecuzione e le specifica di continuazione come sta andando per continuare.

Nel caso di MapReduce si sta fornendo argomenti della funzione che vengono utilizzati più volte. Queste funzioni argomento in realtà non rappresentano tutto il resto del calcolo, ma basta poco la costruzione di blocchi che vengono utilizzati più e più volte. Il "più e più" bit spesso può essere distribuito su più computer rendendo questo un genere parallelo di cose.

Quindi hai ragione a vedere una comunanza. Ma non è davvero un esempio dell'altro.

Answer 4

Map-ridurre è un'implementazione. L'interfaccia di codifica che permette di utilizzare che l'implementazione potrebbe usare continuazioni; è davvero una questione di come il quadro e il controllo di posti di lavoro sono astratte. Prendere in considerazione le interfacce dichiarative per Hadoop, quali maiale, o linguaggi dichiarativi in ??generale come ad esempio SQL; il macchinario sotto l'interfaccia può essere implementato in molti modi.

Per esempio, ecco un astratto Python mappa-ridurre implementazione:

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)

Ed ecco la stessa implementazione utilizzando coroutine, con l'astrazione ancora più magico nascosto:

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