Multithreading in ... lingue funzionali? (Prolog)

Question

Quando il mio amico ha iniziato a studiare Prolog a scuola, l'ho preso in giro per imparare una lingua inutile. Tuttavia, mi ha mostrato alcune cose che non ho mai nemmeno immaginato possibile; Voglio sapere da dove viene questa tecnica.

La tecnica è questa:

permutation(List) :- 
    isAMember(X, List), 
    deleteFirstElement(X, List, Substring), 
    % and so on 

In questo codice, isAMember(X, List) è una funzione che restituisce true se X è in List. Tuttavia, fino a questo punto, X non è definito come variabile - , quindi il programma genererà un gruppo di nuovi thread, uno per ogni possibile valore di isAMember(X, List) true, true, e continuerà da lì.

Questo ci consente di creare un algoritmo multi-thread nel modo più semplice ed elegante che avrei mai potuto immaginare possibile.

Quindi la mia domanda è: Questa specifica è Prolog o una caratteristica di tutti i linguaggi logici e/o funzionali? Inoltre, dove posso imparare più incredibili tecniche di multithreading come questo - questo è sicuramente il futuro della programmazione.

Answer 1

Il sottoinsieme di Prolog noto come "Datalog" è limitato alle sole funzioni logiche (nessun "taglio") e, in linea di principio, la ricerca di prove può essere eseguita in parallelo. Tuttavia dovresti stare attento perché la semantica del Prolog completo è abbastanza sensibile all'ordine in cui i risultati vengono prodotti, e alcuni veri programmi Prolog dipendono da questo.

La situazione nei linguaggi funzionali puri come Haskell e Clean è un po 'meglio — è sempre sicuro valutare le sottoespressioni in parallelo — ma ci sono molte sfide di prestazioni. Se si esegue il parallelismo estremo (ogni sottoespressione) non si ottiene alcun miglioramento delle prestazioni a causa di tutto il sovraccarico.Gli approcci promettenti in questo momento sembrano essere

• Threads (Concurrent Haskell)

• dati Parallelo Haskell

• "Sparks" con par e seq operatori.

Le funzionalità parallele sono in circolazione da quasi 30 anni e le persone cercano ancora di farlo funzionare bene. Se volete maggiori informazioni, provare

• procedimenti recenti del ACM Symposium on Haskell (e prima ancora, il laboratorio Haskell)

• Il lavoro di Arvind al MIT, che era un grande pioniere in questo zona (controllare il suo libro con R. Nikhil sulla programmazione parallela con pH)

Answer 2

Se ricordo il mio Prolog correttamente, non si stanno creando thread, ma invece ogni possibile istanziazione di X viene tentata a sua volta, utilizzando backtracking e unificazione. È piuttosto seriale.

EDIT: Apparentemente ci sono alcuni prologhi paralleli sperimentali là fuori, ad esempio, Reform Prolog. Tuttavia, questa non è la norma nelle implementazioni Prolog, per quanto posso dire.

Answer 3

isAMember(X, List) non creerà thread, la logica di prolog si basa solo in ricorsione e backtracking ed è piuttosto procedurale a meno che non si creino esplicitamente thread.

Nel caso di isAMember(X, List), si guarda al concetto di unificazione. quella funzione si unificherà con tutti i valori che valutano quella funzione in modo vero, in questo caso, tutti gli elementi contenuti nella lista. E procedi con l'esecuzione con X.

Una volta che l'esecuzione ha raggiunto una foglia, tornerà indietro alla prima chiamata "ancora unificabile" (o punto di interruzione, credo, non ricordo il termine corretto) , ad esempio isAMember(X, List), unificherà X al candidato successivo e riprenderà l'esecuzione.

Ho il coraggio di dire che, se non si presta attenzione alla logica, è possibile ottenere facilmente lo stack overflow.

Answer 4

Onestamente, quello che hai dimostrato non sembra diverso da una comprensione lista, eventualmente combinato con un foreach:

012.

foreach {x | x in List} 
    deleteFirstElement(x, List, Substring) 
    // not sure what deleteFirstElement does, so... 

Come lei ha ricordato che isAMember potrebbe essere qualsiasi cosa, di lista può essere più complicato anche

foreach {x | x in List if x % 2 == 0} // ie, even elements of List 

Sulla stessa linea, si può fare la stessa cosa senza di lista

new_list = old_list.every { x | x % 2 == 0 } 

che può essere suddiviso in thread altrettanto facile.