Qualunque linguaggio funzionale supporta la divisione e la conquista in modo nativo?

Question

Mi dispiace di non aver trovato un modo per esprimere la domanda più chiaramente nel titolo, ma in sostanza, è questo: quasi tutti i linguaggi funzionali hanno costrutti che consentono di elaborare un elenco variabile di argomenti attraverso la ricorsione della coda , come in questo pseudocodice Erlang-ish che riassume un elenco di numeri:

sumup(0,A) -> A. 
sumup(N,A) -> sumup(N) + A. 

Tuttavia, uno dei grandi appelli di linguaggi funzionali per me è il loro parallelismo intrinseco. E anche se un problema come riassumere un elenco di numeri è ovviamente abbastanza parallelizzabile, e quasi certamente sarà gestito in modo più efficiente da divide et impera, non sono a conoscenza delle caratteristiche linguistiche che rendono questo un modo naturale di programmare. Infatti, a meno che il linguaggio non abbia caratteristiche che permettano di leggere il numero di argomenti basati su una funzione e di recuperare argomenti basati su indice, non vedo come uno possa fare. Qualche linguaggio funzionale ha caratteristiche per incoraggiare la programmazione dividi e conquista?

Answer 1

Qualche lingua funzionale ha caratteristiche per incoraggiare la programmazione di divide e conquista?

Sì: la capacità di creare nuove funzioni di ordine superiore nelle biblioteche.

Una delle funzioni più importanti di questo tipo, negli elenchi comunque, è foldr, che può essere parallelizzata in linea di principio se applicata a un operatore associativo, anche se ciò avviene raramente nella pratica. Perché? Perché foldr è progettato in base al flusso di dati sequenziale.

La bellezza dei linguaggi funzionali è che una volta riconosciuto questo problema, possiamo risolvere il problema non introducendo nuove funzionalità linguistiche, ma facendo un uso più intelligente delle funzionalità che già possediamo. Per vedere come, guarda Guy Steele's talk from August 2009, in cui spiega il motivo per cui foldr non è la funzione di libreria di destra per la programmazione funzionale in parallelo, e propone

• Un nuovo stile di programmazione
• una nuova rappresentazione di liste
• Nuovo superiore -ordinamento funzioni per le librerie

che sono tutte progettate per supportare la programmazione divide e conquista.

Quello che ho trovato così entusiasmante di questo discorso è che non è necessario introdurre nuove funzionalità linguistiche per supportare la programmazione dividi-conquista in modo "nativo". Basta prendere i primitivi che abbiamo già e usarli per progettare librerie migliori.

Se si ha accesso alla libreria digitale ACM, è possibile vedere il video del discorso di Guy Organizing Functional Code For Parallel Execution oppure, come fa notare Ben Karel, è possibile vedere video taken by Malcom Wallace su Vimeo.

Answer 2

Questo tipo di cose è abbastanza semplice da specificare in Ruby. In questo esempio, dividiamo un intervallo in gruppi di tre e inviamo un metodo di somma per ogni gruppo. Quindi sommiamo le somme parziali risultanti. Si può facilmente espandere questo per renderlo multi-threaded.

(1..10).each_slice(3).map{ |x| x.inject :+ }.inject(:+) 

Questo esempio è un po 'diverso dal tuo, ma mostra il principio.

Answer 3

Non conosco alcun linguaggio con schemi di tipo divide e conquista. Come dici tu, è difficile immaginare come specificare qualcosa del genere.

Senza notazione sfrenatamente nuova, penso che le funzioni classiche come partition siano le migliori che possiamo fare.

Answer 4

Il parallelismo automatico non è così facile come potrebbe sembrare. Il problema è che se il partizionamento viene eseguito automaticamente, c'è il rischio di un partizionamento eccessivo (troppe partizioni), che aggiungerebbe troppo overhead o underpartitioning, il che non richiederebbe il vero vantaggio di tutti i core nelle CPU. Calcolare questo fuori staticamente (vale a dire in fase di compilazione) è piuttosto difficile, motivo per cui di solito è lasciato allo sviluppatore annotare dove parallelizzare.

Esempi:

Haskell ha il par combinator, che serve come annotazione per creare una scintilla , un calcolo che viene trasformato in un thread quando un nucleo CPU diventa disponibile.

Data Parallel Haskell: definisce un tipo di dati di array paralleli per consentire uno stile di parallelizzazione più implicito ma sembra essere al costo di alcune limitazioni ed è ancora codice sperimentale.

(disclaimer: io non sono uno sviluppatore Haskell)

Il Task Parallel Library in .NET: può fare la parallelizzazione automatica dei dati, oppure è possibile implementare il proprio Partitioner. Hai ancora bisogno di sapere come funziona la parallelizzazione, o finirai con over- or underpartitioning. Reed Corpsey ha un great series of articles on the TPL and PLINQ.

DryadLINQ si basa su PLINQ e aggiunge il calcolo distribuito automatico.

Nessuno di questi è veramente nativo per la lingua, ma sono strettamente integrati. C'è anche un PLINQ integration module for F#.

Answer 5

Dai un'occhiata allo Manticore, al suo predecessore NESL e alla sorella ZPL. Tutti questi sono linguaggi almeno parzialmente funzionali con costrutti paralleli per operare sull'intero contenuto di strutture di dati alla volta.