La programación lógica es un paradigma de programación , base 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 problemas. El cálculo se realiza aplicando el 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 lenguajes, las reglas se escriben 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 denomina cabeza de la regla , ..., se denomina cuerpo y se denominan literales o condiciones. Cuando n = 0, la regla se denomina hecho y se escribe de la forma simplificada:B1BnBi
A.Las consultas (u objetivos) tienen la misma sintaxis que los cuerpos de las reglas y comúnmente se escriben en la forma:
?- B1, ..., Bn.En el caso más simple de las 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 de predicado que nombra una relación, como "maternidad", y las 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.
Consideremos, por ejemplo, el siguiente programa de cláusula Horn:
madre_hijo ( 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 respuesta única 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 un par de este tipo:
abuelo_hijo ( X , william ) .X = elizabeth?- abuelo_hijo ( elizabeth , Y ). Y = william ; Y = harry .?- abuelo_hijo ( X , Y ). X = elizabeth Y = william ; X = elizabeth Y = harry .?- abuelo_hijo ( william , harry ). no ?- abuelo_hijo ( elizabeth , harry ). síAunque los programas lógicos con cláusula de Horn son Turing completos , [1] [2] para la mayoría de las aplicaciones prácticas, los programas con cláusula de Horn deben extenderse a programas lógicos "normales" con condiciones negativas. Por ejemplo, la definición de hermano utiliza una condición negativa, donde el predicado = está definido por la cláusula X = X:
hermano ( X , Y ) :- padre_hijo ( Z , X ), padre_hijo ( Z , Y ), no ( X = Y ).Los lenguajes de programación lógica que incluyen condiciones negativas tienen las capacidades de representación de 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 está pensado para 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 por falla not B : se considera que un literal negativo se cumple si y solo 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 tratar de desarrollar una semántica lógica para la negación como fallo y en desarrollar otras semánticas y otras implementaciones para la negación. Estos avances han sido importantes, a su vez, para respaldar 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 de ordenador es también una característica del cálculo lambda , desarrollado por Alonzo Church en la década de 1930. Sin embargo, la primera propuesta de utilizar la forma clausal de la lógica para representar programas de ordenador fue realizada por Cordell Green . [3] Este utilizó una axiomatización de un subconjunto de LISP , junto con una representación de una relación de 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 sobre el orden en el 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 años 1970 sobre representaciones declarativas versus procedimentales del conocimiento en inteligencia artificial . Los defensores de las representaciones declarativas trabajaban en particular 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 procedimentales se centraban principalmente en el MIT , bajo el liderazgo de Marvin Minsky y Seymour Papert . [5]
Aunque se basaba 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 procedimentales 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 programa de comprensión del lenguaje natural SHRDLU , un hito . [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 lugar a los lenguajes de programación QA4 , [8] Popler, [9] Conniver, [10] QLISP, [11] y el lenguaje concurrente Ether. [12]
En Edimburgo, Hayes y Kowalski intentaron reconciliar 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 modificando el comportamiento del demostrador de teoremas. [13]
Mientras tanto, Alain Colmerauer trabajaba en Marsella sobre la comprensión del lenguaje natural , utilizando la lógica para representar la semántica y 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 utilizarse para representar gramáticas formales y que los probadores de teoremas de resolución podían utilizarse para el análisis sintáctico. Observaron que algunos probadores de teoremas, como la hiperresolución, [14] se comportan como analizadores sintácticos de abajo hacia arriba y otros, como la resolución SL (1971) [15] se comportan como analizadores sintácticos de arriba hacia abajo.
Fue en el verano siguiente de 1972 cuando Kowalski, trabajando de nuevo con Colmerauer, desarrolló la interpretación procedimental de las implicaciones en forma de cláusula. También quedó claro que dichas cláusulas podían restringirse a cláusulas definidas o cláusulas Horn , y que la resolución SL podía restringirse (y generalizarse) a la resolución SLD . La interpretación procedimental 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 de 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 de preguntas y respuestas francés. El uso de Prolog como lenguaje de programación práctico recibió un gran impulso con el desarrollo de un compilador por 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ólica 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 de Comercio Internacional e Industria de Japón 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 computadoras masivamente paralelas . Aunque el proyecto inicialmente exploró el uso de Prolog, más tarde adoptó el uso de la programación lógica concurrente , porque era más cercana a 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 de conocimiento y las aplicaciones de resolución de problemas. Además, los sistemas informáticos paralelos desarrollados en el proyecto no pudieron competir con los avances que se estaban produciendo en el desarrollo de ordenadores más convencionales y de propósito general. Juntos, estos dos problemas hicieron 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, los enfoques de programación lógica más declarativos, incluidos los 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 atención para las aplicaciones en el campo de las bases de datos deductivas . El trabajo en este campo se hizo prominente 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 fue renombrado como Datalog .
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 Association for Logic Programming (ALP) fue fundada 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 la ALP pasó a ser 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 una amplia gama de aplicaciones en programación, bases de datos, representación de conocimiento y resolución de problemas.
La interpretación procedimental de programas lógicos, que utiliza razonamiento inverso para reducir objetivos a subobjetivos, 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 . En términos más generales, 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 dada utilizando diferentes representaciones lógicas. [23]
Las dos principales estrategias de resolución de problemas son el razonamiento regresivo (reducción de objetivos) y el razonamiento progresivo , 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 Horn proposicional y un objetivo atómico de nivel superior, el razonamiento inverso determina un árbol and-or , que constituye el espacio de búsqueda para resolver el objetivo. 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 un "and". Los conjuntos alternativos de nodos secundarios correspondientes a formas alternativas de resolver el nodo se agrupan mediante un "or".
Se puede utilizar cualquier estrategia de búsqueda para buscar en este espacio. Prolog utiliza una estrategia secuencial de último en entrar, primero en salir, de retroceso, 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 denominay-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 esté más instanciado o que esté suficientemente instanciado 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 inverso a partir de una consulta o un objetivo es más eficiente que el razonamiento directo. Pero a veces, con la programación de conjuntos de respuestas y registros de datos, puede que no haya ninguna consulta que esté separada del conjunto de cláusulas en su totalidad, y luego generar todos los hechos que se pueden derivar de las cláusulas es una estrategia sensata para la resolución de problemas. Aquí hay otro ejemplo, donde el razonamiento directo supera al razonamiento inverso en una tarea de cálculo más convencional, donde el objetivo ?- fibonacci(n, Result)es encontrar el n -é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 manera redundante el número de Fibonacci de n-2. Este proceso de reducción de un subobjetivo de Fibonacci a dos subobjetivos de Fibonacci continúa hasta que llega a los números 0 y 1. Su complejidad es del orden de 2 n . Por el contrario, el razonamiento hacia delante genera la secuencia de números de Fibonacci, comenzando desde 0 y 1 sin ningún recálculo, y su complejidad es lineal con respecto a n.
Prolog no puede realizar razonamientos directos, pero puede lograr el efecto de razonamiento directo en el contexto de razonamiento inverso mediante la creació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 manera redundante. [27]
La programación lógica puede considerarse 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 solo 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 las funciones anidadas. Por ejemplo, en la sintaxis funcional, la definición de abuela materna se puede escribir en la 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 complemento 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 ( a) ( X ) := padre ( a) ( padre ( a) ( X )). padre ( a ) (X ) := madre ( X ). padre ( a) ( X ) := padre ( a) ( 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 abarcar una variedad de lenguajes de programación que tratan las 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 la lógica de predicados de primer orden.
Otros lenguajes de programación relacional se basan en el cálculo relacional [32] o el á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áusula Horn: un enfoque es la semántica de consecuencia lógica original , que entiende la solución de un objetivo como demostrar que el objetivo es un teorema que es verdadero en todos los modelos del programa.
En este enfoque, el cálculo es una demostración de teoremas en lógica de primer orden ; y tanto el razonamiento inverso , como en la resolución SLD, como el razonamiento directo , como en la hiperresolución, son métodos de demostración de teoremas correctos y completos. A veces, estos métodos de demostración de teoremas también se consideran como una fuente de semántica teórica de demostración (u operacional) independiente para los programas lógicos. Pero desde un punto de vista lógico, son métodos de demostración, más que semántica.
El otro enfoque de la semántica declarativa de los programas con cláusula Horn es la semántica de satisfacibilidad , que entiende que la solución de un objetivo consiste en demostrar que el objetivo es verdadero (o se satisface) en algún modelo previsto (o estándar) del programa. Para los programas con cláusula Horn, siempre existe un modelo estándar de este tipo: es el modelo mínimo único del programa.
Hablando informalmente, un modelo mínimo es un modelo que, cuando se lo considera 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 que se muestra en la introducción de este artículo. Todos los demás hechos sin variables son falsos en el modelo:
madre_hijo ( elizabeth , charles ) . padre_hijo ( charles , william ) . padre_hijo ( charles , harry ). padre_hijo ( elizabeth , charles ) . padre_hijo ( charles , william ). padre_hijo ( charles , harry ). abuelo_hijo ( elizabeth , william ). abuelo_hijo ( 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 paso de inferencia.
Notablemente, 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 consecuencia lógica, son igualmente aplicables a la semántica de satisfacibilidad: el razonamiento hacia adelante genera el modelo mínimo de un programa de cláusula Horn, derivando nuevos hechos de hechos existentes, hasta que no se puedan generar nuevos hechos adicionales. El razonamiento hacia atrás, que tiene éxito al reducir un objetivo a subobjetivos, hasta que todos los subobjetivos se resuelven con hechos, asegura que el objetivo sea verdadero 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 adición y multiplicación en la aritmética de sucesores , 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,es decir X + 1., Aquí están las definiciones estándar de adición 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, utilizando add(X, Y, Z)para representar X + Y = Z,y multiply(X, Y, Z)para representar X × Y = Z:
suma ( X , 0 , X ). suma ( X , s ( Y ), s ( Z )) :- suma ( 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 cuantificadas existencialmente de los objetivos de adición 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 consecuencia lógica existen modelos no estándar del programa, en los que, por ejemplo, add(s(s(0)), s(s(0)), s(s(s(s(s(0)))))),ie 2 + 2 = 5es verdadero. En cambio, en la semántica de satisfacibilidad solo existe un modelo, es decir, el modelo estándar de la 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 consecuencia lógica, el fracaso significa que el valor de verdad del objetivo es desconocido.?- add(s(s(0)), s(s(0)), s(s(s(s(s(0))))))
La negación como fallo (NAF), como forma de concluir que not pse cumple una condición negativa al demostrar 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 denomina SLDNF . Una construcción similar, denominada "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 consecuencia lógica utilizando la finalización de un programa lógico en lógica de primer orden.
La finalización equivale aproximadamente a considerar el conjunto de todas las cláusulas del programa con el mismo predicado en la cabeza, digamos:
A :- Body1. ...A :- Bodyk.como definición del predicado:
A iff (Body1 or ... or Bodyk)donde iffsignifica "si y solo 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 con la compleción del programa.
Consideremos, por ejemplo, el siguiente programa:
should_receive_sanction ( X , castigo ) :- es_un_ladrón ( X ), no should_receive_sanction ( X , rehabilitación ). debería_recibir_sanción ( X , rehabilitación ) :- es_un_ladrón ( X ), es_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 demostrar 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 de hecho menor de edad, la conclusión anterior de que Tom debería ser castigado se reemplaza por la nueva conclusión de que Tom debería 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 nos dicen 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 finalización de este programa es:
should_receive_sanction ( X , Sanción ) si y solo si Sanción = castigo , es_un_ladrón ( X ), no should_receive_sanction ( X , rehabilitación ) o Sanción = rehabilitación , es_un_ladrón ( X ), es_menor ( X ), no es_violento ( X ). es_un_ladrón ( X ) si y solo si X = tom . es_menor ( X ) si y solo si X = tom . es_violento ( X ) si y solo si X = tom .La noción de completitud está estrechamente relacionada con la semántica de circunscripción de John McCarthy para el razonamiento por defecto, [36] y con el supuesto de mundo cerrado de Ray Reiter . [37]
La semántica de completitud para la negación es una semántica de consecuencia lógica, para la cual SLDNF proporciona una implementación basada en la teoría de la prueba. Sin embargo, en la década de 1980, la semántica de satisfacibilidad se hizo más popular para los 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 pretendido de un programa lógico es un modelo único, trivaluado y mínimo, 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 fundada utilizando resolución SLG. [40]
En la semántica de modelos estables alternativos , puede que no haya modelos previstos o que haya varios modelos previstos, todos ellos mínimos y de dos valores. La semántica de modelos estables sustenta la programación de conjuntos de respuestas (ASP).
Tanto la semántica del modelo bien fundamentado como la del modelo estable se aplican a programas de lógica arbitraria con negación. Sin embargo, ambas semánticas coinciden para los 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_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 debería ser rehabilitado y restablece el argumento de que 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 Edinburgh DEC10 incluía "un intérprete y un compilador, ambos escritos en Prolog". [43] El metaprograma más simple es el llamado metaintérprete " vanilla ":
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 predicada (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 tanto como fórmula a nivel de objeto como argumento de los metapredicados prohibitedyapproved.
prohibido ( asiste a ( Persona , Reunión )) :- no ( aprobado ( asiste a ( Persona , Reunión ))).should_receive_sanction ( Persona , regaño ) :- asiste a ( Persona , Reunión ), alto ( Persona ), prohibido ( asiste a ( Persona , Reunión )). should_receive_sanction ( Persona , destierro ) :- asiste a ( Persona , Reunión ), bajo ( Persona ), prohibido ( asiste a ( Persona , Reunión )).aprobado ( asiste ( alicia , fiesta_de_té )). asiste ( sombrerero_loco , fiesta_de_té ). asiste ( lirón , fiesta_de_té ).elevado ( sombrerero loco ). humilde ( lirón ).?- debería_recibir_sanción ( X , Y ). Persona = sombrerero_loco , 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 la lógica y las reglas, sostiene que la lógica utiliza la deducción, pero las reglas utilizan 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 "tienen que interpretarse como universalmente verdaderas ", pero las reglas pueden ser predeterminadas , 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ág. 45). Por ejemplo, "SI quieres ir a casa el fin de semana y tienes dinero para el autobús, ENTONCES puedes coger un autobús". No observa que la misma estrategia de reducir un objetivo a subobjetivos puede interpretarse, a la manera de la programación lógica, como la aplicación del razonamiento inverso a un condicional lógico:
can_go ( tú , casa ) :- have ( tú , bus_fare ), catch ( tú , autobús ).Todas estas características de los sistemas basados en reglas (búsqueda, razonamiento hacia adelante y hacia atrás, razonamiento predeterminado 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) de 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 se puede utilizar el carácter no monótono de los programas lógicos 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 El tratamiento adecuado de los acontecimientos, [46] Michiel van Lambalgen y Fritz Hamm investigan el uso de la programación lógica de restricciones para codificar "nociones temporales en lenguaje natural al observar la forma en que los seres humanos construyen el tiempo".
El uso de la lógica para representar el conocimiento procedimental y la información estratégica fue uno de los principales objetivos que contribuyeron al desarrollo temprano 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 el conocimiento puramente declarativo. Estas aplicaciones incluyen tanto la representación del conocimiento general de sentido común como la representación de la experiencia específica del dominio .
El sentido común incluye el conocimiento sobre causa y efecto, tal como se formaliza, por ejemplo, en el cálculo de situaciones , el cálculo de eventos y los lenguajes de acción . A continuación se presenta un ejemplo simplificado que ilustra las características principales de dichos formalismos. La primera cláusula establece que un hecho se cumple inmediatamente después de que un evento inicia (o causa) el hecho. La segunda cláusula es un axioma marco , que establece que un hecho que se cumple en un momento continúa cumpliéndose en el momento siguiente a menos que sea terminado por un evento que sucede 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 cumple ( Hecho , Tiempo2 ) :- sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , se cumple ( Hecho , Tiempo1 ), no ( terminado ( Hecho , Tiempo1 )).terminado ( Hecho , Tiempo ) :- sucede ( Evento , Tiempo ), termina ( Evento , Hecho ).Aquí holdshay un metapredicado, similar al solveanterior. Sin embargo, mientras que solvetiene solo un argumento, que se aplica a cláusulas generales, el primer argumento de holdses un hecho y el segundo argumento es un tiempo (o estado). La fórmula atómica holds(Fact, Time)expresa que el Factse cumple 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 sucede 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 tiempo 0, el bloque rojo se mueve a la mesa. En el tiempo 1, el bloque verde se mueve sobre el bloque rojo. Mover un objeto a un lugar termina 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 ( bloque_verde , tabla ), 0 ). mantiene ( en ( bloque_rojo , bloque_verde ), 0 ).sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 1 ).inicia ( mover ( Objeto , Lugar ), en ( Objeto , Lugar )). termina ( mover ( Objeto , Lugar2 ), en ( Objeto , Lugar1 )).?- contiene ( Hecho , Tiempo ).Hecho = en ( bloque_verde , mesa ), Tiempo = 0. Hecho = en ( bloque_rojo , bloque_verde ), Tiempo = 0. Hecho = en ( bloque_verde , mesa ), Tiempo = 1. Hecho = en ( bloque_rojo , mesa ), Tiempo = 1. Hecho = en ( bloque_verde , bloque_rojo ), Tiempo = 2. Hecho = en ( bloque_rojo , mesa ), Tiempo = 2.El razonamiento hacia delante y el razonamiento hacia atrás generan las mismas respuestas al objetivo holds(Fact, Time), pero el razonamiento hacia delante genera respuestas fluidas de manera progresiva en orden temporal, y el razonamiento hacia atrás genera respuestas fluidas de manera regresiva , como en el uso específico del dominio de la regresión en el cálculo de situaciones . [47]
La programación lógica también ha demostrado ser útil para representar la experiencia específica de un dominio en sistemas expertos . [48] Pero la experiencia humana, al igual que el sentido común de uso general, es en su mayoría implícita y tácita , y a menudo es difícil representar dicho 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 una 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 ciudadano británico en el momento del nacimiento:
inicia ( nacimiento ( Persona ), ciudadano ( Persona , reino unido )):- hora_de ( nacimiento ( Persona ), Hora ), lugar_de ( nacimiento ( Persona ), reino unido ), padre_hijo ( Otra_Persona , Persona ), sostiene ( ciudadano ( Otra_Persona , reino unido ), Hora ).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 para 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 de 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 SLD es neutral en cuanto al orden en el que se pueden seleccionar subobjetivos en los cuerpos de las cláusulas para su solución. Por razones de eficiencia, Prolog restringe este orden al orden en el que se escriben los subobjetivos. SLD también es neutral en cuanto a la estrategia de búsqueda en el espacio de pruebas SLD. Prolog busca en este espacio, de arriba hacia abajo, en profundidad, probando diferentes cláusulas para resolver el mismo (sub)objetivo en el orden en el que se escriben las cláusulas.
Esta estrategia de búsqueda tiene la ventaja de que la rama actual del árbol se puede representar de manera eficiente 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 , elimina 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 utilizando la siguiente cláusula que coincida con el subobjetivo seleccionado.
El retroceso se puede restringir mediante el uso de un subobjetivo, llamado cut , 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 de cut se puede reemplazar por la negación como falla. De hecho, la negación como falla se puede definir en Prolog, mediante el uso de cut, junto con cualquier literal, digamos fail , que se unifique con el encabezado de la cláusula no:
no ( P ) :- P , !, falla . no ( P ).Prolog ofrece otras funciones, además de la función de corte, que no tienen una interpretación lógica. Entre ellas se incluyen los predicados integrados assert y retract para actualizar de forma destructiva el estado del programa durante su ejecución.
Por ejemplo, el ejemplo del mundo de bloques de juguete anterior se puede implementar sin axiomas de marco utilizando un cambio de estado destructivo:
en ( bloque_verde , tabla ). en ( 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 , mesa ), 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 programación lógica para proporcionar un marco lógico para ese cambio de estado destructivo. [53] [54] [55]
La amplia gama de aplicaciones de 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 cláusulas de Horn con la resolución de restricciones . Extiende 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 de modelo específica del dominio.
En términos procedimentales, 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 comprueba su satisfacibilidad mediante un solucionador de restricciones específico del dominio, que implementa la semántica de los predicados de las restricciones. Un problema inicial se resuelve reduciéndolo a una conjunción de restricciones satisfacibles.
Curiosamente, la primera versión de Prolog ya incluía un predicado de restricción dif(term1, term2), de la tesis doctoral de Philippe Roussel de 1972, que tiene éxito si ambos argumentos son términos diferentes, pero que se retrasa si alguno 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 docente:
enseña ( juan , hardware , T ) :- 1990 ≤ T , T < 1999. enseña ( juan , software , T ) :- 1999 ≤ T , T < 2005. enseña ( juan , lógica , T ) :- 2005 ≤ T , T ≤ 2012. rango ( juan , instructor , T ) :- 1990 ≤ T , T < 2010. rango ( juan , profesor , T ) :- 2010 ≤ T , T < 2014.Aquí ≤y <son predicados de restricción, con su semántica prevista habitual. La siguiente cláusula de objetivo consulta la base de datos para averiguar cuándo johnse enseñó logicy se usó professor:
?- enseña ( juan , lógica , T ), rango ( juan , 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 planificación automatizada de horarios , el control del tráfico aéreo y las finanzas. Está estrechamente relacionada 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 conectores lógicos, como o , y y no, en los cuerpos de reglas para definir relaciones como parte de la base de datos en sí.
Se reconoció temprano en el desarrollo de bases de datos relacionales que las consultas recursivas no se pueden expresar ni en álgebra relacional ni en cálculo relacional, y que esta deficiencia se puede remediar introduciendo un operador de punto mínimo fijo. [56] [57] Por el contrario, las relaciones recursivas se pueden definir de forma natural mediante reglas en programas lógicos, sin 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 son libres de variables y las reglas están restringidas, de modo que si se ejecutan de abajo hacia arriba, los hechos derivados también son libres de variables.
Por ejemplo, consideremos la base de datos familiar:
madre_hijo ( 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 ). antepasado_descendiente ( X , Y ) :- antepasado_descendiente ( X , X ). antepasado_descendiente ( X , Y ) :- antepasado_descendiente ( X , Z ), antepasado_descendiente ( Z , Y ).La ejecución de abajo hacia arriba deriva el siguiente conjunto de hechos adicionales y finaliza:
padre_hijo ( elizabeth , charles ). padre_hijo ( charles , william ). padre_hijo ( charles , harry ).antepasado_descendiente ( elizabeth , charles ). antepasado_descendiente ( charles , william ). antepasado_descendiente ( charles , harry ).antepasado_descendiente ( elizabeth , william ). antepasado_descendiente ( elizabeth , harry ).La ejecución de arriba hacia abajo deriva las mismas respuestas a la consulta:
?- ancestro_descendiente ( X , Y ).Pero luego entra en un bucle infinito. Sin embargo, la ejecución descendente con tabulación proporciona las mismas respuestas y finaliza sin bucle.
Al igual que Datalog, la programación de conjuntos de respuestas (ASP) no es Turing-completa. 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 lo convierte en 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 coloración de 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, necesitamos agregar una restricción que indique que dos países adyacentes no pueden tener el 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 solo tiene 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 los modelos en los que Bodyes verdadero.
De manera confusa, las restricciones en ASP son diferentes a 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 cumplirían los 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 se llevan a cabo en dos pasos: primero, instancian el programa de todas las formas posibles, reduciéndolo a un programa de lógica proposicional (conocido como puesta a tierra ). Luego, aplican un solucionador de problemas de lógica proposicional, como el algoritmo DPLL o un solucionador SAT booleano . Sin embargo, algunas implementaciones, como s(CASP) [59], utilizan un procedimiento de resolución SLD, descendente y dirigido por objetivos sin puesta a tierra.
La programación lógica abductiva [60] (ALP), al igual que la 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 como abducibles (o asumibles ) y se utilizan como en el razonamiento abductivo para explicar observaciones o, de manera más general, 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 momento 0:
mantiene ( en ( bloque_verde , tabla ), 0 ). mantiene ( en ( bloque_rojo , bloque_verde ), 0 ).Supongamos que también se nos da el objetivo:
?- contiene ( en ( bloque_verde , bloque_rojo ), 3 ), contiene ( 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 puede representar un estado de cosas futuro deseado, en cuyo caso una solución es un plan para alcanzar el objetivo. [61]
Podemos utilizar 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 cumple ( Hecho , Tiempo2 ) :- sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , se cumple ( Hecho , Tiempo1 ), no ( terminado ( Hecho , Tiempo1 )). terminado ( Hecho , Tiempo ) :- sucede ( Evento , Tiempo ), 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 añadiendo suposiciones al programa para resolver subobjetivos abducibles. En este caso, existen muchas soluciones alternativas, entre ellas:
sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( marcar , 1 ). sucede ( mover ( bloque_verde , bloque_rojo ), 2 ).sucede ( tick , 0 ). sucede ( mover ( bloque_rojo , tabla ), 1 ). sucede ( mover ( bloque_verde , bloque_rojo ), 2 ).sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 1 ). sucede ( marcar , 2 ).He aquí tickun acontecimiento que marca el paso del tiempo sin iniciar ni finalizar ningún fluido.
También existen soluciones en las que los dos moveeventos ocurren al mismo tiempo. Por ejemplo:
sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 0 ). sucede ( tic , 1 ). sucede ( tic , 2 ).Si no se desean estas soluciones, se pueden eliminar añadiendo una restricción de integridad, que es como una cláusula de restricción en ASP:
:- sucede ( mover ( Bloque1 , Lugar ), Tiempo ), sucede ( mover ( Bloque2 , Bloque1 ), Tiempo ).La programación lógica abductiva se ha utilizado para el diagnóstico de fallos, la planificación, el procesamiento del lenguaje natural y el aprendizaje automático. También se ha utilizado para interpretar la negación como un fallo como una 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 el conocimiento previo 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.
El ILP es similar al ALP, en el sentido de que ambos pueden ser vistos como generadores de hipótesis para explicar observaciones y como aplicadores de restricciones para excluir hipótesis indeseables. Pero en el ALP las hipótesis son hechos libres de variables, y en el ILP las hipótesis son reglas generales. [63] [64]
Por ejemplo, dado solo el conocimiento de fondo 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 una IA de nivel humano.
Trabajos recientes en ILP, que combinan programación lógica, aprendizaje y probabilidad, han 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 por su elección como 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 denomina protección de la cláusula y | es el operador de compromiso. Declarativamente, las cláusulas de Horn protegidas se leen como implicaciones lógicas ordinarias:G1, ... , Gn
H if G1 and ... and Gn and B1 and ... and Bn.Sin embargo, desde el punto de vista procedimental, cuando hay varias cláusulas cuyos encabezados Hcoinciden con un objetivo determinado, todas las cláusulas se ejecutan en paralelo, comprobando si se cumplen sus requisitos. Si se cumplen los requisitos de más de una cláusula, 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 tanto, la programación lógica concurrente implementa una forma de "no determinismo de no importar", en lugar de "no determinismo de no saber".G1, ... , GnB1, ..., Bn
Por ejemplo, el siguiente programa de lógica concurrente define un predicado shuffle(Left, Right, Merge), que se puede usar para mezclar dos listas Lefty Right, combinándolas en una sola lista Mergeque preserva el orden de las dos listas Lefty Right:
shuffle ([], [], []). shuffle ( Izquierda , Derecha , Fusionar ) :- Izquierda = [ Primero | Resto ] | Fusionar = [ Primero | Fusión corta ], shuffle ( Resto , Derecha , Fusión corta ). shuffle ( Izquierda , Derecha , Fusionar ) :- Derecha = [ Primero | Resto ] | Fusionar = [ Primero | Fusión corta ], shuffle ( Izquierda , Resto , Fusión corta ).Aquí, []representa la lista vacía y [Head | Tail]representa una lista con el primer elemento Headseguido de lista Tail, como en Prolog. (Observe que la primera aparición de | en la segunda y tercera cláusulas 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 mezclar las listas [ace, queen, king]e [1, 4, 2]invocando la cláusula de objetivo:
barajar ([ as , reina , rey ], [ 1 , 4 , 2 ], Combinar ).El programa generará de forma no determinista una única solución, por ejemplo Merge = [ace, queen, 1, king, 4, 2].
Carl Hewitt ha argumentado [68] que, debido a la indeterminación del cálculo concurrente , la programación lógica concurrente no puede implementar la concurrencia general. Sin embargo, de acuerdo con 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 se puedan derivar todas las consecuencias lógicas.
La programación lógica con restricciones concurrentes [69] combina la programación lógica concurrente y la programación lógica con restricciones , utilizando 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 protecciones de varias cláusulas, la programación lógica con restricciones concurrentes toma la decisión de utilizar solo una.
Varios investigadores han ampliado 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 en 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 aquellos basados en la lógica clásica. Los programas con cláusula Horn solo pueden representar cambios de estado mediante el cambio de argumentos a predicados. En la programación 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] extiende la programación lógica con objetos y la sintaxis de marco.
Logtalk [77] amplía el lenguaje de programación Prolog con compatibilidad con objetos, protocolos y otros conceptos de programación orientada a objetos. Es compatible con la mayoría de los sistemas Prolog compatibles con el estándar como compiladores backend.
La lógica transaccional [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 teórica como procedimental. Una implementación de un subconjunto de la lógica transaccional está disponible en el sistema Flora-2 [78] . También hay otros prototipos disponibles .
{{cite journal}}: CS1 maint: DOI inactivo a partir de septiembre de 2024 ( enlace )