Sintaxis y semántica de Prolog

La sintaxis y la semántica de Prolog , un lenguaje de programación , son los conjuntos de reglas que definen cómo se escribe un programa Prolog y cómo se interpreta, respectivamente. Las reglas están establecidas en la norma ISO/IEC 13211 ^{[ 1 ],} aunque existen diferencias en las implementaciones de Prolog .

Prolog es de tipado dinámico . Tiene un único tipo de dato , el término , que tiene varios subtipos: átomos , números , variables y términos compuestos .

Un átomo es un nombre de propósito general sin significado inherente. Está compuesto por una secuencia de caracteres que el lector de Prolog analiza como una sola unidad. Los átomos suelen ser palabras simples en el código Prolog, escritas sin sintaxis especial. Sin embargo, los átomos que contienen espacios u otros caracteres especiales deben ir entre comillas simples. Los átomos que comienzan con mayúscula también deben ir entre comillas para distinguirlos de las variables. La lista vacía, escrita [], también es un átomo. Otros ejemplos de átomos incluyen x, blue, 'Taco', y 'some atom'.

Los números pueden ser de coma flotante o enteros . Muchas implementaciones de Prolog también proporcionan enteros ilimitados y números racionales .

Las variables se representan mediante una cadena de caracteres compuesta por letras, números y guiones bajos, que comienza con una letra mayúscula o un guion bajo. En lógica, las variables se asemejan mucho a las variables genéricas, ya que son marcadores de posición para términos arbitrarios. Una variable puede instanciarse (vincularse a un término específico) mediante unificación . Un guion bajo simple (__ _) denota una variable anónima y significa "cualquier término". A diferencia de otras variables, el guion bajo no representa el mismo valor en todos los lugares donde aparece dentro de la definición de un predicado.

Un término compuesto se compone de un átomo llamado "functor" y varios "argumentos", que también son términos. Los términos compuestos se suelen escribir como un functor seguido de una lista de argumentos separados por comas, entre paréntesis. El número de argumentos se denomina aridad del término . Un átomo puede considerarse un término compuesto con aridad cero.

Ejemplos de términos compuestos son truck_year('Mazda', 1986)y 'Person_Friends'(zelda,[tom,jim]). Los términos compuestos con functores que se declaran como operadores pueden escribirse en notación prefija o infija. Por ejemplo, los términos -(z), +(a,b)y =(X,Y)también pueden escribirse como -z, a+by X=Y, respectivamente. Los usuarios pueden declarar functores arbitrarios como operadores con diferentes precedencias para permitir notaciones específicas del dominio. La notación f/n se usa comúnmente para denotar un término con functor f y aridad n .

Casos especiales de términos compuestos:

• Las listas se definen inductivamente: el átomo []es una lista. Un término compuesto con functor .(punto) y aridad 2, cuyo segundo argumento es una lista, es en sí mismo una lista. Existe una sintaxis especial para denotar listas: .(A, B)es equivalente a [A|B]. Por ejemplo, la lista .(1, .(2, .(3, [])))también se puede escribir como [1 | [2 | [3 | []]]], o incluso de forma más compacta como [1,2,3].
• Cadenas : Una secuencia de caracteres entre comillas es equivalente a una lista de códigos de caracteres (numéricos), generalmente en la codificación de caracteres local o Unicode si el sistema admite Unicode.

Los programas Prolog describen relaciones, definidas mediante cláusulas. El Prolog puro se restringe a las cláusulas de Horn , un subconjunto Turing-completo de la lógica de predicados de primer orden . Hay dos tipos de cláusulas: hechos y reglas. Una regla tiene la forma

Cabeza :- Cuerpo .

y se lee como "La cabeza es verdadera si el cuerpo es verdadero". El cuerpo de una regla consta de llamadas a predicados, que se denominan objetivos de la regla. El predicado incorporado ,/2(que significa un operador de 2-aridad con nombre ,) denota la conjunción de objetivos, y ;/2denota la disyunción . Las conjunciones y disyunciones solo pueden aparecer en el cuerpo, no en la cabeza de una regla.

Las cláusulas con cuerpo vacío se denominan hechos . Un ejemplo de hecho es:

gato ( macho ).

lo cual es equivalente a la regla:

gato ( tomo ) : verdadero .

Otro ejemplo es:

X es 3 + 2.

y cuando lo ejecutes, el resultado será

X = 5 Sí .

El predicado incorporado true/0siempre es verdadero.

