¿Concurrente es Prolog?

Question

No puedo encontrar ninguna información en esta línea ... Yo también soy nuevo en Prolog ...

Me parece que podría ser altamente Prolog concurrente, tal vez tratando muchas posibilidades a la vez cuando se trata de coincide con una regla. ¿Los compiladores/intérpretes de Prolog modernos son inherentemente * concurrente? ¿Cuáles? ¿La simultaneidad está activada por defecto? ¿Debo habilitarlo de alguna manera?

* No estoy interesado en multi-threading, solo simultaneidad inherente.

Answer 1

En teoría, eso parece atractivo, pero hay varios problemas que hacen que dicha implementación parezca desaconsejable.

• para mejor o peor, la gente está acostumbrada a pensar en sus programas como la ejecución de izquierda a derecha y de arriba hacia abajo, incluso cuando se programa en Prolog. Tanto el orden de las cláusulas para un predicado como los términos dentro de una cláusula son semánticamente significativos en Prolog estándar. Paralelizarlos cambiaría el comportamiento de demasiado código exising para volverse popular.

• elementos de lenguaje no relacionales como el operador de corte solo pueden utilizarse de manera significativa cuando puede confiar en tales órdenes de ejecución, es decir, se volverían inutilizables en un intérprete paralelo a menos que se inventara un seguimiento de dependencia muy complicado.

• todas las soluciones de paralelización existentes incurren al menos en una sobrecarga de rendimiento para la comunicación entre hilos.

• Prolog se utiliza típicamente para de alto nivel, los problemas profundamente recursivas, tales como traversal gráfica, teorema demostrando etc. paralelización en un máquinas modernas pueden (idealmente) lograr un aumento de velocidad de n para alguna constante n, pero no puede convertir una método de solución recursiva inviable en uno viable, porque eso requeriría una aceleración exponencial de . En contraste, los problemas numéricos que normalmente resuelven los programadores de Fortran y C tienen un costo de cálculo alto pero bastante finito; Vale la pena el esfuerzo de paralelización para convertir un trabajo de 10 horas en un trabajo de 1 hora. Por el contrario, convertir un programa que puede parecerse a 6 movimientos adelante en uno que puede (en promedio) mirar 6.5 movimientos adelante simplemente no es tan convincente.

Answer 2

Desde una rápida búsqueda en Google parece que el paradigma de programación lógica concurrente sólo ha sido la base para unos pocos idiomas de investigación y ya no está activamente desarrollado. He visto afirmaciones de que la lógica concurrente es fácil de hacer en el sistema Mozart/Oz.

Answer 3

¿Los compiladores/intérpretes de Prolog modernos son intrínsecamente * concurrentes? ¿Cuáles? ¿La simultaneidad está activada por defecto?

No. La programación lógica concurrente fue el objetivo principal del programa de computadora de 5ta generación en Japón en la década de 1980; se esperaba que las variantes de Prolog fueran paralelizadas "fácilmente" en hardware masivamente paralelo. El esfuerzo falló en gran medida, porque la concurrencia automática simplemente no es fácil. Hoy en día, los compiladores de Prolog tienden a ofrecer bibliotecas de subprocesos, donde el programa debe controlar manualmente la cantidad de simultaneidad.

Para ver por qué paralelizar Prolog es tan difícil como cualquier otro idioma, considere las dos principales estructuras de control que ofrece el lenguaje: conjunción (Y, ejecución en serie) y disyunción (O, elección con retroceso). Digamos que usted tiene una y construir como

p(X) :- q(X), r(X). 

y que le desea ejecutar q(X) y r(X) en paralelo. Entonces, ¿qué ocurre si q unifica parcialmente X, digamos al vincularlo a f(Y). r debe tener conocimiento de este enlace, por lo tanto, o tiene que comunicarlo, o tiene que esperar a que ambos conjuntos se completen; entonces puede haber perdido el tiempo si uno de ellos falla, a menos que usted, nuevamente, los comunique para sincronizarse. Eso da sobrecarga y es difícil hacerlo bien. Ahora, para O:

p(X) :- q(X). 
p(X) :- r(X). 

Hay un número finito de opciones aquí (Prolog, por supuesto, admite un número infinito de opciones) así que más desea ejecutar ambas en paralelo. Pero entonces, ¿qué pasa si uno tiene éxito? La otra rama del cálculo debe suspenderse y su estado guardado. ¿Cuántos de estos estados vas a salvar a la vez? Tantos como procesadores parecen razonables, pero hay que tener cuidado de que los cálculos no creen estados que no encajen en la memoria. Eso significa que tiene que adivinar qué tan grande es el estado de un cálculo, algo que Prolog esconde de usted, ya que abstrae sobre detalles de implementación tales como procesadores y memoria; no es C.

