Multithreading en ... idiomas funcionales? (Prolog)

Question

Cuando mi amigo comenzó a aprender Prolog en la escuela, me burlé de él por aprender un lenguaje inútil. Sin embargo, me mostró algunas cosas que nunca supe posibles; Quiero saber de dónde viene esta técnica.

La técnica es la siguiente:

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

En este código, isAMember(X, List) es una función que devuelve verdadero si es X en List. Sin embargo, hasta este punto X no se define como una variable - por lo que el programa generará un grupo de nuevos hilos, uno para cada valor posible de X que hace verdadero isAMember(X, List), y continúa desde allí.

Esto nos permite crear un algoritmo de subprocesos múltiples de la manera más simple, más elegante que jamás hubiera imaginado.

Así que mi pregunta es: ¿Es esto específico de Prolog, o una característica de todos los lenguajes lógicos y/o funcionales? Además, ¿dónde puedo aprender técnicas de subprocesamiento múltiple más increíbles como esta? Este es seguramente el futuro de la programación.

Answer 1

El subconjunto de Prolog conocido como "Datalog" está restringido a funciones lógicas puras (sin "corte") y, en principio, la búsqueda de pruebas se puede hacer en paralelo. Sin embargo, tendrías que tener cuidado porque la semántica de Prolog completo es bastante sensible al orden en que se producen los resultados, y algunos programas reales de Prolog dependen de esto.

La situación en lenguajes funcionales puros como Haskell y Clean es un poco mejor — siempre es seguro evaluar subexpresiones en paralelo — pero hay muchos desafíos de rendimiento. Si realiza un paralelismo extremo (cada subexpresión), no obtiene ninguna ganancia de rendimiento debido a todos los gastos generales.Los enfoques prometedores en este momento parecen ser

• Hilos (Haskell concurrente)

• Parallel Data Haskell

• "Sparks" con par y seq operadores.

La función funcional paralela ha existido por casi 30 años y la gente todavía está tratando de hacerlo funcionar bien. Si desea más información, tratar

• actuaciones recientes del Simposio ACM sobre Haskell (y antes de eso, el taller Haskell)

• El trabajo de Arvind en el MIT, que fue un gran pionero en este área (echa un vistazo a su libro con R. Nikhil en la programación en paralelo con el pH)

Answer 2

Si recuerdo correctamente mi Prolog, no está creando subprocesos, sino que cada instancia posible de X se intenta por turno, utilizando retroceso y unificación. Es bastante serial.

EDITAR: Aparentemente hay algunos prólogos paralelos experimentales, por ejemplo, Reform Prolog. Sin embargo, esta no es la norma en las implementaciones de Prolog, hasta donde sé.

Answer 3

isAMember(X, List) no creará subprocesos, la lógica del prólogo solo depende mucho de la recursividad y la retroalimentación, y es bastante procedimental a menos que usted cree explícitamente subprocesos. En el caso de isAMember(X, List), está viendo el concepto de unificación esa función se unificará con todos los valores que evalúan esa función como verdadera, en este caso, todos los elementos contenidos en la lista. Y proceda con la ejecución con X.

Una vez que la ejecución ha llegado a su fin, retrocederá a la primera llamada "aún unificable" (o punto de corte, creo que no recuerdo el término correcto) , digamos isAMember(X, List), unificará X al siguiente candidato y reanudará la ejecución.

Atrévete, si no tienes cuidado con tu lógica, puedes obtener fácilmente desbordamientos de pila.

Answer 4

Honestamente, lo que has demostrado no parece diferente de una lista por comprensión, posiblemente en combinación con un foreach:

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

Como se ha mencionado que isAMember podría ser cualquier cosa, Lista de comprensión puede ser más complicado también

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

En la misma línea, se puede hacer lo mismo sin lista por comprensión

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

cuales se puede dividir en hilos igual de fácil.