Sintaxis y semántica de la programación lógica

La programación lógica es un paradigma de programación que incluye lenguajes basados ​​en lógica formal, entre los que se incluyen Datalog y Prolog . Este artículo describe la sintaxis y la semántica del subconjunto puramente declarativo de estos lenguajes. El nombre "programación lógica" también hace referencia, de manera confusa, a un lenguaje de programación específico que corresponde aproximadamente al subconjunto declarativo de Prolog. Lamentablemente, en este artículo el término debe utilizarse en ambos sentidos.

Los programas de lógica declarativa consisten enteramente en reglas de la forma

B1  , ... , BN .​   

Cada una de estas reglas puede leerse como una implicación :

${\displaystyle B_{1}\land \ldots \land B_{n}\rightarrow H}$

Significado "Si cada una es verdadera, entonces es verdadera". Los programas lógicos calculan el conjunto de hechos que implican sus reglas. $Estilo de visualización B_{i}}$${\estilo de visualización H}$

Muchas implementaciones de Datalog, Prolog y lenguajes relacionados agregan características procedimentales como el operador de corte de Prolog o características extralógicas como una interfaz de función externa . La semántica formal de dichas extensiones está fuera del alcance de este artículo.

Datalog es el lenguaje de programación lógica más simple y ampliamente estudiado. Existen tres definiciones principales de la semántica de Datalog y todas son equivalentes. La sintaxis y la semántica de otros lenguajes de programación lógica son extensiones y generalizaciones de las de Datalog.

Un programa Datalog consta de una lista de reglas ( cláusulas de Horn ). ^[1] Si constante y variable son dos conjuntos contables de constantes y variables respectivamente y relación es un conjunto contable de símbolos de predicado , entonces la siguiente gramática BNF expresa la estructura de un programa Datalog:

< programa >  ::=  < regla >  < programa > | ""
 < regla >  ::=  < átomo > ":-" < lista-átomos > "."
 < átomo >  ::=  < relación > "(" < lista-términos > ")"
 < lista-átomos >  ::=  < átomo > | < átomo > "," < lista-átomos > | ""
 < término >  ::=  < constante > | < variable > 
< lista-términos >  ::=  < término > | < término > "," < lista-términos > | ""

Los átomos también se conocen como literales . El átomo a la izquierda del :-símbolo se denomina cabeza de la regla; los átomos a la derecha son el cuerpo . Todo programa Datalog debe satisfacer la condición de que cada variable que aparece en la cabeza de una regla también aparezca en el cuerpo (esta condición a veces se denomina restricción de rango ). ^{[1] [2]}

Las reglas con cuerpos vacíos se denominan hechos . Por ejemplo, la siguiente regla es un hecho:

y ( x )  :-  .

Muchas implementaciones de programación lógica extienden la gramática anterior para permitir escribir hechos sin :-, de la siguiente manera:

r ( x ).

Muchos también permiten escribir relaciones 0-arias sin paréntesis, de la siguiente manera:

p  :-  q .

Éstas son simplemente abreviaturas ( azúcar sintáctica ); no tienen ningún impacto en la semántica del programa.

El siguiente programa calcula la relación path, que es el cierre transitivo de la relación edge.

borde ( x ,  y ). 
borde ( y ,  z ). 
ruta ( A ,  B )  :-  
  borde ( A ,  B ). 
ruta ( A ,  C )  :-  
  ruta ( A ,  B ),  
  borde ( B ,  C ).

Existen tres enfoques ampliamente utilizados para la semántica de los programas Datalog: teoría de modelos , punto fijo y teoría de pruebas . Se puede demostrar que estos tres enfoques son equivalentes. ^[3]

Un átomo se denomina fundamental si ninguno de sus subtérminos es variable. Intuitivamente, cada una de las semánticas define el significado de un programa como el conjunto de todos los átomos fundamentales que se pueden deducir de las reglas del programa, a partir de los hechos.

Una regla se denomina fundamental si todos sus átomos (cabeza y cuerpo) son fundamentales. Una regla fundamental R ₁ es una instancia fundamental de otra regla R ₂ si R ₁ es el resultado de una sustitución de constantes por todas las variables en R ₂ .

