Origem
A linguagem de programação Prolog nasceu no início dos anos 1970 em um contexto acadêmico, inicialmente motivada por um projeto voltado ao processamento de linguagens naturais. Na Universidade de Marselha, Alain Colmerauer liderava uma equipe interessada em resolver problemas relacionados à dedução e linguística computacional. Ele e seu grupo, que incluía Robert Pasero e Philippe Roussel, começaram a trabalhar em um sistema que pudesse lidar com a resolução de sentenças lógicas.
A linguagem de programação Prolog nasceu no início dos anos 1970 em um contexto acadêmico, inicialmente motivada por um projeto voltado ao processamento de linguagens naturais. Na Universidade de Marselha, Alain Colmerauer liderava uma equipe interessada em resolver problemas relacionados à dedução e linguística computacional. Ele e seu grupo, que incluía Robert Pasero e Philippe Roussel, começaram a trabalhar em um sistema que pudesse lidar com a resolução de sentenças lógicas.
O nome Prolog, escolhido por Philippe Roussel, vem de "Programmation en Logique", refletindo a
essência lógica da linguagem. Essa linguagem rapidamente se destacou por permitir a descrição declarativa
de problemas e a dedução automática de soluções, algo extremamente inovador na época,
principalmente no campo da inteligência artificial.
Regras e fatos
Os programas Prolog descrevem relações, definidas por meio de cláusulas. O Prolog puro é restrito às cláusulas Horn Dois tipos de cláusulas Horn são usados para definir programas Prolog: regras e fatos. Uma regra é da forma
Cabeça :- Corpo .
e é lido como "Cabeça é verdadeira se Corpo é verdadeiro". O corpo de uma regra consiste em chamadas para predicados, que são chamados de objetivos da regra.O operador lógico embutido (significando um operador,/2 de aridade 2 com nome ) denota conjunção de objetivos e denota disjunção . Conjunções e disjunções só podem aparecer no corpo, não no cabeçalho de uma regra. ,;/2
Completude de Turing
Pure Prolog é baseado em um subconjunto de Lógica de predicados ordem,cláusula de Horn, que é Turing Completa. A completude de Turing de Prolog pode ser demonstrada usando-o para simular uma máquina de Turing:
turing ( Tape0 , Tape ) :-
executar ( q0 , [], Ls , Tape0 , Rs ),
reverter ( Ls , Ls1 ),
anexar ( Ls1 , Rs , Tape ).
executar ( qf , Ls , Ls , Rs , Rs ) :- !.
executar ( Q0 , Ls0 , Ls , Rs0 , Rs ) :-
símbolo ( Rs0 , Sym , RsRest ),
uma vez ( regra ( Q0 , Sym , Q1 , NewSym , Action )),
ação ( Ação , Ls0 , Ls1 , [ NewSym | RsRest ], Rs1 ),
executar ( Q1 , Ls1 , Ls , Rs1 , Rs ).
símbolo ([], b , []).
símbolo ([ Sym | Rs ], Sym , Rs ).
ação ( esquerda , Ls0 , Ls , Rs0 , Rs ) : esquerda ( Ls0 , Ls , Rs0 , Rs ).
ação ( ficar , Ls , Ls , Rs , Rs ).
ação ( direita , Ls0 , [ Sym | Ls0 ], [ Sym | Rs ], Rs ).
esquerda ([], [], Rs0 , [ b | Rs0 ]).
esquerda ([ L | Ls ], Ls , Rs , [ L | Rs ]).
Esse código implementa uma Máquina de Turing em Prolog. Uma Máquina de Turing é um modelo computacional que consiste em uma fita infinita (onde os dados são armazenados) e um cabeçote de leitura/escrita que pode mover-se para a esquerda ou direita ao longo da fita, além de modificar os símbolos.
Para eficiência, o código Prolog é normalmente compilado para código de máquina abstrata, frequentemente influenciado pelo conjunto de instruções Warren Abstract Machine (WAM) baseado em registro. Algumas implementações empregam interpretação abstrata para derivar informações de tipo e modo de predicados em tempo de compilação, ou compilam para código de máquina real para alto desempenho. Conceber métodos de implementação eficientes para 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 pilhas
Quebra-cabeça das Torres de Hanói
O objetivo deste famoso quebra-cabeça é mover N discos do pino esquerdo para o pino direito usando o pino central como um pino de retenção auxiliar. Em nenhum momento um disco maior pode ser colocado sobre um disco menor. O diagrama a seguir descreve a configuração inicial para N=3 discos.
Aqui está um programa Prolog recursivo que resolve o quebra-cabeça. Ele consiste em duas cláusulas.
mover(1,X,Y,_) :-
write('Mover disco superior de '),
escreva(X),
escreva('para'),
escreva(Y),
nl.
mover(N,X,Y,Z) :-
N>1,
M é N-1,
mover(M,X,Z,Y),
mover(1,X,Y,_),
mover(M,Z,Y,X).
Esse código é uma implementação do algoritmo de resolução da Torre de Hanói em Prolog, que instrui como mover discos entre pinos para resolver o quebra-cabeça.