Programación lógica de restricciones

Paradigmas de programación
Acción Orientado al agente Orientado a matrices Basado en autómatas Computación concurrente Programación relativista Basado en datos Declarativo (contraste: imperativo ) Funcional Lógica funcional Puramente funcional Lógica Lógica abductiva Conjunto de respuestas Lógica concurrente Lógica funcional Lógica inductiva Restricción Lógica de restricción Lógica de restricción concurrente Flujo de datos Basado en flujo Reactivo Reactivo funcional Ontología Diferenciable Dinámico / scripting Evento conducido Nivel de función (contraste: nivel de valor ) Estilo sin puntos Concatenativo Genérico Imperativo (contraste: declarativo ) Procesal Orientado a objetos Polimórfico Intencional Orientado al lenguaje Específico de dominio Alfabetizado Programación en lenguaje natural Metaprogramación Automático Programación inductiva reflexivo Orientado a atributos Macro Modelo No estructurado (contraste: estructurado ) Formación No determinista Computación paralela Orientado al proceso Probabilístico Cuántico Teórico de conjuntos Basado en pila Estructurado (contraste: no estructurado ) Estructurado en bloque Simultaneidad estructurada Orientado a objetos Basado en actores Basado en clases Concurrente Basado en prototipos Por separación de preocupaciones : Orientado a aspectos Orientado a roles Orientado al sujeto Recursivo Simbólico Nivel de valor (contraste: nivel de función )
v t mi

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 restricción es un programa de lógica que contiene restricciones en el cuerpo de las cláusulas. Un ejemplo de una cláusula que incluye una restricción es . En esta cláusula, hay 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 el enunciado : 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)

Al igual que en la programación lógica normal, se consulta a los programas sobre la probabilidad de un objetivo, que puede contener restricciones además de literales. Una prueba para un objetivo se compone de cláusulas cuyos cuerpos son restricciones satisfactorias y literales que, a su vez, pueden probarse utilizando otras cláusulas. La ejecución la realiza un intérprete, que parte de la meta y escanea recursivamente las cláusulas tratando de probar la meta. Las restricciones encontradas durante este escaneo se colocan en un conjunto llamado almacén de restricciones . Si se descubre que este conjunto no es satisfactorio, el intérprete retrocede , intentando utilizar otras cláusulas para demostrar el objetivo. En la práctica, la satisfacción del almacén de restricciones puede comprobarse mediante un algoritmo incompleto, que no siempre detecta inconsistencias.

Resumen

Formalmente, los programas de lógica de restricción son como programas de lógica regular, pero el cuerpo de las cláusulas puede contener restricciones, además de los literales de programación lógica regular. Como ejemplo, X>0es una restricción y se incluye en la última cláusula del siguiente programa de lógica de restricción.

B ( X , 1 ): -  X < 0. B ( X , Y ): -  X = 1 ,  Y > 0. A ( X , Y ): -  X > 0 ,  B ( X , Y ).

Como 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. Como en la programación lógica regular, esto a su vez requiere probar el objetivo B(X,1). Contrariamente a la programación lógica regular, esto también requiere que se satisfaga una restricción:, X>0la 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é vinculado a un término completamente básico y la ejecución del el 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 después, el intérprete almacena la restricción X>0y luego procede 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 B(X,1)a que concluya la evaluación de .

En general, la evaluación de un programa de lógica de restricción procede como lo hace un programa de lógica regular. Sin embargo, las restricciones encontradas durante la evaluación se colocan en un conjunto llamado almacenamiento de restricciones. Como ejemplo, la evaluación del objetivo A(X,1)procede evaluando el cuerpo de la primera cláusula con Y=1; esta evaluación se suma X>0a la reserva de restricciones y requiere B(X,1)que se pruebe 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 la restricción de almacenamiento sea insatisfactoria. El intérprete luego retrocede, eliminando la última adición del almacén de restricciones. La evaluación de la segunda cláusula agrega X=1yY>0al almacén de restricciones. Dado que el almacén de restricciones es satisfactorio y no queda ningún otro literal por probar, el intérprete se detiene con la solución X=1, Y=1.

Semántica

