performance - sentencia - sintaxis de prolog

¿Concurrente es Prolog? (6)

No puedo encontrar ninguna información sobre esto en línea ... También soy nuevo en Prolog ...

Me parece que Prolog podría ser muy concurrente, quizás probando muchas posibilidades a la vez cuando intenta hacer coincidir una regla. ¿Los compiladores / intérpretes modernos de Prolog son intrínsecamente * concurrentes? ¿Cuáles? ¿La simultaneidad está activada por defecto? ¿Debo habilitarlo de alguna manera?

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

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

No. La programación lógica simultánea 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 tienes una construcción AND como

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

y querrías ejecutar q(X) y r(X) en paralelo. Entonces, ¿qué pasa si q unifica parcialmente a X , digamos uniéndolo a f(Y) ? Debe tener conocimiento de este enlace, por lo que debe comunicarlo o debe esperar a que se completen ambos conjuntos. entonces puede haber perdido el tiempo si uno de ellos falla, a menos que, una vez más, los haga comunicarse para sincronizarse. Eso da sobrecarga y es difícil hacerlo bien. Ahora para OR:

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

Aquí hay un número finito de opciones (Prolog, por supuesto, admite infinitas opciones) por lo que querría ejecutar ambas en paralelo. Pero entonces, ¿qué pasa si uno tiene éxito? La otra rama del cálculo debe suspenderse y su estado debe guardarse . ¿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 quepan 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 al diseñar 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.

A partir de una búsqueda rápida en Google, parece que el paradigma de programación lógica simultánea solo ha sido la base de algunos idiomas de investigación y ya no se desarrolla activamente. He visto afirmaciones de que la lógica concurrente es fácil de hacer en el sistema Mozart / Oz.

ECLiPSe-CLP, un lenguaje "en gran parte compatible con versiones anteriores de Prolog", admite el paralelismo de OR, aunque "actualmente esta funcionalidad no se mantiene activamente debido a otras prioridades".

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

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

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

para bien o para mal, la gente está acostumbrada a pensar que sus programas se ejecutan 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.
Los elementos del lenguaje no relacional, como el operador de corte, solo se pueden usar de manera significativa cuando se puede confiar en tales órdenes de ejecución, es decir, quedarían inutilizables en un intérprete paralelo a menos que se invente 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 usa típicamente para problemas recursivos de alto nivel, como atravesar gráficos, probar teoremas, etc. La paralelización en máquinas modernas puede (idealmente) lograr una aceleración de n para algunas n constantes, pero no puede convertir un método de solución recursivo inviable en uno viable, porque eso requeriría una aceleración exponencial . 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.

Hay dos conceptos de concurrencia en Prolog. Una está ligada al multihilo y la otra a objetivos suspendidos . No estoy seguro de lo que quieres saber. Así que voy a ampliar un poco sobre el multihilo 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 están multiproceso aquí:

Sistema operativo y funciones relacionadas con la web

Multithreading es un sitio previo a varios 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 ricas que proporcionan sincronización de subprocesos, comunicación de subprocesos, depuración de subprocesos e hilos de código externo. 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 una forma independiente del sistema Prolog. Por ejemplo, Logtalk tiene algunas construcciones que se asignan a varios sistemas Prolog objetivo.

Ahora veamos los 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 consideran objetivos concurrentes, pero la mejor idea para esta forma de paralelismo serían las corotinas.

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 enfoque más nuevo para los sistemas de resolución de restricciones son las 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 resolución de restricciones ya sea a través de objetivos suspendidos o reglas de manejo de restricciones se puede ver aquí:

Descripción general de los sistemas Prolog

Atentamente

Hubo una gran esperanza en los años 80/90 de lograr un paralelismo en el lenguaje (lo que lo hizo "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 sobre esto es

"La evolución de los lenguajes de programación lógica concurrente"

por Evan Tick, marzo de 1994. Apareció en "Journal of Logic Programming, Tenth Anniversary Special Issue, 1995". El archivo Postscript vinculado está completo, a diferencia del PDF que obtienes en Elsevier.

El autor dice:

Hay dos puntos de vista principales de la programación lógica concurrente y su desarrollo en los últimos años. La mayoría de la literatura de programación lógica considera los lenguajes de programación lógica concurrente como una derivada o variante de programas lógicos, es decir, la principal diferencia es el uso extensivo del no determinismo "do not care" en lugar del no determinismo "no sabe" (backtracking). De ahí el nombre cometido elección o CC idiomas. Una segunda opinión es que los programas lógicos simultáneos son programas concurrentes y reactivos, no muy diferentes de otros lenguajes concurrentes "tradicionales" como "C" con mensajes explícitos, en el sentido de que los procedimientos son procesos que se comunican a través de flujos de datos para producir incrementalmente respuestas. Un cínico podría decir que la visión anterior tiene más riqueza académica, mientras que la última visión 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 simultánea, por lo que la divulgación completa de estos dos puntos de vista no es particularmente relevante. En cambio, será suficiente una descripción general rápida de la semántica básica del lenguaje y cómo se relacionan con los paradigmas de programación fundamentales en una variedad de idiomas dentro de la familia. No se intentará cubrir los muchos paradigmas de programación factibles; ni matices semánticos, ni la historia familiar. (...).
El punto principal que deseo hacer en este artículo es que los lenguajes de programación lógica concurrente han estado profundizando desde su creación, hace unos diez años, debido a la siguiente degradación :
Los diseñadores de sistemas y los escritores de compiladores solo podrían proporcionar ciertas características limitadas en robustas; implementaciones eficientes. Esto llevó al mercado a aceptar estos lenguajes restringidos como, en cierto sentido informal, estándares de facto.
Los programadores se dieron cuenta de que ciertas características del lenguaje más expresivas no eran críticamente importantes para que las aplicaciones se escribieran y no exigían su inclusión.
Por lo tanto, mi postura en este artículo será una tercera visión: cómo las lenguas inicialmente ricas perdieron gradualmente sus "dientes" y se volvieron más débiles, pero más implementables prácticamente, y lograron un rendimiento más rápido.
La historia de la evolución comienza con Concurrent Prolog (protecciones profundas, unificación atómica, variables anotadas de solo lectura para la sincronización) y después de una serie de reducciones (por ejemplo: GHC (sincronización de ajuste de entrada), Parlog (seguro), FCP ( plano), Fleng (sin guardias), Janus (comunicación restringida), Strand (asignación en lugar de la unificación de salida)), y termina por ahora con PCN (protecciones planas, asignaciones no atómicas, sincronización de entrada de concordancia y definición explícita variables mutables). Esta y otra terminología se definirán a medida que avance el artículo.
Esta visión puede desagradar a algunos lectores porque presupone que el rendimiento es la principal fuerza motriz del mercado del lenguaje; y además, que el principal "valor agregado" 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 deevolución observada es mala cuando las capacidades reactivas se negocian por velocidad.