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 ISO/IEC 13211 [1] aunque existen diferencias en las implementaciones de Prolog .
Prolog se escribe dinámicamente . 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 propósito general sin significado inherente. Se compone de una secuencia de caracteres que el lector 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 estar entre comillas simples. Los átomos que comienzan con mayúscula también deben citarse 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 flotantes o enteros . Muchas implementaciones de Prolog también proporcionan números enteros ilimitados y números racionales .
Las variables se indican 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 que son marcadores de posición para términos arbitrarios. Una variable puede convertirse en instancia (vinculada a un término específico) mediante unificación . Un guión bajo simple ( _) indica 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 se compone de un átomo llamado "functor" y una serie de "argumentos", que nuevamente son términos. Los términos compuestos normalmente se escriben como un functor seguido de una lista de términos de argumentos separados por comas, que está contenida entre paréntesis. El número de argumentos se llama aridad del término . Un átomo puede considerarse como 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 declarados como operadores se pueden escribir en notación de prefijo o infijo. Por ejemplo, los términos -(z)y +(a,b)también =(X,Y)se pueden escribir como y -z, respectivamente. Los usuarios pueden declarar functores arbitrarios como operadores con diferentes precedencias para permitir notaciones específicas de dominio. La notación f/n se usa comúnmente para denotar un término con funtor f y aridad n .a+bX=Y
Casos especiales de términos compuestos:
[]es una lista. Un término compuesto con funtor .(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)equivale 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 mediante cláusulas. Pure Prolog está restringido a cláusulas de Horn , un subconjunto completo de Turing de lógica de predicados de primer orden . Hay dos tipos de cláusulas: de hechos y de reglas. Una regla es de 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(es decir, un operador de 2 aridades con nombre ,) denota conjunción de objetivos y ;/2denota disyunción . Las conjunciones y disyunciones sólo pueden aparecer en el cuerpo, no en el encabezamiento de una regla.
Las cláusulas con cuerpo vacío se llaman hechos . Un ejemplo de un hecho es:
gato ( tom ).que es equivalente a la regla:
gato ( tom ) : - cierto .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 publica un único objetivo, denominado consulta. Lógicamente, el motor Prolog intenta encontrar una resolución que refute la consulta negada. El método de resolución utilizado por Prolog se llama resolución SLD . Si la consulta negada puede ser refutada, se deduce que la consulta, con las vinculaciones de variables apropiadas implementadas, es una consecuencia lógica del programa. En ese caso, todas las vinculaciones de variables generadas se informan al usuario y se dice que la consulta se realizó correctamente. Operacionalmente, la estrategia de ejecución de Prolog puede considerarse como una generalización de llamadas a funciones en otros lenguajes, con una diferencia que varios encabezados de cláusulas pueden coincidir con una llamada determinada. En ese caso, el sistema crea un punto de elección, unifica la meta con la cláusula principal de la primera alternativa y continúa con las metas de esa primera alternativa. Si algún objetivo falla durante la ejecución del programa, todas las vinculaciones de variables que se realizaron desde que se creó el punto de elección más reciente se deshacen y la ejecución continúa con la siguiente alternativa de ese punto de elección. Esta estrategia de ejecución se llama retroceso cronológico .
madre_niño ( truda , sally ). padre_hijo ( tom , sally ). padre_hijo ( tom , erica ). padre_hijo ( mike , tom ). hermano ( X , Y ) : - parent_child ( Z , X ), parent_child ( 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 ( 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 equivale a probar el cuerpo de esa cláusula con las vinculaciones de variables apropiadas en su lugar, es decir, la conjunción (parent_child(Z,sally), parent_child(Z,erica)). El próximo objetivo a demostrar es el más a la izquierda de esta conjunción, es decir, parent_child(Z, sally). Dos cabezas 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 se genera la vinculación Z = tomy el siguiente objetivo a demostrar es la segunda parte de la conjunción anterior parent_child(tom, erica):. Una vez más, esto puede demostrarse mediante el hecho correspondiente. Como se pudieron probar todos los objetivos, la consulta tiene éxito. Dado que la consulta no contenía variables, no se informa ningún enlace al usuario. Una consulta con variables, como:
?- padre_hijo ( Padre , Hijo ).enumera todas las respuestas válidas sobre el retroceso.
Tenga en cuenta que con el código indicado anteriormente, la consulta ?- sibling(sally, sally).también se realiza correctamente. Si se desea, se insertarían objetivos adicionales para describir las restricciones relevantes.
Los algoritmos iterativos se pueden implementar mediante predicados recursivos. Los sistemas Prolog generalmente implementan una técnica de optimización conocida llamada optimización de llamadas de cola (TCO) para predicados deterministas que exhiben recursividad 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 deterministas recursivos de cola se ejecutan con un espacio de pila constante, como los bucles en otros lenguajes.
Un corte ( !) dentro de una regla evitará que Prolog retroceda cualquier predicado detrás del corte:
predicado ( X ) : - uno ( X ), !, dos ( X ).fallará si el primer valor encontrado de Xfor que one(X)es verdadero conduce 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 en una lista un valor determinado:
contiene ( V , [ V | _ ]). contiene ( V , [ _ | T ]) : - contiene ( V , T ).El predicado Prolog incorporado \+/1proporciona negación como fracaso , 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 puede encontrar una prueba para ese objetivo, el objetivo original (es decir, \+ illegal(X)) falla. Si no se pueden encontrar pruebas, el objetivo original tiene éxito. Por lo tanto, el \+/1operador de prefijo se denomina operador "no demostrable", ya que la consulta ?- \+ Goal.tiene éxito si el objetivo no es demostrable. Este tipo de negación es válida si su argumento es "fundamental" (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.
Bajo 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 procesal, 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 incorporados impuros para los cuales el orden de evaluación es importante. Además, como los intérpretes de Prolog intentan unificar cláusulas en el orden en que se proporcionan, no dar un orden correcto puede llevar a una recursividad infinita, como en:
predicado1 ( X ) : - predicado2 ( X , X ). predicado2 ( X , Y ) : - predicado1 ( X ), X \ = Y.Dado este orden, cualquier consulta del formulario
?- 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 conduciría a un resultado No. en muy poco tiempo.
Existe una notación especial llamada gramáticas de cláusulas definidas ( DCG ). El preprocesador expande una regla definida vía -->/2en lugar de ( , 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 ordinarias. En particular, la reescritura equipa al predicado con dos argumentos adicionales, que pueden usarse para enhebrar implícitamente el estado, de manera análoga a las mónadas en otros lenguajes. Los DCG se utilizan a menudo para escribir analizadores o generadores de listas, ya que también proporcionan una interfaz conveniente para enumerar diferencias.:-/2expand_term/2
Un ejemplo más amplio mostrará el potencial de utilizar Prolog en el análisis .
Dada la oración expresada en forma Backus-Naur :
< oración > ::= < stat_part > < stat_part > ::= < declaración > | < stat_part > < 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, correspondientes a un analizador predictivo con un token anticipado:
oración ( S ) --> declaración ( S0 ), oración_r ( S0 , S ). frase_r ( S , S ) --> []. frase_r ( S0 , seq ( S0 , S )) --> declaración ( S1 ), frase_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 ). term_r ( T , T ) --> []. term_r ( T0 , T ) --> [ * ], factor ( F ), term_r ( veces ( T0 , F ), T ). factor ( identificación ( identificación )) --> identificación ( identificación ). factor ( dígito ( D )) --> [ D ], { ( número ( D ) ; var ( D )), entre ( 0 , 9 , D )}. identificación ( a ) --> [ a ]. identificación ( segundo ) --> [ segundo ].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 ), veces ( 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, compilar dichas expresiones en código de máquina o 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 comprobar si un árbol determinado corresponde a una lista determinada de tokens. Utilizando la profundización iterativa para una enumeración justa, eventualmente se generará cada oración arbitraria pero fija y su correspondiente AST:
?- longitud ( Tokens , _ ), frase ( oración ( AST ), Tokens ). Fichas = [ a , = , a , (;)], AST = asignar ( a , id ( a )) ; Tokens = [ a , = , b , (;)], AST = asignar ( a , id ( b )) , etc.