Che cos'è la programmazione funzionale che la rende intrinsecamente adatta all'esecuzione parallela? [duplicare]

La ragione principale è che la trasparenza referenziale (e ancor più la pigrizia) si sottrae all'ordine di esecuzione. Ciò rende banale parallelizzare la valutazione.

Ad esempio, se sia a , b e || sono referenzialmente trasparenti, non importa se in

a || b

a viene valutato per primo, b viene valutato per primo, o b non viene valutato affatto (perché a è stato valutato a true ).

In

a || a

non importa se a viene valutato una o due volte (o, diamine, anche 5 volte ... che non avrebbe senso, ma non importa comunque).

Quindi, se non importa in quale ordine vengono valutati e non importa se vengono valutati inutilmente, allora puoi semplicemente valutare ogni sottoespressione in parallelo. Quindi, potremmo valutare a e b in parallelo, e quindi, || potrebbe aspettare che uno dei due thread finisca, guarda cosa ha restituito, e se restituisce true , potrebbe persino annullare l'altro e restituisce immediatamente true .

Ogni sottoespressione può essere valutata in parallelo. Banalmente.

Nota, tuttavia, che questa non è una bacchetta magica. Alcune delle prime versioni sperimentali di GHC hanno fatto questo, ed è stato un disastro: c'era solo troppo parallelismo potenziale. Anche un semplice programma può generare centinaia, migliaia, milioni di thread e per la stragrande maggioranza delle sottoespressioni che generano il thread richiede molto più tempo rispetto alla valutazione dell'espressione in primo luogo. Con così tanti thread, il tempo di commutazione del contesto domina completamente qualsiasi computazione utile.

Si potrebbe dire che la programmazione funzionale capovolge il problema: in genere, il problema è come separare un programma seriale nella giusta dimensione di "blocchi" paralleli, mentre con la programmazione funzionale, il problema è come raggruppare insieme i sottoprogrammi paralleli in "blocchi" seriali.

Il modo in cui GHC lo fa oggi è che puoi annotare manualmente due sottoespressioni da valutare in parallelo. Questo è in realtà simile a come lo faresti anche in un linguaggio imperativo, mettendo le due espressioni in thread separati. Ma c'è una differenza importante: l'aggiunta di questa annotazione non può mai cambiare il risultato del programma! Può renderlo più veloce, può renderlo più lento, può farne usare più memoria, ma non può cambiare il suo risultato. In questo modo modo è più facile sperimentare con il parallelismo per trovare la giusta quantità di parallelismo e la giusta dimensione dei blocchi.

Diamo prima un'occhiata al motivo per cui la programmazione procedurale è così negativa nei thread simultanei.

Con un modello di programmazione concorrente, si stanno scrivendo istruzioni sequenziali che (per impostazione predefinita) prevedono di essere eseguite separatamente. Quando si introducono più thread, è necessario controllare esplicitamente l'accesso per impedire l'accesso simultaneo a una variabile condivisa quando tali modifiche possono influire a vicenda. Questa è una programmazione difficile da correggere e, durante i test, è impossibile dimostrare che è stata eseguita in modo sicuro. Nella migliore delle ipotesi, puoi solo confermare che in questa esecuzione di prova non si sono verificati problemi osservabili.

Nella programmazione funzionale, il problema è diverso. Non ci sono dati condivisi. Non c'è accesso simultaneo alla stessa variabile. In effetti, è possibile impostare una variabile solo una volta, non ci sono "for loops", ci sono solo blocchi di codice che, se eseguiti con un determinato set di valori, eseguiranno sempre lo stesso risultato. Ciò rende il test prevedibile e un buon indicatore di correttezza.

Il problema che lo sviluppatore deve risolvere nella programmazione funzionale è come progettare la soluzione riducendo al minimo lo stato comune. Quando il problema di progettazione richiede livelli elevati di concorrenza e uno stato minimo condiviso, le implementazioni funzionali sono una strategia molto efficace.

