La programación lógica con restricciones concurrentes es una versión de la programación lógica con restricciones que apunta principalmente a programar procesos concurrentes en lugar de (o además de) resolver problemas de satisfacción de restricciones . Los objetivos en la programación lógica con restricciones se evalúan de manera concurrente; por lo tanto, un proceso concurrente se programa como la evaluación de un objetivo por parte del intérprete .
Sintácticamente , los programas de lógica de restricciones concurrentes son similares a los programas no concurrentes, con la única excepción de que las cláusulas incluyen guardas , que son restricciones que pueden bloquear la aplicabilidad de la cláusula bajo ciertas condiciones. Semánticamente, la programación de lógica de restricciones concurrente difiere de sus versiones no concurrentes porque una evaluación de objetivo está destinada a realizar un proceso concurrente en lugar de encontrar una solución a un problema. En particular, esta diferencia afecta a cómo se comporta el intérprete cuando es aplicable más de una cláusula: la programación de lógica de restricciones no concurrente prueba recursivamente todas las cláusulas; la programación de lógica de restricciones concurrente elige solo una. Este es el efecto más evidente de una direccionalidad intencionada del intérprete, que nunca revisa una elección que ha tomado previamente. Otros efectos de esto son la posibilidad semántica de tener un objetivo que no se puede probar mientras que toda la evaluación no falle, y una forma particular de equiparar un objetivo y una cabeza de cláusula.
Las reglas de manejo de restricciones pueden verse como una forma de programación lógica de restricciones concurrentes, [1] pero se utilizan para programar un simplificador o solucionador de restricciones en lugar de procesos concurrentes.
En la programación lógica de restricciones, los objetivos del objetivo actual se evalúan de forma secuencial, generalmente siguiendo un orden LIFO en el que los objetivos más nuevos se evalúan primero. La versión concurrente de la programación lógica permite evaluar los objetivos en paralelo : cada objetivo es evaluado por un proceso y los procesos se ejecutan simultáneamente. Estos procesos interactúan a través del almacén de restricciones: un proceso puede agregar una restricción al almacén de restricciones mientras otro verifica si el almacén implica una restricción.
La adición de una restricción al almacén se realiza como en la programación lógica de restricciones normal. La comprobación de la implicación de una restricción se realiza mediante protecciones a las cláusulas. Las protecciones requieren una extensión sintáctica: una cláusula de programación lógica de restricciones concurrente se escribe como H :- G | Bdonde Ges una restricción llamada la protección de la cláusula. En términos generales, se puede utilizar una nueva variante de esta cláusula para reemplazar un literal en el objetivo solo si la protección está implicada por el almacén de restricciones después de la ecuación del literal y se le agrega el encabezado de la cláusula. La definición precisa de esta regla es más complicada y se proporciona a continuación.
La principal diferencia entre la programación lógica de restricciones concurrente y no concurrente es que la primera está orientada a la búsqueda, mientras que la segunda está orientada a la implementación de procesos concurrentes. Esta diferencia afecta a si las elecciones se pueden deshacer, si se permite que los procesos no terminen y cómo se equiparan los objetivos y los encabezados de las cláusulas.
La primera diferencia semántica entre la programación lógica de restricciones regular y concurrente tiene que ver con la condición de que se pueda usar más de una cláusula para probar un objetivo. La programación lógica no concurrente prueba todas las cláusulas posibles al reescribir un objetivo: si el objetivo no se puede probar al reemplazarlo con el cuerpo de una nueva variante de una cláusula, se prueba otra cláusula, si existe alguna. Esto se debe a que el objetivo es probar el objetivo: se prueban todas las formas posibles de probar el objetivo. Por otro lado, la programación lógica de restricciones concurrente apunta a programar procesos paralelos. En la programación concurrente general, si un proceso hace una elección, esta elección no se puede deshacer. La versión concurrente de la programación lógica de restricciones implementa los procesos permitiéndoles tomar decisiones, pero comprometiéndose con ellas una vez que las han tomado. Técnicamente, si se puede usar más de una cláusula para reescribir un literal en el objetivo, la versión no concurrente prueba todas las cláusulas a su vez, mientras que la versión concurrente elige una única cláusula arbitraria: al contrario de la versión no concurrente, las otras cláusulas nunca se probarán. Estas dos formas diferentes de manejar opciones múltiples a menudo se denominan "no determinismo de no saber" y "no determinismo de no importar".
Al reescribir un literal en el objetivo, las únicas cláusulas consideradas son aquellas cuya protección está implícita en la unión del almacén de restricciones y la ecuación del literal con la cabeza de la cláusula. Las protecciones proporcionan una forma de saber qué cláusulas no se deben considerar en absoluto. Esto es particularmente importante dado el compromiso con una sola cláusula de la programación lógica de restricciones concurrente: una vez que se ha elegido una cláusula, esta elección nunca se reconsiderará. Sin protecciones, el intérprete podría elegir una cláusula "incorrecta" para reescribir un literal, mientras que existen otras cláusulas "buenas". En la programación no concurrente, esto es menos importante, ya que el intérprete siempre prueba todas las posibilidades. En la programación concurrente, el intérprete se compromete con una sola posibilidad sin probar las otras.
Un segundo efecto de la diferencia entre la versión no concurrente y la concurrente es que la programación lógica de restricciones concurrente está diseñada específicamente para permitir que los procesos se ejecuten sin terminar. Los procesos sin terminación son comunes en general en el procesamiento concurrente; la versión concurrente de la programación lógica de restricciones los implementa al no usar la condición de falla: si no hay ninguna cláusula aplicable para reescribir un objetivo, el proceso que evalúa este objetivo se detiene en lugar de hacer que toda la evaluación falle como en la programación lógica de restricciones no concurrente. Como resultado, el proceso que evalúa un objetivo puede detenerse porque no hay ninguna cláusula disponible para continuar, pero al mismo tiempo los otros procesos siguen ejecutándose.
La sincronización entre procesos que resuelven diferentes objetivos se logra mediante el uso de protecciones. Si un objetivo no se puede reescribir porque todas las cláusulas que se podrían usar tienen una protección que no está implícita en el almacén de restricciones, el proceso que resuelve este objetivo se bloquea hasta que los otros procesos agreguen las restricciones que sean necesarias para implicar la protección de al menos una de las cláusulas aplicables. Esta sincronización está sujeta a interbloqueos : si todos los objetivos están bloqueados, no se agregarán nuevas restricciones y, por lo tanto, nunca se desbloqueará ningún objetivo.
Un tercer efecto de la diferencia entre la programación lógica concurrente y no concurrente está en la forma en que un objetivo se equipara al encabezado de una nueva variante de una cláusula. Operativamente, esto se hace comprobando si las variables en el encabezado pueden equipararse a términos de tal manera que el encabezado sea igual al objetivo. Esta regla difiere de la regla correspondiente para la programación lógica de restricciones en que solo permite agregar restricciones en la forma variable=término, donde la variable es uno de los encabezados. Esta limitación puede verse como una forma de direccionalidad, en el sentido de que el objetivo y el encabezado de la cláusula se tratan de manera diferente.
Precisamente, la regla que dice si una variante nueva H:-G|Bde una cláusula puede usarse para reescribir un objetivo Aes la siguiente. Primero, se verifica si Ay Htienen el mismo predicado. Segundo, se verifica si existe una manera de igualar con el almacén de restricciones actual dado; al contrario de la programación lógica regular, esto se hace bajo unificación unilateral , que solo permite que una variable del núcleo sea igual a un término. Tercero, se verifica la implicación del almacén de restricciones y las ecuaciones generadas en el segundo paso; el núcleo puede contener variables que no se mencionan en el núcleo de la cláusula: estas variables se interpretan existencialmente. Este método para decidir la aplicabilidad de una variante nueva de una cláusula para reemplazar un objetivo puede expresarse de manera compacta de la siguiente manera: el almacén de restricciones actual implica que existe una evaluación de las variables del núcleo y el núcleo tal que el núcleo es igual al objetivo y el núcleo está implicado. En la práctica, la implicación puede verificarse con un método incompleto.
Una extensión de la sintaxis y semántica de la programación lógica concurrente es el atomic tell . Cuando el intérprete usa una cláusula, su protección se agrega al almacén de restricciones. Sin embargo, también se agregan las restricciones del cuerpo. Debido al compromiso con esta cláusula, el intérprete no retrocede si las restricciones del cuerpo son inconsistentes con el almacén. Esta condición se puede evitar mediante el uso de atomic tell, que es una variante en la que la cláusula contiene una especie de "segunda protección" que solo se verifica por consistencia. Una cláusula de este tipo se escribe H :- G:D|B. Esta cláusula se usa para reescribir un literal solo si Gestá implícito en el almacén de restricciones y Des consistente con él. En este caso, tanto Gy Dse agregan al almacén de restricciones.
El estudio de la programación lógica con restricciones concurrentes comenzó a fines de la década de 1980, cuando Michael J. Maher integró algunos de los principios de la programación lógica con restricciones en la programación lógica concurrente. Las propiedades teóricas de la programación lógica con restricciones concurrentes fueron estudiadas posteriormente por varios autores, entre ellos Martin Rinard y Vijay A. Saraswat. [2]
