Prolog - Prolog

Prolog
Paradigma Lógica
Projetado por Alain Colmerauer , Robert Kowalski
Apareceu pela primeira vez 1972 ; 49 anos atrás (1972)
Versão estável
Parte 1: Core-Edition 1 geral (junho de 1995 ; 26 anos atrás ) Parte 2: Módulos-Edition 1 (junho de 2000 ; 21 anos atrás )  (1995-06)
 (2000-06)
Disciplina de digitação Sem tipo (seu único tipo de dados é "termo")
Extensões de nome de arquivo .pl, .pro,.P
Local na rede Internet Parte 1: www .iso .org / standard / 21413 .html
Parte 2: www .iso .org / standard / 20775 .html
Implementações principais
B-Prolog , Ciao , ECLiPSe , GNU Prolog , Poplog Prolog, P # , Quintus Prolog , SICStus , Strawberry , SWI-Prolog , Tau Prolog , tuProlog, WIN-PROLOG , XSB , YAP .
Dialetos
ISO Prolog, Edinburgh Prolog
Influenciado por
Planejador
Influenciado
CHR , Clojure , Datalog , Erlang , KL0 , KL1 , Mercury , Oz , Strand , Visual Prolog , XSB

Prolog é uma linguagem de programação lógica associada à inteligência artificial e linguística computacional .

Prolog tem suas raízes na lógica de primeira ordem , uma lógica formal , e ao contrário de muitas outras linguagens de programação , Prolog é planejado principalmente como uma linguagem de programação declarativa : a lógica do programa é expressa em termos de relações , representadas como fatos e regras . Um cálculo é iniciado executando uma consulta sobre essas relações.

A linguagem foi desenvolvida e implementada em Marselha, França, em 1972 por Alain Colmerauer com Philippe Roussel, com base na interpretação processual de Robert Kowalski das cláusulas de Horn .

Prolog foi uma das primeiras linguagens de programação lógica e continua a ser a linguagem mais popular hoje, com várias implementações gratuitas e comerciais disponíveis. A linguagem tem sido usada para prova de teoremas , sistemas especialistas , reescrita de termos , sistemas de tipos e planejamento automatizado , bem como seu campo de uso pretendido original, processamento de linguagem natural . Os ambientes Prolog modernos suportam a criação de interfaces gráficas com o usuário , bem como aplicativos administrativos e de rede.

O Prolog é adequado para tarefas específicas que se beneficiam de consultas lógicas baseadas em regras, como pesquisa de bancos de dados , sistemas de controle de voz e preenchimento de modelos.

Sintaxe e semântica

No Prolog, a lógica do programa é expressa em termos de relações e um cálculo é iniciado executando uma consulta sobre essas relações. Relações e consultas são construídas usando o único tipo de dados do Prolog, o termo . As relações são definidas por cláusulas . Dada uma consulta, o mecanismo Prolog tenta encontrar uma refutação de resolução para a consulta negada. Se a consulta negada pode ser refutada, ou seja, uma instanciação para todas as variáveis ​​livres é encontrada que torna a união de cláusulas e o conjunto singleton consistindo na consulta negada falsa, segue-se que a consulta original, com a instanciação encontrada aplicada, é um conseqüência lógica do programa. Isso torna o Prolog (e outras linguagens de programação lógica) particularmente útil para aplicativos de banco de dados, matemática simbólica e análise de linguagem. Como o Prolog permite predicados impuros , verificar o valor verdadeiro de certos predicados especiais pode ter algum efeito colateral deliberado , como imprimir um valor na tela. Por causa disso, o programador tem permissão para usar alguma quantidade de programação imperativa convencional quando o paradigma lógico é inconveniente. Ele tem um subconjunto puramente lógico, denominado "Prolog puro", bem como uma série de recursos extralógicos.

Tipos de dados

O único tipo de dado do Prolog é o termo . Os termos são átomos , números , variáveis ou termos compostos .

  • Um átomo é um nome de propósito geral sem nenhum significado inerente. Exemplos de átomos incluem x, red, 'Taco', e 'some atom'.
  • Os números podem ser flutuantes ou inteiros . Os sistemas Prolog compatíveis com o padrão ISO podem verificar o sinalizador Prolog "limitado". A maioria dos principais sistemas Prolog suporta números inteiros de comprimento arbitrário.
  • Variáveis são denotadas por uma string consistindo de letras, números e caracteres de sublinhado, e começando com uma letra maiúscula ou sublinhado. As variáveis ​​se assemelham muito às variáveis ​​na lógica, pois são marcadores de posição para termos arbitrários.
  • Um termo composto é composto por um átomo denominado "functor" e uma série de "argumentos", que também são termos. Os termos compostos são normalmente escritos como um functor seguido por uma lista separada por vírgulas de termos de argumento, que está contida entre parênteses. O número de argumentos é denominado aridade do termo . Um átomo pode ser considerado um termo composto com aridade zero. Um exemplo de termo composto é person_friends(zelda,[tom,jim]).