Stato condiviso ridotto a icona

What is it about functional programming that makes it inherently adapted to parallel execution?

La pura natura delle funzioni ( trasparenza referenziale ), ovvero senza effetti collaterali, lead a un minor numero di oggetti condivisi e quindi a uno stato meno condiviso.

Un semplice esempio è;

double CircleCircumference(double radius)
{
  return 2 * 3.14 * radius; // constants for illustration
}

L'output dipende esclusivamente dall'input, non esiste uno stato incluso; in contrasto con una funzione come GetNextStep(); in cui l'output dipende da quale sia il passo corrente (generalmente considerato come membro di dati di un oggetto).

È lo stato condiviso che necessita dell'accesso per essere controllato tramite mutex e lock. Avere maggiori garanzie sullo stato condiviso consente migliori ottimizzazioni parallele e una migliore composizione parallela.

Trasparenza referenziale ed espressioni pure

Maggiori dettagli su ciò che la trasparenza referenziale è possibile trovare qui su Programmers.SE .

[It] means that you can replace any expression in the program with the result of evaluating that expression (or vice versa) without changing the meaning of the program. Jörg W Mittag

Che a sua volta consente espressioni pure utilizzate per costruire funzioni pure - funzioni che valutano lo stesso risultato dati gli stessi argomenti di input. Ogni espressione può quindi essere valutata in parallelo.

Il codice funzionale puro è sicuro per i thread per impostazione predefinita.

Questo, di per sé, è già una grande vittoria. In altri linguaggi di programmazione, la progettazione di blocchi di codice completamente sicuri per i thread può essere davvero molto impegnativa. Ma un linguaggio funzionale puro ti costringe a rendere tutto sicuro per i thread, tranne che nei pochi punti in cui fai esplicitamente qualcosa che non è thread-safe. Potresti dire che in codice imperativo, essere thread-safe è esplicito [e quindi tipicamente raro], mentre nel puro codice funzionale, thread-unsafe è esplicito [e quindi tipicamente raro].

In un linguaggio imperativo, la maggior parte del problema è come aggiungere un blocco sufficiente per evitare strane razze di dati, ma non troppo per uccidere le prestazioni o provocare deadlock casuali. In un linguaggio puramente funzionale, la maggior parte delle volte tali considerazioni sono discutibili. Il problema ora è "solo" capire come suddividere il lavoro in modo uniforme.

Ad un estremo, hai un piccolo numero di attività parallele che non usano tutti i core disponibili. All'estremo opposto, ci sono miliardi di piccoli compiti che introducono un sovraccarico così grande che tutto rallenta a passo d'uomo. Certo, cercare di capire "quanto lavoro" fa una particolare chiamata di funzioni è spesso molto difficile.

Tutti questi problemi esistono anche nel codice imperativo; è solo che i programmatori imperiosi sono solitamente troppo occupati a lottare solo cercando di far funzionare la cosa affatto per preoccuparsi della delicata messa a punto delle dimensioni delle attività.

La parte più difficile della scrittura del codice parallelo è quella di impedire a un thread di leggere i dati che vengono aggiornati da un altro thread.

Una soluzione comune a questo è usare oggetti immutabili , in modo che una volta creato un oggetto non venga mai aggiornato. Ma nella vita reale i dati devono essere cambiati, quindi vengono utilizzati i dati "persistence" , dove ogni aggiornamento restituisce un nuovo oggetto - questo può essere reso efficiente da un'attenta scelta delle strutture dati.

Poiché la programmazione funzionale non consente alcun effetto collaterale, gli "oggetti di persistenza" vengono normalmente utilizzati durante la programmazione funzionale. Quindi il dolore che un programmatore funzionale è costretto a prendere a causa della mancanza di effetti collaterali, porta a una soluzione che funziona bene per la programmazione parallela.

Un altro vantaggio è dato dal fatto che i sistemi linguistici funzionali controllano che tu stia rispettando le regole e disponi di molti strumenti per aiutarti a farlo.