sintaxe e semântica Prolog - Prolog syntax and semantics

A sintaxe e semântica da linguagem de programação Prolog são o conjunto de regras que define como um programa Prolog é escrito e como ele é interpretado. As regras são estabelecidas na norma ISO ISO / IEC 13211 , embora existam diferenças nas implementações Prolog .

Tipos de dados

Prolog é tipagem dinâmica . Tem um único tipo de dados , o termo , que tem vários subtipos: átomos , números , variáveis e termos compostos .

Um átomo é um nome de uso geral com nenhum significado inerente. É composto de uma sequência de caracteres que é analisado pelo leitor Prolog como uma única unidade. Átomos são geralmente palavras nuas no código Prolog, escritos sem sintaxe especial. No entanto, contendo átomos de espaços ou de certos outros caracteres especiais deve ser rodeado por plicas. Átomos começando com uma letra maiúscula também deve ser citado, para distingui-las das variáveis. A lista vazia, escrita [], é também um átomo de. Outros exemplos de átomos incluem x, blue, 'Taco', e 'some atom'.

Números podem ser carros alegóricos ou inteiros . Muitas implementações Prolog também fornecem números inteiros ilimitados e números racionais .

Variáveis são indicados por uma string consistindo de letras, números e caracteres de sublinhado, e começando com uma letra maiúscula ou sublinhado. Variáveis assemelham variáveis na lógica em que eles são espaços reservados para termos arbitrários. Uma variável pode tornar-se instanciado (ligado para igualar um termo específico) através de unificação . Um único sublinhado ( _) denota uma variável anônima e significa "qualquer prazo." Ao contrário de outras variáveis, o sublinhado não representa o mesmo valor em todos os lugares que ocorre dentro de uma definição predicado.

Um termo composto é constituído por um átomo de um chamado "functor" e uma série de "argumentos", que são novamente termos. Termos compostos são vulgarmente escritas como um functor seguido por uma lista separada por vírgulas de termos de argumento, que está contido em parênteses. O número de argumentos é chamado do termo arity . Um átomo pode ser considerada como um termo composto com aridade zero.

Exemplos de termos compostos são truck_year('Mazda', 1986)e 'Person_Friends'(zelda,[tom,jim]). Termos compostos com functors que são declarados como operadores pode ser escrito em prefixo ou notação infixa. Por exemplo, os termos -(z), +(a,b)e =(X,Y)pode também ser escrito como -z, a+be X=Y, respectivamente. Os usuários podem declarar functors arbitrárias como operadores com precedências diferentes para permitir anotações específicas de domínio. A notação f / N é utilizada para designar um termo com functor f e aridade n .

Casos especiais de termos compostos:

• Listas são definidos indutivamente: O átomo []é uma lista. Um termo composto com functor .(ponto) e aridade 2, cujo segundo argumento é uma lista, é em si uma lista. Não existe sintaxe especial para denotar listas: .(A, B)é equivalente a [A|B]. Por exemplo, a lista .(1, .(2, .(3, [])))também pode ser escrito como [1 | [2 | [3 | []]]], ou mesmo mais compacta como [1,2,3].
• Cordas : Uma sequência de caracteres entre aspas é equivalente a uma lista de códigos de caracteres (numéricos), geralmente no local de codificação de caracteres ou Unicode se o sistema suporta Unicode.

programas Prolog

Programas Prolog descrever as relações, definidas por meio de cláusulas. Pure Prolog é restrito a cláusulas de Horn , um Turing completo subconjunto de primeira ordem lógica de predicados . Existem dois tipos de cláusulas: Factos e regras. Uma regra é da forma

Head :- Body.

e é lido como "Cabeça é verdade se o corpo é verdadeiro". O corpo de uma regra consiste em chamadas para predicados, que são chamados da regra objetivos . O embutido predicado ,/2 (significando um operador de 2-aridade com nome ,) indica a conjugação de objectivos, e ;/2indica a disjunção . Conjunções e disjunções só pode aparecer no corpo, não na cabeça de uma regra.

Cláusulas com corpos vazios são chamados fatos . Um exemplo de um fato é:

cat(tom).

o que equivale à regra:

cat(tom) :- true.

outro exemplo é a seguinte:

X is 3+2.

e quando você executá-lo, o resultado será

 X=5
 Yes.

O predicado built-in true/0é sempre verdadeiro.

Avaliação

Execução de um programa Prolog é iniciada por postagem do usuário de um único objetivo, chamada de consulta. Logicamente, o motor Prolog tenta encontrar uma resolução refutação da consulta negada. O método de resolução usado por Prolog é chamado de resolução SLD . Se a consulta negado pode ser refutada, segue-se que a consulta, com as ligações variáveis apropriadas no lugar, é uma consequência lógica do programa. Nesse caso, todas as ligações variáveis geradas são relatados para o usuário, ea consulta é dito ter conseguido. Operacionalmente, estratégia de execução do Prolog pode ser pensado como uma generalização da função chama em outros idiomas, uma diferença é que várias cabeças cláusula pode corresponder a uma determinada chamada. Nesse caso, o sistema cria um ponto de escolha, unifica o objetivo com a cabeça cláusula da primeira alternativa, e continua com os objetivos de que a primeira alternativa. Se qualquer objetivo falha no curso da execução do programa, todas as ligações variáveis que foram feitas desde a escolha ponto mais recente foi criado são desfeitas, e a execução continua com a próxima alternativa de que a escolha de ponto. Esta estratégia de execução é chamado cronológica retrocesso . Por exemplo:

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
 
parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

Isto resulta na seguinte consulta a ser avaliada como verdadeira:

?- sibling(sally, erica).
Yes

Isto é obtido como se segue: Inicialmente, o único correspondente cláusula de cabeça para a consulta sibling(sally, erica)é o primeiro, de modo a revelar a consulta é equivalente a provar o corpo do referido artigo, com as ligações apropriadas variáveis no local, ou seja, o conjunto (parent_child(Z,sally), parent_child(Z,erica)). O objectivo seguinte para ser provado é o mais à esquerda deste conjunto, isto é, parent_child(Z, sally). Duas cabeças cláusula corresponder a esse objetivo. O sistema cria um ponto de escolha e tenta a primeira alternativa, cujo corpo é father_child(Z, sally). Este objectivo pode ser comprovada utilizando o fato father_child(tom, sally), de modo que a ligação Z = tomé gerado, e a próxima baliza a ser comprovado é a segunda parte do conjunto acima: parent_child(tom, erica). Novamente, isso pode ser comprovado pelo fato correspondente. Desde todas as metas poderia ser provado, a consulta for bem-sucedido. Desde a consulta não continha variáveis, não ligações são relatados para o usuário. Uma consulta com variáveis, tais como:

?- father_child(Father, Child).

enumera todas as respostas válidas em retrocesso.

Note-se que com o código como dito acima, a consulta ?- sibling(sally, sally).também consegue. Alguém poderia inserir metas adicionais para descrever as restrições relevantes, se desejar.

Loops e recursão

Algoritmos iterativos pode ser implementada por meio de predicados recursivos. Sistemas Prolog tipicamente implementar uma técnica de optimização chamado bem conhecida chamada cauda optimização (TCO) de predicados determinísticos exibem cauda recursão ou, mais geralmente, cauda chama: quadro de pilha de uma cláusula é descartado antes de efectuar uma chamada numa posição cauda. Portanto, predicados cauda-recursivo determinísticos são executados com espaço de pilha constante, como loops em outras línguas.

cortes

Um corte ( !) dentro de uma regra vai impedir Prolog de retrocesso quaisquer predicados atrás do corte:

predicate(X) :- one(X), !, two(X).

falhará se o primeiro-encontrada valor Xpara o qual one(X)é verdadeiro leva a two(X)ser falso.

Variáveis ​​anônimos

Variáveis anônimas _não são obrigados a um valor e pode ser usado várias vezes em um predicado.

Por exemplo procurando uma lista para um dado valor:

contains(V, []) :- false.
contains(V, [V|_]) :- true.
contains(V, [_|T]) :- contains(V, T).

Negação

O predicado Prolog embutido \+/1fornece negação como falha , o que permite não monótona raciocínio. O objetivo \+ illegal(X)na regra

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