Casos especiais de termos compostos:

  • Uma lista é uma coleção ordenada de termos. É denotado por colchetes com os termos separados por vírgulas ou, no caso da lista vazia, por []. Por exemplo, [1,2,3]ou [red,green,blue].
  • Strings : uma sequência de caracteres entre aspas é equivalente a uma lista de códigos de caracteres (numéricos), uma lista de caracteres (átomos de comprimento 1) ou um átomo, dependendo do valor do sinalizador Prolog double_quotes. Por exemplo "to be, or not to be",.

ISO Prolog fornece os atom/1, number/1, integer/1, e float/1predicados para verificação de tipo .

Regras e fatos

Os programas Prolog descrevem relações, definidas por meio de cláusulas. Pure Prolog é restrito a cláusulas de Horn . Existem dois tipos de cláusulas: fatos e regras. Uma regra é da forma

Head :- Body.

e é lido como "A cabeça é verdadeira se o corpo for verdadeiro". O corpo de uma regra consiste em chamadas para predicados, que são chamados de objetivos da regra . O operador lógico embutido ,/2(significando um operador arity 2 com nome ,) denota conjunção de objetivos e ;/2denota disjunção . Conjunções e disjunções só podem aparecer no corpo, não no cabeçalho de uma regra.

As cláusulas com corpos vazios são chamadas de fatos . Um exemplo de fato é:

cat(crookshanks).

o que equivale à regra:

cat(crookshanks) :- true.

O predicado embutido true/0é sempre verdadeiro.

Diante do fato acima, pode-se perguntar:

o bandido é um gato?

 ?- cat(crookshanks).
 Yes

que coisas são gatos?

 ?- cat(X).
 X = crookshanks

As cláusulas com corpos são chamadas de regras . Um exemplo de regra é:

animal(X) :- cat(X).

Se adicionarmos essa regra e perguntarmos o que são animais?

 ?- animal(X).
 X = crookshanks

Devido à natureza relacional de muitos predicados embutidos, eles podem ser usados ​​em várias direções. Por exemplo, length/2pode ser usado para determinar o comprimento de uma lista ( length(List, L)dada uma lista List), bem como para gerar um esqueleto de lista de um determinado comprimento ( length(X, 5)), e também para gerar os esqueletos de lista e seus comprimentos juntos ( length(X, L)). Da mesma forma, append/3pode ser usado para anexar duas listas (listas append(ListA, ListB, X)fornecidas ListAe ListB), bem como para dividir uma determinada lista em partes ( append(X, Y, List), dada uma lista List). Por esta razão, um conjunto comparativamente pequeno de predicados de biblioteca é suficiente para muitos programas Prolog.

Como uma linguagem de propósito geral, Prolog também fornece vários predicados embutidos para realizar atividades de rotina como entrada / saída , usando gráficos e de outra forma se comunicando com o sistema operacional. Esses predicados não recebem um significado relacional e são úteis apenas para os efeitos colaterais que exibem no sistema. Por exemplo, o predicado write/1exibe um termo na tela.

Execução

A execução de um programa Prolog é iniciada pela postagem do usuário de um único objetivo, chamado de consulta. Logicamente, o mecanismo do Prolog tenta encontrar uma refutação de resolução para a consulta negada. O método de resolução usado pelo Prolog é chamado de resolução SLD . Se a consulta negada pode ser refutada, segue-se que a consulta, com as associações de variáveis ​​apropriadas no lugar, é uma consequência lógica do programa. Nesse caso, todas as associações de variáveis ​​geradas são relatadas ao usuário e a consulta é considerada bem-sucedida. Operacionalmente, a estratégia de execução do Prolog pode ser pensada como uma generalização das chamadas de função em outras linguagens, uma diferença é que vários cabeçalhos de cláusula podem corresponder a uma determinada chamada. Nesse caso, o sistema cria um ponto de escolha, unifica a meta com a cláusula principal da primeira alternativa e continua com as metas dessa primeira alternativa. Se algum objetivo falhar durante a execução do programa, todas as associações de variáveis ​​feitas desde a criação do ponto de escolha mais recente são desfeitas e a execução continua com a próxima alternativa desse ponto de escolha. Essa estratégia de execução é chamada de retrocesso cronológico . 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).

