La sintaxis y la semántica del lenguaje de programación Prolog son el conjunto de reglas que definen cómo se escribe y cómo se interpreta un programa Prolog. Las reglas se establecen en la norma ISO ISO / IEC 13211 [1], aunque existen diferencias en las implementaciones de Prolog .
Tipos de datos
Prolog se escribe dinámicamente . Tiene un solo 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 un significado inherente. Se compone de una secuencia de caracteres que el lector de Prolog analiza como una sola unidad. Los átomos suelen ser palabras desnudas en código Prolog, escritas sin una sintaxis especial. Sin embargo, los átomos que contienen espacios u otros caracteres especiales deben estar entre comillas simples. Los átomos que comienzan con una letra mayúscula también deben estar entrecomillados 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 comienza con una letra mayúscula o un subrayado. Las variables se parecen mucho a las variables en lógica, ya que son marcadores de posición para términos arbitrarios. Una variable puede convertirse en instanciada (enlazada para igualar un término específico) a través de 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 en los que aparece dentro de una definición de predicado.
Un término compuesto se compone de un átomo llamado "funtor" y una serie de "argumentos", que también 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 incluye entre paréntesis. El número de argumentos se denomina aridad del término . Un átomo se puede considerar 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 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+b
y X=Y
, 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 .
Casos especiales de términos compuestos:
- Las listas se definen inductivamente: el átomo
[]
es una lista. Un término compuesto con functor.
(punto) y arity 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 rodeada de comillas equivale 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.
Programas de prólogo
Los programas de Prolog describen relaciones, definidas mediante cláusulas. Pure Prolog está restringido a las cláusulas de Horn , un subconjunto completo de Turing 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 aridades con nombre ,
) denota conjunción de objetivos y ;/2
denota disyunción . Las conjunciones y disyunciones solo pueden aparecer en el cuerpo, no en la cabeza de una regla.
Las cláusulas con cuerpos vacíos se denominan 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/0
siempre es verdadero.
Evaluación
La ejecución de un programa Prolog se inicia mediante la publicación del usuario de un único objetivo, llamado consulta. Lógicamente, el motor de Prolog intenta encontrar una refutación de 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 los enlaces de variables apropiados en su lugar, es una consecuencia lógica del programa. En ese caso, todos los enlaces de variables generados se informan al usuario y se dice que la consulta se ha realizado correctamente. Desde el punto de vista operativo, la estrategia de ejecución de Prolog se puede considerar como una generalización de las llamadas a funciones en otros lenguajes, una diferencia es que varios encabezados de cláusula pueden coincidir con una llamada determinada. En ese caso, el sistema crea un punto de elección, unifica el objetivo con el encabezado de la cláusula de la primera alternativa y continúa con los objetivos de esa primera alternativa. Si algún objetivo falla en el curso de la ejecución del programa, todos los enlaces de variables que se hicieron 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 denomina retroceso cronológico . Por ejemplo:
madre_hijo ( trude , 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 es equivalente a probar el cuerpo de esa cláusula con los enlaces de variable apropiados en su lugar, es decir, la conjunción (parent_child(Z,sally), parent_child(Z,erica))
. El siguiente objetivo a ser probado 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 demostrar utilizando el hecho de father_child(tom, sally)
, por lo que la unión Z = tom
se genera, y el siguiente objetivo a ser probada es la segunda parte de la conjunción arriba: parent_child(tom, erica)
. Nuevamente, esto puede probarse con el hecho correspondiente. Dado que se pudieron probar todos los objetivos, la consulta se realiza correctamente. Dado que la consulta no contenía variables, no se informa al usuario de enlaces. Una consulta con variables, como:
? - father_child ( padre , hijo ).
enumera todas las respuestas válidas sobre la marcha atrás.
Tenga en cuenta que con el código como se indicó anteriormente, la consulta ?- sibling(sally, sally).
también se realiza correctamente. Se insertarían objetivos adicionales para describir las restricciones relevantes, si se desea.
Bucles y recursividad
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 recursivos de cola deterministas se ejecutan con un espacio de pila constante, como bucles en otros lenguajes.
Cortes
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 X
for which one(X)
es verdadero conduce a two(X)
ser falso.
Variables anónimas
Las variables anónimas _
nunca están vinculadas a un valor y se pueden usar varias veces en un predicado.
Por ejemplo, buscando en una lista un valor dado:
contiene ( V , []) : - falso . contiene ( V , [ V | _ ]) : - verdadero . contiene ( V , [ _ | T ]) : - contiene ( V , T ).
Negación
El predicado Prolog integrado \+/1
proporciona la negación como falla , lo que permite un razonamiento no monótono . El gol \+ 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 puede encontrar ninguna prueba, el objetivo original tiene éxito. Por lo tanto, el \+/1
operador de prefijo se denomina operador "no demostrable", ya que la consulta se realiza ?- \+ Goal.
correctamente si el objetivo no es demostrable. Este tipo de negación es sólida si su argumento es "base" (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.
Semántica
Bajo una lectura declarativa, el orden de las reglas y de los objetivos dentro de las reglas es irrelevante ya que la disyunción lógica y la conjunción son conmutativas. Sin embargo, desde el punto de vista del procedimiento, 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 que importa el orden de evaluación. 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 conducir a una recursividad infinita, como en:
predicado1 ( X ) : - predicado2 ( X , X ). predicate2 ( X , Y ) : - predicate1 ( 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 cambiaron a:
predicado2 ( X , Y ) : - X \ = Y , predicado1 ( X ).
la misma consulta conduciría a un resultado No. en muy poco tiempo.
Gramáticas de cláusulas definidas
Existe una notación especial llamada gramáticas de cláusulas definidas ( DCG ). El preprocesador expande una regla definida mediante en -->/2
lugar de :-/2
( expand_term/2
una función análoga a las macros en otros idiomas) de acuerdo con unas pocas reglas de reescritura sencillas, lo que da como resultado cláusulas Prolog ordinarias. Más notablemente, la reescritura equipa el 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. Los DCG se utilizan a menudo para escribir analizadores o generadores de listas, ya que también proporcionan una interfaz conveniente para enumerar las diferencias.
Ejemplo de analizador
Un ejemplo más grande mostrará el potencial de usar Prolog en el análisis .
Dada la oración expresada en forma Backus – Naur :
< frase > :: = < parte_estatal > < parte_estatal > :: = < sentencia > | < 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 de anticipación:
enunciado ( S ) -> enunciado ( S0 ), enunciado_r ( S0 , S ). oración_r ( S , S ) -> []. sentencia_r ( S0 , seq ( S0 , S )) -> sentencia ( S1 ), sentencia_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 ( 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 ), veces ( dígito ( 3 ), id ( b )))), asignar ( b , dígito ( 0 ))) ;
El AST se representa usando términos de Prolog y se puede usar para aplicar optimizaciones, para compilar dichas expresiones en código de máquina o para interpretar directamente tales declaraciones. Como es típico de la naturaleza relacional de los predicados, estas definiciones se pueden usar tanto para analizar como para generar oraciones, y también para verificar si un árbol dado corresponde a una lista dada de tokens. Usando la profundización iterativa para una enumeración justa, cada oración arbitraria pero fija y su correspondiente AST se generarán eventualmente:
? - longitud ( Tokens , _ ), frase ( oración ( AST ), Tokens ). Fichas = [ a , = , a , (;)], AST = asignar ( a , id ( a )) ; Tokens = [ a , = , b , (;)], AST = Asignar ( una , ID ( b )) etc .
Ver también
Referencias
- ^ ISO / IEC 13211: Tecnología de la información - Lenguajes de programación - Prólogo . Organización Internacional de Normalización , Ginebra.