Programación lógica

La interpretación procedimental de programas lógicos, que utiliza el razonamiento regresivo 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 y obtener así el comportamiento de un algoritmo . De forma 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 dada utilizando diferentes representaciones lógicas. ^{[ 23 ]}

Las dos estrategias principales para la resolución de problemas son el razonamiento hacia atrás (reducción de objetivos) y el razonamiento hacia adelante , también conocidos como razonamiento descendente y ascendente, respectivamente.

En el caso simple de un programa de cláusulas proposicionales de Horn y un objetivo atómico de nivel superior, el razonamiento hacia atrás determina un árbol "y-o" , 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 hijos que corresponden a los subobjetivos en el cuerpo de la cláusula. Estos nodos hijos se agrupan mediante un "y". Los conjuntos alternativos de hijos que corresponden a formas alternativas de resolver el nodo se agrupan mediante un "o".

Se puede utilizar cualquier estrategia de búsqueda para explorar este espacio. Prolog utiliza una estrategia secuencial, de último en entrar, primero en salir, con retroceso, en la que solo se considera 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 en paralelo y la segunda estrategia se llamao en paralelo . También son posibles otras estrategias de búsqueda, como el retroceso inteligente, ^{[ 24 ]} o la búsqueda primero en amplitud para encontrar una solución óptima, ^{[ 25 ]} .

En el caso más general y 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 hacia atrás a partir de una consulta u objetivo es más eficiente que el razonamiento hacia adelante. Sin embargo, a veces, con Datalog y la Programación de Conjuntos de Respuestas, puede que no exista una consulta independiente del conjunto de cláusulas en su totalidad, y entonces generar todos los hechos que se pueden derivar de las cláusulas es una estrategia sensata para la resolución de problemas. He aquí otro ejemplo, donde el razonamiento hacia adelante supera al razonamiento hacia atrás en una tarea de cálculo más convencional, cuyo 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 ), Resultado es F1 + F2 .

Aquí la relación fibonacci(N, M)representa la función fibonacci(N) = M, y el predicado N is Expressiones la notación de 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 redundantemente el número de Fibonacci de n-2. Este proceso de reducir 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 ⁿ . En contraste, el razonamiento hacia adelante 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 razonamiento hacia adelante directamente. Sin embargo, puede lograr el efecto del razonamiento hacia adelante dentro del contexto del razonamiento hacia atrás mediante el uso de tablas : los subobjetivos se almacenan 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 resolver los subobjetivos de forma redundante. ^{[ 27 ]}

La programación lógica puede considerarse 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 una sola 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 las funciones como relaciones.

En comparación con la sintaxis relacional, la sintaxis funcional es más compacta para 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 su forma plana y sin anidar:

abuela_materna ( X , Y ) :- madre ( X , Z ), madre ( Z , Y ).

Sin embargo, la sintaxis anidada puede considerarse 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 puede utilizarse 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 abarcar diversos 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 lógica de predicados de primer orden.

Otros lenguajes de programación relacionales 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 de lógica de cláusulas de Horn: un enfoque es la semántica de consecuencia lógica original , que entiende que resolver un objetivo es demostrar que el objetivo es un teorema que es verdadero en todos los modelos del 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 de demostración de teoremas correctos y completos. A veces, estos métodos de demostración de teoremas también se consideran como una semántica teórica de la demostración (u operacional) independiente para los programas lógicos. Pero desde un punto de vista lógico, son métodos de demostración, no semántica.

El otro enfoque para la semántica declarativa de los programas de cláusulas de Horn es la semántica de satisfacibilidad , que entiende la resolución de un objetivo como la demostración de que dicho objetivo es verdadero (o satisfecho) en algún modelo previsto (o estándar) del programa. Para los programas de cláusulas de Horn, siempre existe tal modelo estándar: es el único modelo mínimo del programa.

