La programación lógica de restricciones es una forma de programación de restricciones , en la que la programación lógica se extiende para incluir conceptos de satisfacción de restricciones . Un programa lógico de restricciones es un programa lógico que contiene restricciones en el cuerpo de cláusulas. Un ejemplo de cláusula que incluye una restricción es . En esta cláusula, es una restricción; , y son literales como en la programación lógica normal. Esta cláusula establece una condición bajo la cual se cumple la afirmación: es mayor que cero y ambos y son verdaderos.A(X,Y) :- X+Y>0, B(X), C(Y)X+Y>0A(X,Y)B(X)C(Y)A(X,Y)X+YB(X)C(Y)
Como en la programación lógica normal, a los programas se les pregunta sobre la demostrabilidad de un objetivo, que a su vez puede contener restricciones además de literales. Una prueba de un objetivo se compone de cláusulas cuyos cuerpos son restricciones satisfacibles y literales que a su vez pueden demostrarse utilizando otras cláusulas. La ejecución la realiza un intérprete, que parte del objetivo y escanea recursivamente las cláusulas intentando probar el objetivo. Las restricciones encontradas durante este escaneo se colocan en un conjunto llamado almacén de restricciones . Si se descubre que este conjunto es insatisfactorio, el intérprete retrocede , intentando utilizar otras cláusulas para demostrar el objetivo. En la práctica, la satisfacibilidad del almacén de restricciones se puede comprobar utilizando un algoritmo incompleto, que no siempre detecta inconsistencias.
Formalmente, los programas de lógica de restricciones son como programas de lógica normal, pero el cuerpo de cláusulas puede contener restricciones, además de los literales de programación lógica normal. Como ejemplo, X>0es una restricción y se incluye en la última cláusula del siguiente programa de lógica de restricciones.
B ( X , 1 ): - X < 0. B ( X , Y ): - X = 1 , Y > 0. A ( X , Y ): - X > 0 , B ( X , Y ).Al igual que en la programación lógica normal, evaluar un objetivo como A(X,1)requiere evaluar el cuerpo de la última cláusula con Y=1. Como en la programación lógica normal, esto a su vez requiere demostrar el objetivo B(X,1). Al contrario de la programación lógica normal, esto también requiere que se cumpla una restricción: X>0, la restricción en el cuerpo de la última cláusula. (En la programación lógica normal, X>0 no se puede probar a menos que X esté vinculado a un término completamente básico y la ejecución del programa fallará si ese no es el caso).
No siempre se puede determinar si se cumple una restricción cuando se encuentra la restricción. En este caso, por ejemplo, el valor de Xno se determina cuando se evalúa la última cláusula. Como resultado, la restricción X>0no se satisface ni se viola en este punto. En lugar de proceder con la evaluación de B(X,1)y luego verificar si el valor resultante de Xes positivo, el intérprete almacena la restricción X>0y luego continúa con la evaluación de B(X,1); De esta manera, el intérprete puede detectar una violación de la restricción X>0durante la evaluación de B(X,1)y retroceder inmediatamente si este es el caso, en lugar de esperar a que B(X,1)concluya la evaluación de.
En general, la evaluación de un programa de lógica de restricciones procede como lo hace un programa de lógica normal. Sin embargo, las restricciones encontradas durante la evaluación se colocan en un conjunto llamado almacén de restricciones. A modo de ejemplo, la evaluación del objetivo A(X,1)se procede evaluando el cuerpo de la primera cláusula con Y=1; esta evaluación se suma X>0al almacén de restricciones y requiere B(X,1)que se demuestre el objetivo. Al intentar demostrar este objetivo, se aplica la primera cláusula pero su evaluación aumenta X<0el almacén de restricciones. Esta adición hace que el almacén de restricciones sea insatisfactorio. Luego, el intérprete retrocede, eliminando la última adición del almacén de restricciones. La evaluación de la segunda cláusula agrega X=1y Y>0al almacén de restricciones. Dado que el almacén de restricciones es satisfactoria y no queda ningún otro literal por probar, el intérprete se detiene con la solución X=1, Y=1.
La semántica de los programas de lógica de restricciones se puede definir en términos de un intérprete virtual que mantiene un par durante la ejecución. El primer elemento de este par se llama objetivo actual; el segundo elemento se llama almacén de restricciones. El objetivo actual contiene los literales que el intérprete intenta probar y también puede contener algunas restricciones que intenta satisfacer; el almacén de restricciones contiene todas las restricciones que el intérprete ha supuesto satisfactorias hasta el momento.
Inicialmente, el objetivo actual es el objetivo y el almacén de restricciones está vacío. El intérprete procede eliminando el primer elemento del objetivo actual y analizándolo. Los detalles de este análisis se explican a continuación, pero al final este análisis puede producir una terminación exitosa o un fracaso. Este análisis puede implicar llamadas recursivas y la adición de nuevos literales al objetivo actual y nuevas restricciones al almacén de restricciones. El intérprete retrocede si se genera un error. Se genera una terminación exitosa cuando el objetivo actual está vacío y el almacén de restricciones es satisfactoria.
El detalle del análisis de un literal retirado de la meta es el siguiente. Después de haber eliminado este literal del frente de la meta, se verifica si es una restricción o un literal. Si es una restricción, se agrega al almacén de restricciones. Si es un literal, se elige una cláusula cuyo encabezamiento tenga el mismo predicado que el literal; la cláusula se reescribe reemplazando sus variables con nuevas variables (variables que no aparecen en el objetivo): el resultado se denomina nueva variante de la cláusula; el cuerpo de la nueva variante de la cláusula se coloca entonces delante de la portería; la igualdad de cada argumento del literal con el correspondiente de la nueva variante head también se coloca al frente de la meta.
Durante estas operaciones se realizan algunos controles. En particular, se comprueba la coherencia del almacén de restricciones cada vez que se le agrega una nueva restricción. En principio, siempre que el almacén de restricciones sea insatisfactorio, el algoritmo podría retroceder. Sin embargo, comprobar la insatisfacibilidad en cada paso sería ineficaz. Por este motivo, se puede utilizar en su lugar un verificador de satisfacibilidad incompleta. En la práctica, la satisfacibilidad se verifica utilizando métodos que simplifican el almacén de restricciones, es decir, lo reescriben en una forma equivalente pero más sencilla de resolver. Estos métodos a veces, pero no siempre, pueden demostrar la insatisfacibilidad de un almacén de restricciones insatisfactorias.
El intérprete ha demostrado el objetivo cuando el objetivo actual está vacío y el almacén de restricciones no se detecta como insatisfactorio. El resultado de la ejecución es el conjunto actual de restricciones (simplificadas). Este conjunto puede incluir restricciones como las que fuerzan a las variables a un valor específico, pero también puede incluir restricciones como las que solo vinculan variables sin darles un valor específico.
Formalmente, la semántica de la programación lógica de restricciones se define en términos de derivaciones . Una transición es un par de pares meta/tienda, señaló . Tal par plantea la posibilidad de ir de un estado a otro . Esta transición es posible en tres casos posibles:
Una secuencia de transiciones es una derivación. Se puede demostrar una meta G si existe una derivación de a para algún almacén de restricciones satisfacible S. Esta semántica formaliza las posibles evoluciones de un intérprete que elige arbitrariamente el literal del objetivo a procesar y la cláusula a reemplazar literales. En otras palabras, una meta se prueba bajo esta semántica si existe una secuencia de elecciones de literales y cláusulas, entre los posiblemente muchos, que conduzcan a una meta vacía y a un almacén satisfactible.
Los intérpretes reales procesan los elementos del objetivo en un orden LIFO : los elementos se agregan al frente y se procesan desde el frente. También eligen la cláusula de la segunda regla según el orden en que están escritas y reescriben el almacén de restricciones cuando se modifica.
El tercer tipo posible de transición es la sustitución del almacén de restricciones por uno equivalente. Este reemplazo se limita a aquellos realizados mediante métodos específicos, como la propagación de restricciones . La semántica de la programación lógica de restricciones es paramétrica no sólo en cuanto al tipo de restricciones utilizadas sino también al método para reescribir el almacén de restricciones. Los métodos específicos utilizados en la práctica reemplazan el almacén de restricciones por uno que es más sencillo de resolver. Si el almacén de restricciones es insatisfactorio, esta simplificación puede detectar esta insatisfacibilidad algunas veces, pero no siempre.
El resultado de evaluar un objetivo frente a un programa de lógica de restricciones se define si se demuestra el objetivo. En este caso, existe una derivación del par inicial a un par donde la meta está vacía. El almacén de restricciones de este segundo par se considera el resultado de la evaluación. Esto se debe a que el almacén de restricciones contiene todas las restricciones que se supone que son satisfactorias para demostrar el objetivo. En otras palabras, el objetivo se demuestra para todas las evaluaciones de variables que satisfacen estas restricciones.
La igualdad por pares de los argumentos de dos literales a menudo se denota de forma compacta por : esta es una abreviatura de las restricciones . Una variante común de la semántica para la programación de lógica de restricciones se suma directamente al almacén de restricciones en lugar de al objetivo.
Se utilizan diferentes definiciones de términos, generando diferentes tipos de programación lógica de restricciones: sobre árboles, reales o dominios finitos. Un tipo de restricción que siempre está presente es la igualdad de términos. Estas restricciones son necesarias porque el intérprete añade t1=t2al objetivo cada vez que un literal P(...t1...)se reemplaza con el cuerpo de una cláusula con una nueva variante cuyo encabezado es P(...t2...).
La programación lógica de restricciones con términos de árbol emula la programación lógica normal al almacenar sustituciones como restricciones en el almacén de restricciones. Los términos son variables, constantes y símbolos de funciones aplicados a otros términos. Las únicas restricciones consideradas son las igualdades y desigualdades entre términos. La igualdad es particularmente importante, ya que t1=t2a menudo el intérprete genera restricciones como ésta. Las restricciones de igualdad en los términos se pueden simplificar, es decir, resolver, mediante la unificación :
Una restricción t1=t2se puede simplificar si ambos términos son símbolos de función aplicados a otros términos. Si los dos símbolos de función son iguales y el número de subtérminos también es el mismo, esta restricción se puede reemplazar con la igualdad de subtérminos por pares. Si los términos están compuestos por diferentes símbolos de función o el mismo functor pero en un número diferente de términos, la restricción es insatisfactoria.
Si uno de los dos términos es una variable, el único valor permitido que puede tomar la variable es el otro término. Como resultado, el otro término puede reemplazar la variable en el almacén de objetivos y restricciones actual, eliminando así prácticamente la variable de la consideración. En el caso particular de igualdad de una variable consigo misma, la restricción se puede eliminar como siempre satisfecha.
En esta forma de satisfacción de restricciones, los valores de las variables son términos.
La programación de lógica de restricciones con números reales utiliza expresiones reales como términos. Cuando no se utilizan símbolos de función, los términos son expresiones sobre reales y posiblemente incluyan variables. En este caso, cada variable sólo puede tomar como valor un número real.
Para ser precisos, los términos son expresiones sobre variables y constantes reales. La igualdad entre términos es un tipo de restricción que siempre está presente, ya que el intérprete genera igualdad de términos durante la ejecución. Como ejemplo, si el primer literal del objetivo actual es A(X+1)y el intérprete ha elegido una cláusula que A(Y-1):-Y=1después de reescribir es variable, las restricciones agregadas al objetivo actual son X+1=Y-1y . Las reglas de simplificación utilizadas para los símbolos de funciones obviamente no se utilizan: no es insatisfactorio simplemente porque la primera expresión se construye usando y la segunda usando .X+1=Y-1+-
Los símbolos reales y de función se pueden combinar, lo que da lugar a términos que son expresiones sobre reales y símbolos de función aplicados a otros términos. Formalmente, las variables y las constantes reales son expresiones, como cualquier operador aritmético sobre otras expresiones. Las variables, las constantes (símbolos de función de aridad cero) y las expresiones son términos, como cualquier símbolo de función aplicado a los términos. En otras palabras, los términos se construyen sobre expresiones, mientras que las expresiones se construyen sobre números y variables. En este caso, las variables abarcan números y términos reales . En otras palabras, una variable puede tomar como valor un número real, mientras que otra toma un término.
La igualdad de dos términos se puede simplificar usando las reglas para términos de árbol si ninguno de los dos términos es una expresión real. Por ejemplo, si los dos términos tienen el mismo símbolo de función y el mismo número de subtérminos, su restricción de igualdad se puede reemplazar con la igualdad de subtérminos.
La tercera clase de restricciones utilizadas en la programación lógica de restricciones es la de dominios finitos. En este caso, los valores de las variables se toman de un dominio finito, a menudo el de los números enteros . Para cada variable, se puede especificar un dominio diferente: X::[1..5]por ejemplo, significa que el valor de Xestá entre 1y 5. El dominio de una variable también se puede dar enumerando todos los valores que puede tomar una variable; por lo tanto, la declaración de dominio anterior también se puede escribir X::[1,2,3,4,5]. Esta segunda forma de especificar un dominio permite dominios que no están compuestos de números enteros, como X::[george,mary,john]. Si no se especifica el dominio de una variable, se supone que es el conjunto de números enteros representables en el lenguaje. A un grupo de variables se le puede dar el mismo dominio mediante una declaración como [X,Y,Z]::[1..5].
El dominio de una variable puede reducirse durante la ejecución. De hecho, a medida que el intérprete agrega restricciones al almacén de restricciones, realiza la propagación de restricciones para imponer una forma de coherencia local , y estas operaciones pueden reducir el dominio de las variables. Si el dominio de una variable queda vacío, el almacén de restricciones es inconsistente y el algoritmo retrocede. Si el dominio de una variable se convierte en un singleton , a la variable se le puede asignar el valor único en su dominio. Las formas de coherencia que normalmente se aplican son la coherencia de arco , la coherencia de hiperarco y la coherencia ligada . El dominio actual de una variable se puede inspeccionar utilizando literales específicos; por ejemplo, dom(X,D)descubre el dominio actual Dde una variable X.
En cuanto a dominios de reales, se pueden utilizar functores con dominios de números enteros. En este caso, un término puede ser una expresión sobre números enteros, una constante o la aplicación de un funtor sobre otros términos. Una variable puede tomar un término arbitrario como valor, si su dominio no ha sido especificado como un conjunto de números enteros o constantes.
El almacén de restricciones contiene las restricciones que actualmente se suponen satisfactorias. Se puede considerar cuál es la sustitución actual de la programación lógica regular. Cuando sólo se permiten términos de árbol, el almacén de restricciones contiene restricciones en el formato t1=t2; estas restricciones se simplifican mediante la unificación, lo que da como resultado restricciones de la forma variable=term; tales restricciones son equivalentes a una sustitución.
Sin embargo, el almacén de restricciones también puede contener restricciones en el formulario , si se permite t1!=t2la diferencia entre términos. !=Cuando se permiten restricciones sobre dominios reales o finitos, el almacén de restricciones también puede contener restricciones específicas de dominio como X+2=Y/2, etc.
El almacén de restricciones amplía el concepto de sustitución actual de dos maneras. Primero, contiene no sólo las restricciones derivadas de equiparar un literal con el encabezado de una nueva variante de una cláusula, sino también las restricciones del cuerpo de cláusulas. En segundo lugar, contiene no sólo restricciones de la forma variable=valuesino también restricciones del lenguaje de restricciones considerado. Mientras que el resultado de una evaluación exitosa de un programa lógico regular es la sustitución final, el resultado de un programa lógico de restricciones es el almacén de restricciones final, que puede contener restricciones de la forma variable=valuepero también restricciones arbitrarias.
Las restricciones específicas del dominio pueden llegar al almacén de restricciones tanto desde el cuerpo de una cláusula como al equiparar un literal con un encabezado de cláusula: por ejemplo, si el intérprete reescribe el literal A(X+2)con una cláusula cuyo nuevo encabezado variante es A(Y/2), la restricción X+2=Y/2se agrega a el almacén de restricciones. Si una variable aparece en una expresión de dominio real o finito, solo puede tomar un valor en el dominio real o finito. Una variable de este tipo no puede tomar como valor un término formado por un functor aplicado a otros términos. El almacén de restricciones es insatisfactorio si una variable está obligada a tomar tanto un valor del dominio específico como un functor aplicado a los términos.
Después de agregar una restricción al almacén de restricciones, se realizan algunas operaciones en el almacén de restricciones. Las operaciones que se realizan dependen del dominio y las restricciones considerados. Por ejemplo, la unificación se utiliza para igualdades de árboles finitos, la eliminación de variables para ecuaciones polinomiales sobre reales y la propagación de restricciones para imponer una forma de consistencia local para dominios finitos. Estas operaciones tienen como objetivo hacer que el almacén de restricciones sea más sencillo de verificar para verificar su satisfacibilidad y resolverlo.
Como resultado de estas operaciones, la adición de nuevas restricciones puede cambiar las antiguas. Es esencial que el intérprete pueda deshacer estos cambios cuando retroceda. El método de caso más simple es que el intérprete guarde el estado completo de la tienda cada vez que hace una elección (elige una cláusula para reescribir un objetivo). Existen métodos más eficientes para permitir que el almacén de restricciones vuelva a un estado anterior. En particular, uno puede simplemente guardar los cambios realizados en el almacén de restricciones entre dos puntos de elección, incluidos los cambios realizados en las restricciones anteriores. Esto se puede hacer simplemente guardando el valor antiguo de las restricciones que se han modificado; este método se llama seguimiento . Un método más avanzado es guardar los cambios que se han realizado en las restricciones modificadas. Por ejemplo, una restricción lineal se cambia modificando su coeficiente: guardar la diferencia entre el coeficiente antiguo y el nuevo permite revertir un cambio. Este segundo método se llama retroceso semántico , porque se guarda la semántica del cambio en lugar de solo la versión anterior de las restricciones.
Los literales de etiquetado se utilizan en variables en dominios finitos para verificar la satisfacibilidad o la satisfacibilidad parcial del almacén de restricciones y encontrar una asignación satisfactoria. Un literal de etiquetado tiene la forma labeling([variables]), donde el argumento es una lista de variables en dominios finitos. Siempre que el intérprete evalúa dicho literal, realiza una búsqueda en los dominios de las variables de la lista para encontrar una asignación que satisfaga todas las restricciones relevantes. Normalmente, esto se hace mediante una forma de retroceso : las variables se evalúan en orden, probando todos los valores posibles para cada una de ellas y retrocediendo cuando se detecta una inconsistencia.
El primer uso del literal de etiquetado es verificar la satisfacibilidad real o parcial del almacén de restricciones. Cuando el intérprete agrega una restricción al almacén de restricciones, solo le impone una forma de coherencia local. Es posible que esta operación no detecte inconsistencias incluso si el almacenamiento de restricciones no es satisfactorio. Un literal de etiquetado sobre un conjunto de variables impone una verificación de satisfacibilidad de las restricciones sobre estas variables. Como resultado, el uso de todas las variables mencionadas en la tienda de restricciones da como resultado verificar la satisfacibilidad de la tienda.
El segundo uso del literal de etiquetado es determinar una evaluación de las variables que satisfaga el almacén de restricciones. Sin el literal de etiquetado, a las variables se les asignan valores solo cuando el almacén de restricciones contiene una restricción de la forma X=valuey cuando la coherencia local reduce el dominio de una variable a un solo valor. Un literal de etiquetado sobre algunas variables obliga a evaluar estas variables. En otras palabras, una vez considerado el literal de etiquetado, a todas las variables se les asigna un valor.
Normalmente, los programas de lógica de restricciones se escriben de tal manera que los literales de etiquetado se evalúen sólo después de que se hayan acumulado tantas restricciones como sea posible en el almacén de restricciones. Esto se debe a que el etiquetado de literales impone la búsqueda, y la búsqueda es más eficiente si hay más restricciones que satisfacer. Un problema de satisfacción de restricciones normalmente se resuelve mediante un programa lógico de restricciones que tiene la siguiente estructura:
resolver ( X ): - restricciones ( X ), etiquetado ( X ) restricciones ( X ) : - ( todas las restricciones del CSP )Cuando el intérprete evalúa el objetivo solve(args), coloca el cuerpo de una nueva variante de la primera cláusula en el objetivo actual. Dado que el primer objetivo es constraints(X'), se evalúa la segunda cláusula y esta operación mueve todas las restricciones en el objetivo actual y, finalmente, en el almacén de restricciones. Luego se evalúa el literal labeling(X'), lo que obliga a buscar una solución del almacén de restricciones. Dado que el almacén de restricciones contiene exactamente las restricciones del problema de satisfacción de restricciones original, esta operación busca una solución del problema original.
Un programa de lógica de restricciones determinado puede reformularse para mejorar su eficiencia. Una primera regla es que los literales etiquetados deben colocarse después de que se hayan acumulado en el almacén de restricciones la mayor cantidad posible de restricciones sobre los literales etiquetados. Si bien en teoría es equivalente a , la búsqueda que se realiza cuando el intérprete encuentra el literal de etiquetado se realiza en un almacén de restricciones que no contiene la restricción . Como resultado, puede generar soluciones, como , que luego se descubre que no satisfacen esta restricción. Por otro lado, en la segunda formulación la búsqueda se realiza sólo cuando la restricción ya está en el almacén de restricciones. Como resultado, la búsqueda solo devuelve soluciones que sean consistentes con ella, aprovechando el hecho de que restricciones adicionales reducen el espacio de búsqueda.A(X):-labeling(X),X>0A(X):-X>0,labeling(X)X>0X=-1
Una segunda reformulación que puede aumentar la eficiencia es colocar restricciones antes de los literales en el cuerpo de las cláusulas. De nuevo, y son en principio equivalentes. Sin embargo, el primero puede requerir más cálculos. Por ejemplo, si el almacén de restricciones contiene la restricción , el intérprete evalúa recursivamente en el primer caso; si tiene éxito, descubre que el almacén de restricciones es inconsistente al agregar . En el segundo caso, al evaluar esa cláusula, el intérprete primero agrega al almacén de restricciones y luego posiblemente evalúa . Dado que el almacenamiento de restricciones después de la adición de resulta ser inconsistente, la evaluación recursiva de no se realiza en absoluto.A(X):-B(X),X>0A(X):-X>0,B(X)X<-2B(X)X>0X>0B(X)X>0B(X)
Una tercera reformulación que puede aumentar la eficiencia es la adición de restricciones redundantes. Si el programador sabe (por cualquier medio) que la solución de un problema satisface una restricción específica, puede incluir esa restricción para causar inconsistencia en el almacén de restricciones lo antes posible. Por ejemplo, si se sabe de antemano que la evaluación de B(X)dará como resultado un valor positivo para X, el programador puede agregar X>0antes de cualquier aparición de B(X). Por ejemplo, A(X,Y):-B(X),C(X)fallará en la meta A(-2,Z), pero esto solo se descubre durante la evaluación de la submeta B(X). Por otro lado, si la cláusula anterior se reemplaza por , el intérprete retrocede tan pronto como se agrega la restricción al almacén de restricciones, lo que ocurre antes de que comience la evaluación de pares.A(X,Y):-X>0,A(X),B(X)X>0B(X)
Las reglas de manejo de restricciones se definieron inicialmente como un formalismo independiente para especificar solucionadores de restricciones y luego se incorporaron a la programación lógica. Hay dos tipos de reglas de manejo de restricciones. Las reglas del primer tipo especifican que, bajo una condición dada, un conjunto de restricciones es equivalente a otro. Las reglas del segundo tipo especifican que, bajo una condición dada, un conjunto de restricciones implica otro. En un lenguaje de programación de lógica de restricciones que soporta reglas de manejo de restricciones, un programador puede usar estas reglas para especificar posibles reescrituras del almacén de restricciones y posibles adiciones de restricciones al mismo. Las siguientes son reglas de ejemplo:
A(X) <=> B(X) | C(X)A(X) ==> B(X) | C(X)
La primera regla dice que, si B(X)la tienda la implica, la restricción A(X)se puede reescribir como C(X). Como ejemplo, N*X>0se puede reescribir como X>0si la tienda implicara que N>0. El símbolo <=>se asemeja a la equivalencia en lógica e indica que la primera restricción es equivalente a la última. En la práctica, esto implica que la primera restricción puede ser reemplazada por la segunda.
En cambio, la segunda regla especifica que la última restricción es una consecuencia de la primera, si la restricción en el medio está implicada por el almacén de restricciones. Como resultado, si A(X)está en el almacén de restricciones y B(X)está incluido en el almacén de restricciones, C(X)se puede agregar al almacén. A diferencia del caso de equivalencia, se trata de una adición y no de un reemplazo: se agrega la nueva restricción pero la anterior permanece.
La equivalencia permite simplificar el almacén de restricciones reemplazando algunas restricciones por otras más simples; en particular, si la tercera restricción en una regla de equivalencia es truey la segunda restricción está implicada, la primera restricción se elimina del almacén de restricciones. La inferencia permite agregar nuevas restricciones, lo que puede llevar a demostrar la inconsistencia del almacén de restricciones y, en general, puede reducir la cantidad de búsqueda necesaria para establecer su satisfacibilidad.
Se pueden utilizar cláusulas de programación lógica junto con reglas de manejo de restricciones para especificar un método para establecer la satisfacibilidad del almacén de restricciones. Se utilizan diferentes cláusulas para implementar las diferentes opciones del método; Las reglas de manejo de restricciones se utilizan para reescribir el almacén de restricciones durante la ejecución. Como ejemplo, se puede implementar el retroceso con propagación unitaria de esta manera. Let holds(L)representa una cláusula proposicional, en la que los literales de la lista Lestán en el mismo orden en que se evalúan. El algoritmo se puede implementar utilizando cláusulas para elegir asignar un literal a verdadero o falso, y reglas de manejo de restricciones para especificar la propagación. Estas reglas especifican que holds([l|L])se puede eliminar si l=truese sigue de la tienda y se puede reescribir como holds(L)si l=falsese sigue desde la tienda. Del mismo modo, holds([l])se puede sustituir por l=true. En este ejemplo, la elección del valor de una variable se implementa mediante cláusulas de programación lógica; sin embargo, se puede codificar en reglas de manejo de restricciones usando una extensión llamada reglas de manejo de restricciones disyuntivas o CHR ∨ .
La estrategia estándar de evaluación de programas lógicos es de arriba hacia abajo y primero en profundidad : a partir del objetivo, se identifican una serie de cláusulas que posiblemente puedan probar el objetivo y se realiza la recursividad sobre los literales de sus cuerpos. Una estrategia alternativa es partir de los hechos y utilizar cláusulas para derivar nuevos hechos; Esta estrategia se llama ascendente . Se considera mejor que el de arriba hacia abajo cuando el objetivo es producir todas las consecuencias de un programa determinado, en lugar de demostrar un objetivo único. En particular, encontrar todas las consecuencias de un programa de la manera estándar de arriba hacia abajo y primero en profundidad puede no terminar mientras termina la estrategia de evaluación de abajo hacia arriba.
La estrategia de evaluación ascendente mantiene el conjunto de hechos demostrados hasta ahora durante la evaluación. Este conjunto está inicialmente vacío. Con cada paso, se derivan nuevos hechos aplicando una cláusula de programa a los hechos existentes y se agregan al conjunto. Por ejemplo, la evaluación ascendente del siguiente programa requiere dos pasos:
A(q).B(X):-A(X).
El conjunto de consecuencias está inicialmente vacío. En el primer paso, A(q)es la única cláusula cuyo cuerpo se puede probar (porque está vacío), y A(q)por tanto se añade al conjunto actual de consecuencias. En el segundo paso, ya A(q)probado, se puede utilizar la segunda cláusula y B(q)se añade a las consecuencias. Como no se puede demostrar ninguna otra consecuencia {A(q),B(q)}, la ejecución termina.
La ventaja de la evaluación ascendente sobre la descendente es que los ciclos de derivaciones no producen un bucle infinito . Esto se debe a que agregar una consecuencia al conjunto actual de consecuencias que ya la contiene no tiene ningún efecto. Como ejemplo, agregar una tercera cláusula al programa anterior genera un ciclo de derivaciones en la evaluación de arriba hacia abajo:
A(q).B(X):-A(X).A(X):-B(X).
Por ejemplo, al evaluar todas las respuestas al objetivo A(X), la estrategia de arriba hacia abajo produciría las siguientes derivaciones:
A(q)A(q):-B(q), B(q):-A(q), A(q)A(q):-B(q), B(q):-A(q), A(q):-B(q), B(q):-A(q), A(q)
En otras palabras, la única consecuencia A(q)se produce primero, pero luego el algoritmo recorre derivaciones que no producen ninguna otra respuesta. En términos más generales, la estrategia de evaluación de arriba hacia abajo puede recorrer posibles derivaciones, posiblemente cuando existan otras.
La estrategia ascendente no tiene el mismo inconveniente, ya que las consecuencias que ya se derivaron no tienen ningún efecto. En el programa anterior, la estrategia ascendente comienza a aumentar A(q)el conjunto de consecuencias; en el segundo paso, B(X):-A(X)se utiliza para derivar B(q); en el tercer paso, los únicos hechos que se pueden derivar de las consecuencias actuales son A(q)y B(q), que sin embargo ya están en el conjunto de consecuencias. Como resultado, el algoritmo se detiene.
En el ejemplo anterior, los únicos hechos utilizados fueron literales básicos. En general, toda cláusula que sólo contenga restricciones en el cuerpo se considera un hecho. Por ejemplo, una cláusula A(X):-X>0,X<10también se considera un hecho. Para esta definición ampliada de hechos, algunos hechos pueden ser equivalentes aunque no sintácticamente iguales. Por ejemplo, A(q)es equivalente a A(X):-X=qy ambos son equivalentes a A(X):-X=Y, Y=q. Para resolver este problema, los hechos se traducen a una forma normal en la que el encabezado contiene una tupla de variables totalmente diferentes; Entonces, dos hechos son equivalentes si sus cuerpos son equivalentes en las variables de la cabeza, es decir, sus conjuntos de soluciones son los mismos cuando se restringen a estas variables.
Como se describió, el enfoque ascendente tiene la ventaja de no considerar las consecuencias que ya se han derivado. Sin embargo, todavía se pueden derivar consecuencias que conllevan las ya derivadas sin ser igual a ninguna de ellas. Como ejemplo, la evaluación ascendente del siguiente programa es infinita:
Un ( 0 ). A ( X ): - X > 0. A ( X ): - X = Y + 1 , A ( Y ).El algoritmo de evaluación ascendente primero deriva que A(X)es cierto para X=0y X>0. En el segundo paso, el primer hecho con la tercera cláusula permite derivar A(1). En el tercer paso, A(2)se deriva, etc. Sin embargo, estos hechos ya están implicados por el hecho de que A(X)es cierto para cualquier no negativo X. Este inconveniente puede superarse comprobando los hechos de vinculación que deben agregarse al conjunto actual de consecuencias. Si la nueva consecuencia ya está incluida en el conjunto, no se le añade. Dado que los hechos se almacenan como cláusulas, posiblemente con "variables locales", la vinculación está restringida a las variables de sus cabezas.
Las versiones concurrentes de programación lógica de restricciones están dirigidas a programar procesos concurrentes en lugar de resolver problemas de satisfacción de restricciones . Los objetivos en la programación de lógica de restricciones se evalúan simultáneamente; Por lo tanto, se programa un proceso concurrente como la evaluación de una meta por parte del intérprete .
Sintácticamente, los programas lógicos de restricciones concurrentes son similares a los programas no concurrentes, con la única excepción de que las cláusulas incluyen guardias , que son restricciones que pueden bloquear la aplicabilidad de la cláusula bajo algunas condiciones. Semánticamente, la programación lógica de restricciones concurrentes difiere de sus versiones no concurrentes porque la evaluación de objetivos tiene como objetivo realizar un proceso concurrente en lugar de encontrar una solución a un problema. En particular, esta diferencia afecta cómo se comporta el intérprete cuando se aplica más de una cláusula: la programación lógica de restricciones no concurrentes prueba recursivamente todas las cláusulas; La programación lógica de restricciones concurrentes elige solo una. Éste 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 no falle toda la evaluación, y una forma particular de equiparar un objetivo y un encabezado de cláusula.
La programación lógica de restricciones se ha aplicado a varios campos, como programación automatizada , [1] inferencia de tipos , [2] ingeniería civil , ingeniería mecánica , verificación de circuitos digitales , control de tráfico aéreo , finanzas y otros. [ cita necesaria ]
La programación lógica de restricciones fue introducida por Jaffar y Lassez en 1987. [3] Generalizaron la observación de que los términos ecuaciones y disecuaciones de Prolog II eran una forma específica de restricciones, y generalizaron esta idea a lenguajes de restricciones arbitrarios. Las primeras implementaciones de este concepto fueron Prolog III, CLP(R) y CHIP . [ cita necesaria ]