I riduttori (in Clojure) risolvono il problema dell'accumulazione di foldr di ridimensionamento delineato da Guy Steele?

Question

Nel suo discorso The Future Of Clojure Bodil fa la seguente affermazione:

Guy Steele ha tenuto un discorso a ICFP chiamato Organizing Functional Code for Parallel Execution (or, foldl and foldr Considered Slightly Harmful) (anche in ACM).

In esso Guy Steele afferma sul vetrino 70:

Non appena dici “prima, SUM = 0” si contengano errori. Gli accumulatori sono BAD per il parallelismo. Si noti che foldl e foldr, sebbene funzionali, sono fondamentalmente cumulativi.

Che è un po 'interessante. Quindi Bodil sta dicendo che Guy Steele sta chiamando un problema. Poi ha affermato che Rich lo ha affrontato con Reducers (e Transducers che sono una continuazione di questa linea di pensiero). In the Transducers talk alle 16:11 vediamo Rich chiamando alcuni documenti particolari su foldr.

• Bird - Lectures on Constructive Functional Programming (1988)
• Hutton - A tutorial on the universality and expressiveness of fold (1999)

Rich dice effettivamente che fold s sono componibili - e si possono usare per costruire altre funzioni di ordine superiore, come map e filter.

La mia domanda è - era giusto Bodil? Rich ha risolto il problema creato da Guy Steele? I riduttori (in Clojure) risolvono il problema dell'accumulazione di foldr raddrizzamento delineato da Guy Steele?

Answer 1

Sì, i riduttori risolvono questo problema, perché hanno una semantica leggermente diversa dal tipo di piega a cui si riferisce Guy Steele (sebbene l'effetto possa essere molto simile nella pratica).

foldr e foldl accettano un singolo argomento di funzione, che viene applicato a turno a ciascun membro di una raccolta (insieme a un valore di accumulatore). Come dice Steele, sono intrinsecamente sequenziali (motivo per cui è significativo avere varianti "sinistra" e "destra"). La funzione clojure.core/reduce di Clojure funziona anche in questo modo.

clojure.core.reducers/fold, d'altra parte, prende due argomenti di funzione, una funzione di riduzione e una funzione di combinazione. La raccolta è suddivisa in blocchi, ognuno dei quali viene ridotto utilizzando la funzione di riduzione e questi risultati vengono quindi combinati utilizzando la funzione di combinazione. Graficamente questo assomiglia a questo:

(questo diagramma viene dal mio libro Seven Concurrency Models in Seven Weeks, che comprende una sezione sulla Riduttori).

A volte, è possibile utilizzare una singola funzione sia per la riduzione che per la combinazione (sommando una sequenza di numeri interi, ad esempio). Ma in altri casi, questo non è possibile.

Quando si utilizza una funzione singola per la riduzione e la combinazione, clojure.core.reducers/fold darà gli stessi risultati di una piega sequenziale se e solo se la funzione di riduzione/combinazione è associativa.

Answer 2

Il post originale su riduttori (Reducers - A Library and Model for Collection Processing) introduce la funzione fold nella sezione semplicità è Opportunità.

La firma primario di piega prende una funzione di combinazione, un funzione di riduzione, ed una raccolta e restituisce il risultato della combinazione dei risultati di ridurre sottosegmenti della raccolta, potenzialmente in parallelo.

Le strutture di dati del cloquesto sfruttano l'eventuale paralellismo.

Fa questo quando la raccolta è suscettibile di suddivisione in parallelo. I candidati ideali sono strutture di dati ricavate dagli alberi. I vettori Clojure e le mappe sono alberi e hanno implementazioni parallele di piega basate su sul framework ForkJoin.

E se la raccolta è una sequenza, viene applicata la buona vecchia funzione reduce.

E se la raccolta sottostante non è suscettibile (ad es. È una sequenza )? piega solo devolve in riduzione, producendo lo stesso risultato semantico, se non fisico, .