La semántica de los programas de lógica de restricción 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 meta actual; el segundo elemento se llama almacén de restricciones. El objetivo actual contiene los literales que el intérprete está tratando de probar y también puede contener algunas restricciones que está tratando de satisfacer; el almacén de restricciones contiene todas las restricciones que el intérprete ha asumido que son satisfactorias hasta ahora.${\displaystyle \langle G,S\rangle }$

Inicialmente, el objetivo actual es el objetivo y el almacén de restricciones está vacío. El intérprete procede quitando 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 una nueva restricción al almacén de restricciones. El intérprete retrocede si se genera una falla. Se genera una terminación exitosa cuando el objetivo actual está vacío y el almacén de restricciones es satisfactorio.

Los detalles del análisis de un literal eliminado de la meta 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 encabezado tenga el mismo predicado del literal; la cláusula se reescribe reemplazando sus variables con nuevas variables (variables que no ocurren en el objetivo): el resultado se llama una nueva variante de la cláusula; el cuerpo de la nueva variante de la cláusula se coloca delante de la portería; la igualdad de cada argumento del literal con el correspondiente del nuevo encabezado de variante también se coloca delante de la meta.

Algunas comprobaciones se realizan durante estas operaciones. 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 almacenamiento de restricciones no sea satisfactorio, el algoritmo podría retroceder. Sin embargo, comprobar la insatisfacción en cada paso sería ineficaz. Por esta razón, se puede utilizar en su lugar un verificador de satisfacción incompleta. En la práctica, la satisfacibilidad se verifica utilizando métodos que simplifican el almacenamiento de restricciones, es decir, lo reescriben en una forma equivalente pero más simple de resolver. A veces, pero no siempre, estos métodos pueden resultar insatisfactorios en un almacén de restricciones insatisfactorio.

El intérprete ha probado 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.${\displaystyle X=2}$${\displaystyle X>2}$

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 / tienda, anotó . Tal par establece la posibilidad de ir de un estado a otro . Tal transición es posible en tres casos posibles:${\displaystyle \langle G,S\rangle \rightarrow \langle G',S'\rangle }$${\displaystyle \langle G,S\rangle }$${\displaystyle \langle G',S'\rangle }$

• un elemento de G es una restricción C , y ; en otras palabras, una restricción se puede mover del objetivo al almacén de restricciones${\displaystyle G'=G\backslash \{C\}}$${\displaystyle S'=S\cup \{C\}}$
• un elemento de G es un literal , existe una cláusula que, reescrita usando nuevas variables, es , es G con reemplazado por , y ; en otras palabras, un literal puede ser reemplazado por el cuerpo de una variante nueva de una cláusula que tiene el mismo predicado en el encabezado, agregando el cuerpo de la variante fresca y las igualdad de términos anteriores a la meta.${\displaystyle L(t_{1},\ldots ,t_{n})}$${\displaystyle L(t_{1}',\ldots ,t_{n}'):-B}$${\displaystyle G'}$${\displaystyle L(t_{1},\ldots ,t_{n})}$${\displaystyle t_{1}=t_{1}',\ldots ,t_{n}=t_{n}',B}$${\displaystyle S'=S}$
• S y son equivalentes según la semántica de restricción específica${\displaystyle S'}$

Una secuencia de transiciones es una derivación. Se puede demostrar un objetivo G si existe una derivación de a para algún almacén de restricciones S satisfactorio . 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 los 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 satisfactorio.${\displaystyle \langle G,\emptyset \rangle }$${\displaystyle \langle \emptyset ,S\rangle }$

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 de acuerdo con el orden en que están escritas y reescriben el almacén de restricciones cuando se modifica.

El tercer tipo de transición posible es la sustitución del almacén de restricciones por uno equivalente. Este reemplazo se limita a los 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 más simple de resolver. Si el almacén de restricciones no es satisfactorio, esta simplificación puede detectar esta insatisfacción a veces, pero no siempre.

El resultado de evaluar un objetivo frente a un programa de lógica de restricción se define si se demuestra el objetivo. 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 términos de dos literales a menudo se denota de forma compacta por : esta es una forma abreviada de las restricciones . Una variante común de la semántica para la programación lógica de restricciones se suma directamente al almacén de restricciones en lugar de al objetivo.${\displaystyle L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')}$${\displaystyle t_{1}=t_{1}',\ldots ,t_{n}=t_{n}'}$${\displaystyle L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')}$

