Programación de lógica de restricción concurrente - Concurrent constraint logic programming

La programación lógica de restricción concurrente es una versión de la programación lógica de restricción dirigida principalmente a programar procesos concurrentes en lugar de (o además) a resolver problemas de satisfacción de restricciones . Los objetivos en la programación de lógica de restricción se evalúan al mismo tiempo; Por tanto, se programa un proceso concurrente como la evaluación de un objetivo por parte del intérprete .

Sintácticamente, los programas lógicos de restricciones concurrentes son similares a los programas no concurrentes, la única excepción es que las cláusulas incluyen protecciones , que son restricciones que pueden bloquear la aplicabilidad de la cláusula en algunas condiciones. Semánticamente, la programación de lógica de restricción concurrente difiere de sus versiones no concurrentes porque la evaluación de un objetivo está destinada a realizar un proceso concurrente en lugar de encontrar una solución a un problema. Más notablemente, esta diferencia afecta cómo se comporta el intérprete cuando es aplicable más de una cláusula: la programación lógica de restricción no concurrente intenta recursivamente todas las cláusulas; La programación de lógica de restricción 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 anteriormente. Otros efectos de esto son la posibilidad semántica de tener un objetivo que no se puede probar mientras no falla la evaluación completa, y una forma particular de equiparar un objetivo y un encabezado de cláusula.

Las reglas de manejo de restricciones pueden verse como una forma de programación lógica de restricciones concurrentes, pero se utilizan para programar un simplificador o solucionador de restricciones en lugar de procesos concurrentes.

Descripción

En la programación de lógica de restricción, las metas en la meta actual se evalúan secuencialmente, generalmente procediendo en un orden LIFO en el que las metas más nuevas se evalúan primero. La versión concurrente de la programación lógica permite evaluar metas en paralelo : cada meta es evaluada por un proceso y los procesos se ejecutan al mismo tiempo. 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 que otro comprueba si la tienda implica una restricción.

La adición de una restricción a la tienda se realiza como en la programación lógica de restricciones normal. La verificació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 restricción 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 usar una nueva variante de esta cláusula para reemplazar un literal en el objetivo solo si el almacén de restricciones implica la protección después de agregarle la ecuación del literal y el encabezado de la cláusula. La definición precisa de esta regla es más complicada y se da a continuación.

La principal diferencia entre la programación lógica de restricciones no concurrente y concurrente es que la primera está dirigida a la búsqueda, mientras que la segunda está dirigida a implementar procesos concurrentes. Esta diferencia afecta si las opciones 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 restricción regular y concurrente se refiere a la condición en la que se puede usar más de una cláusula para demostrar un objetivo. La programación lógica no concurrente intenta todas las cláusulas posibles cuando se reescribe una meta: si la meta no se puede probar mientras se reemplaza con el cuerpo de una variante nueva de una cláusula, se prueba otra cláusula, si la hay. Esto se debe a que el objetivo es demostrar el objetivo: se prueban todas las formas posibles de demostrar el objetivo. Por otro lado, la programación de lógica de restricción concurrente tiene como objetivo 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 procesos permitiéndoles tomar elecciones, pero comprometiéndose con ellas una vez que se 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 intenta a su vez todas las cláusulas, 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 será probado. Estas dos formas diferentes de manejar opciones múltiples a menudo se denominan "no sé el no determinismo" y "no me importa el no determinismo".