En otras palabras, la paralelización automática es difícil. El proyecto de la quinta generación de computadoras solucionó algunos de los problemas mediante el diseño de lenguajes de elección comprometida, es decir, dialectos Prolog sin retroceder. Al hacerlo, cambiaron drásticamente el idioma. Cabe señalar que el lenguaje concurrente Erlang es una derivación de Prolog, y también se ha cambiado en retroceso por algo que está más cerca de la programación funcional. Todavía requiere la guía del usuario para saber qué partes de un programa se pueden ejecutar de manera segura al mismo tiempo.

Answer 4

Hay dos conceptos de concurrencia en Prolog. Uno está vinculado a multithreading, el otro a objetivos suspendidos. No estoy seguro de lo que quieres saber. Así que voy a ampliar un poco sobre multihebra primero:

Hoy en día, el sistema Prolog ampliamente disponible se puede diferenciar si son multiproceso o no. En un sistema Prolog multiproceso, puede generar múltiples hilos que se ejecutan simultáneamente sobre la misma base de conocimiento. Esto plantea algunos problemas para consulta y predicados dinámicos, que son resueltos por estos sistemas Prolog.

Puede encontrar una lista de los sistemas Prolog que se multiproceso aquí:

Operating system and Web-related features

multihilo es un prerequesite para diversos paradigmas de paralelización. En consecuencia, los sistemas Prolog individuales proporcionan constructos que sirven a ciertos paradigmas. Los paradigmas típicos son la agrupación de subprocesos, por ejemplo, se usa en servidores web o genera un subproceso para tareas de GUI de larga ejecución.

Actualmente no existe un estándar ISO para una biblioteca de subprocesos, aunque ha habido una propuesta y cada sistema Prolog tiene típicamente bibliotecas enriquecidas que proporcionan sincronización de subprocesos, comunicación de subprocesos, depuración de subprocesos e hilos de código extranjeros.Un cierto progreso en la recolección de basura en el sistema Prolog fue necesario para permitir aplicaciones con hilos que tienen hilos de ejecución potencialmente infinitamente largos.

Algunas capas existentes incluso permiten paradigmas de paralelización de alto nivel en un sistema independiente de Prolog. Por ejemplo, Logtalk tiene algunas construcciones que se asignan a varios sistemas Prolog objetivo.

Ahora pasemos a objetivos suspendidos. Desde sistemas Prolog más antiguos (desde Prolog II, 1982, de hecho) conocemos el comando freeze/2 o las directivas de bloqueo. Estos constructos obligan a un objetivo que no debe ampliarse mediante cláusulas existentes, sino que se pone en una lista de espera. El objetivo puede ser despertado más tarde. Dado que la ejecución de la meta no es inmediata sino solo cuando se despierta, las metas suspendidas a veces se ven como objetivos concurrentes, , pero la mejor idea para esta forma de paralelismo serían las corrutinas.

Los objetivos suspendidos son útiles para implementar sistemas de resolución de restricciones. En el caso más simple, la lista dormida es un atributo variable. Pero un nuevo enfoque para los sistemas de resolución de restricciones es reglas de manejo de restricciones. En las reglas de manejo de restricciones, las condiciones de activación pueden suspenderse en los patrones de pares de objetivos. La disponibilidad de restricción de la solución, ya sea a través de objetivos suspendidos o reglas que las restricciones se puede ver aquí:

Overview of Prolog Systems

Saludos

Answer 5

Eclipse-CLP, un lenguaje "compatible con versiones anteriores en gran medida con Prolog", soportes o -paralelismo, aunque "actualmente esta funcionalidad no se mantiene activamente debido a otras prioridades".

[1,2] documento OR- (y AND-) paralelismo en ECLiPSe-CLP.

Sin embargo, traté de hacerlo funcionar alguna vez usando el código del repositorio de ECLiPSe-CLP, pero no lo conseguí.

• [1] http://eclipseclp.org/reports/book.ps.gz
• [2] http://eclipseclp.org/doc/bips/kernel/compiler/parallel-1.html

Answer 6

