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 tiene tipado dinámico . Tiene un único tipo de datos , el término , que tiene varios subtipos: átomos , números , variables y términos compuestos .
Un átomo es un nombre de uso 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 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 una letra 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 son x, blue, 'Taco'y 'some atom'.
Los números pueden ser de tipo flotante o enteros . Muchas implementaciones de Prolog también proporcionan números enteros y racionales ilimitados .
Las variables se denotan mediante una cadena que consta de letras, números y caracteres de subrayado, y que comienza con una letra mayúscula o un guión bajo. Las variables se parecen mucho a las variables en lógica en el sentido de que son marcadores de posición para términos arbitrarios. Una variable puede instanciarse (ligarse a ser igual a un término específico) mediante la unificación . Un solo guión bajo ( _) denota una variable anónima y significa "cualquier término". A diferencia de otras variables, el guión bajo no representa el mismo valor en todos los lugares donde aparece dentro de una definición de predicado.
Un término compuesto está formado por un átomo llamado "funtor" y una serie de "argumentos", que a su vez son términos. Los términos compuestos se escriben normalmente como un funtor seguido de una lista de términos de argumentos separados por comas, que se encuentra entre paréntesis. La cantidad 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 funtores que se declaran como operadores se pueden escribir en notación de prefijo o infijo. Por ejemplo, los términos -(z), +(a,b)y =(X,Y)también se pueden escribir como -z, a+by X=Y, respectivamente. Los usuarios pueden declarar funtores 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 funtor f y aridad n .
Casos especiales de términos compuestos:
[]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].Los programas Prolog describen relaciones, definidas por medio de cláusulas. Prolog puro está restringido 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 "Head es verdadero si Body es verdadero". El cuerpo de una regla consta de llamadas a predicados, que se denominan objetivos de la regla. El predicado integrado ,/2(es decir, un operador de 2-aridad con nombre ,) denota conjunción de objetivos y ;/2denota disyunción . Las conjunciones y disyunciones solo pueden aparecer en el cuerpo, no en el encabezado de una regla.
Las cláusulas con cuerpos vacíos se denominan hechos . Un ejemplo de un hecho es:
gato ( tom ).lo que equivale a la regla:
gato ( tom ) :- 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 envía un único objetivo, denominado consulta. Lógicamente, el motor Prolog intenta encontrar una refutación de la resolución de la consulta negada. El método de resolución utilizado por Prolog se denomina resolución SLD . Si la consulta negada se puede refutar, se deduce que la consulta, con las vinculaciones de variables adecuadas en su lugar, es una consecuencia lógica del programa. En ese caso, se informan al usuario todas las vinculaciones de variables generadas y se dice que la consulta ha tenido éxito. Operativamente, la estrategia de ejecución de Prolog puede considerarse como una generalización de las llamadas de función en otros lenguajes, con una diferencia que es posible que varias cabezas de cláusula coincidan con una llamada determinada. En ese caso, el sistema crea un punto de elección, unifica el objetivo con la cabeza de cláusula de la primera alternativa y continúa con los objetivos de esa primera alternativa. Si algún objetivo falla durante la ejecución del programa, se deshacen todas las vinculaciones de variables que se realizaron desde que se creó el punto de elección más reciente y la ejecución continúa con la siguiente alternativa de ese punto de elección. Esta estrategia de ejecución se denomina retroceso cronológico .
madre_hijo ( 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_hija ( X , Y ).Esto da como resultado que la siguiente consulta se evalúe como verdadera:
?- Hermanos ( Sally , Erica ). SíEsto se obtiene de la siguiente manera: Inicialmente, el único encabezado de cláusula coincidente para la consulta sibling(sally, erica)es el primero, por lo que probar la consulta es equivalente a probar el cuerpo de esa cláusula con los enlaces de variables apropiados en su lugar, 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 encabezados 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 utilizando el hecho father_child(tom, sally), por lo que Z = tomse genera el enlace y el siguiente objetivo a probar es la segunda parte de la conjunción anterior: parent_child(tom, erica). Nuevamente, esto se puede probar con el hecho correspondiente. Dado que todos los objetivos se pueden probar, la consulta tiene éxito. Dado que la consulta no contenía variables, no se informan enlaces al usuario. Una consulta con variables, como:
?- padre_hijo ( Padre , Hijo ).enumera todas las respuestas válidas al retroceder.
Tenga en cuenta que con el código indicado anteriormente, la consulta ?- sibling(sally, sally).también se realiza correctamente. Si lo desea, puede insertar objetivos adicionales para describir las restricciones relevantes.
Los algoritmos iterativos se pueden implementar por medio de predicados recursivos. Los sistemas Prolog suelen implementar una técnica de optimización conocida llamada optimización de llamadas de cola (TCO) para predicados deterministas que presentan recursión de cola o, de manera más general, 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 un espacio de pila constante, como los bucles en otros lenguajes.
Un corte ( !) dentro de una regla evitará que Prolog retroceda en el tiempo a cualquier predicado detrás del corte:
predicado ( X ) :- uno ( X ), !, dos ( X ).fallará si el primer valor encontrado de Xpara el cual one(X)es verdadero resulta en 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 en una lista un valor determinado:
contiene ( V , [ V | _ ]). contiene ( V , [ _ | T ]) :- contiene ( V , T ).El predicado Prolog incorporado \+/1proporciona negación como falla , lo que permite un razonamiento no monótono . El objetivo \+ illegal(X)de la regla
legal ( X ) :- \+ ilegal ( X ).se evalúa de la siguiente manera: Prolog intenta probar el illegal(X). Si se puede encontrar una prueba para ese objetivo, el objetivo original (es decir, \+ illegal(X)) falla. Si no se puede encontrar 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 sólida si su argumento es "fundamento" (es decir, no contiene variables). La solidez se pierde si el argumento contiene variables. En particular, la consulta ?- legal(X).ahora no se puede utilizar para enumerar todas las cosas que son legales.
En una lectura 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 el punto de vista procedimental, a menudo es importante tener en cuenta la estrategia de ejecución de Prolog, ya sea por razones de eficiencia o debido a la semántica de predicados impuros incorporados para los que el orden de evaluación es importante. Además, como los intérpretes de Prolog intentan unificar las cláusulas en el orden en que se proporcionan, no dar un orden correcto puede llevar a una recursión infinita, como en:
predicado1 ( X ) :- predicado2 ( X , X ). predicado2 ( X , Y ) :- predicado1 ( X ), X \= Y .Dado este ordenamiento, cualquier consulta de la forma
?- predicado1 ( átomo ).se repetirá hasta que se agote la pila. Sin embargo, si las últimas 3 líneas se cambiaron a:
predicado2 ( X , Y ) :- X \= Y , predicado1 ( X ).La misma consulta conduciría a un resultado negativo en muy poco tiempo.
Existe una notación especial llamada gramática de cláusulas definidas ( DCG, por sus siglas en inglés ). Una regla definida mediante -->/2en lugar de :-/2se expande por el preprocesador ( expand_term/2, una función análoga a las macros en otros lenguajes) de acuerdo con unas pocas reglas de reescritura sencillas, lo que da como resultado cláusulas Prolog comunes. En particular, la reescritura equipa al predicado con dos argumentos adicionales, que se pueden usar para enhebrar implícitamente el estado, de manera análoga a las mónadas en otros lenguajes. Las DCG se usan a menudo para escribir analizadores sintácticos o generadores de listas, ya que también proporcionan una interfaz conveniente para enumerar diferencias.
Un ejemplo más amplio mostrará el potencial de usar Prolog en el análisis .
Dada la oración expresada en forma Backus-Naur :
< oración > ::= < parte_estadística > < parte_estadística > ::= < declaración > | < parte_estadística > < declaración > < declaración > ::= < id > = < expresión > ; < expresión > ::= < operando > | < expresión > < operador > < operando > < operando > ::= < id > | < dígito > < id > ::= a | b < dígito > ::= 0..9 < operador > ::= + | - | *Esto se puede escribir en Prolog usando DCG, lo que corresponde a un analizador predictivo con una mirada hacia adelante de un token:
oración ( S ) --> declaración ( S0 ), oración_r ( S0 , S ). oración_r ( S , S ) --> []. oración_r ( S0 , seq ( S0 , S )) --> declaración ( S1 ), oración_r ( S1 , S ). declaració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 ( más ( E0 , T ), E ). expresión_r ( E0 , E ) --> [ - ], término ( T ), expresión_r ( menos ( 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 ].Este código define una relación entre una oración (dada como una lista de tokens) y su árbol de sintaxis abstracta (AST). Consulta de ejemplo:
?- frase ( oración ( AST ), [ a , = , 1 , + , 3 , * , b ,;, b , = , 0 ,;]). AST = seq ( asignar ( a , más ( dígito ( 1 ), por ( dígito ( 3 ), id ( b )))), asignar ( b , dígito ( 0 ))) ;El AST se representa mediante términos de Prolog y se puede utilizar para aplicar optimizaciones, para compilar dichas expresiones en código de máquina o para interpretar directamente dichas declaraciones. Como es típico de la naturaleza relacional de los predicados, estas definiciones se pueden utilizar tanto para analizar y generar oraciones como para verificar si un árbol determinado corresponde a una lista dada de tokens. Al utilizar la profundización iterativa para una enumeración justa, cada oración arbitraria pero fija y su AST correspondiente se generarán eventualmente:
?- longitud ( Tokens , _ ), frase ( oración ( AST ), Tokens ). Tokens = [ a , = , a , (;)], AST = asignar ( a , id ( a )) ; Tokens = [ a , = , b , (;)], AST = asignar ( a , id ( b ) ) etc.