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 de lógica de restricciones es un programa lógico que contiene restricciones en el cuerpo de cláusulas. Un ejemplo de una 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 regular. Esta cláusula establece una condición bajo la cual se cumple la declaración: es mayor que cero y tanto 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)
Al igual que en la programación lógica normal, se consulta a los programas sobre la demostrabilidad de un objetivo, que 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 comienza desde el objetivo y escanea recursivamente las cláusulas tratando de demostrar el objetivo. Las restricciones encontradas durante este escaneo se colocan en un conjunto llamado almacén de restricciones . Si se descubre que este conjunto no es satisfacible, el intérprete retrocede e intenta utilizar otras cláusulas para demostrar el objetivo. En la práctica, la satisfacibilidad del almacén de restricciones se puede verificar utilizando un algoritmo incompleto, que no siempre detecta la inconsistencia.
Formalmente, los programas de lógica de restricciones son como los programas de lógica regular, pero el cuerpo de cláusulas puede contener restricciones, además de los literales de programación lógica regular. Por 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 regular, evaluar un objetivo como A(X,1)requiere evaluar el cuerpo de la última cláusula con Y=1. Al igual que en la programación lógica regular, esto a su vez requiere probar el objetivo B(X,1). A diferencia de la programación lógica regular, 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 regular, X>0 no se puede probar a menos que X esté ligado a un término completamente fundamental 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 cumple ni se viola en este punto. En lugar de continuar 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 la 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 se lleva a cabo como lo hace un programa de lógica regular. Sin embargo, las restricciones encontradas durante la evaluación se colocan en un conjunto llamado almacén de restricciones. Como ejemplo, la evaluación del objetivo A(X,1)se lleva a cabo 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 se suma X<0al almacén de restricciones. Esta adición hace que el almacén de restricciones no se pueda satisfacer. Luego, el intérprete retrocede y elimina 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 se puede satisfacer y no queda ningún otro literal por demostrar, 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 denomina objetivo actual; el segundo elemento se denomina almacén de restricciones. El objetivo actual contiene los literales que el intérprete está intentando probar y también puede contener algunas restricciones que está intentando satisfacer; el almacén de restricciones contiene todas las restricciones que el intérprete ha asumido que se pueden satisfacer hasta el momento.
Inicialmente, el objetivo actual es el objetivo y el almacén de restricciones está vacío. El intérprete procede a eliminar el primer elemento del objetivo actual y analizarlo. 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 error. Este análisis puede implicar llamadas recursivas y la adición de nuevos literales al objetivo actual y una nueva restricción 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 satisfacible.
Los detalles del análisis de un literal eliminado del objetivo son los siguientes. Después de haber eliminado este literal del frente del objetivo, 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 núcleo tenga el mismo predicado que el literal; la cláusula se reescribe reemplazando sus variables con nuevas variables (variables que no ocurren en el objetivo): el resultado se llama una variante nueva de la cláusula; el cuerpo de la variante nueva de la cláusula se coloca entonces al frente del objetivo; la igualdad de cada argumento del literal con el correspondiente del núcleo de la variante nueva también se coloca al frente del objetivo.
Durante estas operaciones se realizan algunas comprobaciones. En particular, se comprueba la coherencia del almacén de restricciones cada vez que se le añade una nueva restricción. En principio, siempre que el almacén de restricciones sea insatisfacible, el algoritmo podría dar marcha atrás. Sin embargo, comprobar la insatisfacbilidad en cada paso sería ineficiente. Por este motivo, se puede utilizar en su lugar un verificador de satisfacibilidad incompleta. En la práctica, la satisfacibilidad se comprueba 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 pueden, a veces, pero no siempre, demostrar la insatisfacbilidad de un almacén de restricciones insatisfacible.
El intérprete ha demostrado el objetivo cuando el objetivo actual está vacío y no se detecta que el almacén de restricciones no es 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 tener un valor específico, pero también puede incluir restricciones como las que solo limitan las 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 objetivo/almacén, anotado . Dicho par establece la posibilidad de pasar de un estado a otro . Dicha transición es posible en tres casos posibles:
Una secuencia de transiciones es una derivación. Un objetivo G puede probarse 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 para reemplazar literales. En otras palabras, un objetivo se prueba bajo esta semántica si existe una secuencia de elecciones de literales y cláusulas, entre las posiblemente muchas, que conducen a un objetivo vacío y un almacén satisfacible.
Los intérpretes actuales procesan los elementos de la meta en un orden LIFO : los elementos se agregan al principio y se procesan desde el principio. También eligen la cláusula de la segunda regla según el orden en que se escriben y reescriben el almacén de restricciones cuando se modifica.
El tercer tipo posible de transición es un reemplazo del almacén de restricciones por uno equivalente. Este reemplazo se limita a aquellos que se realizan 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 solo para el tipo de restricciones utilizadas, sino también para el 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 simple de resolver. Si el almacén de restricciones es insatisfactorio, esta simplificación puede detectar esta insatisfacción algunas veces, pero no siempre.
El resultado de evaluar un objetivo frente a un programa de lógica de restricciones se define si el objetivo se demuestra. En este caso, existe una derivación del par inicial a un par donde el objetivo está vacío. 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 suponen 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 suele denotarse de forma compacta mediante : esta es una forma abreviada de las restricciones . Una variante común de la semántica para la programación lógica de restricciones agrega directamente al almacén de restricciones en lugar de al objetivo.
Se utilizan distintas definiciones de términos, lo que genera distintos tipos de programación lógica de restricciones: sobre árboles, números reales o dominios finitos. Un tipo de restricción que siempre está presente es la igualdad de términos. Tales restricciones son necesarias porque el intérprete añade t1=t2al objetivo siempre que P(...t1...)se reemplaza un literal con el cuerpo de una cláusula nueva variante cuyo núcleo es P(...t2...).
La programación lógica de restricciones con términos de árbol emula la programación lógica regular al almacenar sustituciones como restricciones en el almacén de restricciones. Los términos son variables, constantes y símbolos de función aplicados a otros términos. Las únicas restricciones consideradas son las igualdades y desigualdades entre términos. La igualdad es particularmente importante, ya que las restricciones como t1=t2las genera a menudo el intérprete. Las restricciones de igualdad en 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 por la igualdad de subtérminos por pares. Si los términos están compuestos por diferentes símbolos de función o el mismo funtor 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 a 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 puede eliminarse como siempre satisfecha.
En esta forma de satisfacción de restricciones, los valores de las variables son términos.
La programación lógica con 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 números reales, que pueden incluir variables. En este caso, cada variable solo puede tomar un número real como valor.
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. A modo de ejemplo, si el primer literal del objetivo actual es A(X+1)y el intérprete ha elegido una cláusula que es A(Y-1):-Y=1después de reescribir es variables, las restricciones añadidas al objetivo actual son X+1=Y-1y . Las reglas de simplificación utilizadas para los símbolos de función obviamente no se utilizan: no es insatisfactible solo porque la primera expresión se construye utilizando y la segunda utilizando .X+1=Y-1+-
Los símbolos de números reales y funciones se pueden combinar, lo que da lugar a términos que son expresiones sobre números reales y símbolos de funciones 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 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 se componen de números reales y términos . En otras palabras, una variable puede tomar un número real como valor, mientras que otra toma un término.
La igualdad de dos términos se puede simplificar utilizando 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 número de subtérminos, su restricción de igualdad se puede reemplazar por 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 utilizando 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 una propagación de restricciones para imponer una forma de consistencia local , y estas operaciones pueden reducir el dominio de las variables. Si el dominio de una variable se vacía, el almacén de restricciones es inconsistente y el algoritmo retrocede. Si el dominio de una variable se convierte en un singleton , se le puede asignar a la variable el valor único en su dominio. Las formas de consistencia que se imponen típicamente son consistencia de arco , consistencia de hiperarco y consistencia de límite . 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 los dominios de los números reales, los funtores se pueden utilizar 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 se ha especificado como un conjunto de números enteros o constantes.
El almacén de restricciones contiene las restricciones que actualmente se suponen satisfacibles. Se puede considerar cuál es la sustitución actual para la programación lógica regular. Cuando solo se permiten términos de árbol, el almacén de restricciones contiene restricciones en la forma t1=t2; estas restricciones se simplifican mediante la unificación, lo que da como resultado restricciones de la forma variable=term; dichas restricciones son equivalentes a una sustitución.
Sin embargo, el almacén de restricciones también puede contener restricciones en la forma , 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 del dominio como , etc.!=X+2=Y/2
El almacén de restricciones extiende el concepto de sustitución actual de dos maneras. En primer lugar, no solo contiene 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, no solo contiene 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 de dominio pueden llegar al almacén de restricciones tanto desde el cuerpo de una cláusula como desde la equiparación de un literal con el encabezado de una cláusula: por ejemplo, si el intérprete reescribe el literal A(X+2)con una cláusula cuyo encabezado de variante nueva es A(Y/2), la restricción X+2=Y/2se agrega al almacén de restricciones. Si una variable aparece en una expresión de dominio real o finito, solo puede tomar un valor en los dominios reales o finito. Dicha variable no puede tomar un término formado por un funtor aplicado a otros términos como valor. El almacén de restricciones es insatisfactorio si una variable está obligada a tomar tanto un valor del dominio específico como un funtor aplicado a 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 considerado y de las restricciones. Por ejemplo, se utiliza la unificación para las igualdades de árboles finitos, la eliminación de variables para ecuaciones polinómicas sobre números reales y la propagación de restricciones para imponer una forma de consistencia local para dominios finitos. Estas operaciones tienen como objetivo hacer que sea más fácil verificar la satisfacibilidad del almacén de restricciones 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 del almacén cada vez que realiza 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 regrese a un estado anterior. En particular, uno puede simplemente guardar los cambios en el almacén de restricciones realizados entre dos puntos de elección, incluidos los cambios realizados en las restricciones antiguas. Esto se puede hacer simplemente guardando el valor anterior de las restricciones que se han modificado; este método se llama trailing . 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 semantic backtracking , 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 sobre dominios finitos para comprobar la satisfacibilidad total o parcial del almacén de restricciones y para encontrar una asignación satisfactoria. Un literal de etiquetado tiene la forma labeling([variables]), donde el argumento es una lista de variables sobre dominios finitos. Siempre que el intérprete evalúa un literal de este tipo, realiza una búsqueda sobre 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 aplica una forma de consistencia local en ella. Esta operación puede no detectar inconsistencias incluso si el almacén de restricciones no es satisfacible. Un literal de etiquetado sobre un conjunto de variables aplica una verificación de satisfacibilidad de las restricciones sobre estas variables. Como resultado, el uso de todas las variables mencionadas en el almacén de restricciones da como resultado la verificación de la satisfacibilidad del almacén.
El segundo uso del literal de etiquetado es determinar una evaluación de las variables que satisface 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 consistencia local reduce el dominio de una variable a un único valor. Un literal de etiquetado sobre algunas variables obliga a que se evalúen estas variables. En otras palabras, después de que se ha considerado el literal de etiquetado, se asigna un valor a todas las variables.
Por lo general, los programas de lógica de restricciones se escriben de tal manera que los literales de etiquetado se evalúan solo después de que se hayan acumulado tantas restricciones como sea posible en el almacén de restricciones. Esto se debe a que los literales de etiquetado imponen 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 se resuelve típicamente mediante un programa de lógica 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. labeling(X')Luego se evalúa el literal, lo que obliga a buscar una solución en el 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 dado puede ser reformulado para mejorar su eficiencia. Una primera regla es que los literales de etiquetado deben colocarse después de que se acumulen tantas restricciones sobre los literales etiquetados como sea posible en el almacén de restricciones. 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 solo cuando la restricción ya está en el almacén de restricciones. Como resultado, la búsqueda solo devuelve soluciones que son consistentes con ella, aprovechando el hecho de que las 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. Nuevamente, y son en principio equivalentes. Sin embargo, la primera 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 almacén 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 provocar una 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 ocurrencia de B(X). Por ejemplo, A(X,Y):-B(X),C(X)fallará en el objetivo A(-2,Z), pero esto solo se descubre durante la evaluación del subobjetivo 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 sucede antes de que comience la evaluación de .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, posteriormente, se incorporaron a la programación lógica. Existen 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 lógica de restricciones que admita 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)se implica en el almacén, la restricción A(X)se puede reescribir como C(X). Por ejemplo, N*X>0se puede reescribir como X>0si el almacén 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 se puede reemplazar por la última.
La segunda regla, en cambio, especifica que la última restricción es una consecuencia de la primera, si la restricción intermedia está implícita en el almacén de restricciones. Como resultado, si A(X)está en el almacén de restricciones y B(X)está implícita en el almacén de restricciones, entonces C(X)se puede añadir al almacén. A diferencia del caso de equivalencia, se trata de una adición y no de un reemplazo: se añade la nueva restricción, pero la antigua 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 true, y la segunda restricción está implícita, la primera restricción se elimina del almacén de restricciones. La inferencia permite la adición de 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.
Las cláusulas de programación lógica junto con las reglas de manejo de restricciones se pueden utilizar 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 de unidades 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 la elección de 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=truesigue del almacén, y se puede reescribir como holds(L)si l=falsesigue del almacén. De manera similar, holds([l])se puede reemplazar por l=true. En este ejemplo, la elección del valor de una variable se implementa utilizando cláusulas de programación lógica; sin embargo, se puede codificar en reglas de manejo de restricciones utilizando 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 en profundidad : a partir del objetivo, se identifican varias cláusulas que posiblemente puedan probar el objetivo y se realiza una recursión sobre los literales de sus cuerpos. Una estrategia alternativa es comenzar a partir de los hechos y usar cláusulas para derivar nuevos hechos; esta estrategia se llama de abajo hacia arriba . Se considera mejor que la de arriba hacia abajo cuando el objetivo es producir todas las consecuencias de un programa dado, en lugar de probar un solo objetivo. En particular, encontrar todas las consecuencias de un programa en la forma estándar de arriba hacia abajo y en profundidad puede no terminar mientras que la estrategia de evaluación de abajo hacia arriba termina.
La estrategia de evaluación ascendente mantiene el conjunto de hechos probados hasta el momento durante la evaluación. Este conjunto está inicialmente vacío. Con cada paso, se derivan nuevos hechos aplicando una cláusula del 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 puede probarse (porque está vacío) y, A(q)por lo tanto, se agrega al conjunto actual de consecuencias. En el segundo paso, dado que A(q)se prueba , se puede usar la segunda cláusula y B(q)se agrega a las consecuencias. Dado que no se puede probar ninguna otra consecuencia a partir de {A(q),B(q)}, la ejecución finaliza.
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. A modo de ejemplo, agregar una tercera cláusula al programa anterior genera un ciclo de derivaciones en la evaluación descendente:
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, primero se produce la única consecuencia A(q), pero luego el algoritmo recorre en ciclos las derivaciones que no producen ninguna otra respuesta. En términos más generales, la estrategia de evaluación descendente puede recorrer en ciclos las posibles derivaciones, posiblemente cuando existan otras.
La estrategia ascendente no tiene el mismo inconveniente, ya que las consecuencias que ya se han derivado no tienen ningún efecto. En el programa anterior, la estrategia ascendente comienza a agregar A(q)al 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, cada cláusula que solo contiene 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 extendida de hechos, algunos hechos pueden ser equivalentes aunque no sean 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 núcleo contiene una tupla de variables totalmente diferentes; dos hechos son entonces equivalentes si sus cuerpos son equivalentes en las variables del núcleo, es decir, sus conjuntos de soluciones son los mismos cuando se restringen a estas variables.
Como se ha descrito, el enfoque ascendente tiene la ventaja de no considerar las consecuencias que ya se han derivado. Sin embargo, aún puede derivar consecuencias que están implícitas en las ya derivadas, aunque no sean iguales a ninguna de ellas. A modo de 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 verdadero para X=0y X>0. En el segundo paso, el primer hecho con la tercera cláusula permite la derivación de 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 verdadero para cualquier no negativo X. Este inconveniente se puede superar comprobando los hechos de implicación que se van a añadir al conjunto actual de consecuencias. Si la nueva consecuencia ya está implicada por el conjunto, no se añade a él. Dado que los hechos se almacenan como cláusulas, posiblemente con "variables locales", la implicación está restringida sobre las variables de sus cabezas.
Las versiones concurrentes de la programación lógica de restricciones tienen como objetivo programar procesos concurrentes en lugar de resolver problemas de satisfacción de restricciones . Los objetivos en la programación lógica de 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 guardias , 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. Más notablemente, esta diferencia afecta cómo se comporta el intérprete cuando más de una cláusula es aplicable: 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.
La programación lógica de restricciones se ha aplicado a varios campos, como la programación automatizada , [1] la inferencia de tipos , [2] la ingeniería civil , la ingeniería mecánica , la verificación de circuitos digitales , el control del tráfico aéreo , las finanzas y otros. [ cita requerida ]
La programación lógica con restricciones fue introducida por Jaffar y Lassez en 1987. [3] Ellos generalizaron la observación de que las ecuaciones y disecuaciones de Prolog II eran una forma específica de restricciones, y generalizaron esta idea a lenguajes con restricciones arbitrarias. Las primeras implementaciones de este concepto fueron Prolog III, CLP(R) y CHIP . [ cita requerida ]