Isso faz com que a seguinte consulta seja avaliada como verdadeira:

 ?- sibling(sally, erica).
 Yes

Isso é obtido da seguinte forma: Inicialmente, o único cabeçalho de cláusula correspondente para a consulta sibling(sally, erica)é o primeiro, portanto, provar que a consulta é equivalente a provar o corpo dessa cláusula com as associações de variáveis ​​apropriadas no lugar, ou seja, a conjunção (parent_child(Z,sally), parent_child(Z,erica)). O próximo objetivo a ser provado é o mais à esquerda dessa conjunção, ou seja parent_child(Z, sally),. Duas cabeças de cláusula correspondem a este objetivo. O sistema cria um ponto de escolha e tenta a primeira alternativa, de quem é o 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 provado pelo fato correspondente. Uma vez que todos os objetivos puderam ser provados, a consulta foi bem-sucedida. Como a consulta não continha variáveis, nenhuma ligação é relatada ao usuário. Uma consulta com variáveis, como:

?- father_child(Father, Child).

enumera todas as respostas válidas sobre retrocesso.

Observe que, com o código mencionado acima, a consulta ?- sibling(sally, sally).também é bem-sucedida. Seriam inseridos objetivos adicionais para descrever as restrições relevantes, se desejado.

Loops e recursão

Algoritmos iterativos podem ser implementados por meio de predicados recursivos.

Negação

O predicado Prolog embutido \+/1fornece negação como falha , o que permite raciocínio não monotônico . O objetivo \+ illegal(X)da regra

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

é avaliado da seguinte forma: Prolog tenta provar illegal(X). Se uma prova para esse objetivo puder ser encontrada, o objetivo original (isto é, \+ illegal(X)) falha. Se nenhuma prova for encontrada, o objetivo original foi bem-sucedido. Portanto, o \+/1operador de prefixo é chamado de operador "não comprovável", pois a consulta ?- \+ Goal.é bem-sucedida se a meta não for comprovável. Esse tipo de negação é válido se seu argumento for "base" (ou seja, não contém variáveis). A integridade é perdida se o argumento contém variáveis ​​e o procedimento de prova está completo. Em particular, a consulta ?- legal(X).agora não pode ser usada para enumerar todas as coisas que são legais.

Programação em Prolog

No Prolog, o código de carregamento é conhecido como consultoria . O Prolog pode ser usado interativamente inserindo consultas no prompt do Prolog ?-. Se não houver solução, Prolog escreve no. Se houver uma solução, ela será impressa. Se houver várias soluções para a consulta, elas podem ser solicitadas inserindo um ponto-e-vírgula ;. Existem diretrizes sobre boas práticas de programação para melhorar a eficiência, legibilidade e manutenção do código.

Seguem alguns exemplos de programas escritos em Prolog.

Olá Mundo

Um exemplo de consulta:

?- write('Hello World!'), nl.
Hello World!
true.

?-

Otimização do compilador

Qualquer cálculo pode ser expresso declarativamente como uma sequência de transições de estado. Por exemplo, um compilador de otimização com três passos de otimização pode ser implementado como uma relação entre um programa inicial e sua forma otimizada:

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

ou de forma equivalente usando a notação DCG :

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

Ordenação rápida

O algoritmo de classificação quicksort , relacionando uma lista à sua versão classificada:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].
quicksort([X|Xs]) -->
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

Padrões de design do Prolog

Um padrão de design é uma solução reutilizável geral para um problema comum em design de software . Alguns padrões de projeto no Prolog são esqueletos, técnicas, clichês, esquemas de programa, esquemas de descrição lógica e programação de ordem superior .

Programação de ordem superior

Um predicado de ordem superior é um predicado que recebe um ou mais outros predicados como argumentos. Embora o suporte para a programação de ordem mais elevada leva Prolog fora do domínio da lógica de primeira ordem, que não permite a quantificação sobre predicados, ISO Prolog tem agora alguns embutido predicados de ordem superior, tais como call/1, call/2, call/3, findall/3, setof/3, e bagof/3. Além disso, uma vez que objetivos arbitrários do Prolog podem ser construídos e avaliados em tempo de execução, é fácil escrever predicados de ordem superior como maplist/2, que aplica um predicado arbitrário a cada membro de uma determinada lista, e sublist/3, que filtra elementos que satisfazem um determinado predicado , também permitindo currying .

