Como implementar um intérprete de prólogo em uma linguagem puramente funcional?

25

Existe uma referência clara, com pseudo-código, sobre como implementar um intérprete Prolog em uma linguagem puramente funcional? O que encontrei até agora parece lidar apenas com linguagens imperativas, é apenas uma demonstração do Prolog implementado por si só, ou não oferece nenhum algoritmo concreto para usar na interpretação. Eu ficaria muito agradecido por uma resposta.

Jimster
fonte
4
A Implementação do Prolog (Série Princeton em Ciência da Computação) por Patrice Boizumault possui a implementação do Lisp.
Will Ness
Veja esta resposta para uma abordagem relativamente nova.
false

Respostas:

24

Desde Prolog = Unificação Sintática + Encadeamento para Trás + REPL

Todas as três partes podem ser encontradas em Inteligência artificial: estruturas e estratégias para solução de problemas complexos por George F. Luger. Na quarta edição do livro, todas as três partes são implementadas no LISP na Seção 15.8, Programação lógica no LISP. Ele também coloca o mesmo código em seus outros livros, mas eu não tenho todos eles para anotar aqui. O código para seus livros pode ser encontrado aqui .

Outra fonte com as três partes pode ser encontrada em Paradigmas de programação de inteligência artificial: estudos de caso em Common Lisp, de Peter Norvig. Veja os Capítulos 11, Programação Lógica e 12, Compilando Programas Lógicos. O código para seu livro pode ser encontrado aqui .

Outra fonte é a estrutura e interpretação de programas de computador de Hal Abelson, Jerry Sussman e Julie Sussman. Veja Seção 4.4 Programação Lógica. O site do livro está aqui e o código do livro está aqui .

Não é incomum encontrar o algoritmo de unificação com encadeamento implementado em muitos aplicativos, se você souber onde procurar; é especialmente prevalente em inferências de tipo em compiladores funcionais. O uso da unificação de palavras-chave ou ocorre ajuda a identificar as funções. Além disso, a maioria das implementações usa unif para o nome da função de unificação.

Para uma versão do Prolog, menos o REPL, feito no OCaml, consulte Código e recursos para "Manual de lógica prática e raciocínio automatizado" - prolog.ml

Uma tradução do código do livro para F # pode ser encontrada aqui . Uma tradução do código do livro para Haskell pode ser encontrada aqui .

Em termos de localização do código, o algoritmo de unificação é mais fácil de encontrar e, em seguida, implementações com encadeamento embutido em aplicativos. Encontrar uma implementação totalmente funcional do Prolog em uma linguagem funcional com um REPL é o mais difícil. Na maioria das vezes, o código não está em um formato para uso direto no PROLOG; ele é altamente personalizado para aprimorar o desempenho; portanto, você pode encontrar o código, mas não valerá o preço do provocador das peças que você deseja. Meu conselho seria ler o livro de Luger e construí-lo do zero no seu idioma de escolha, mesmo que isso signifique instalar e aprender LISP e traduzir para isso.

EDITAR

Como essa é uma pergunta duplicada do StackOverflow, o OP é novo e, nos comentários, diz:

Para dar mais contexto, estou tentando implementar a inferência de tipos, no entanto, os intrincados recursos no sistema de tipos da minha linguagem (tipos dependentes, tipos de refinamento, tipos lineares para citar alguns dos menos comuns) me fazem sentir que seria seja útil basear minha inferência de tipo fora dos algoritmos que conduzem o Prolog, para obter um algoritmo muito geral. Observarei que sou totalmente autodidata, portanto meu conhecimento está ausente em grandes áreas.

Vou expandir isso aqui, mas percebo que o OP deve fazer uma nova pergunta.

Para algumas coisas de introdução, consulte implementação de inferência de tipo .

O melhor livro que conheço sobre isso é Tipos e linguagens de programação de Benjamin C. Pierce. O site do livro está aqui . Os recursos com links para o código OCaml estão aqui . E foi iniciada recentemente, mas a tradução mais completa disso para F # está aqui .

Tipos dependentes: pág. 462 Tipos de refinamento: pág. 207 Sistemas de lógica e tipo linear: pág. 109

Guy Coder
fonte
11
Guy Coder, seu senhor é um cavalheiro e um estudioso! Sua ajuda é muito útil, e não posso agradecer o suficiente por dedicar algum tempo para responder a essa pergunta. = D - Colaborador de Jimster e amigo cansado de pesquisa
Shenzao 11/11
Agradeço novamente, já obtive esses livros (isto é, não como em uma rápida viagem a uma livraria).
11132 Jimster
O código de @Jimster Norvig é agradável e claro, cabe na página IIRC. Não me lembro se é puro .
Will Ness
De interesse: unify_P3.py, que faz parte da Tarefa 2
Guy Coder