Términos y condiciones

Se utilizan diferentes definiciones de términos, lo que genera 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. Tales restricciones son necesarias porque el intérprete agrega t1=t2al objetivo cada vez que un literal P(...t1...)se reemplaza con el cuerpo de una variante nueva de cláusula cuyo encabezado es P(...t2...).

Términos del árbol

La programación lógica de restricciones con términos de árbol emula la programación lógica regular almacenando 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 t1=t2el intérprete suele generar limitaciones como estas. Las restricciones de igualdad en los términos se pueden simplificar, es decir, se resuelven 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 subtermos también es el mismo, esta restricción se puede reemplazar con la igualdad de los subterms por pares. Si los términos están compuestos por diferentes símbolos de función o el mismo funtor pero en diferente número de términos, la restricción es insatisfactoria.

Si uno de los dos términos es una variable, el único valor permitido que la variable puede tomar es el otro término. Como resultado, el otro término puede reemplazar la variable en el objetivo actual y el almacén de restricciones, por lo que prácticamente quita la variable de consideración. En el caso particular de igualdad de una variable consigo misma, la restricción se puede eliminar como siempre se cumple.

En esta forma de satisfacción de restricciones, los valores de las variables son términos.

Reales

La programación de lógica de restricción con números reales usa expresiones reales como términos. Cuando no se utilizan símbolos de función, los términos son expresiones sobre reales, posiblemente incluyendo 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 una especie de restricción que siempre está presente, ya que el intérprete genera igualdad de términos durante la ejecución. Por 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 las variables, las restricciones agregadas al objetivo actual son X+1=Y-1y . Las reglas de simplificación usadas para los símbolos de función obviamente no se usan: no es insatisfactorio solo porque la primera expresión se construye usando y la segunda usando .${\displaystyle Y=1}$X+1=Y-1+-

Los símbolos reales y de función se pueden combinar, dando 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, constantes (símbolos de función cero-aridad) y 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 varían sobre números y términos reales . 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 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 subterráneos, su restricción de igualdad se puede reemplazar con la igualdad de subtermos.

Dominios finitos

Ver también: problema de satisfacción de restricciones

