La programación lógica es un paradigma de programación , bases de datos y representación del conocimiento basado en la lógica formal . Un programa lógico es un conjunto de oraciones en forma lógica que representan el conocimiento sobre algún dominio de problema. La computación se realiza aplicando razonamiento lógico a ese conocimiento, para resolver problemas en el dominio. Las principales familias de lenguajes de programación lógica incluyen Prolog , Answer Set Programming (ASP) y Datalog . En todos estos idiomas, las reglas están escritas en forma de cláusulas :
A :- B1, ..., Bn.y se leen como oraciones declarativas en forma lógica:
A if B1 and ... and Bn.Ase llama cabeza de la regla, , ..., se llama cuerpo y se llaman literales o condiciones. Cuando n = 0, la regla se llama hecho y se escribe en forma simplificada:B1BnBi
A.Las consultas (u objetivos) tienen la misma sintaxis que los cuerpos de reglas y comúnmente se escriben en la forma:
?- B1, ..., Bn.En el caso más simple de cláusulas de Horn (o cláusulas "definidas"), todas las A, B 1 , ..., B n son fórmulas atómicas de la forma p(t 1 ,..., t m ), donde p es un símbolo predicado que nombra una relación, como "maternidad", y los t i son términos que nombran objetos (o individuos). Los términos incluyen tanto símbolos constantes, como "charles", como variables, como X, que comienzan con una letra mayúscula.
Considere, por ejemplo, el siguiente programa de cláusula Horn:
madre_niño ( elizabeth , charles ). padre_hijo ( charles , william ). padre_hijo ( charles , harry ). padre_hijo ( X , Y ) : - madre_hijo ( X , Y ). padre_hijo ( X , Y ) : - padre_hijo ( X , Y ). abuelo_hijo ( X , Y ) : - padre_hijo ( X , Z ), padre_hijo ( Z , Y ).Dada una consulta, el programa produce respuestas. Por ejemplo, para una consulta ?- parent_child(X, william), la única respuesta es
X = CarlosSe pueden realizar varias consultas. Por ejemplo, se puede consultar al programa tanto para generar abuelos como para generar nietos. Incluso se puede utilizar para generar todos los pares de nietos y abuelos, o simplemente para comprobar si un par determinado es tal par:
abuelo_hijo ( X , william ). X = Isabel?- abuelo_niño ( elizabeth , Y ). Y = Guillermo ; Y = Harry .?- abuelo_hijo ( X , Y ). X = Isabel Y = Guillermo ; X = Elizabeth Y = Harry .?- abuelo_niño ( william , harry ). ¿no ? - abuelo_niño ( elizabeth , harry ). SíAunque los programas lógicos de cláusulas de Horn son completos de Turing , [1] [2] para la mayoría de las aplicaciones prácticas, los programas de cláusulas de Horn deben extenderse a programas lógicos "normales" con condiciones negativas. Por ejemplo, la definición de hermano usa una condición negativa, donde el predicado = está definido por la cláusula X = X:
hermano ( X , Y ) : - parent_child ( Z , X ), parent_child ( Z , Y ), no ( X = Y ).Los lenguajes de programación lógica que incluyen condiciones negativas tienen las capacidades de representación del conocimiento de una lógica no monótona .
En ASP y Datalog los programas lógicos tienen sólo una lectura declarativa y su ejecución se realiza mediante un procedimiento de prueba o generador de modelos cuyo comportamiento no debe ser controlado por el programador. Sin embargo, en la familia de lenguajes Prolog, los programas lógicos también tienen una interpretación procedimental como procedimientos de reducción de objetivos. Desde este punto de vista, la cláusula A :- B 1 ,...,B n se entiende como:
A, resolver , y ... y resolver .B1BnLas condiciones negativas en los cuerpos de las cláusulas también tienen una interpretación procesal, conocida como negación como fracaso : se considera que un literal negativo not Bse cumple si y sólo si el literal positivo Bno se cumple.
Gran parte de la investigación en el campo de la programación lógica se ha centrado en intentar desarrollar una semántica lógica para la negación como fracaso y en desarrollar otras semánticas y otras implementaciones para la negación. Estos desarrollos han sido importantes, a su vez, para apoyar el desarrollo de métodos formales para la verificación y transformación de programas basados en la lógica .
El uso de la lógica matemática para representar y ejecutar programas informáticos también es una característica del cálculo lambda , desarrollado por Alonzo Church en la década de 1930. Sin embargo, la primera propuesta para utilizar la forma clausal de lógica para representar programas de computadora fue realizada por Cordell Green . [3] Esto utilizó una axiomatización de un subconjunto de LISP , junto con una representación de una relación entrada-salida, para calcular la relación simulando la ejecución del programa en LISP. Absys de Foster y Elcock , por otro lado, empleó una combinación de ecuaciones y cálculo lambda en un lenguaje de programación asertivo que no impone restricciones al orden en que se realizan las operaciones. [4]
La programación lógica, con su sintaxis actual de hechos y reglas, se remonta a los debates de finales de los años 1960 y principios de los 1970 sobre las representaciones declarativas versus procedimentales del conocimiento en la inteligencia artificial . Los defensores de las representaciones declarativas trabajaban notablemente en Stanford , asociados con John McCarthy , Bertram Raphael y Cordell Green, y en Edimburgo , con John Alan Robinson (un visitante académico de la Universidad de Syracuse ), Pat Hayes y Robert Kowalski . Los defensores de las representaciones procesales se centraron principalmente en el MIT , bajo el liderazgo de Marvin Minsky y Seymour Papert . [5]
Aunque se basó en los métodos de prueba de la lógica, Planner , desarrollado por Carl Hewitt en el MIT, fue el primer lenguaje que surgió dentro de este paradigma procedimentalista. [6] Planner presentaba una invocación dirigida por patrones de planes de procedimiento a partir de objetivos (es decir, reducción de objetivos o encadenamiento hacia atrás ) y de afirmaciones (es decir, encadenamiento hacia adelante ). La implementación más influyente de Planner fue el subconjunto de Planner, llamado Micro-Planner, implementado por Gerry Sussman , Eugene Charniak y Terry Winograd . Winograd utilizó Micro-Planner para implementar el emblemático programa de comprensión del lenguaje natural SHRDLU . [7] En aras de la eficiencia, Planner utilizó una estructura de control de retroceso para que solo se tuviera que almacenar una ruta de cálculo posible a la vez. Planner dio origen a los lenguajes de programación QA4 , [8] Popler, [9] Conniver, [10] QLISP, [11] y el lenguaje concurrente Ether. [12]
Hayes y Kowalski en Edimburgo intentaron conciliar el enfoque declarativo basado en la lógica para la representación del conocimiento con el enfoque procedimental de Planner. Hayes (1973) desarrolló un lenguaje ecuacional, Golux, en el que se podían obtener diferentes procedimientos alterando el comportamiento del demostrador de teoremas. [13]
Mientras tanto, Alain Colmerauer en Marsella estaba trabajando en la comprensión del lenguaje natural , usando la lógica para representar la semántica y usando la resolución para responder preguntas. Durante el verano de 1971, Colmerauer invitó a Kowalski a Marsella y juntos descubrieron que la forma clausal de la lógica podía usarse para representar gramáticas formales y que los demostradores de teoremas de resolución podían usarse para el análisis sintáctico. Observaron que algunos demostradores de teoremas, como la hiperresolución, [14] se comportan como analizadores ascendentes y otros, como la resolución SL (1971) [15], se comportan como analizadores descendentes.
Fue en el verano siguiente de 1972 cuando Kowalski, trabajando nuevamente con Colmerauer, desarrolló la interpretación procesal de las implicaciones en forma clausal. También quedó claro que tales cláusulas podrían restringirse a cláusulas definidas o cláusulas Horn , y que la resolución SL podría restringirse (y generalizarse) a la resolución SLD . La interpretación procesal de Kowalski y la SLD se describieron en un memorando de 1973, publicado en 1974. [16]
Colmerauer, junto con Philippe Roussel, utilizó la interpretación procedimental como base para Prolog, que se implementó en el verano y otoño de 1972. El primer programa Prolog, también escrito en 1972 e implementado en Marsella, fue un sistema francés de preguntas y respuestas. El uso de Prolog como lenguaje de programación práctico recibió un gran impulso con el desarrollo de un compilador por parte de David HD Warren en Edimburgo en 1977. Los experimentos demostraron que Edinburgh Prolog podía competir con la velocidad de procesamiento de otros lenguajes de programación simbólicos como Lisp . [17] Edinburgh Prolog se convirtió en el estándar de facto e influyó fuertemente en la definición del estándar ISO Prolog.
La programación lógica ganó atención internacional durante la década de 1980, cuando fue elegida por el Ministerio japonés de Industria y Comercio Internacional para desarrollar el software para el proyecto de Sistemas Informáticos de Quinta Generación (FGCS). El proyecto FGCS tenía como objetivo utilizar la programación lógica para desarrollar aplicaciones avanzadas de Inteligencia Artificial en ordenadores masivamente paralelos . Aunque el proyecto inicialmente exploró el uso de Prolog, luego adoptó el uso de programación lógica concurrente , porque estaba más cerca de la arquitectura informática FGCS.
Sin embargo, la característica de elección comprometida de la programación lógica concurrente interfirió con la semántica lógica del lenguaje [18] y con su idoneidad para la representación del conocimiento y aplicaciones de resolución de problemas. Además, los sistemas informáticos paralelos desarrollados en el proyecto no lograron competir con los avances que se estaban produciendo en el desarrollo de ordenadores más convencionales y de uso general. En conjunto, estos dos problemas dieron como resultado que el proyecto FGCS no cumpliera sus objetivos. El interés tanto en la programación lógica como en la IA cayó en declive a nivel mundial. [19]
Mientras tanto, enfoques de programación de lógica más declarativa, incluidos aquellos basados en el uso de Prolog, continuaron avanzando independientemente del proyecto FGCS. En particular, aunque Prolog se desarrolló para combinar representaciones declarativas y procedimentales del conocimiento, la interpretación puramente declarativa de programas lógicos se convirtió en el foco de aplicaciones en el campo de las bases de datos deductivas . El trabajo en este campo cobró importancia alrededor de 1977, cuando Hervé Gallaire y Jack Minker organizaron un taller sobre lógica y bases de datos en Toulouse. [20] El campo finalmente pasó a llamarse Registro de datos .
Este enfoque en la lectura lógica y declarativa de programas lógicos recibió un mayor impulso con el desarrollo de la programación lógica de restricciones en la década de 1980 y la programación de conjuntos de respuestas en la década de 1990. También está recibiendo un énfasis renovado en aplicaciones recientes de Prolog [21].
La Asociación para la Programación Lógica (ALP) se fundó en 1986 para promover la programación lógica. Su revista oficial hasta el año 2000 fue The Journal of Logic Programming . Su editor en jefe fundador fue J. Alan Robinson . [22] En 2001, la revista pasó a llamarse The Journal of Logic and Algebraic Programming , y la revista oficial de ALP se convirtió en Theory and Practice of Logic Programming , publicada por Cambridge University Press .
Los programas lógicos disfrutan de una rica variedad de semántica y métodos de resolución de problemas, así como de una amplia gama de aplicaciones en programación, bases de datos, representación del conocimiento y resolución de problemas.
La interpretación procedimental de programas lógicos, que utiliza razonamiento hacia atrás para reducir metas a submetas, es un caso especial del uso de una estrategia de resolución de problemas para controlar el uso de una representación lógica declarativa del conocimiento para obtener el comportamiento de un algoritmo . De manera más general, se pueden aplicar diferentes estrategias de resolución de problemas a la misma representación lógica para obtener diferentes algoritmos. Alternativamente, se pueden obtener diferentes algoritmos con una estrategia de resolución de problemas determinada utilizando diferentes representaciones lógicas. [23]
Las dos principales estrategias de resolución de problemas son el razonamiento hacia atrás (reducción de objetivos) y el razonamiento hacia adelante , también conocidos como razonamiento de arriba hacia abajo y de abajo hacia arriba, respectivamente.
En el caso simple de un programa de cláusula proposicional de Horn y una meta atómica de nivel superior, el razonamiento hacia atrás determina un árbol y/o , que constituye el espacio de búsqueda para resolver la meta. El objetivo de nivel superior es la raíz del árbol. Dado cualquier nodo en el árbol y cualquier cláusula cuyo encabezado coincida con el nodo, existe un conjunto de nodos secundarios correspondientes a los subobjetivos en el cuerpo de la cláusula. Estos nodos secundarios se agrupan mediante una "y". Los conjuntos alternativos de hijos correspondientes a formas alternativas de resolver el nodo se agrupan mediante una "o".
Se puede utilizar cualquier estrategia de búsqueda para buscar este espacio. Prolog utiliza una estrategia de retroceso secuencial, último en entrar, primero en salir, en la que solo se consideran una alternativa y un subobjetivo a la vez. Por ejemplo, los subobjetivos se pueden resolver en paralelo y las cláusulas también se pueden probar en paralelo. La primera estrategia se llamay-paralelo y la segunda estrategia se llamao-paralelo . También son posibles otras estrategias de búsqueda, como el retroceso inteligente[24]o la búsqueda del mejor primero para encontrar una solución óptima[25].
En el caso más general, no proposicional, donde los subobjetivos pueden compartir variables, se pueden utilizar otras estrategias, como elegir el subobjetivo que tenga más instancias o que esté lo suficientemente instanciado como para que solo se aplique un procedimiento. [26] Estas estrategias se utilizan, por ejemplo, en la programación lógica concurrente .
En la mayoría de los casos, el razonamiento hacia atrás a partir de una consulta o un objetivo es más eficiente que el razonamiento hacia adelante. Pero a veces con el registro de datos y la programación del conjunto de respuestas, es posible que no haya ninguna consulta separada del conjunto de cláusulas en su conjunto, y luego generar todos los hechos que se pueden derivar de las cláusulas es una estrategia sensata de resolución de problemas. Aquí hay otro ejemplo, donde el razonamiento directo supera al razonamiento hacia atrás en una tarea de cálculo más convencional, donde el objetivo ?- fibonacci(n, Result)es encontrar el enésimo número de Fibonacci:
Fibonacci ( 0 , 0 ). Fibonacci ( 1 , 1 ).fibonacci ( N , resultado ) : - N > 1 , N1 es N - 1 , N2 es N - 2 , fibonacci ( N1 , F1 ), fibonacci ( N2 , F2 ), el resultado es F1 + F2 .Aquí la relación fibonacci(N, M)representa la función fibonacci(N) = My el predicado N is Expressiones la notación Prolog para el predicado que instancia la variable Nal valor de Expression.
Dado el objetivo de calcular el número de Fibonacci de n, el razonamiento hacia atrás reduce el objetivo a los dos subobjetivos de calcular los números de Fibonacci de n-1 y n-2. Reduce el subobjetivo de calcular el número de Fibonacci de n-1 a los dos subobjetivos de calcular los números de Fibonacci de n-2 y n-3, calculando de forma redundante el número de Fibonacci de n-2. Este proceso de reducir una submeta de Fibonacci a dos submetas de Fibonacci continúa hasta llegar a los números 0 y 1. Su complejidad es del orden 2 n . Por el contrario, el razonamiento directo genera la secuencia de números de Fibonacci, comenzando desde 0 y 1 sin ningún nuevo cálculo, y su complejidad es lineal con respecto a n.
Prolog no puede realizar razonamiento directo directamente. Pero puede lograr el efecto de razonamiento hacia adelante dentro del contexto del razonamiento hacia atrás mediante la presentación de tablas : los subobjetivos se mantienen en una tabla, junto con sus soluciones. Si se vuelve a encontrar un subobjetivo, se resuelve directamente utilizando las soluciones que ya están en la tabla, en lugar de volver a resolver los subobjetivos de forma redundante. [27]
La programación lógica puede verse como una generalización de la programación funcional, en la que las funciones son un caso especial de relaciones. [28] Por ejemplo, la función madre(X) = Y, (cada X tiene sólo una madre Y) puede representarse mediante la relación madre(X, Y). En este sentido, los programas lógicos son similares a las bases de datos relacionales , que también representan funciones como relaciones.
En comparación con la sintaxis relacional, la sintaxis funcional es más compacta para funciones anidadas. Por ejemplo, en sintaxis funcional, la definición de abuela materna se puede escribir en forma anidada:
abuela_materna ( X ) = madre ( madre ( X )).La misma definición en notación relacional debe escribirse en forma aplanada y no anidada:
abuela_materna ( X , Y ) : - madre ( X , Z ), madre ( Z , Y ).Sin embargo, la sintaxis anidada puede considerarse como un azúcar sintáctico para la sintaxis no anidada. Ciao Prolog, por ejemplo, transforma la sintaxis funcional en forma relacional y ejecuta el programa lógico resultante utilizando la estrategia de ejecución estándar de Prolog. [29] Además, la misma transformación se puede utilizar para ejecutar relaciones anidadas que no son funcionales. Por ejemplo:
abuelo ( X ) := padre ( padre ( X )). padre ( X ) : = madre ( X ). padre ( X ) : = padre ( X ).madre ( charles ) : = elizabeth . padre ( charles ) : = phillip . madre ( harry ) : = diana . padre ( harry ) : = charles .?- abuelo ( X , Y ). X = harry , Y = elizabeth . X = harry , Y = phillip .El término programación relacional se ha utilizado para cubrir una variedad de lenguajes de programación que tratan funciones como un caso especial de relaciones. Algunos de estos lenguajes, como miniKanren [28] y la programación lineal relacional [30] son lenguajes de programación lógica en el sentido de este artículo.
Sin embargo, el lenguaje relacional RML es un lenguaje de programación imperativo [31] cuya construcción central es una expresión relacional, que es similar a una expresión en lógica de predicados de primer orden.
Otros lenguajes de programación relacional se basan en el cálculo relacional [32] o álgebra relacional. [33]
Visto en términos puramente lógicos, hay dos enfoques para la semántica declarativa de los programas lógicos de cláusulas de Horn: Un enfoque es la semántica de consecuencias lógicas originales , que entiende que resolver una meta muestra que la meta es un teorema que es verdadero en todos los modelos de la lógica. programa.
En este enfoque, la computación es una demostración de teoremas en lógica de primer orden ; y tanto el razonamiento hacia atrás , como en la resolución SLD, como el razonamiento hacia adelante , como en la hiperresolución, son métodos correctos y completos de demostración de teoremas. A veces, también se considera que estos métodos de demostración de teoremas proporcionan una semántica teórica (u operativa) de prueba separada para programas lógicos. Pero desde un punto de vista lógico, son métodos de prueba, más que semánticos.
El otro enfoque de la semántica declarativa de los programas de cláusulas de Horn es la semántica de satisfacibilidad , que entiende que resolver un objetivo muestra que el objetivo es verdadero (o satisfecho) en algún modelo previsto (o estándar) del programa. Para los programas con cláusulas de Horn, siempre existe un modelo estándar: es el modelo mínimo único del programa.
Hablando informalmente, un modelo mínimo es un modelo que, cuando se ve como el conjunto de todos los hechos (libres de variables) que son verdaderos en el modelo, no contiene un conjunto más pequeño de hechos que también sea un modelo del programa.
Por ejemplo, los siguientes hechos representan el modelo mínimo del ejemplo de relaciones familiares en la introducción de este artículo. Todos los demás hechos libres de variables son falsos en el modelo:
madre_niño ( elizabeth , charles ). padre_hijo ( charles , william ). padre_hijo ( charles , harry ). padre_hijo ( elizabeth , charles ). padre_hijo ( charles , william ). padre_hijo ( charles , harry ). abuelo_niño ( elizabeth , william ). abuelo_niño ( elizabeth , harry ).La semántica de satisfacibilidad también tiene una caracterización alternativa, más matemática, como el punto menos fijo de la función que utiliza las reglas del programa para derivar nuevos hechos a partir de hechos existentes en un solo paso de inferencia.
Sorprendentemente, los mismos métodos de resolución de problemas de razonamiento hacia adelante y hacia atrás, que fueron desarrollados originalmente para la semántica de consecuencias lógicas, son igualmente aplicables a la semántica de satisfacibilidad: el razonamiento directo genera el modelo mínimo de un programa de cláusula de Horn, al derivar nuevos hechos a partir de datos existentes. hechos, hasta que no se puedan generar nuevos hechos adicionales. El razonamiento hacia atrás, que tiene éxito al reducir una meta a submetas, hasta que todas las submetas se resuelven mediante hechos, garantiza que la meta sea verdadera en el modelo mínimo, sin generar el modelo explícitamente. [34]
La diferencia entre las dos semánticas declarativas se puede ver con las definiciones de suma y multiplicación en la aritmética sucesora , que representa los números naturales 0, 1, 2, ...como una secuencia de términos de la forma 0, s(0), s(s(0)), .... En general, el término s(X)representa el sucesor de X,a saber. X + 1.Aquí están las definiciones estándar de suma y multiplicación en notación funcional:
X + 0 = X. X + s(Y) = s(X + Y).es decir, X + (Y + 1) = (X + Y) + 1 X × 0 = 0. X × s(Y) = X + (X × Y).es decir, X × (Y + 1) = X + (X × Y).
Aquí están las mismas definiciones que un programa lógico, usando add(X, Y, Z)para representar X + Y = Z,y multiply(X, Y, Z)representar X × Y = Z:
sumar ( X , 0 , X ). agregar ( X , s ( Y ), s ( Z )) : - agregar ( X , Y , Z ).multiplicar ( X , 0 , 0 ). multiplicar ( X , s ( Y ), W ) : - multiplicar ( X , Y , Z ), sumar ( X , Z , W ).Las dos semánticas declarativas dan las mismas respuestas para las mismas conjunciones existencialmente cuantificadas de objetivos de suma y multiplicación. Por ejemplo 2 × 2 = Xtiene la solución X = 4; y X × X = X + Xtiene dos soluciones X = 0y X = 2:
?- multiplicar ( s ( s ( 0 ) ), s ( s ( 0 ) ), X ). X = s ( s ( s ( s ( 0 )))).?- multiplicar ( X , X , Y ), sumar ( X , X , Y ). X = 0 , Y = 0. X = s ( s ( 0 ) ), Y = s ( s ( s ( s ( 0 )))) .Sin embargo, en la semántica de consecuencias lógicas, existen modelos de programa no estándar, en los que, por ejemplo, add(s(s(0)), s(s(0)), s(s(s(s(s(0)))))),ie 2 + 2 = 5es verdadero. Pero con la semántica de satisfacibilidad, sólo hay un modelo, a saber, el modelo estándar de aritmética, en el que 2 + 2 = 5es falso.
En ambas semánticas, el objetivo falla. En la semántica de satisfacibilidad, el fracaso del objetivo significa que el valor de verdad del objetivo es falso. Pero en la semántica de consecuencias lógicas, el fracaso significa que se desconoce el valor de verdad del objetivo.?- add(s(s(0)), s(s(0)), s(s(s(s(s(0))))))
La negación como fracaso (NAF), como una forma de concluir que una condición negativa not pse cumple mostrando que la condición positiva pno se cumple, ya era una característica de los primeros sistemas Prolog. La extensión resultante de la resolución SLD se llama SLDNF . Una construcción similar, llamada "thnot", también existía en Micro-Planner .
La semántica lógica de NAF quedó sin resolver hasta que Keith Clark [35] demostró que, bajo ciertas condiciones naturales, NAF es una forma eficiente, correcta (y a veces completa) de razonar con la semántica de consecuencias lógicas utilizando la finalización de un programa lógico en primer lugar. lógica de orden.
Completar equivale aproximadamente a considerar el conjunto de todas las cláusulas del programa con el mismo predicado en el encabezado, digamos:
A :- Body1. ...A :- Bodyk.como definición del predicado:
A iff (Body1 or ... or Bodyk)donde iffsignifica "si y sólo si". La compleción también incluye axiomas de igualdad, que corresponden a la unificación . Clark demostró que las pruebas generadas por SLDNF son estructuralmente similares a las pruebas generadas por un estilo de razonamiento de deducción natural al finalizar el programa.
Considere, por ejemplo, el siguiente programa:
debería_recibir_sanción ( X , castigo ) : - es_un_ladrón ( X ), no debería_recibir_sanción ( X , rehabilitación ). debería_recibir_sanción ( X , rehabilitación ) : - es_un_ladrón ( X ), es_un_menor ( X ), no es_violento ( X ). es_un_ladrón ( tom ).Dado el objetivo de determinar si Tom debe recibir una sanción, la primera regla logra mostrar que Tom debe ser castigado:
?- debería_recibir_sanción ( tom , Sanción ). Sanción = castigo .Esto se debe a que Tom es un ladrón y no se puede demostrar que Tom deba ser rehabilitado. No se puede demostrar que Tom deba ser rehabilitado, porque no se puede demostrar que Tom sea menor de edad.
Sin embargo, si recibimos nueva información de que Tom es efectivamente menor de edad, la conclusión anterior de que Tom debe ser castigado se reemplaza por la nueva conclusión de que Tom debe ser rehabilitado:
menor ( tom ).?- debería_recibir_sanción ( tom , Sanción ). Sanción = rehabilitación .Esta propiedad de retirar una conclusión cuando se agrega nueva información se llama no monotonía y hace que la programación lógica sea una lógica no monótona .
Pero, si ahora se nos dice que Tom es violento, se restablecerá la conclusión de que Tom debe ser castigado:
violento ( tom ).?- debería_recibir_sanción ( tom , Sanción ). Sanción = castigo .La realización de este programa es:
debería_recibir_sanción ( X , Sanción ) si Sanción = castigo , es_un_ladrón ( X ), no debería_recibir_sanción ( X , rehabilitación ) o Sanción = rehabilitación , es_un_ladrón ( X ), es_un_menor ( X ), no es_violento ( X ). es_un_ladrón ( X ) si y así X = tom . is_a_minor ( X ) si y así X = tom . is_violent ( X ) si X = tom .La noción de finalización está estrechamente relacionada con la semántica de circunscripción de John McCarthy para el razonamiento predeterminado [36] y con el supuesto de mundo cerrado de Ray Reiter . [37]
La semántica de finalización para la negación es una semántica de consecuencia lógica, para la cual SLDNF proporciona una implementación teórica de prueba. Sin embargo, en la década de 1980, la semántica de satisfacibilidad se hizo más popular para programas lógicos con negación. En la semántica de satisfacibilidad, la negación se interpreta de acuerdo con la definición clásica de verdad en un modelo previsto o estándar del programa lógico.
En el caso de programas lógicos con condiciones negativas, existen dos variantes principales de la semántica de satisfacibilidad: en la semántica bien fundada , el modelo previsto de un programa lógico es un modelo mínimo único, de tres valores, que siempre existe. La semántica bien fundada generaliza la noción de definición inductiva en lógica matemática. [38] XSB Prolog [39] implementa la semántica bien fundamentada utilizando resolución SLG. [40]
En la semántica del modelo estable alternativo , puede que no haya modelos previstos o varios modelos previstos, todos los cuales son mínimos y de dos valores. La semántica del modelo estable sustenta la programación de conjuntos de respuestas (ASP).
Tanto la semántica del modelo estable como la bien fundada se aplican a programas lógicos arbitrarios con negación. Sin embargo, ambas semánticas coinciden para programas de lógica estratificada . Por ejemplo, el programa para sancionar a los ladrones está estratificado (localmente) y las tres semánticas del programa determinan el mismo modelo previsto:
debería_recibir_sanción ( tom , castigo ). es_un_ladrón ( tom ). es_un_menor ( tom ). es_violento ( tom ).Los intentos de comprender la negación en la programación lógica también han contribuido al desarrollo de marcos de argumentación abstracta . [41] En una interpretación argumentativa de la negación, el argumento inicial de que Tom debería ser castigado porque es un ladrón, es atacado por el argumento de que debería ser rehabilitado porque es menor de edad. Pero el hecho de que Tom sea violento socava el argumento de que Tom debería ser rehabilitado y restablece el argumento de que Tom debería ser castigado.
La metaprogramación , en la que los programas se tratan como datos, ya era una característica de las primeras implementaciones de Prolog. [42] [43] Por ejemplo, la implementación de Prolog en Edimburgo DEC10 incluía "un intérprete y un compilador, ambos escritos en el propio Prolog". [43] El metaprograma más simple es el llamado metaintérprete " vainilla ":
resolver ( verdadero ). resolver (( B , C )):- resolver ( B ), resolver ( C ). resolver ( A ): - cláusula ( A , B ), resolver ( B ).donde verdadero representa una conjunción vacía y (B,C) es un término compuesto que representa la conjunción de B y C. La cláusula de predicado (A,B) significa que hay una cláusula de la forma A:- B.
La metaprogramación es una aplicación del uso más general de una metalógica o metalenguaje para describir y razonar sobre otro lenguaje, llamado lenguaje objeto .
La programación metalógica permite combinar representaciones a nivel de objeto y metanivel, como en el lenguaje natural. Por ejemplo, en el siguiente programa, la fórmula atómica attends(Person, Meeting)aparece como una fórmula a nivel de objeto y como un argumento de los metapredicados prohibitedyapproved.
prohibido ( asiste ( persona , reunión )) :- no ( aprobado ( asiste ( persona , reunión ))).debería_recibir_sanción ( Persona , regañar ) : - asiste ( Persona , Reunión ), elevado ( Persona ), prohibido ( asiste ( Persona , Reunión )). debería_recibir_sanción ( Persona , destierro ) : - asiste ( Persona , Reunión ), humilde ( Persona ), prohibido ( asiste ( Persona , Reunión )).aprobado ( asiste ( alice , tea_party )). asiste ( mad_hatter , tea_party ). asiste ( lirón , tea_party ).elevado ( mad_hatter ). humilde ( lirón ).?- debería_recibir_sanción ( X , Y ). Persona = mad_hatter , Sanción = regaño . Persona = lirón , Sanción = destierro .En su popular Introducción a la ciencia cognitiva, [44] Paul Thagard incluye la lógica y las reglas como enfoques alternativos para modelar el pensamiento humano. Sostiene que las reglas, que tienen la forma SI condición ENTONCES acción , son "muy similares" a los condicionales lógicos, pero son más simples y tienen mayor plausibilidad psicológica (página 51). Entre otras diferencias entre lógica y reglas, sostiene que la lógica usa la deducción, pero las reglas usan la búsqueda (página 45) y pueden usarse para razonar hacia adelante o hacia atrás (página 47). Las oraciones en lógica "deben interpretarse como universalmente verdaderas ", pero las reglas pueden ser valores predeterminados , que admiten excepciones (página 44).
Afirma que "a diferencia de la lógica, los sistemas basados en reglas también pueden representar fácilmente información estratégica sobre qué hacer" (página 45). Por ejemplo, "SI quieres volver a casa el fin de semana y tienes billete de autobús, ENTONCES puedes coger un autobús". No observa que la misma estrategia de reducir una meta a submetas pueda interpretarse, a la manera de la programación lógica, como una aplicación de razonamiento regresivo a un condicional lógico:
can_go ( tú , casa ) : - tener ( tú , pasaje_de_autobús ), coger ( tú , autobús ).Todas estas características de los sistemas basados en reglas (búsqueda, razonamiento hacia adelante y hacia atrás, razonamiento por defecto y reducción de objetivos) también son características definitorias de la programación lógica. Esto sugiere que la conclusión de Thagard (página 56) es que:
Gran parte del conocimiento humano se describe naturalmente en términos de reglas, y muchos tipos de pensamiento, como la planificación, pueden modelarse mediante sistemas basados en reglas.
También se aplica a la programación lógica.
Keith Stenning y Michiel van Lambalgen presentan otros argumentos que muestran cómo se puede utilizar la programación lógica para modelar aspectos del pensamiento humano en su libro Human Reasoning and Cognitive Science. [45] Muestran cómo el carácter no monótono de los programas lógicos puede utilizarse para explicar el desempeño humano en una variedad de tareas psicológicas. También muestran (página 237) que "el razonamiento de mundo cerrado en su forma de programación lógica tiene una implementación neuronal atractiva, a diferencia de la lógica clásica".
En The Proper Treatment of Events, [46] Michiel van Lambalgen y Fritz Hamm investigan el uso de programación lógica de restricciones para codificar "nociones temporales en lenguaje natural observando la forma en que los seres humanos construyen el tiempo".
El uso de la lógica para representar conocimiento procedimental e información estratégica fue uno de los principales objetivos que contribuyeron al desarrollo inicial de la programación lógica. Además, sigue siendo una característica importante de la familia Prolog de lenguajes de programación lógica en la actualidad. Sin embargo, muchas aplicaciones de programación lógica, incluidas las aplicaciones Prolog, se centran cada vez más en el uso de la lógica para representar conocimiento puramente declarativo. Estas aplicaciones incluyen tanto la representación del conocimiento general de sentido común como la representación de la experiencia en un dominio específico .
El sentido común incluye el conocimiento sobre causa y efecto, tal como está formalizado, por ejemplo, en el cálculo de situaciones , el cálculo de eventos y los lenguajes de acción . A continuación se ofrece un ejemplo simplificado que ilustra las características principales de tales formalismos. La primera cláusula establece que un hecho se mantiene inmediatamente después de que un evento inicia (o causa) el hecho. La segunda cláusula es un axioma del marco , que establece que un hecho que se cumple en un momento continúa siendo válido en el momento siguiente a menos que sea terminado por un evento que suceda en ese momento. Esta formulación permite que ocurra más de un evento al mismo tiempo:
sostiene ( Hecho , Tiempo2 ) : - sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , inicia ( Evento , Hecho ). se mantiene ( Hecho , Tiempo2 ) : - sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , se mantiene ( Hecho , Tiempo1 ), no ( terminado ( Hecho , Tiempo1 )).terminado ( Hecho , Hora ) : - sucede ( Evento , Hora ), termina ( Evento , Hecho ).Aquí holdshay un metapredicado, similar al solveanterior. Sin embargo, mientras que solvetiene un solo argumento, que se aplica a cláusulas generales, el primer argumento holdses un hecho y el segundo argumento es un tiempo (o estado). La fórmula atómica holds(Fact, Time)expresa que se Factmantiene en el Time. Estos hechos que varían en el tiempo también se denominan fluidos . La fórmula atómica happens(Event, Time)expresa que el Evento ocurre en el Time.
El siguiente ejemplo ilustra cómo se pueden utilizar estas cláusulas para razonar sobre la causalidad en un mundo de bloques de juguete . Aquí, en el estado inicial en el tiempo 0, un bloque verde está sobre una mesa y un bloque rojo está apilado sobre el bloque verde (como un semáforo). En el momento 0, el bloque rojo se mueve a la mesa. En el momento 1, el bloque verde se mueve al bloque rojo. Mover un objeto a un lugar finaliza el hecho de que el objeto está en cualquier lugar e inicia el hecho de que el objeto está en el lugar al que se mueve:
mantiene ( en ( green_block , tabla ), 0 ). mantiene ( en ( bloque_rojo , bloque_verde ), 0 ).sucede ( mover ( red_block , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 1 ).inicia ( mover ( Objeto , Lugar ), en ( Objeto , Lugar )). termina ( mover ( Objeto , Lugar2 ), en ( Objeto , Lugar1 )).?- sostiene ( Hecho , Tiempo ).Hecho = activado ( bloque_verde , tabla ), Tiempo = 0. Hecho = activado ( bloque_rojo , bloque_verde ), Tiempo = 0. Hecho = activado ( bloque_verde , tabla ), Tiempo = 1. Hecho = activado ( bloque_rojo , tabla ), Tiempo = 1. Hecho = activado ( bloque_verde , bloque_rojo ), Tiempo = 2. Hecho = activado ( bloque_rojo , tabla ), Tiempo = 2.El razonamiento hacia adelante y el razonamiento hacia atrás generan las mismas respuestas al objetivo holds(Fact, Time). Pero el razonamiento directo genera flujos progresivamente en orden temporal, y el razonamiento hacia atrás genera flujos regresivamente , como en el uso de la regresión en un dominio específico en el cálculo de situaciones . [47]
La programación lógica también ha demostrado ser útil para representar la experiencia de un dominio específico en sistemas expertos . [48] Pero la experiencia humana, al igual que el sentido común de propósito general, es en su mayor parte implícita y tácita , y a menudo es difícil representar ese conocimiento implícito en reglas explícitas. Sin embargo, esta dificultad no surge cuando se utilizan programas lógicos para representar las reglas explícitas existentes de una organización empresarial o autoridad legal.
Por ejemplo, aquí hay una representación de una versión simplificada de la primera oración de la Ley de Nacionalidad Británica, que establece que una persona que nace en el Reino Unido se convierte en ciudadano británico en el momento del nacimiento si uno de los padres de la persona es británico. ciudadano en el momento de su nacimiento:
iniciados ( nacimiento ( Persona ), ciudadano ( Persona , Reino Unido )): - tiempo_de ( nacimiento ( Persona ), Hora ), lugar_de ( nacimiento ( Persona ), Reino Unido ), padre_hijo ( Otra_Persona , Persona ), retiene ( ciudadano ( Otra_Persona , Reino Unido) ), Tiempo ).Históricamente, la representación de una gran parte de la Ley de Nacionalidad Británica como un programa lógico en la década de 1980 [49] fue "enormemente influyente para el desarrollo de representaciones computacionales de la legislación, mostrando cómo la programación lógica permite representaciones intuitivamente atractivas que pueden implementarse directamente en generar inferencias automáticas". [50]
Más recientemente, el sistema PROLEG, [51] iniciado en 2009 y que consta de aproximadamente 2500 reglas y excepciones del código civil y reglas de casos de la Corte Suprema en Japón, se ha convertido posiblemente en la base de reglas legales más grande del mundo. [52]
La regla de inferencia de resolución de SLD es neutral en cuanto al orden en el que se pueden seleccionar los subobjetivos en los cuerpos de cláusulas para su solución. En aras de la eficiencia, Prolog restringe este orden al orden en que se escriben los subobjetivos. SLD también se muestra neutral en cuanto a la estrategia de búsqueda en el espacio de las pruebas SLD. Prolog busca este espacio, de arriba hacia abajo, primero en profundidad, probando diferentes cláusulas para resolver el mismo (sub)objetivo en el orden en que están escritas las cláusulas.
Esta estrategia de búsqueda tiene la ventaja de que la rama actual del árbol se puede representar eficientemente mediante una pila . Cuando una cláusula de objetivo en la parte superior de la pila se reduce a una nueva cláusula de objetivo, la nueva cláusula de objetivo se coloca en la parte superior de la pila. Cuando el subobjetivo seleccionado en la cláusula de objetivo en la parte superior de la pila no se puede resolver, la estrategia de búsqueda retrocede , eliminando la cláusula de objetivo de la parte superior de la pila y vuelve a intentar la solución intentada del subobjetivo seleccionado en la cláusula de objetivo anterior usando el siguiente cláusula que coincida con el subobjetivo seleccionado.
El retroceso se puede restringir mediante el uso de un subobjetivo, llamado cortar , escrito como !, que siempre tiene éxito pero no se puede retroceder. Cut se puede utilizar para mejorar la eficiencia, pero también puede interferir con el significado lógico de las cláusulas. En muchos casos, el uso del corte puede ser sustituido por la negación como fracaso. De hecho, la negación como falla se puede definir en Prolog, usando cut, junto con cualquier literal, digamos fail , que se unifique con el encabezado de ninguna cláusula:
no ( P ) :- P , !, falla . no ( P ).Prolog proporciona otras funciones, además de cortar, que no tienen una interpretación lógica. Estos incluyen los predicados integrados afirmar y retractar para actualizar destructivamente el estado del programa durante la ejecución del programa.
Por ejemplo, el ejemplo anterior del mundo de bloques de juguete se puede implementar sin axiomas de marco utilizando un cambio de estado destructivo:
en ( bloque_verde , tabla ). encendido ( bloque_rojo , bloque_verde ).mover ( Objeto , Lugar2 ) : - retraer ( en ( Objeto , Lugar1 )), afirmar ( en ( Objeto , Lugar2 ).La secuencia de eventos de movimiento y las ubicaciones resultantes de los bloques se pueden calcular ejecutando la consulta:
?- mover ( bloque_rojo , tabla ), mover ( bloque_verde , bloque_rojo ), en ( Objeto , Lugar ).Objeto = bloque_rojo , Lugar = mesa . Objeto = bloque_verde , Lugar = bloque_rojo .Se han desarrollado varias extensiones de la programación lógica para proporcionar un marco lógico para un cambio de estado tan destructivo. [53] [54] [55]
La amplia gama de aplicaciones Prolog, tanto de forma aislada como en combinación con otros lenguajes, se destaca en el Libro del Año de Prolog, [21] que celebra el 50 aniversario de Prolog en 2022.
Prolog también ha contribuido al desarrollo de otros lenguajes de programación, incluidos ALF , Fril , Gödel , Mercury , Oz , Ciao , Visual Prolog , XSB y λProlog .
La programación lógica de restricciones (CLP) combina la programación lógica de la cláusula Horn con la resolución de restricciones . Amplía las cláusulas de Horn al permitir que algunos predicados, declarados como predicados de restricción, aparezcan como literales en el cuerpo de una cláusula. Los predicados de restricción no están definidos por los hechos y las reglas del programa, sino que están predefinidos por alguna estructura o teoría teórica del modelo de dominio específico.
Desde el punto de vista procesal, los subobjetivos cuyos predicados están definidos por el programa se resuelven mediante reducción de objetivos, como en la programación lógica ordinaria, pero las restricciones se simplifican y se verifica su satisfacibilidad mediante un solucionador de restricciones de dominio específico, que implementa la semántica de los predicados de restricciones. Un problema inicial se resuelve reduciéndolo a una conjunción satisfactoria de restricciones.
Curiosamente, la primera versión de Prolog ya incluía un predicado de restricción dif(término1, término2), de la tesis doctoral de Philippe Roussel de 1972, que tiene éxito si ambos argumentos son términos diferentes, pero que se retrasa si cualquiera de los términos contiene una variable. [52]
El siguiente programa de lógica de restricciones representa una base de datos temporal de juguete de john'sla historia como profesor:
enseña ( john , hardware , T ) : - 1990 ≤ T , T < 1999. enseña ( john , software , T ) : - 1999 ≤ T , T < 2005. enseña ( john , lógica , T ) : - 2005 ≤ T , T ≤ 2012. rango ( john , instructor , T ) : - 1990 ≤ T , T < 2010. rango ( john , profesor , T ) : - 2010 ≤ T , T < 2014.Aquí ≤y <están los predicados de restricción, con su semántica habitual. La siguiente cláusula de objetivo consulta la base de datos para averiguar cuándo johnenseñó logicy fue professor:
?- enseña ( john , lógica , T ), rango ( john , profesor , T ).La solución 2010 ≤ T, T ≤ 2012resulta de simplificar las restricciones.2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.
La programación lógica de restricciones se ha utilizado para resolver problemas en campos como la ingeniería civil , la ingeniería mecánica , la verificación de circuitos digitales , la programación automatizada de horarios , el control del tráfico aéreo y las finanzas. Está estrechamente relacionado con la programación lógica abductiva .
Datalog es un lenguaje de definición de bases de datos, que combina una vista relacional de los datos, como en las bases de datos relacionales , con una vista lógica, como en la programación lógica.
Las bases de datos relacionales utilizan un cálculo relacional o álgebra relacional, con operaciones relacionales , como unión , intersección , diferencia de conjuntos y producto cartesiano para especificar consultas que acceden a una base de datos. Datalog utiliza conectivos lógicos, como o , y y no en los cuerpos de reglas para definir relaciones como parte de la propia base de datos.
Desde el principio del desarrollo de las bases de datos relacionales se reconoció que las consultas recursivas no pueden expresarse ni en álgebra relacional ni en cálculo relacional, y que esta deficiencia puede remediarse introduciendo un operador de punto mínimo fijo. [56] [57] Por el contrario, las relaciones recursivas se pueden definir naturalmente mediante reglas en programas lógicos, sin la necesidad de nuevos conectivos u operadores lógicos.
Datalog se diferencia de la programación lógica más general en que solo tiene constantes y variables como términos. Además, todos los hechos están libres de variables y las reglas están restringidas, de modo que si se ejecutan de abajo hacia arriba, los hechos derivados también están libres de variables.
Por ejemplo, considere la base de datos familiar:
madre_niño ( elizabeth , charles ). padre_hijo ( charles , william ). padre_hijo ( charles , harry ). padre_hijo ( X , Y ) : - madre_hijo ( X , Y ). padre_hijo ( X , Y ) : - padre_hijo ( X , Y ). ancestro_descendiente ( X , Y ) : - padre_hijo ( X , X ). ancestro_descendiente ( X , Y ) : - ancestro_descendiente ( X , Z ), ancestro_descendiente ( Z , Y ).La ejecución ascendente deriva el siguiente conjunto de hechos adicionales y finaliza:
padre_hijo ( elizabeth , charles ). padre_hijo ( charles , william ). padre_hijo ( charles , harry ).ancestro_descendiente ( elizabeth , charles ). ancestro_descendiente ( charles , william ). ancestro_descendiente ( charles , harry ).ancestro_descendiente ( elizabeth , william ). ancestro_descendiente ( elizabeth , harry ).La ejecución de arriba hacia abajo genera las mismas respuestas a la consulta:
?- ancestro_descendiente ( X , Y ).Pero luego entra en un bucle infinito. Sin embargo, la ejecución de arriba hacia abajo con tabulación da las mismas respuestas y finaliza sin bucles.
Al igual que Datalog, la programación del conjunto de respuestas (ASP) no está completa en Turing. Además, en lugar de separar los objetivos (o consultas) del programa que se utilizará para resolverlos, ASP trata todo el programa como un objetivo y lo resuelve generando un modelo estable que hace que el objetivo sea verdadero. Para ello utiliza la semántica de modelos estables , según la cual un programa lógico puede tener cero, uno o más modelos previstos. Por ejemplo, el siguiente programa representa una variante degenerada del problema de colorear mapas de colorear dos países de rojo o verde:
país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( C , rojo ) : - país ( C ), no ( color ( C , verde )). color ( C , verde ) : - país ( C ), no ( color ( C , rojo )).El problema tiene cuatro soluciones representadas por cuatro modelos estables:
país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( oz , rojo ). color ( iz , rojo ).país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( oz , verde ). color ( iz , verde ).país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( oz , rojo ). color ( iz , verde ).país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( oz , verde ). color ( iz , rojo ).Para representar la versión estándar del problema de coloración de mapas, debemos agregar la restricción de que dos países adyacentes no pueden colorearse del mismo color. En ASP, esta restricción se puede escribir como una cláusula de la forma:
:- país ( C1 ), país ( C2 ), adyacente ( C1 , C2 ), color ( C1 , X ), color ( C2 , X ).Con la adición de esta restricción, el problema ahora tiene sólo dos soluciones:
país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( oz , rojo ). color ( iz , verde ).país ( oz ). país ( iz ). adyacente ( oz , iz ). color ( oz , verde ). color ( iz , rojo ).La adición de restricciones de la forma :- Body.elimina modelos en los que Bodyes verdadero.
De manera confusa, las restricciones en ASP son diferentes de las restricciones en CLP . Las restricciones en CLP son predicados que califican las respuestas a las consultas (y las soluciones de los objetivos). Las restricciones en ASP son cláusulas que eliminan modelos que de otro modo satisfacerían objetivos. Las restricciones en ASP son como las restricciones de integridad en las bases de datos.
Esta combinación de cláusulas de programación lógica ordinaria y cláusulas de restricción ilustra la metodología de generación y prueba de resolución de problemas en ASP: las cláusulas ordinarias definen un espacio de búsqueda de posibles soluciones y las restricciones filtran las soluciones no deseadas. [58]
La mayoría de las implementaciones de ASP proceden en dos pasos: primero, crean instancias del programa de todas las formas posibles, reduciéndolo a un programa de lógica proposicional (conocido como conexión a tierra ). Luego aplican un solucionador de problemas de lógica proposicional, como el algoritmo DPLL o un solucionador booleano SAT . Sin embargo, algunas implementaciones, como s(CASP) [59], utilizan un procedimiento similar a una resolución SLD, de arriba hacia abajo, dirigido a objetivos, sin conexión a tierra.
La programación lógica abductiva [60] (ALP), al igual que CLP, extiende la programación lógica normal al permitir que los cuerpos de las cláusulas contengan literales cuyos predicados no están definidos por las cláusulas. En ALP, estos predicados se declaran abducibles (o asumibles ) y se utilizan como en el razonamiento abductivo para explicar observaciones o, más generalmente, para agregar nuevos hechos al programa (como suposiciones) para resolver objetivos.
Por ejemplo, supongamos que se nos da un estado inicial en el que un bloque rojo está sobre un bloque verde en una mesa en el tiempo 0:
mantiene ( en ( green_block , tabla ), 0 ). mantiene ( en ( bloque_rojo , bloque_verde ), 0 ).Supongamos que también se nos da el objetivo:
?- mantiene ( en ( bloque_verde , bloque_rojo ), 3 ), mantiene ( en ( bloque_rojo , tabla ), 3 ).El objetivo puede representar una observación, en cuyo caso una solución es una explicación de la observación. O la meta puede representar un estado de cosas futuro deseado, en cuyo caso una solución es un plan para lograr la meta. [61]
Podemos usar las reglas de causa y efecto presentadas anteriormente para resolver el objetivo, tratando el happenspredicado como abducible:
sostiene ( Hecho , Tiempo2 ) : - sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , inicia ( Evento , Hecho ). se mantiene ( Hecho , Tiempo2 ) : - sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , se mantiene ( Hecho , Tiempo1 ), no ( terminado ( Hecho , Tiempo1 )). terminado ( Hecho , Hora ) : - sucede ( Evento , Hora ), termina ( Evento , Hecho ).inicia ( mover ( Objeto , Lugar ), en ( Objeto , Lugar )). termina ( mover ( Objeto , Lugar2 ), en ( Objeto , Lugar1 )).ALP resuelve el objetivo razonando hacia atrás y agregando suposiciones al programa para resolver subobjetivos abducibles. En este caso existen muchas soluciones alternativas, entre ellas:
sucede ( mover ( red_block , tabla ), 0 ). sucede ( marca , 1 ). sucede ( mover ( bloque_verde , bloque_rojo ), 2 ).sucede ( marca , 0 ). sucede ( mover ( red_block , tabla ), 1 ). sucede ( mover ( bloque_verde , bloque_rojo ), 2 ).sucede ( mover ( red_block , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 1 ). sucede ( marca , 2 ).Aquí tickhay un evento que marca el paso del tiempo sin iniciar ni terminar ningún flujo.
También existen soluciones en las que los dos moveeventos ocurren al mismo tiempo. Por ejemplo:
sucede ( mover ( red_block , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 0 ). sucede ( marca , 1 ). sucede ( marca , 2 ).Estas soluciones, si no se desean, se pueden eliminar agregando una restricción de integridad, que es como una cláusula de restricción en ASP:
:- sucede ( mover ( Bloque1 , Lugar ), Hora ), sucede ( mover ( Bloque2 , Bloque1 ), Hora ).La programación lógica abductiva se ha utilizado para el diagnóstico de fallas, la planificación, el procesamiento del lenguaje natural y el aprendizaje automático. También se ha utilizado para interpretar la negación como fracaso como forma de razonamiento abductivo. [62]
La programación lógica inductiva (ILP) es un enfoque del aprendizaje automático que induce programas lógicos como generalizaciones hipotéticas de ejemplos positivos y negativos. Dado un programa lógico que representa conocimientos previos y ejemplos positivos junto con restricciones que representan ejemplos negativos, un sistema ILP induce un programa lógico que generaliza los ejemplos positivos y excluye los ejemplos negativos.
ILP es similar a ALP, en el sentido de que se puede considerar que ambos generan hipótesis para explicar las observaciones y emplean restricciones para excluir hipótesis indeseables. Pero en ALP las hipótesis son hechos libres de variables y en ILP las hipótesis son reglas generales. [63] [64]
Por ejemplo, dado solo el conocimiento previo de las relaciones madre_hijo y padre_hijo, y ejemplos adecuados de la relación abuelo_hijo, los sistemas ILP actuales pueden generar la definición de abuelo_hijo, inventando un predicado auxiliar, que puede interpretarse como la relación padre_hijo: [65 ]
abuelo_hijo ( X , Y ): - auxiliar ( X , Z ), auxiliar ( Z , Y ). auxiliar ( X , Y ): - madre_hijo ( X , Y ). auxiliar ( X , Y ): - padre_hijo ( X , Y ).Stuart Russell [66] se ha referido a esta invención de nuevos conceptos como el paso más importante necesario para alcanzar la IA a nivel humano.
El trabajo reciente en ILP, que combina programación lógica, aprendizaje y probabilidad, ha dado lugar a los campos del aprendizaje relacional estadístico y la programación lógica inductiva probabilística .
La programación lógica concurrente integra conceptos de programación lógica con programación concurrente . Su desarrollo recibió un gran impulso en la década de 1980 cuando se eligió el lenguaje de programación de sistemas del Proyecto Japonés de Quinta Generación (FGCS) . [67]
Un programa lógico concurrente es un conjunto de cláusulas Horn protegidas de la forma:
H :- G1, ..., Gn | B1, ..., Bn.La conjunción se llama guardia de la cláusula y | es el operador de compromiso . Declarativamente, las cláusulas cautelosas de Horn se leen como implicaciones lógicas ordinarias:G1, ... , Gn
H if G1 and ... and Gn and B1 and ... and Bn.Sin embargo, procesalmente, cuando hay varias cláusulas cuyos encabezados Hcoinciden con un objetivo determinado, todas las cláusulas se ejecutan en paralelo, comprobando si sus guardias se mantienen. Si se mantienen las guardas de más de una cláusula, entonces se realiza una elección comprometida con una de las cláusulas y la ejecución continúa con los subobjetivos de la cláusula elegida. Estos subobjetivos también se pueden ejecutar en paralelo. Por lo tanto, la programación lógica concurrente implementa una forma de "no me importa el no determinismo", en lugar de "no conozco el no determinismo".G1, ... , GnB1, ..., Bn
Por ejemplo, el siguiente programa de lógica concurrente define un predicado shuffle(Left, Right, Merge), que se puede utilizar para mezclar dos listas Lefty Right, combinándolas en una única lista Mergeque conserva el orden de las dos listas Lefty Right:
mezclar ([], [], []). barajar ( Izquierda , Derecha , Fusionar ) : - Izquierda = [ Primero | Descanso ] | Fusionar = [ Primero | ShortMerge ], aleatorio ( Descanso , Derecha , ShortMerge ). barajar ( Izquierda , Derecha , Fusionar ) : - Derecha = [ Primero | Descanso ] | Fusionar = [ Primero | ShortMerge ], aleatorio ( Izquierda , Resto , ShortMerge ).Aquí, []representa la lista vacía y [Head | Tail]representa una lista con el primer elemento Headseguido de list Tail, como en Prolog. (Observe que la primera aparición de | en las cláusulas segunda y tercera es el constructor de la lista, mientras que la segunda aparición de | es el operador de compromiso). El programa se puede utilizar, por ejemplo, para barajar las listas [ace, queen, king]e [1, 4, 2]invocar la cláusula objetivo. :
barajar ([ as , reina , rey ], [ 1 , 4 , 2 ], fusionar ).El programa generará de forma no determinista una solución única, por ejemplo Merge = [ace, queen, 1, king, 4, 2].
Carl Hewitt ha argumentado [68] que, debido a la indeterminación de la computación concurrente , la programación lógica concurrente no puede implementar la concurrencia general. Sin embargo, según la semántica lógica, cualquier resultado de un cálculo de un programa lógico concurrente es una consecuencia lógica del programa, aunque no todas las consecuencias lógicas puedan derivarse.
La programación lógica de restricciones concurrentes [69] combina la programación lógica concurrente y la programación lógica de restricciones y utiliza restricciones para controlar la concurrencia. Una cláusula puede contener una protección, que es un conjunto de restricciones que pueden bloquear la aplicabilidad de la cláusula. Cuando se satisfacen las garantías de varias cláusulas, la programación lógica de restricciones concurrentes toma la decisión comprometida de usar solo una.
Varios investigadores han extendido la programación lógica con características de programación de orden superior derivadas de la lógica de orden superior , como las variables de predicado. Dichos lenguajes incluyen las extensiones Prolog HiLog [70] y λProlog . [71]
Basar la programación lógica dentro de la lógica lineal ha dado como resultado el diseño de lenguajes de programación lógica que son considerablemente más expresivos que los basados en la lógica clásica. Los programas de cláusulas Horn solo pueden representar cambios de estado mediante el cambio de argumentos a predicados. En la programación de lógica lineal, se puede utilizar la lógica lineal ambiental para respaldar el cambio de estado. Algunos de los primeros diseños de lenguajes de programación lógica basados en lógica lineal incluyen LO, [72] Lolli, [73] ACL, [74] y Forum. [75] Forum proporciona una interpretación dirigida a objetivos de toda la lógica lineal.
F-logic [76] amplía la programación lógica con objetos y la sintaxis de marco.
Logtalk [77] amplía el lenguaje de programación Prolog con soporte para objetos, protocolos y otros conceptos de programación orientada a objetos. Es compatible con la mayoría de los sistemas Prolog que cumplen con los estándares como compiladores backend.
La lógica de transacciones [53] es una extensión de la programación lógica con una teoría lógica de actualizaciones que modifican el estado. Tiene una semántica tanto de teoría de modelos como de procedimiento. Una implementación de un subconjunto de lógica de transacciones está disponible en el sistema Flora-2 [78] . Otros prototipos también están disponibles .
