que - Multithreading en... idiomas funcionales?(Prólogo)

simultaneous multithreading

Question

Cuando mi amigo comenzó a aprender Prolog en la escuela, me burlé de él por aprender un idioma 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 esta:

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 X está en List . Sin embargo, hasta este punto, X no se define como una variable, por lo que el programa generará un grupo de hilos nuevos, uno para cada valor posible de X que haga que isAMember(X, List) verdadero y continúe desde allí.

Esto nos permite crear un algoritmo de subprocesos múltiples de la manera más simple y elegante que podría haber 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 podría realizarse 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 las subexpresiones en paralelo, pero existen 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)

• Datos paralelos Haskell

• "Chispas" con operadores par y seq .

Las funcionalidades paralelas han existido por casi 30 años y la gente todavía está tratando de hacerlo funcionar bien. Si quieres más información, prueba

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

• El trabajo de Arvind en el MIT, que fue un gran pionero en esta área (consulte su libro con R. Nikhil sobre la programación paralela con pH)

Answer 2

Si recuerdo mi Prolog correctamente, no estás creando subprocesos, sino que cada posible instanciación de X se intenta a su vez, 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 recursión y la retroalimentación, y es bastante procedimental a menos que usted cree explícitamente subprocesos.

En el caso de isAMember(X, List) , estás 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 puede recordar el término correcto), digamos isAMember(X, List) , unificará X al próximo candidato, y reanudar la ejecución.

Me atrevo a decir que si no tienes cuidado con tu lógica, puedes obtener fácilmente desbordamientos de pila.

Answer 4

Honestamente, lo que has mostrado no parece ser diferente de una lista de comprensión, posiblemente combinada con un foreach:

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

Como mencionaste que el MIEMBRO podría ser cualquier cosa, la Comprensión de listas también puede ser más complicada.

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

En la misma línea, puedes hacer lo mismo sin una lista de comprensión

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

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