La base de Herbrand de un programa Datalog es el conjunto de todos los átomos fundamentales que se pueden crear con las constantes que aparecen en el programa. Una interpretación (también conocida como instancia de base de datos ) es un subconjunto de la base de Herbrand. Un átomo fundamental es verdadero en una interpretación I si es un elemento de I. Una regla es verdadera en una interpretación I si para cada instancia fundamental de esa regla, si todas las cláusulas del cuerpo son verdaderas en I , entonces el encabezado de la regla también es verdadero en I.

Un modelo de un programa Datalog P es una interpretación I de P que contiene todos los hechos básicos de P y hace que todas las reglas de P sean verdaderas en I. La semántica de teoría de modelos establece que el significado de un programa Datalog es su modelo mínimo (equivalentemente, la intersección de todos sus modelos). ^[4]

Por ejemplo, este programa:

borde ( x ,  y ). 
borde ( y ,  z ). 
ruta ( A ,  B )  :-  
  borde ( A ,  B ). 
ruta ( A ,  C )  :-  
  ruta ( A ,  B ),  
  borde ( B ,  C ).

tiene este universo Herbrand: x, y,z

y esta base de Herbrand: edge(x, x), edge(x, y), ..., edge(z, z), path(x, x), ...,path(z, z)

y este modelo minimalista de Herbrand: edge(x, y), edge(y, z), path(x, y), path(y, z),path(x, z)

Sea I el conjunto de interpretaciones de un programa Datalog P , es decir, I = P ( H ) , donde H es la base de Herbrand de P y P es el operador de conjunto potencia . El operador de consecuencia inmediata para P es la siguiente función T de I a I : Para cada instancia básica de cada regla en P , si cada cláusula en el cuerpo está en la interpretación de entrada, entonces agregue la cabeza de la instancia básica a la interpretación de salida. Esta función T es monótona con respecto al orden parcial dado por la inclusión de subconjuntos en T . Por el teorema de Knaster–Tarski , esta función tiene un punto fijo mínimo; por el teorema de punto fijo de Kleene el punto fijo es el supremo de la cadena . El punto fijo mínimo de M coincide con el modelo mínimo de Herbrand del programa. ^[5]${\displaystyle T(\conjunto vacío ),T(T(\conjunto vacío )),\ldots ,T^{n}(\conjunto vacío ),\ldots }$

La semántica de punto fijo sugiere un algoritmo para calcular el modelo mínimo de Herbrand: comenzar con el conjunto de hechos básicos del programa y luego agregar repetidamente consecuencias de las reglas hasta que se alcance un punto fijo. Este algoritmo se denomina evaluación ingenua .

Dado un programa P , un árbol de prueba de un átomo fundamental A es un árbol con una raíz etiquetada por A , hojas etiquetadas por átomos fundamentales desde las cabezas de los hechos en P , y ramas con hijos etiquetados por átomos fundamentales G tales que existe una instancia fundamental ${\displaystyle A_{1},\ldots ,A_{n}}$

G :- A1, ..., An.

de una regla en P . La semántica de teoría de pruebas define el significado de un programa Datalog como el conjunto de átomos básicos que se pueden descifrar a partir de dichos árboles. Este conjunto coincide con el modelo mínimo de Herbrand. ^[6]

A uno le podría interesar saber si un átomo fundamental en particular aparece o no en el modelo mínimo de Herbrand de un programa Datalog, tal vez sin preocuparse demasiado por el resto del modelo. Una lectura de arriba hacia abajo de los árboles de prueba descritos anteriormente sugiere un algoritmo para calcular los resultados de dichas consultas ; dicha lectura informa el algoritmo de resolución SLD , que forma la base para la evaluación de Prolog .

La semántica de Datalog también se ha estudiado en el contexto de puntos fijos sobre semianillos más generales . ^[7]

Si bien el nombre "programación lógica" se utiliza para referirse a todo el paradigma de lenguajes de programación, incluidos Datalog y Prolog, cuando se habla de semántica formal, generalmente se hace referencia a una extensión de Datalog con símbolos de función . Los programas lógicos también se denominan programas de cláusula Horn . La programación lógica, tal como se analiza en este artículo, está estrechamente relacionada con el subconjunto "puro" o declarativo de Prolog .

La sintaxis de la programación lógica amplía la sintaxis de Datalog con símbolos de función. La programación lógica elimina la restricción de rango, lo que permite que aparezcan variables en los encabezados de las reglas que no aparecen en sus cuerpos. ^[8]