é avaliada como se segue: Prolog tentativas para provar a illegal(X). Se uma prova para esse objetivo pode ser encontrado, o objetivo original (ou seja, \+ illegal(X)) falhar. Se nenhuma prova pode ser encontrado, o objetivo original bem-sucedido. Portanto, o \+/1operador de prefixo é chamado o operador "não provável", uma vez que a consulta ?- \+ Goal.for bem-sucedido se o objetivo não é demonstrável. Este tipo de negação é som se seu argumento é "terra" (ou seja, não contém variáveis). Solidez é perdido se o argumento contém variáveis. Em particular, a consulta ?- legal(X).agora pode não ser usado para enumerar todas as coisas que são legais.

Semântica

Sob uma leitura declarativa, a ordem das regras e dos objetivos dentro regras, é irrelevante, uma vez disjunção lógica e conjunto são comutativos. Processualmente, no entanto, muitas vezes é importante levar em estratégia conta execução do Prolog, quer por razões de eficiência, ou devido à semântica do impuros predicados internos para que a ordem das questões de avaliação. Além disso, como intérpretes Prolog tentar unificar cláusulas na ordem em que são fornecidas, não dar um ordenamento correto pode levar a recursividade infinita, como em:

predicate1(X) :-
  predicate2(X,X).
predicate2(X,Y) :-
  predicate1(X),
  X \= Y.

Dada esta ordem, qualquer consulta da forma

?- predicate1(atom).

deverá repetir-se até que a pilha está esgotada. Se, no entanto, nos últimos 3 linhas foram alteradas para:

predicate2(X,Y) :-
  X \= Y,
  predicate1(X).

a mesma consulta levaria a um No. resultado em um tempo muito curto.

gramática de cláusulas definidas

Há uma notação especial chamado gramática de cláusulas definidas ( DCG ). A regra definida via -->/2, em vez de :-/2se expandiu pelo pré-processador ( expand_term/2, uma instalação análogo ao macros em outros idiomas) de acordo com algumas regras de reescrita simples, resultando em cláusulas Prolog comuns. Mais notavelmente, a reescrita equipa o predicado com dois argumentos adicionais, que podem ser usados para enfiar implicitamente estado em torno de, análogas às mônadas em outros idiomas. DCG são muitas vezes utilizados para escrever analisadores ou geradores da lista, como eles também fornecem uma interface conveniente para listar as diferenças.

exemplo analisador

Um exemplo maior irá mostrar o potencial da utilização de Prolog em análise .

Dada a sentença expressa em forma de Backus-Naur :

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

Isto pode ser escrito em Prolog usando DCGs, correspondendo a um analisador preditivo com um sinal olhar em frente:

sentence(S)                --> statement(S0), sentence_r(S0, S).
sentence_r(S, S)           --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).
 
statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].
 
expression(E) --> term(T), expression_r(T, E).
expression_r(E, E)  --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).
 
term(T)       --> factor(F), term_r(F, T).
term_r(T, T)  --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).
 
factor(id(ID))   --> id(ID).
factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}.
 
id(a) --> [a].
id(b) --> [b].

Esse código define uma relação entre uma frase (dado como uma lista de tokens) e sua árvore de sintaxe abstrata (AST). Exemplo consulta:

?- phrase(sentence(AST), [a,=,1,+,3,*,b,;,b,=,0,;]).
AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;

A AST é representado usando termos Prolog e pode ser usado para aplicar as optimizações, compilar tais expressões de código de máquina, ou directamente para interpretar tais considerações. Como é típico para a natureza relacional de predicados, essas definições podem ser usados tanto para analisar e gerar frases, e também para verificar se um determinado árvore corresponde a uma determinada lista de tokens. Usando aprofundamento iterativo para enumeração justo, cada sentença arbitrária, mas fixo e sua AST correspondente será gerado, eventualmente:

?- length(Tokens, _), phrase(sentence(AST), Tokens).
 Tokens = [a, =, a, (;)], AST = assign(a, id(a)) ;
 Tokens = [a, =, b, (;)], AST = assign(a, id(b))
 etc.

Veja também

• Comparação de implementações Prolog

Referências