A linguagem de programação Prolog foi explicitamente apresentada como baseada na lógica matemática. A base dessa alegação era que um programa Prolog podia literalmente ser lido como um conjunto de fórmulas em um fragmento da lógica de primeira ordem, herdando o modelo de teoria e demonstração da lógica de primeira ordem.
Prolog foi desenvolvida em 1972 por Alain Colmerauer. Ela veio de uma colaboração entre Colmerauer em Marselha e Robert Kowalski em Edinburgo. Colmerauer estava trabalhando na compreensão da linguagem natural, usando lógica para representar semânticas e usando resolução para questionamento-resposta. Durante o verão de 1971, Colmerauer e Kowalski descobriram que a forma clausal da lógica poderia ser usada para representar gramáticas formais e que demonstrações do teorema da resolução poderia ser usado para análise gramatical. Eles observaram que algumas demonstrações de teoremas, como o da hiper-resolução, comportavam-se como analisadores ascendentes e outros, como resolução-SL (1971), comportavam-se como analisadores descendentes.
Durante o seguinte verão de 1972, Kowalski, novamente trabalhando com Colmerauer, observou que resolução-SL trata cláusulas universalmente quantificadas na forma declarativa de implicações
B1 e … e Bn implica H
como procedimentos de objetivo-redução
para mostrar/resolver H, mostrar/resolver B1 e … e Bn.
Essa interpretação dupla declarativa/procedimental depois foi formalizada na notação do Prolog
H :- B1, …, Bn.
que pode ser lida (e usada) tanto declarativamente como procedimentalmente. Tornou-se também claro que tais cláusulas poderiam ser restringidas para definir cláusulas ou cláusulas de Horn, em que H, B1, …, Bn são todos os predicados atômicos, e que resolução-SL poderia ser restrita (e gerada) para LUSH ou resolução-SLD.
Colmerauer, com Philippe Roussel, usou essa interpretação dupla de cláusulas assim como a base do Prolog, a qual foi implementada no verão e outono de 1972. O primeiro programa na linguagem, também escrito em 1972 e implementado em Marseille, foi um sistema francês de pergunta-resposta. A interpretação procedimental de Kowalski e LUSH foi depois descrita em um memorando em 1973, publicado em 1974.
A relação próxima entre interpretação declarativa e processual resulta numa característica típica das linguagens de programação lógica, embora a relação se torne mais complexa quando há negação, disjunção e outros quantificadores são permitidos em programas.
Negação por falha
Micro-Planner teve uma construção, chamada "thnot", que quando aplicada a uma expressão retorna o valor verdadeiro se (e somente se) a avaliação da expressão falha. Um operador equivalente é normalmente construído em implementações do Prolog moderno e tem sido chamado "negação por falha". Ele é normalmente escrito como not(p), onde p é um átomo cujas variáveis foram normalmente instanciadas no momento que not(p) é invocado. Uma sintaxe mais complexa (mas padrão) é \+ p . Literais de negação por falha podem ocorrer como condições not(Bi) no corpo das cláusulas do programa.
Ainda que incompleta, a regra de negação como falha é uma sólida regra de inferência (sob certas restrições) respeitando a conclusão de um programa. Conclusão de um programa lógico foi inicialmente definida por Keith Clark basicamente assemelhava-se a considerar o conjunto de todas as cláusulas do programa, com o mesmo predicado, do lado esquerdo,
H :- Corpo1
…
H :- Corpok
Como uma única fórmula equivalente
H sse (Corpo1 ou … ou Corpok)
Escrever o completamento também requer o uso explícito de predicado de igualdade e a inclusão de um conjunto de axiomas apropriados por igualdade. A noção de conclusão é estreitamente relacionada à técnica de circunscrição de McCarty para desenvolver um raciocínio não monotônico, e a suposição de um mundo fechado.
Como uma alternativa para semânticas de completamento, negação por falha também pode ser interpretada epistemologicamente, assim como na semântica de modelo estável do conjunto de respostas. Nesta interpretação, not(Bi) significa literalmente que Bi não é conhecido ou não é acreditado. A interpretação epistêmica tem a vantagem que pode ser combinada muito simplesmente com a negação clássica, assim como na "lógica de programação estendida", para formalizar frases como "o contrário não pode ser mostrado", onde "contrario" está a negação clássica e "que não pode ser mostrado" é a interpretação epistêmica da negação por falha.
Implementações
A primeira implementação do Prolog foi a Marseille Prolog, desenvolvida em 1972. O uso do Prolog como uma linguagem de programação prática teve seu ápice com o desenvolvimento de um compilador por David Warren em Edinburgo, em 1977. Alguns experimentos demonstraram que o Edinburgh Prolog podia competir com a velocidade de processamento de outras linguagens de programação simbólica tais como Lisp. O Edinburgh Prolog tornou-se o padrão de facto e influenciou a definição de Prolog padrão ISO.