En términos informales, un modelo mínimo es un modelo que, cuando se considera como el conjunto de todos los hechos (libres de variables) que son verdaderos en el modelo, no contiene ningún 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 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 fijo mínimo 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, desarrollados originalmente para la semántica de la consecuencia lógica, son igualmente aplicables a la semántica de la satisfacibilidad: el razonamiento hacia adelante genera el modelo mínimo de un programa de cláusulas de Horn, derivando nuevos hechos a partir de hechos existentes, hasta que no se puedan generar nuevos hechos adicionales. El razonamiento hacia atrás, que tiene éxito reduciendo un objetivo a subobjetivos, hasta que todos los subobjetivos se resuelven mediante hechos, garantiza 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 observar con las definiciones de suma 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 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 en un programa lógico, usando add(X, Y, Z)para representar X + Y = Z,y multiply(X, Y, Z)para representar X × Y = Z:

agregar ( 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 cuantificadas existencialmente 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, con la semántica de consecuencias lógicas, 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)))))),es 2 + 2 = 5verdadero. Pero con la semántica de satisfacibilidad, solo hay un modelo, a saber, 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 fallo del objetivo implica que su valor de verdad es falso. En cambio, en la semántica de consecuencia lógica, el fallo implica 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 fallo (NAF), como forma de concluir que una condición negativa not pse cumple demostrando 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 no se resolvió 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 completitud equivale aproximadamente a considerar el conjunto de todas las cláusulas del programa con el mismo predicado en la cabecera, por ejemplo:

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 deductivo natural con la compleción del programa.

Consideremos, por ejemplo, el siguiente programa:

should_receive_sanction ( X , punishment ) :- is_a_thief ( X ), not should_receive_sanction ( X , rehabilitation ).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 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 deba ser rehabilitado. No se puede demostrar que Tom deba ser rehabilitado porque no se puede demostrar que sea menor de edad.

Sin embargo, si recibimos nueva información que confirma que Tom es 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:

es_un_menor ( tom ).?- debería_recibir_sanción ( tom , Sanción ). Sanción = rehabilitación .

Esta propiedad de retractarse de una conclusión cuando se agrega nueva información se llama no monotonicidad, 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:

es_violento ( tom ).?- debería_recibir_sanción ( tom , Sanción ). Sanción = castigo .

La finalización de este programa es:

debería_recibir_sanción ( X , Sanción ) si y solo 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 solo si X = tom . es_un_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 la suposición 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 teórica de la demostración. Sin embargo, en la década de 1980, la semántica de satisfacibilidad se popularizó para los programas lógicos con negación. En la semántica de satisfacibilidad, la negación se interpreta según la definición clásica de verdad en un modelo estándar o previsto 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 y trivalente, 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 la resolución SLG. ^{[ 40 ]}

En la semántica de modelos estables alternativos , puede que no existan modelos previstos o que haya varios, todos ellos mínimos y bivaluados. La semántica de modelos estables es la base de la programación de conjuntos de respuestas (ASP).