La ejecución de un programa Prolog se inicia cuando el usuario introduce un único objetivo, denominado consulta. Lógicamente, el motor Prolog intenta encontrar una refutación de la consulta negada. El método de resolución utilizado por Prolog se denomina resolución SLD . Si la consulta negada puede refutarse, se deduce que la consulta, con las asignaciones de variables adecuadas, es una consecuencia lógica del programa. En ese caso, se informan al usuario todas las asignaciones de variables generadas y se considera que la consulta ha tenido éxito. Operacionalmente, la estrategia de ejecución de Prolog puede considerarse una generalización de las llamadas a funciones en otros lenguajes, con la diferencia de que varias cabeceras de cláusula pueden coincidir con una llamada dada. En ese caso, el sistema crea un punto de decisión, unifica el objetivo con la cabecera de cláusula de la primera alternativa y continúa con los objetivos de dicha primera alternativa. Si algún objetivo falla durante la ejecución del programa, se deshacen todas las asignaciones de variables realizadas desde la creación del último punto de decisión, y la ejecución continúa con la siguiente alternativa de ese punto de decisión. Esta estrategia de ejecución se denomina retroceso cronológico .

madre_hija ( trude , sally ).padre_hijo ( tom , sally ). padre_hijo ( tom , erica ). padre_hijo ( mike , tom ).hermano ( X , Y ) :- padre_hijo ( Z , X ), padre_hijo ( Z , Y ).padre_hijo ( X , Y ) :- padre_hijo ( X , Y ). padre_hijo ( X , Y ) :- madre_hijo ( X , Y ).

Esto da como resultado que la siguiente consulta se evalúe como verdadera:

¿ Hermano/a ( Sally , Erica )? Sí

Esto se obtiene de la siguiente manera: Inicialmente, la única cabecera de cláusula que coincide con la consulta sibling(sally, erica)es la primera, por lo que probar la consulta es equivalente a probar el cuerpo de esa cláusula con las vinculaciones de variables apropiadas, es decir, la conjunción (parent_child(Z,sally), parent_child(Z,erica)). El siguiente objetivo a probar es el más a la izquierda de esta conjunción, es decir, parent_child(Z, sally). Dos cabeceras de cláusula coinciden con este objetivo. El sistema crea un punto de elección y prueba la primera alternativa, cuyo cuerpo es father_child(Z, sally). Este objetivo se puede probar usando el hecho father_child(tom, sally), por lo que se genera la vinculación Z = tom, y el siguiente objetivo a probar es la segunda parte de la conjunción anterior: parent_child(tom, erica). Nuevamente, esto se puede probar mediante el hecho correspondiente. Dado que todos los objetivos se pudieron probar, la consulta tiene éxito. Como la consulta no contenía variables, no se informan vinculaciones al usuario. Una consulta con variables, como:

?- padre_hijo ( Padre , Hijo ).

Enumera todas las respuestas válidas en el método de retroceso.

Observe que, con el código descrito anteriormente, la consulta ?- sibling(sally, sally).también se ejecuta correctamente. Si se desea, se pueden añadir objetivos adicionales para describir las restricciones pertinentes.

Los algoritmos iterativos pueden implementarse mediante predicados recursivos. Los sistemas Prolog suelen implementar una técnica de optimización bien conocida, denominada optimización de llamadas de cola (TCO, por sus siglas en inglés), para predicados deterministas que presentan recursión de cola o, más generalmente, llamadas de cola: el marco de pila de una cláusula se descarta antes de realizar una llamada en una posición de cola. Por lo tanto, los predicados recursivos de cola deterministas se ejecutan con espacio de pila constante, al igual que los bucles en otros lenguajes.

Un corte ( !) dentro de una regla impedirá que Prolog retroceda cualquier predicado que se encuentre detrás del corte:

predicado ( X ) :- uno ( X ), !, dos ( X ).

fallará si el primer valor encontrado para Xel cual one(X)es verdadero lleva a two(X)ser falso.

Las variables anónimas _nunca están vinculadas a un valor y pueden usarse varias veces en un predicado.

Por ejemplo, buscar un valor determinado en una lista:

contiene ( V , [ V | _ ]). contiene ( V , [ _ | T ]) :- contiene ( V , T ).

El predicado integrado de Prolog \+/1proporciona la negación como fallo , lo que permite un razonamiento no monótono . El objetivo \+ illegal(X)en la regla

legal ( X ) :- \+ ilegal ( X ).