Para converter soluções de representação temporal (substituições de resposta no retrocesso) para representação espacial (termos), Prolog tem vários predicados de todas as soluções que coletam todas as substituições de resposta de uma determinada consulta em uma lista. Isso pode ser usado para compreensão de lista . Por exemplo, números perfeitos são iguais à soma de seus divisores apropriados:

 perfect(N) :-
     between(1, inf, N), U is N // 2,
     findall(D, (between(1,U,D), N mod D =:= 0), Ds),
     sumlist(Ds, N).

Isso pode ser usado para enumerar números perfeitos e também para verificar se um número é perfeito.

Como outro exemplo, o predicado maplistaplica um predicado Pa todas as posições correspondentes em um par de listas:

maplist(_, [], []).
maplist(P, [X|Xs], [Y|Ys]) :-
   call(P, X, Y),
   maplist(P, Xs, Ys).

Quando Pé um predicado que para todos X, P(X,Y)unifica Ycom um único valor único, maplist(P, Xs, Ys)equivale a aplicar a função de mapa na programação funcional como Ys = map(Function, Xs).

O estilo de programação de alta ordem no Prolog foi pioneiro em HiLog e λProlog .

Módulos

Para programação em grande escala , Prolog fornece um sistema de módulo . O sistema de módulos é padronizado pela ISO. No entanto, nem todos os compiladores Prolog suportam módulos e existem problemas de compatibilidade entre os sistemas de módulo dos principais compiladores Prolog. Conseqüentemente, os módulos escritos em um compilador Prolog não funcionarão necessariamente em outros.

Análise

Existe uma notação especial chamada gramáticas de cláusulas definidas (DCGs). Uma regra definida via em -->/2vez de :-/2é expandida pelo pré-processador ( expand_term/2um recurso análogo a macros em outras linguagens) de acordo com algumas regras de reescrita diretas, resultando em cláusulas Prolog comuns. Mais notavelmente, a reescrita equipa o predicado com dois argumentos adicionais, que podem ser usados ​​para encadear implicitamente o estado, análogo às mônadas em outras linguagens. Os DCGs são freqüentemente usados ​​para escrever analisadores ou geradores de lista, pois também fornecem uma interface conveniente para listas de diferenças.

Meta-intérpretes e reflexão

Prolog é uma linguagem homoicônica e oferece muitas facilidades para reflexão . Sua estratégia de execução implícita torna possível escrever um avaliador metacircular conciso (também chamado de meta-interpretador ) para código Prolog puro:

solve(true).
solve((Subgoal1,Subgoal2)) :- 
    solve(Subgoal1),
    solve(Subgoal2).
solve(Head) :- 
    clause(Head, Body),
    solve(Body).

onde truerepresenta uma conjunção vazia e clause(Head, Body)unifica com cláusulas no banco de dados do formulário Head :- Body.

Como os programas Prolog são sequências de termos Prolog ( :-/2é um operador infixo ) que são facilmente lidos e inspecionados usando mecanismos embutidos (como read/1), é possível escrever interpretadores personalizados que aumentam o Prolog com recursos específicos de domínio. Por exemplo, Sterling e Shapiro apresentam um meta-intérprete que executa o raciocínio com incerteza, reproduzido aqui com pequenas modificações:

solve(true, 1) :- !.
solve((Subgoal1,Subgoal2), Certainty) :-
    !,
    solve(Subgoal1, Certainty1),
    solve(Subgoal2, Certainty2),
    Certainty is min(Certainty1, Certainty2).
solve(Goal, 1) :-
    builtin(Goal), !, 
    Goal.
solve(Head, Certainty) :-
    clause_cf(Head, Body, Certainty1),
    solve(Body, Certainty2),
    Certainty is Certainty1 * Certainty2.

Este interpretador usa uma tabela de predicados Prolog embutidos do formulário

builtin(A is B).
builtin(read(X)).
% etc.

e cláusulas representadas como clause_cf(Head, Body, Certainty). Diante disso, pode ser acionado solve(Goal, Certainty)para executar Goale obter uma medida de certeza sobre o resultado.

Completude de Turing

Pure Prolog é baseado em um subconjunto da lógica de predicados de primeira ordem , cláusulas de Horn , que é Turing-complete . A integridade de Turing do Prolog pode ser mostrada usando-o para simular uma máquina de Turing:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
 
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Um exemplo simples de máquina de Turing é especificado pelos fatos:

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

Esta máquina executa a incrementação por um de um número na codificação unária: ela faz um loop em qualquer número de células "1" e acrescenta um "1" adicional no final. Consulta de exemplo e resultado:

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