La tercera clase de restricciones utilizadas en la programación lógica de restricciones es la de los 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, también se puede escribir la declaración de dominio anterior X::[1,2,3,4,5]. Esta segunda forma de especificar un dominio permite dominios que no están compuestos por números enteros, comoX::[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 usando 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 coherencia 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 , a la variable se le puede asignar el valor único en su dominio. Las formas de coherencia que normalmente se aplican son la coherencia del arco , la coherencia del hiper-arco y la coherencia del 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 reales, los functores se pueden usar con dominios de 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 enteros o constantes.

La tienda de restricciones

El almacén de restricciones contiene las restricciones que actualmente se asumen que son satisfactorias. Se puede considerar cuál es la sustitución actual de la programación lógica regular. Cuando solo se permiten términos de árbol, el almacén de restricciones contiene restricciones en el formulario t1=t2; estas restricciones se simplifican por la unificación, lo que resulta en 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 t1!=t2, si !=se permite la 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 formas. Primero, no solo contiene las restricciones derivadas de equiparar un literal con el encabezado de una variante nueva 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 en el lenguaje de restricciones considerado. Si bien el resultado de una evaluación exitosa de un programa de lógica regular es la sustitución final, el resultado de un programa de lógica de restricción es el almacén de restricción final, que puede contener una restricción de la forma variable = valor, pero en general puede contener restricciones arbitrarias.

Las restricciones específicas del dominio pueden llegar al almacén de restricciones tanto del cuerpo de una cláusula como de 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 encabezado de variante nuevo 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 los reales o en el dominio finito. Tal variable no puede tomar como valor un término compuesto por un funtor 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 funtor 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 consideradas. Por ejemplo, la unificación se usa para igualaciones de árboles finitos, eliminación de variables para ecuaciones polinómicas sobre reales, propagación de restricciones para imponer una forma de consistencia local para dominios finitos. Estas operaciones tienen como objetivo hacer que el almacenamiento de restricciones sea más simple 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 retrocede. 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, se pueden guardar los cambios en el almacén de restricciones realizados entre dos puntos de elección, incluidos los cambios realizados en las restricciones anteriores. 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 consiste en 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 denomina retroceso semántico , porque la semántica del cambio se guarda en lugar de solo la versión anterior de las restricciones.

Etiquetado

Los literales de etiquetado se utilizan en variables sobre dominios finitos para comprobar la satisfacibilidad o satisfacibilidad 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 tal literal, 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 para comprobar la satisfacibilidad real o la satisfacibilidad parcial del almacén de restricciones. Cuando el intérprete agrega una restricción al almacén de restricciones, solo aplica una forma de coherencia local en él. Es posible que esta operación no detecte incoherencias 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 restricción da como resultado la verificación de la satisfacción de la tienda.

El segundo uso del literal de etiquetado es determinar realmente una evaluación de las variables que satisfaga la restricción de almacenamiento. Sin el literal de etiquetado, a las variables se les asignan valores solo cuando el almacén de restricciones contiene una restricción del formulario 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 que se ha considerado el literal de etiquetado, a todas las variables se les asigna un valor.

Normalmente, los programas de lógica de restricción 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 normalmente 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 variante nueva 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. A labeling(X')continuación, se evalúa el literal , 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.

Reformulaciones del programa

Un programa de lógica de restricción dado puede reformularse para mejorar su eficiencia. Una primera regla es que los literales de etiquetado deben colocarse después de que se acumulen tantas restricciones en los literales etiquetados 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 está en un almacén de restricciones que no contiene la restricción . Como resultado, puede generar soluciones, comoA(X):-labeling(X),X>0A(X):-X>0,labeling(X)X>0X=-1, 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 coherentes con ella, aprovechando el hecho de que las restricciones adicionales reducen el espacio de búsqueda.

Una segunda reformulación que puede aumentar la eficiencia es colocar restricciones antes que los literales en el cuerpo de las cláusulas. De nuevo, y en principio son 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 de forma recursiva 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 de X, el programador puede agregar X>0antes de que ocurra 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 subobjetiva B(X). Por otro lado, si la cláusula anterior es reemplazada por , el intérprete retrocede tan pronto como la restricciónA(X,Y):-X>0,A(X),B(X)X>0se agrega al almacén de restricciones, lo que ocurre antes de que comience la evaluación de B(X)even.

Reglas de manejo de restricciones

Las reglas de manejo de restricciones se definieron inicialmente como un formalismo independiente para especificar solucionadores de restricciones, y luego se integraron en 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 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)la tienda lo exige, la restricción A(X)se puede reescribir como C(X). Como ejemplo, N*X>0se puede reescribir como X>0si la tienda lo implicara N>0. El símbolo se <=>parece a la equivalencia en lógica y dice que la primera restricción es equivalente a la última. En la práctica, esto implica que la primera restricción puede reemplazarse por la última.

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 la tienda de restricción y B(X)está vinculado por la tienda de restricción, entonces C(X)se puede agregar a la tienda. A diferencia del caso de equivalencia, esto es una adición y no un reemplazo: la nueva restricción se agrega pero la anterior permanece.

La equivalencia permite simplificar el almacenamiento 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á implicada, la primera restricción se elimina del almacén de restricciones. La inferencia permite la adición de nuevas restricciones, lo que puede conducir a probar la inconsistencia del almacenamiento 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 capacidad de satisfacción 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 la 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 usando cláusulas para la opció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 sil=truesigue de la tienda, y se puede reescribir como holds(L)si fuera l=falsede la tienda. Del mismo modo, 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 usando una extensión llamada reglas de manejo de restricciones disyuntivas o CHR ^∨ .

Evaluación ascendente

La estrategia estándar de evaluación de los programas lógicos es de arriba hacia abajo y 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 de abajo hacia arriba . 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 único objetivo. En particular, la determinación de todas las consecuencias de un programa en la forma estándar de arriba hacia abajo y en profundidad puede no terminar mientras finaliza la estrategia de evaluación de abajo hacia arriba .

La estrategia de evaluación de abajo hacia arriba mantiene el conjunto de hechos probados 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 de abajo hacia arriba 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 lo tanto, se agrega al conjunto actual de consecuencias. En el segundo paso, dado que A(q)está probado, se puede utilizar la segunda cláusula y B(q)se agrega a las consecuencias. Dado que no se puede probar 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 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, la única consecuencia A(q)se produce primero, pero luego el algoritmo realiza un ciclo sobre derivaciones que no producen ninguna otra respuesta. De manera más general, la estrategia de evaluación de arriba hacia abajo puede alternar entre posibles derivaciones, posiblemente cuando existen otras.

La estrategia de abajo hacia arriba no tiene el mismo inconveniente, ya que las consecuencias que ya se derivaron no tienen efecto. En el programa anterior, la estrategia de abajo hacia arriba comienza a sumarse A(q)al conjunto de consecuencias; en el segundo paso, B(X):-A(X)se usa para derivar B(q); en el tercer paso, los únicos hechos que pueden derivarse 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 también A(X):-X>0,X<10se considera un hecho. Para esta definición ampliada de hechos, algunos hechos pueden ser equivalentes pero no iguales sintácticamente. 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; dos hechos son entonces 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 de abajo hacia arriba tiene la ventaja de no considerar las consecuencias que ya se han derivado. Sin embargo, aún puede derivar consecuencias que conlleven las ya derivadas sin ser iguales a ninguna de ellas. Como ejemplo, la evaluación de abajo hacia arriba del siguiente programa es infinita:

A ( 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 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 cierto para cualquier no negativo X. Este inconveniente puede superarse comprobando los hechos de implicación que deban añadirse al conjunto actual de consecuencias. Si la nueva consecuencia ya está implícita en el conjunto, no se le agrega. Dado que los hechos se almacenan como cláusulas, posiblemente con "variables locales", la vinculación se restringe a las variables de sus cabezas.

Programación de lógica de restricción concurrente

Artículo principal: Programación lógica de restricciones concurrentes

Las versiones concurrentes de la programación lógica de restricciones están destinadas a programar procesos concurrentes en lugar de 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 lo 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, con la única excepción de 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 intencionadadel 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 demostrar mientras no falle toda la evaluación, y una forma particular de equiparar un objetivo y un encabezado de cláusula.

Aplicaciones

La programación de lógica de restricción se ha aplicado a varios campos, como la programación automatizada , ^[1] inferencia de tipo , ^[2] ingeniería civil , ingeniería mecánica , verificación de circuitos digitales , control de tráfico aéreo , finanzas y otros. ^{[ cita requerida ]}

Historia

La programación lógica de restricciones fue introducida por Jaffar y Lassez en 1987. ^[3] Generalizaron la observación de que el término ecuaciones y desecuaciones 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 requerida ]}

Ver también

• BPrólogo
• BNR Prolog (también conocido como CLP (BNR))
• Ciao
• CLP (R)
• Distribuido Oz Mozart
• Eclipse
• Prólogo GNU
• SWI-Prolog

Referencias

• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 1-55860-890-7. ISBN  1-55860-890-7
• Apt, Krzysztof (2003). Principios de la programación de restricciones . Prensa de la Universidad de Cambridge. ISBN 0-521-82583-0. ISBN  0-521-82583-0
• 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. 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 .
• Colmerauer, Alain (1987). "Abriendo el Universo Prolog III". Byte . Agosto.

Referencias

1. Abdennadher, Slim y Hans Schlenker. " Programación de enfermería mediante programación lógica de restricciones ". AAAI / IAAI. 1999.
2. Michaylov, Spiro y Frank Pfenning. " Programación lógica de orden superior como programación lógica de restricción ". PPCP. Vol. 93. 1993.
3. Jaffar, Joxan y JL. Lassez. " Programación lógica de restricciones ". Actas del 14º simposio ACM SIGACT-SIGPLAN sobre Principios de lenguajes de programación. ACM, 1987.