se evalúa de la siguiente manera: Prolog intenta probar el illegal(X). Si se encuentra una prueba para ese objetivo, el objetivo original (es decir, \+ illegal(X)) falla. Si no se encuentra ninguna prueba, el objetivo original tiene éxito. Por lo tanto, el \+/1operador de prefijo se llama operador "no demostrable", ya que la consulta ?- \+ Goal.tiene éxito si el Objetivo no es demostrable. Este tipo de negación es correcta si su argumento es "ground" (es decir, no contiene variables). La corrección se pierde si el argumento contiene variables. En particular, la consulta ?- legal(X).ya no se puede usar para enumerar todas las cosas que son válidas.

Desde una perspectiva declarativa, el orden de las reglas, y de los objetivos dentro de las reglas, es irrelevante, ya que la disyunción y la conjunción lógicas son conmutativas. Sin embargo, desde una perspectiva procedimental, suele ser importante tener en cuenta la estrategia de ejecución de Prolog, ya sea por razones de eficiencia o debido a la semántica de los predicados impuros integrados, para los cuales el orden de evaluación es relevante. Además, dado que los intérpretes de Prolog intentan unificar las cláusulas en el orden en que se proporcionan, no establecer un orden correcto puede conducir a una recursión infinita, como en:

predicado1 ( X ) :- predicado2 ( X , X ). predicado2 ( X , Y ) :- predicado1 ( X ), X \= Y .

Dado este orden, cualquier consulta de la forma

?- predicado1 ( átomo ).

se repetirá hasta que se agote la pila. Sin embargo, si las últimas 3 líneas se cambiaran a:

predicado2 ( X , Y ) :- X \= Y , predicado1 ( X ).

La misma consulta daría como resultado un "No" en muy poco tiempo.

Existe una notación especial llamada gramáticas de cláusulas definidas ( DCG ). Una regla definida mediante -->/2en lugar de :-/2es expandida por el preprocesador ( expand_term/2, una función análoga a las macros en otros lenguajes) según unas pocas reglas de reescritura sencillas, lo que da como resultado cláusulas Prolog ordinarias. Lo más notable es que la reescritura dota al predicado de dos argumentos adicionales, que pueden usarse para enhebrar implícitamente el estado alrededor, de forma análoga a las mónadas en otros lenguajes. Las DCG se utilizan a menudo para escribir analizadores sintácticos o generadores de listas, ya que también proporcionan una interfaz conveniente para las diferencias de listas.

< oración > ::= < parte_estadística > < parte_estadística > ::= < instrucción > | < parte_estadística > < instrucción > < instrucción > ::= < id > = < expresión > ; < expresión > ::= < operando > | < expresión > < operador > < operando > < operando > ::= < id > | < dígito > < id > ::= a | b < dígito > ::= 0..9 < operador > ::= + | - | * 

oración ( S ) --> declaración ( S0 ), sentence_r ( S0 , S ). sentence_r ( S , S ) --> []. sentence_r ( S0 , seq ( S0 , S )) --> declaración ( S1 ), sentence_r ( S1 , S ).instrucción ( asignar ( Id , E )) --> id ( Id ), [ = ], expresión ( E ), [;].expresión ( E ) --> término ( T ), expresión_r ( T , E ). expresión_r ( E , E ) --> []. expresión_r ( E0 , E ) --> [ + ], término ( T ), expresión_r ( plus ( E0 , T ), E ). expresión_r ( E0 , E ) --> [ - ], término ( T ), expresión_r ( minus ( E0 , T ), E ).término ( T ) --> factor ( F ), término_r ( F , T ). término_r ( T , T ) --> []. término_r ( T0 , T ) --> [ * ], factor ( F ), término_r ( veces ( T0 , F ), T ).factor ( id ( ID )) --> id ( ID ). factor ( dígito ( D )) --> [ D ], { ( número ( D ) ; var ( D )), entre ( 0 , 9 , D )}.id ( a ) --> [ a ]. id ( b ) --> [ b ].

?- frase ( oración ( AST ), [ a , = , 1 , + , 3 , * , b ,;, b , = , 0 ,;]). AST = seq ( asignar ( a , más ( dígito ( 1 ), veces ( dígito ( 3 ), id ( b )))), asignar ( b , dígito ( 0 ))) ;

?- longitud ( Tokens , _ ), frase ( oración ( AST ), Tokens ). Tokens = [ a , = , a , (;)], AST = asignar ( a , id ( a )) ; Tokens = [ a , = , b , (;)], AST = asignar ( a , id ( b )) etc .

• Comparación de implementaciones de Prolog