Isso ilustra como qualquer cálculo pode ser expresso declarativamente como uma sequência de transições de estado, implementadas no Prolog como uma relação entre estados sucessivos de interesse.

Implementação

ISO Prolog

O padrão ISO Prolog consiste em duas partes. ISO / IEC 13211-1, publicado em 1995, visa padronizar as práticas existentes das muitas implementações dos elementos centrais do Prolog. Ele esclareceu aspectos da linguagem que antes eram ambíguos e leva a programas portáteis. Existem três retificações: Cor.1: 2007, Cor.2: 2012 e Cor.3: 2017. ISO / IEC 13211-2, publicado em 2000, adiciona suporte para módulos ao padrão. O padrão é mantido pelo grupo de trabalho ISO / IEC JTC1 / SC22 / WG17. ANSI X3J17 é o Grupo Consultivo Técnico dos EUA para o padrão.

Compilação

Para maior eficiência, o código Prolog é normalmente compilado para abstrair o código de máquina, geralmente influenciado pelo conjunto de instruções Warren Abstract Machine (WAM) baseado em registradores . Algumas implementações empregam interpretação abstrata para derivar informações de tipo e modo de predicados em tempo de compilação, ou compilar em código de máquina real para alto desempenho. Elaborar métodos de implementação eficientes para o código Prolog é um campo de pesquisa ativa na comunidade de programação lógica, e vários outros métodos de execução são empregados em algumas implementações. Isso inclui binarização de cláusulas e máquinas virtuais baseadas em pilha .

Recursão de cauda

Os sistemas Prolog normalmente implementam um método de otimização bem conhecido chamado otimização de chamada final (TCO) para predicados determinísticos exibindo recursão final ou, mais geralmente, chamadas finais: o quadro de pilha de uma cláusula é descartado antes de realizar uma chamada em uma posição final. Portanto, predicados recursivos de cauda determinísticos são executados com espaço de pilha constante, como loops em outras linguagens.

Indexação de termos

Encontrar cláusulas que são unificáveis ​​com um termo em uma consulta é linear no número de cláusulas. A indexação de termos usa uma estrutura de dados que permite pesquisas de tempo sublinear. A indexação afeta apenas o desempenho do programa, não afeta a semântica. A maioria dos Prologs usa a indexação apenas no primeiro termo, pois a indexação em todos os termos é cara, mas as técnicas baseadas em palavras codificadas por campo ou palavras - código sobrepostas fornecem indexação rápida em toda a consulta e no cabeçalho.

Hashing

Alguns sistemas Prolog, como WIN-PROLOG e SWI-Prolog, agora implementam hashing para ajudar a lidar com grandes conjuntos de dados com mais eficiência. Isso tende a gerar ganhos de desempenho muito grandes ao trabalhar com grandes corpora, como o WordNet .

Tabela

Alguns sistemas Prolog, ( B-Prolog , XSB , SWI-Prolog , YAP e Ciao ), implementam um método de memoização chamado tabling , que libera o usuário de armazenar manualmente os resultados intermediários. A tabulação é uma troca de espaço-tempo ; o tempo de execução pode ser reduzido usando mais memória para armazenar resultados intermediários:

As submetas encontradas em uma avaliação de consulta são mantidas em uma tabela, junto com as respostas a essas submetas. Se uma subobjetiva for encontrada novamente, a avaliação reutiliza as informações da tabela em vez de repetir a resolução nas cláusulas do programa.

A tabulação pode ser estendida em várias direções. Ele pode suportar predicados recursivos por meio de resolução SLG ou tabulação linear. Em um sistema Prolog multi-threaded, os resultados da tabela podem ser mantidos privados para um thread ou compartilhados entre todos os threads. E na mesa incremental, a mesa pode reagir às mudanças.

Implementação em hardware

Durante o projeto de Sistemas de Computador de Quinta Geração , houve tentativas de implementar Prolog em hardware com o objetivo de alcançar uma execução mais rápida com arquiteturas dedicadas. Além disso, o Prolog possui uma série de propriedades que podem permitir a aceleração por meio da execução paralela. Uma abordagem mais recente tem sido compilar programas Prolog restritos para um array de portas programáveis ​​em campo . No entanto, o rápido progresso em hardware de uso geral ultrapassou consistentemente arquiteturas mais especializadas.

Limitações