Debido a la presencia de símbolos de función, los modelos Herbrand de programas lógicos pueden ser infinitos. Sin embargo, la semántica de un programa lógico todavía se define como su modelo Herbrand mínimo. En relación con esto, el punto fijo del operador de consecuencia inmediata puede no converger en un número finito de pasos (o en un conjunto finito). Sin embargo, cualquier átomo fundamental en el modelo Herbrand mínimo tendrá un árbol de prueba finito. Es por esto que Prolog se evalúa de arriba hacia abajo. ^[8] Al igual que en Datalog, las tres semánticas se pueden demostrar equivalentes.

La programación lógica tiene la propiedad deseable de que las tres definiciones principales de la semántica de los programas lógicos concuerdan. En contraste, existen muchas propuestas contradictorias para la semántica de los programas lógicos con negación. La fuente del desacuerdo es que los programas lógicos tienen un modelo Herbrand mínimo único, pero en general, los programas de programación lógica (o incluso los de Datalog) con negación no lo tienen.

La negación se escribe noty puede aparecer delante de cualquier átomo en el cuerpo de una regla.

< lista-de-átomos >  ::=  < átomo > | "no" < átomo > | < átomo > "," < lista-de-átomos > | ""

Un programa lógico con negación está estratificado cuando es posible asignar cada relación a algún estrato , de modo que si una relación R aparece negada en el cuerpo de una relación S , entonces R está en un estrato inferior a S. ^[9] La semántica de teoría de modelos y de punto fijo de Datalog se puede extender para manejar la negación estratificada, y dichas extensiones se pueden demostrar equivalentes .

Muchas implementaciones de Datalog utilizan un modelo de evaluación ascendente inspirado en la semántica de punto fijo. Dado que esta semántica puede manejar la negación estratificada, varias implementaciones de Datalog implementan la negación estratificada.

Si bien la negación estratificada es una extensión común de Datalog, existen programas razonables que no se pueden estratificar. El siguiente programa describe un juego de dos jugadores en el que un jugador gana si su oponente no tiene movimientos: ^[10]

mover ( a ,  b ). 
ganar ( X )  :-  mover ( X ,  Y ),  no  ganar ( Y ).

Este programa no está estratificado, pero parece razonable pensar que adebería ganar el juego.

La semántica del modelo estable define una condición para llamar estables a ciertos modelos Herbrand de un programa . Intuitivamente, los modelos estables son los "posibles conjuntos de creencias que un agente racional podría tener, dado [el programa]" como premisas. ^[11]

Un programa con negación puede tener muchos modelos estables o ningún modelo estable. Por ejemplo, el programa

p  :-  no  q . 
q  :-  no  p .

tiene dos modelos estables , . El programa de una regla ${\estilo de visualización \{p\}}$${\estilo de visualización \{q\}}$

p  :-  no  p .

No tiene modelos estables.

Todo modelo estable es un modelo mínimo de Herbrand. Un programa Datalog sin negación tiene un único modelo estable, que es exactamente su modelo mínimo de Herbrand. La semántica del modelo estable define el significado de un programa lógico con negación como su modelo estable, si es que hay exactamente uno. Sin embargo, puede ser útil investigar todos (o al menos varios) de los modelos estables de un programa; este es el objetivo de la programación de conjuntos de respuestas .

Se han propuesto y estudiado varias otras extensiones de Datalog, incluidas variantes con soporte para constantes y funciones enteras (incluido DatalogZ ), ^{[12] [13] restricciones} de desigualdad en los cuerpos de reglas y funciones agregadas .

La programación lógica de restricciones permite que las restricciones sobre dominios como los números reales o enteros aparezcan en los cuerpos de las reglas.

• Estructura de Herbrand
• Programación lógica
• La negación como fracaso
• Sintaxis y semántica de Prolog

• Ceri, S.; Gottlob, G.; Tanca, L. (marzo de 1989). "Lo que siempre quiso saber sobre Datalog (y nunca se atrevió a preguntar)" (PDF) . IEEE Transactions on Knowledge and Data Engineering . 1 (1): 146–166. CiteSeerX  10.1.1.210.1118 . doi :10.1109/69.43410. ISSN  1041-4347.