Tanto la semántica de modelo bien fundamentada como la estable se aplican a programas lógicos arbitrarios con negación. Sin embargo, ambas semánticas coinciden para programas lógicos estratificados . Por ejemplo, el programa para sancionar a los ladrones es estratificado (localmente), y las tres semánticas para el 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 abstractos . ^{[ 41 ]} En una interpretación argumentativa de la negación, el argumento inicial de que Tom debe ser castigado porque es un ladrón, es atacado por el argumento de que debe ser rehabilitado porque es menor de edad. Pero el hecho de que Tom sea violento socava el argumento de que Tom debe ser rehabilitado y restablece el argumento de que Tom debe 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 DEC10 de Prolog de Edimburgo 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 predicativa (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 metaloló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 a nivel meta, como en el lenguaje natural. Por ejemplo, en el siguiente programa, la fórmula atómica attends(Person, Meeting)aparece tanto como una fórmula a nivel de objeto 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ño ) :- asiste ( Persona , Reunión ), altivo ( 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 ( dormouse , tea_party ).altivo ( 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. Argumenta que las reglas, que tienen la forma SI condición ENTONCES acción , son "muy similares" a las condicionales lógicas, 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, mientras que las reglas utilizan la búsqueda (página 45) y pueden usarse para razonar tanto hacia adelante como 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 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, al estilo de la programación lógica, como la aplicación de un razonamiento inverso a una condición lógica:

can_go ( tú , casa ) :- have ( tú , tarifa_autobús ), catch ( 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— son también 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 de forma natural 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.

Otros argumentos que demuestran cómo la programación lógica puede utilizarse para modelar aspectos del pensamiento humano son presentados por Keith Stenning y Michiel van Lambalgen 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 diversas tareas psicológicas. También demuestran (página 237) que «el razonamiento de mundo cerrado, bajo la 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 eventos, ^{[ 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 observando 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 impulsaron el desarrollo inicial de la programación lógica. Además, sigue siendo una característica importante de la familia de lenguajes de programación lógica Prolog en la actualidad. Sin embargo, muchas aplicaciones de la programación lógica, incluidas las de Prolog, se centran cada vez más en el uso de la lógica para representar conocimiento puramente declarativo. Estas aplicaciones abarcan tanto la representación del conocimiento general de sentido común como la representación de la experiencia específica de un dominio .

El sentido común incluye el conocimiento de causa y efecto, formalizado, por ejemplo, en el cálculo de situaciones , el cálculo de eventos y los lenguajes de acción . He aquí 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 lo inicie (o lo cause). La segunda cláusula es un axioma de marco , que establece que un hecho que se cumple en un momento dado continúa cumpliéndose en el siguiente momento a menos que sea terminado por un evento que ocurra en ese momento. Esta formulación permite que ocurran varios eventos simultáneamente.

contiene ( Hecho , Tiempo2 ) :- sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , inicia ( Evento , Hecho ).contiene ( Hecho , Tiempo2 ) :- sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , contiene ( 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 las 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. Tales hechos que varían en el tiempo también se llaman fluentes . La fórmula atómica happens(Event, Time)expresa que el Evento ocurre en el Time.

El siguiente ejemplo ilustra cómo se pueden usar 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.

contiene ( en ( green_block , tabla ), 0 ). contiene ( en ( red_block , green_block ), 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 )).?- sostiene ( Hecho , Tiempo ).Hecho = en ( green_block , tabla ), Tiempo = 0. Hecho = en ( red_block , green_block ), Tiempo = 0. Hecho = en ( green_block , tabla ), Tiempo = 1. Hecho = en ( red_block , tabla ), Tiempo = 1. Hecho = en ( green_block , red_block ), Tiempo = 2. Hecho = en ( red_block , 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 hacia adelante genera fluentes progresivamente en orden temporal, y el razonamiento hacia atrás los genera regresivamente , 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 el conocimiento especializado en sistemas expertos . ^{[ 48 ]} Pero el conocimiento humano, al igual que el sentido común general, es mayormente implícito y tácito , y a menudo resulta 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 autoridad legal.

Por ejemplo, aquí se muestra una versión simplificada de la primera frase de la Ley de Nacionalidad Británica, que establece que una persona nacida en el Reino Unido se convierte en ciudadano británico en el momento del nacimiento si uno de sus padres es ciudadano británico en ese momento:

inicia ( nacimiento ( Persona ), ciudadano ( Persona , uk )):- hora_de ( nacimiento ( Persona ), Hora ), lugar_de ( nacimiento ( Persona ), uk ), padre_hijo ( Otra_Persona , Persona ), sostiene ( ciudadano ( Otra_Persona , uk ), 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 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 resolución de inferencia SLD es neutral respecto al orden en que se pueden seleccionar los subobjetivos en los cuerpos de las 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 es neutral respecto a la estrategia para buscar 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 que se escriben 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 objetivo en la parte superior de la pila se reduce a una nueva cláusula objetivo, esta nueva cláusula se coloca en la parte superior de la pila. Si no se puede resolver el subobjetivo seleccionado en la cláusula objetivo en la parte superior de la pila, la estrategia de búsqueda retrocede , eliminando la cláusula objetivo de la parte superior de la pila y volviendo a intentar la solución del subobjetivo seleccionado en la cláusula objetivo anterior utilizando la siguiente cláusula que coincida con el subobjetivo seleccionado.

El retroceso puede restringirse mediante el uso de un subobjetivo, llamado `cut` , escrito como  `!`, que siempre tiene éxito pero no permite el retroceso. `cut` puede usarse 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` puede reemplazarse por la negación como fallo. De hecho, la negación como fallo puede definirse en Prolog, usando `cut` junto con cualquier literal, por ejemplo `fail` , que se unifique con el núcleo de la cláusula `no`:

no ( P ) :- P , !, falla . no ( P ).

Prolog ofrece otras funciones, además de `cut`, que no tienen una interpretación lógica. Entre ellas se incluyen los predicados integrados `assert` y `retract`, que permiten 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 la programación lógica para proporcionar un marco lógico para dicho 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 Year of Prolog, ^{[ 21 ]} que celebra el 50 aniversario de Prolog en 2022.

Prolog también ha contribuido al desarrollo de otros lenguajes de programación, como ALF , Fril , Gödel , Mercury , Oz , Ciao , Visual Prolog , XSB y λProlog .

La programación lógica con restricciones (PLC) combina la programación lógica con cláusulas de Horn con la resolución de restricciones . Extiende las cláusulas de Horn permitiendo que ciertos predicados, declarados como predicados de restricción, aparezcan como literales en el cuerpo de una cláusula. Los predicados de restricción no se definen mediante los hechos y las reglas del programa, sino que están predefinidos por alguna estructura o teoría de modelos 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 convencional, 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 restricción. Un problema inicial se resuelve reduciéndolo a una conjunción satisfacible 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 alguno de los términos contiene una variable. ^{[ 52 ]}

El siguiente programa de lógica de restricciones representa una base de datos temporal de john'shistoria de juguete que actúa 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 <son predicados de restricción, con su semántica habitual prevista. La siguiente cláusula de objetivo consulta la base de datos para averiguar cuándo johnse enseñó logicy fue un professor:

?- enseña ( john , lógica , T ), rango ( john , profesor , T ).

La solución 2010 ≤ T, T ≤ 2012 resulta de simplificar las restricciones. 2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.

La programación lógica con 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 elaboració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 visión relacional de los datos, como en las bases de datos relacionales , con una visión 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 la base de datos. Datalog utiliza conectores lógicos como OR y NOT en el cuerpo de las reglas para definir relaciones como parte de la propia base de datos.

Se reconoció desde el principio del desarrollo de las bases de datos relacionales que las consultas recursivas no pueden expresarse ni en álgebra relacional ni en cálculo relacional, y que esta deficiencia puede subsanarse introduciendo un operador de punto fijo mínimo. ^{[ 56 ] [ 57 ]} En cambio, las relaciones recursivas pueden definirse de forma natural mediante reglas en programas lógicos, sin necesidad de nuevos conectores u operadores lógicos.

Datalog se diferencia de la programación lógica más general al utilizar únicamente 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, 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 ). ancestro_descendiente ( X , Y ) :- padre_hijo ( X , X ). ancestro_descendiente ( X , Y ) :- ancestro_descendiente ( X , Z ), ancestro_descendiente ( Z , Y ).

La ejecución ascendente obtiene 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 obtiene las mismas respuestas a la consulta:

?- ancestro_descendiente ( X , Y ).

Pero entonces entra en un bucle infinito. Sin embargo, la ejecución de arriba hacia abajo con tabulación da las mismas respuestas y termina 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 hace 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 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 impida que dos países adyacentes tengan 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 tiene solo 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.

Resulta confuso que las restricciones en ASP sean diferentes de las restricciones en CLP . En CLP, las restricciones son predicados que califican las respuestas a las consultas (y las soluciones a los objetivos). En ASP, las restricciones son cláusulas que eliminan modelos que, de otro modo, satisfarían los objetivos. Las restricciones en ASP son similares a las restricciones de integridad en las bases de datos.

Esta combinación de cláusulas de programación lógica ordinarias y cláusulas de restricción ilustra la metodología de generación y prueba para la 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, instancian el programa de todas las maneras posibles, reduciéndolo a un programa de lógica proposicional (conocido como puesta en 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 orientado a objetivos, sin puesta en tierra.

La programación lógica abductiva ^{[ 60 ]} (ALP), al igual que la programación lógica condicional (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 presumibles ) y se utilizan, como en el razonamiento abductivo, para explicar observaciones o, de forma más general, para añadir nuevos hechos al programa (como supuestos) para resolver objetivos.

Por ejemplo, supongamos que se nos da un estado inicial en el que un bloque rojo está sobre un bloque verde sobre una mesa en el instante 0:

contiene ( en ( green_block , tabla ), 0 ). contiene ( en ( red_block , green_block ), 0 ).

Supongamos que también se nos da el siguiente 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 dicha observación. O bien, el objetivo puede representar un estado futuro deseado, en cuyo caso una solución es un plan para alcanzar dicho objetivo. ^{[ 61 ]}

Podemos utilizar las reglas de causa y efecto presentadas anteriormente para resolver el objetivo, tratando el happenspredicado como abducible:

contiene ( Hecho , Tiempo2 ) :- sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , inicia ( Evento , Hecho ).contiene ( Hecho , Tiempo2 ) :- sucede ( Evento , Tiempo1 ), Tiempo2 es Tiempo1 + 1 , contiene ( 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 supuestos al programa para resolver subobjetivos abducibles. En este caso, existen muchas soluciones alternativas, entre ellas:

sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( tick , 1 ). sucede ( mover ( bloque_verde , bloque_rojo ), 2 ).

sucede ( tick , 0 ). sucede ( move ( red_block , table ), 1 ). sucede ( move ( green_block , red_block ), 2 ).

sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 1 ). sucede ( tick , 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 ambos moveeventos ocurren simultáneamente. Por ejemplo:

sucede ( mover ( bloque_rojo , tabla ), 0 ). sucede ( mover ( bloque_verde , bloque_rojo ), 0 ). sucede ( tick , 1 ). sucede ( tick , 2 ).

Si no se desean dichas soluciones, se pueden eliminar añadiendo una restricción de integridad, que es similar a 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 (PLI) es un enfoque de aprendizaje automático que genera 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 de PLI genera un programa lógico que generaliza los ejemplos positivos y excluye los negativos.

La PLI es similar a la PLA, ya que ambas pueden considerarse generadoras de hipótesis para explicar las observaciones y empleando restricciones para excluir hipótesis indeseables. Sin embargo, en la PLA las hipótesis son hechos independientes de variables, mientras que en la PLI son reglas generales. ^{[ 63 ] [ 64 ]}

Por ejemplo, dado únicamente 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 dicha invención de nuevos conceptos como el paso más importante necesario para alcanzar la IA a nivel humano.

Los trabajos recientes en programación lógica inductiva (PLI), 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 al ser elegida como lenguaje de programación de sistemas del Proyecto de Quinta Generación japonés (FGCS) . ^{[ 67 ]}

Un programa lógico concurrente es un conjunto de cláusulas de Horn protegidas de la forma:

H :- G1, ..., Gn | B1, ..., Bn.

La conjunción se denomina guardia de la cláusula, y | es el operador de compromiso. Declarativamente, las cláusulas de Horn con guardia 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 varias cláusulas tienen como cabeza Hun objetivo determinado, todas se ejecutan en paralelo, comprobando si sus condiciones se cumplen. Si se cumplen las condiciones de más de una cláusula, se elige una de ellas y la ejecución continúa con los subobjetivos de la cláusula seleccionada. Estos subobjetivos también pueden ejecutarse en paralelo. De este modo, la programación lógica concurrente implementa una forma de "no determinismo indiferente", en lugar de un "no determinismo desconocido".G1, ... , GnB1, ..., Bn

Por ejemplo, el siguiente programa lógico concurrente define un predicado shuffle(Left, Right, Merge)que puede usarse para mezclar dos listas Lefty Right, combinándolas en una sola lista Mergeque conserva el orden de las dos listas Lefty Right:

shuffle([],[],[]).shuffle(Left,Right,Merge):-Left=[First|Rest]|Merge=[First|ShortMerge],shuffle(Rest,Right,ShortMerge).shuffle(Left,Right,Merge):-Right=[First|Rest]|Merge=[First|ShortMerge],shuffle(Left,Rest,ShortMerge).

Here, [] represents the empty list, and [Head | Tail] represents a list with first element Head followed by list Tail, as in Prolog. (Notice that the first occurrence of | in the second and third clauses is the list constructor, whereas the second occurrence of | is the commitment operator.) The program can be used, for example, to shuffle the lists [ace, queen, king] and [1, 4, 2] by invoking the goal clause:

shuffle([ace,queen,king],[1,4,2],Merge).

The program will non-deterministically generate a single solution, for example Merge = [ace, queen, 1, king, 4, 2].

Carl Hewitt has argued^[68] that, because of the indeterminacy of concurrent computation, concurrent logic programming cannot implement general concurrency. However, according to the logical semantics, any result of a computation of a concurrent logic program is a logical consequence of the program, even though not all logical consequences can be derived.

Concurrent constraint logic programming^[69] combines concurrent logic programming and constraint logic programming, using constraints to control concurrency. A clause can contain a guard, which is a set of constraints that may block the applicability of the clause. When the guards of several clauses are satisfied, concurrent constraint logic programming makes a committed choice to use only one.

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 de 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 considerablemente más expresivos que los basados ​​en la lógica clásica. Los programas de cláusulas de Horn solo pueden representar el cambio de estado mediante el cambio de argumentos de los predicados. En la programación lógica lineal, se puede utilizar la lógica lineal ambiental para admitir el cambio de estado. Algunos diseños iniciales de lenguajes de programación lógica basados ​​en la lógica lineal incluyen LO, ^{[ 72 ]} Lolli, ^{[ 73 ]} ACL, ^{[ 74 ]} y Forum. ^{[ 75 ]} Forum proporciona una interpretación orientada a objetivos de toda la lógica lineal.

F-logic ^{[ 76 ]} extiende la programación lógica con objetos y la sintaxis de marcos.

Logtalk ^{[ 77 ]} extiende el lenguaje de programación Prolog con soporte para objetos, protocolos y otros conceptos de POO. Es compatible con la mayoría de los sistemas Prolog que cumplen con el estándar como compiladores de 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. Posee una semántica tanto de teoría de modelos como procedimental. Una implementación de un subconjunto de la lógica transaccional está disponible en el sistema Flora-2 ^{[ 78 ]} . También existen otros prototipos .

• Baral, C.; Gelfond, M. (1994). "Programación lógica y representación del conocimiento" (PDF) . The Journal of Logic Programming . 19–20 : 73–148 . doi : 10.1016/0743-1066(94)90025-6 .
• Kowalski, RA (1988). "Los primeros años de la programación lógica" (PDF) . Communications of the ACM . 31 : 38–43 . doi : 10.1145/35043.35046 . S2CID 12259230 . 
• Lloyd, JW (1987). Fundamentos de la programación lógica (2ª  ed.). Springer-Verlag.

• John McCarthy. "Programas con sentido común" . Simposio sobre la mecanización de los procesos de pensamiento . Laboratorio Nacional de Física. Teddington, Inglaterra. 1958.
• Miller, Dale; Nadathur, Gopalan; Pfenning, Frank; Scedrov, Andre (1991). "Pruebas uniformes como fundamento para la programación lógica" . Annals of Pure and Applied Logic . 51 ( 1–2 ): 125–157 . doi : 10.1016/0168-0072(91)90068-W .
• Ehud Shapiro (Editor). Prólogo concurrente . MIT Press. 1987.
• James Slagle. "Experimentos con un programa deductivo de preguntas y respuestas" . CACM. Diciembre de 1965.
• Gabbay, Dov M.; Hogger, Christopher John; Robinson, JA, eds. (1993–1998). Manual de lógica en inteligencia artificial y programación lógica . Vols. 1–5, Oxford University Press.