Embora Prolog seja amplamente utilizado em pesquisa e educação, Prolog e outras linguagens de programação lógica não tiveram um impacto significativo na indústria de computadores em geral. A maioria dos aplicativos é pequena para os padrões industriais, com alguns excedendo 100.000 linhas de código. A programação em geral é considerada complicada porque nem todos os compiladores Prolog suportam módulos e há problemas de compatibilidade entre os sistemas de módulo dos principais compiladores Prolog. A portabilidade do código Prolog entre as implementações também tem sido um problema, mas os desenvolvimentos desde 2007 significaram: "a portabilidade dentro da família de implementações Prolog derivadas de Edimburgo / Quintus é boa o suficiente para permitir a manutenção de aplicativos portáteis do mundo real."

O software desenvolvido em Prolog foi criticado por ter uma penalidade de alto desempenho em comparação com as linguagens de programação convencionais. Em particular, a estratégia de avaliação não determinística do Prolog pode ser problemática ao programar computações determinísticas, ou mesmo quando usar "não importa o não determinismo" (onde uma única escolha é feita ao invés de voltar atrás em todas as possibilidades). Cortes e outras construções de linguagem podem ter que ser usados ​​para atingir o desempenho desejável, destruindo uma das principais atrações do Prolog, a capacidade de executar programas "para frente e para trás".

Prolog não é puramente declarativo: por causa de construções como o operador cut , uma leitura procedural de um programa Prolog é necessária para entendê-lo. A ordem das cláusulas em um programa Prolog é significativa, pois a estratégia de execução da linguagem depende disso. Outras linguagens de programação lógica, como Datalog , são verdadeiramente declarativas, mas restringem a linguagem. Como resultado, muitos programas Prolog práticos são escritos em conformidade com a ordem de pesquisa em profundidade do Prolog , ao invés de programas lógicos puramente declarativos.

Extensões

Várias implementações foram desenvolvidas a partir do Prolog para estender os recursos de programação lógica em várias direções. Isso inclui tipos , modos, programação lógica de restrição (CLP), programação lógica orientada a objetos (OOLP), simultaneidade, lógica linear (LLP), recursos de programação lógica funcional e de ordem superior , além de interoperabilidade com bases de conhecimento :

Tipos

Prolog é uma linguagem sem tipo. As tentativas de introduzir tipos datam da década de 1980 e, a partir de 2008, ainda há tentativas de estender o Prolog com tipos. As informações de tipo são úteis não apenas para segurança de tipo, mas também para raciocinar sobre programas Prolog.

Modos

Especificador de modo Interpretação
+ nonvar na entrada
- var na entrada
? Não especificado

A sintaxe do Prolog não especifica quais argumentos de um predicado são entradas e quais são saídas. No entanto, esta informação é significativa e recomenda-se que seja incluída nos comentários. Os modos fornecem informações valiosas ao raciocinar sobre os programas Prolog e também podem ser usados ​​para acelerar a execução.

Restrições

A programação de lógica de restrição estende o Prolog para incluir conceitos de satisfação de restrição . Um programa de lógica de restrição permite restrições no corpo das cláusulas, tais como: A(X,Y) :- X+Y>0. É adequado para problemas de otimização combinatória em grande escala e, portanto, é útil para aplicações em ambientes industriais, como cronograma automatizado e programação de produção . A maioria dos sistemas Prolog vem com pelo menos um solucionador de restrições para domínios finitos, e freqüentemente também com solucionadores para outros domínios, como números racionais.

Orientação a objetos

Flora-2 é uma representação de conhecimento orientada a objetos e sistema de raciocínio baseado na lógica F e incorpora HiLog , lógica de transação e raciocínio inviável .

Logtalk é uma linguagem de programação lógica orientada a objetos que pode usar a maioria das implementações Prolog como um compilador de back-end. Como uma linguagem multiparadigma, inclui suporte para protótipos e classes.

Oblog é uma extensão pequena, portátil e orientada a objetos do Prolog de Margaret McDougall da EdCAAD, Universidade de Edimburgo.

Objlog era uma linguagem baseada em quadros que combinava objetos e Prolog II do CNRS, Marselha, França.

Prolog ++ foi desenvolvido pela Logic Programming Associates e lançado pela primeira vez em 1989 para PCs com MS-DOS. Foi adicionado suporte para outras plataformas e uma segunda versão foi lançada em 1995. Um livro sobre Prolog ++ de Chris Moss foi publicado pela Addison-Wesley em 1994.

Visual Prolog é uma linguagem multiparadigma com interfaces, classes, implementações e expressões de objetos.

Gráficos

Os sistemas Prolog que fornecem uma biblioteca gráfica são SWI-Prolog , Visual Prolog , WIN-PROLOG e B-Prolog .

Simultaneidade