Al reescribir un literal en el objetivo, las únicas cláusulas consideradas son aquellas cuya protección está implicada por la unión del almacén de restricciones y la ecuación del literal con el encabezado de la cláusula. Los guardias proporcionan una forma de saber qué cláusulas no deben considerarse en absoluto. Esto es particularmente importante dado el compromiso con una sola cláusula de programación lógica de restricción concurrente: una vez que se ha elegido una cláusula, esta elección nunca se reconsiderará. Sin guardias, 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 intenta todas las posibilidades. En la programación concurrente, el intérprete se compromete con una única 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 restricción concurrente está diseñada específicamente para permitir que los procesos se ejecuten sin terminar. Los procesos que no terminan son comunes en general en el procesamiento concurrente; la versión concurrente de la programación lógica de restricción los implementa al no usar la condición de falla: si ninguna cláusula es aplicable para reescribir una meta, el proceso que evalúa esta meta se detiene en lugar de hacer que toda la evaluación falle como en la programación lógica de restricción 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 están resolviendo diferentes objetivos se logra mediante el uso de guardias. Si un objetivo no se puede reescribir porque todas las cláusulas que podrían usarse tienen una protección que no está impuesta por el almacén de restricciones, el proceso que resuelve esta meta se bloquea hasta que los otros procesos agreguen las restricciones que son necesarias para implicar la protección de al menos uno. de las cláusulas aplicables. Esta sincronización está sujeta a interbloqueos : si se bloquean todos los objetivos, no se agregarán nuevas restricciones y, por lo tanto, no se desbloqueará ningún objetivo.

Un tercer efecto de la diferencia entre la programación lógica concurrente y no concurrente es 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 la cabeza se pueden equiparar a términos de tal manera que la cabeza sea igual a la meta. Esta regla se diferencia 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 una de las cabezas. Esta limitación puede verse como una forma de direccionalidad, ya que el objetivo y el encabezado de la cláusula se tratan de manera diferente.

Precisamente, la regla que indica si H:-G|Bse puede usar una nueva variante de una cláusula para reescribir un objetivo Aes la siguiente. Primero, se comprueba si Ay Htienen el mismo predicado. En segundo lugar, se comprueba si existe una forma de equiparar con dado el almacén de restricciones actual; contrariamente a la programación lógica regular, esto se hace bajo unificación unilateral , lo que solo permite que una variable de la cabeza sea igual a un término. En tercer lugar, se comprueba la guarda para determinar la vinculación del almacén de restricciones y las ecuaciones generadas en el segundo paso; la guardia puede contener variables que no se mencionan en el encabezado de la cláusula: estas variables se interpretan existencialmente. Este método para decidir la aplicabilidad de una nueva variante de una cláusula para reemplazar un objetivo se puede expresar de manera compacta de la siguiente manera: el almacenamiento de restricciones actual implica que existe una evaluación de las variables de la cabeza y la protección de manera que la cabeza es igual a el gol y la guardia están implicados. En la práctica, la vinculación puede comprobarse con un método incompleto.

Una extensión de la sintaxis y la semántica de la programación lógica concurrente es el tell atómico . Cuando el intérprete usa una cláusula, su protección se agrega al almacén de restricciones. Sin embargo, también se añaden las limitaciones del cuerpo. Debido al compromiso con esta cláusula, el intérprete no retrocede si las restricciones del cuerpo son inconsistentes con la tienda. Esta condición puede evitarse mediante el uso de tell atómico, que es una variante en la que la cláusula contiene una especie de "segunda protección" cuya coherencia solo se comprueba. Esta cláusula está escrita 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, ambos Gy Dse agregan al almacén de restricciones.

Historia

El estudio de la programación lógica de restricciones concurrentes comenzó a finales de la década de 1980, cuando algunos de los principios de la programación lógica concurrente fueron integrados en la programación lógica de restricciones por Michael J. Maher . Las propiedades teóricas de la programación lógica de restricciones concurrentes fueron posteriormente estudiadas por varios autores.

Ver también

Referencias

  • Marriott, Kim; Peter J. Stuckey (1998). Programación con restricciones: una introducción . MIT Press. ISBN  0-262-13341-5
  • Frühwirth, Thom; Slim Abdennadher (2003). Fundamentos de la programación de restricciones . Saltador. ISBN  3-540-67623-6
  • Jaffar, Joxan; Michael J. Maher (1994). "Programación lógica de restricciones: una encuesta" . Revista de programación lógica . 19/20: 503–581. doi : 10.1016 / 0743-1066 (94) 90033-7 .
Específico
  1. ^ Frühwirth, Thom. " Teoría y práctica de las reglas de manejo de restricciones ". The Journal of Logic Programming 37.1-3 (1998): 95-138.