Hubo una gran esperanza en los 80s/90s para cocer el paralelismo a la lengua (por lo que es "inherentemente" paralelo), en particular, en el contexto del Proyecto de Quinta Generación. Incluso se estudiaron construcciones de hardware especiales para implementar "Máquina de inferencia paralela" (PIM) (similar al hardware especial para máquinas LISP en el campo de "programación funcional"). Los esfuerzos de hardware se abandonaron debido a la mejora continua de las CPU disponibles y el esfuerzo de software se abandonó debido a la excesiva complejidad del compilador, la falta de demanda de funciones de alto nivel difíciles de implementar y la probable falta de pago: paralelismo que parece transparente y elegantemente explotable en el nivel de lenguaje generalmente significa costosas comunicaciones entre procesos y bloqueo transaccional "bajo el capó".

Una buena lectura de esto es

"The Deevolution of Concurrent Logic Programming Languages"

por Evan Tick, marzo de 1994. Apareció en "Programación Diario de la lógica, Décimo Aniversario Número especial de 1995". El archivo Postscript vinculado está completo, a diferencia del PDF que obtienes en Elsevier.

El autor dice:

Hay dos principales puntos de vista de la programación lógica concomitante y su desarrollo durante los últimos años. La mayoría de la programación lógica literatura consulta lenguajes de programación lógica concurrente como derivada o variante de programas lógicos, es decir, la principal diferencia es el uso extensivo de no determinismo "no importa" en lugar de "no sabe" (retroceso) no determinismo. Por lo tanto, el nombre cometió opción o idiomas CC. Una segunda opinión es que los programas de lógica concurrente son programas concurrentes y reactivos, no diferentes de otros lenguajes concurrentes "tradicionales" como 'C' con mensaje explícito pasando, en el sentido de que los procedimientos son procesos que comunican sobre flujos de datos de forma incremental producir respuestas Un cínico podría decir que la vista anterior tiene más riqueza académica, mientras que la última vista tiene un valor de relaciones públicas más práctico.

Este artículo es una encuesta de las técnicas de implementación de los lenguajes de programación lógica concurrentes , y por lo tanto la divulgación completa de estas dos vistas no es particularmente relevante. En su lugar, bastará con una descripción general rápida de la semántica básica del lenguaje , y cómo se relacionan con los paradigmas fundamentales de programación en una variedad de idiomas dentro de la familia. No se intentará cubrir los muchos paradigmas de programación posibles ; ni matices semánticos, ni la historia familiar. (...).

El punto principal que deseo hacer en este artículo es que concurrentes lógica lenguajes de programación han sido deevolving desde su creación, hace unos diez años, debido a la tanteo siguiente:

• Los diseñadores de sistemas y los escritores del compilador solo podrían proporcionar ciertas características limitadas en robustas; implementaciones eficientes. Esto impulsó al mercado a aceptar estos lenguajes restringidos como, en algunos sentidos informales , estándares de facto.
• Los programadores se dieron cuenta de que ciertas características de lenguaje más expresivas no eran críticamente importantes para obtener las aplicaciones escritas y no exigían su inclusión.

Por lo tanto mi postura en este artículo será un tercer punto de vista: ¿cómo las lenguas inicialmente ricos perdieron gradualmente sus "dientes", y se debilitaron, pero más aplicable en la práctica, y ha logrado un rendimiento más rápido.

La historia deevolutionary comienza con Prolog concurrente (guardias profundas, atómica Unifi-catión; las variables anotadas para sincronización de sólo lectura), y después de una serie de reducciones (por ejemplo: GHC (sincronización de entrada de coincidencia), Parlog (seguro), FCP (plano), Fleng (no guardias), Janus (comunicación restringida), Strand (asignación más bien que la unifi cación de salida)), y termina por ahora con PCN (protectores planos, no atómico asignaciones de sincronización de entrada-coincidencia, y variables mutables explícitamente definidas). Esta y otra terminología serán definidas a medida que avance el artículo.

Esta vista puede desagradar algunos lectores porque presupone que el rendimiento es la principal fuerza impulsora del mercado de idiomas; y además que el principal "valor añadido " de los programas lógicos concurrentes sobre los programas lógicos es la capacidad de explotar naturalmente el paralelismo para ganar velocidad. Ciertamente, la naturaleza reactiva de los idiomas también agrega valor; por ejemplo, en la construcción de aplicaciones complejas orientadas a objetos . Por lo tanto, se puede argumentar que la deevolution presenciada es algo malo cuando las capacidades reactivas se comercializan para la velocidad.