Prolog-MPI é uma extensão SWI-Prolog de código aberto para computação distribuída na interface de passagem de mensagem . Além disso, existem várias linguagens de programação Prolog concorrentes.

Programação da Web

Algumas implementações de Prolog, notavelmente Visual Prolog , SWI-Prolog e Ciao , suportam programação web do lado do servidor com suporte para protocolos web, HTML e XML . Também existem extensões para suportar formatos de web semântica , como RDF e OWL . Prolog também foi sugerido como uma linguagem do lado do cliente . Além disso, o Visual Prolog oferece suporte a JSON-RPC e Websockets .

Adobe Flash

Cedar é um intérprete Prolog básico e gratuito. A partir da versão 4 e superior, o Cedar tem suporte para FCA (Flash Cedar App). Isso fornece uma nova plataforma para programação em Prolog por meio do ActionScript .

De outros

Interfaces para outros idiomas

Existem estruturas que podem fazer a ponte entre o Prolog e outras linguagens:

  • O LPA Intelligence Server permite a incorporação do LPA Prolog para Windows em C, C #, C ++, Java, VB, Delphi, .Net, Lua, Python e outras linguagens. Ele explora o tipo de dados de string dedicado que o LPA Prolog fornece
  • A API Logic Server permite a extensão e incorporação de Prolog em C, C ++, Java, VB, Delphi, .NET e qualquer linguagem / ambiente que possa chamar um .dll ou .so. Ele é implementado para Amzi! Prolog Amzi! Prolog + Logic Server, mas a especificação da API pode ser disponibilizada para qualquer implementação.
  • JPL é uma ponte Java Prolog bidirecional que vem com SWI-Prolog por padrão, permitindo que Java e Prolog chamem um ao outro (recursivamente). É conhecido por ter um bom suporte à concorrência e está em desenvolvimento ativo.
  • InterProlog , uma ponte de biblioteca de programação entre Java e Prolog, implementando predicado / método de chamada bidirecional entre as duas linguagens. Os objetos Java podem ser mapeados em termos do Prolog e vice-versa. Permite o desenvolvimento de GUIs e outras funcionalidades em Java, deixando o processamento lógico na camada Prolog. Suporta XSB , com suporte para SWI-Prolog e YAP planejado para 2013.
  • Prova fornece integração de sintaxe nativa com Java, mensagens de agente e regras de reação. Prova se posiciona como um sistema de script baseado em regras (RBS) para middleware. A linguagem inova ao combinar programação imperativa e declarativa .
  • PROL Um mecanismo Prolog embutido para Java. Inclui um pequeno IDE e algumas bibliotecas.
  • GNU Prolog para Java é uma implementação do ISO Prolog como uma biblioteca Java (gnu.prolog)
  • A Ciao fornece interfaces para C, C ++, Java e bancos de dados relacionais.
  • C # -Prolog é um interpretador Prolog escrito em C # (gerenciado). Pode ser facilmente integrado em programas C #. Características: interpretador confiável e razoavelmente rápido, interface de linha de comando, interface do Windows, DCG embutido, predicados XML, predicados SQL, extensível. O código-fonte completo está disponível, incluindo um gerador de analisador que pode ser usado para adicionar extensões para fins especiais.
  • A Warren Abstract Machine para PHP Um compilador e interpretador Prolog em PHP 5.3. Uma biblioteca que pode ser usada autônoma ou dentro do framework Symfony2.1 que foi traduzida do trabalho de Stephan Buettcher em Java que pode ser encontrada [aqui stefan .buettcher .org / cs / wam / index .html ]
  • tuProlog é um sistema Prolog leve para aplicativos e infraestruturas distribuídas, intencionalmente projetado em torno de um núcleo mínimo, para ser configurado estaticamente ou dinamicamente por carregamento / descarregamento de bibliotecas de predicados. tuProlog suporta nativamente a programação multiparadigma, fornecendo um modelo de integração limpo e contínuo entre Prolog e as principais linguagens orientadas a objetos - a saber, Java, para a versão tuProlog Java, e qualquer linguagem baseada em .NET (C #, F # ..), para tuProlog. Versão NET.

História

O nome Prolog foi escolhido por Philippe Roussel como uma abreviatura para programmation en logique ( francês para programação em lógica ). Foi criado por volta de 1972 por Alain Colmerauer com Philippe Roussel, com base na interpretação processual de Robert Kowalski das cláusulas de Horn . Foi motivado em parte pelo desejo de reconciliar o uso da lógica como uma linguagem de representação declarativa do conhecimento com a representação procedural do conhecimento que era popular na América do Norte no final dos anos 1960 e início dos anos 1970. De acordo com Robert Kowalski , o primeiro sistema Prolog foi desenvolvido em 1972 por Colmerauer e Phillipe Roussel. A primeira implementação do Prolog foi um intérprete escrito em Fortran por Gerard Battani e Henri Meloni. David HD Warren levou este intérprete para Edimburgo, e lá implementou um front-end alternativo, que veio definir a sintaxe “Prolog de Edimburgo” usada pela maioria das implementações modernas. Warren também implementou o primeiro compilador para Prolog, criando o influente DEC-10 Prolog em colaboração com Fernando Pereira. Warren mais tarde generalizou as idéias por trás do DEC-10 Prolog, para criar a Warren Abstract Machine .

Os pesquisadores europeus de IA favoreciam o Prolog, enquanto os americanos preferiam o Lisp , supostamente causando muitos debates nacionalistas sobre os méritos das línguas. Muito do desenvolvimento moderno do Prolog veio do ímpeto do projeto Fifth Generation Computer Systems (FGCS), que desenvolveu uma variante do Prolog chamada Kernel Language para seu primeiro sistema operacional .

Pure Prolog foi originalmente restrito ao uso de um provador de teorema de resolução com cláusulas de Horn da forma:

H :- B1, ..., Bn.

A aplicação do provador de teoremas trata tais cláusulas como procedimentos:

to show/solve H, show/solve B1 and ... and Bn.

O Prolog puro foi logo estendido, entretanto, para incluir a negação como falha , na qual condições negativas da forma não (B i ) são mostradas tentando-se e falhando em resolver as correspondentes condições positivas B i .

As extensões subsequentes do Prolog pela equipe original introduziram habilidades de programação de lógica de restrição nas implementações.

Uso na indústria

O Prolog foi usado no Watson . O Watson usa o software DeepQA da IBM e a estrutura Apache UIMA (Unstructured Information Management Architecture). O sistema foi escrito em várias linguagens, incluindo Java, C ++ e Prolog, e é executado no sistema operacional SUSE Linux Enterprise Server 11 usando a estrutura Apache Hadoop para fornecer computação distribuída. Prolog é usado para correspondência de padrões em árvores de análise de linguagem natural. Os desenvolvedores declararam: "Exigimos uma linguagem na qual pudéssemos expressar convenientemente as regras de correspondência de padrões sobre as árvores de análise e outras anotações (como resultados de reconhecimento de entidades nomeadas) e uma tecnologia que pudesse executar essas regras de maneira muito eficiente. Descobrimos que Prolog foi a escolha ideal para o idioma devido à sua simplicidade e expressividade. " Prolog está sendo utilizado na plataforma de desenvolvimento Low-Code GeneXus , que tem como foco a IA. O banco de dados de gráficos de código aberto TerminusDB é implementado no prólogo. TerminusDB é projetado para construir e curar gráficos de conhecimento de forma colaborativa .

Veja também

Linguagens relacionadas

  • A linguagem Gödel é uma implementação fortemente tipada de programação de lógica de restrição simultânea . É construído em SICStus Prolog.
  • Visual Prolog , anteriormente conhecido como PDC Prolog e Turbo Prolog, é um dialeto orientado a objetos fortemente tipado do Prolog, que é muito diferente do Prolog padrão. Como Turbo Prolog, ele foi comercializado pela Borland, mas agora é desenvolvido e comercializado pela empresa dinamarquesa PDC (Prolog Development Center) que o produziu originalmente.
  • Datalog é um subconjunto do Prolog. É limitado a relacionamentos que podem ser estratificados e não permite termos compostos. Em contraste com Prolog, Datalog não é Turing-completo .
  • Mercury é um desdobramento do Prolog voltado para a engenharia de software em geral com um sistema do tipo estático polimórfico, bem como um sistema de modo e determinismo.
  • GraphTalk é uma implementação proprietária da Máquina Abstrata de Warren, com propriedades adicionais orientadas a objetos.
  • De certa forma, Prolog é um subconjunto do Planner . As ideias no Planner foram posteriormente desenvolvidas na metáfora da comunidade científica .
  • AgentSpeak é uma variante do Prolog para programar o comportamento do agente em sistemas multiagentes .
  • Erlang começou com uma implementação baseada em Prolog e mantém muito da sintaxe baseada em unificação do Prolog.
  • Pilog é uma linguagem declarativa construída em cima do PicoLisp , que possui a semântica do Prolog, mas utiliza a sintaxe do Lisp.

Referências

Leitura adicional