¿Cómo implementar un intérprete prólogo en un lenguaje puramente funcional?

25

¿Existe una referencia clara, con pseudocódigo, sobre cómo implementar un intérprete Prolog en un lenguaje puramente funcional? Lo que he encontrado hasta ahora parece tratar solo con lenguajes imperativos, es simplemente una demostración de Prolog implementado en sí mismo, o no ofrece un algoritmo concreto para usar para la interpretación. Le agradecería mucho una respuesta.

Jimster
fuente
44
La Implementación de Prolog (Serie Princeton en Ciencias de la Computación) por Patrice Boizumault tiene implementación de Lisp.
Will Ness
Vea esta respuesta para un enfoque relativamente nuevo.
falso

Respuestas:

24

Desde Prolog = Unificación sintáctica + Encadenamiento hacia atrás + REPL

Las tres partes se pueden encontrar en Inteligencia artificial: estructuras y estrategias para la resolución de problemas complejos por George F. Luger. En la cuarta edición del libro, las tres partes se implementan en LISP en la Sección 15.8, Programación lógica en LISP. También pone el mismo código en sus otros libros, pero no los tengo todos por señalar aquí. El código de sus libros se puede encontrar aquí .

Se puede encontrar otra fuente con las tres partes en Paradigmas de programación de inteligencia artificial: estudios de casos en Common Lisp por Peter Norvig. Consulte los capítulos 11, Programación lógica y 12, Compilación de programas lógicos. El código de su libro se puede encontrar aquí .

Otra fuente es Estructura e interpretación de programas de computadora de Hal Abelson, Jerry Sussman y Julie Sussman. Consulte la Sección 4.4 Programación lógica. El sitio para el libro está aquí y el código para el libro está aquí .

No es raro encontrar el algoritmo de unificación con encadenamiento inverso implementado en muchas aplicaciones si sabe dónde buscar; Es especialmente frecuente en la inferencia de tipos en compiladores funcionales. El uso de las palabras clave unificación u ocurre ayuda a detectar las funciones. Además, la mayoría de las implementaciones usan unif para el nombre de la función de unificación.

Para obtener una versión de Prolog, menos la REPL, realizada en OCaml, consulte Código y recursos para "Manual de lógica práctica y razonamiento automatizado" - prolog.ml

Una traducción del código del libro a F # se puede encontrar aquí . Puede encontrar una traducción del código del libro a Haskell aquí .

En términos de encontrar el código, el algoritmo de unificación es más fácil de encontrar, luego las implementaciones con encadenamiento incrustado en las aplicaciones. Encontrar una implementación completamente funcional de Prolog en un lenguaje funcional con un REPL es lo más difícil. La mayoría de las veces el código no está en un formato para uso directo dentro de PROLOG; está muy personalizado para mejorar el rendimiento, por lo que puede encontrar el código, pero no valdrá la pena el precio para extraer las piezas que desea. Mi consejo sería leer el libro de Luger y construirlo desde cero en el idioma de su elección, incluso si eso significa instalar y aprender LISP y traducir para hacerlo.

EDITAR

Dado que esta es una pregunta duplicada de StackOverflow y el OP es nuevo y en los comentarios dice:

Para dar más contexto, estoy tratando de implementar la inferencia de tipos, sin embargo, las características intrincadas en el sistema de tipos de mi lenguaje (tipos dependientes, tipos de refinamiento, tipos lineales para nombrar algunos de los menos comunes) me hacen sentir que sería Sería útil basar mi inferencia de tipos en los algoritmos que conducen a Prolog para obtener un algoritmo muy general. Notaré que soy completamente autodidacta, por lo que me falta conocimiento en grandes áreas.

Expandiré esto aquí, pero me doy cuenta de que el OP debe hacer una nueva pregunta.

Para algunas cosas de introducción, ver implementación de inferencia de tipos .

El mejor libro que conozco sobre esto es Tipos y lenguajes de programación de Benjamin C. Pierce. El sitio del libro está aquí . Los recursos con enlaces al código OCaml están aquí . Y recientemente comenzó, pero la traducción completa de esto a F # está aquí .

Tipos dependientes: pág. 462 Tipos de refinamiento: pág. 207 Lógica lineal y sistemas de tipos: pág. 109

Guy Coder
fuente
1
Guy Coder, señor, usted es un caballero y un erudito. Su ayuda es muy útil, y no puedo agradecerle lo suficiente por tomarse el tiempo para responder esta pregunta. = D - Colaborador de Jimster y amigo de la investigación
Shenzao
Le agradezco nuevamente, ya he obtenido estos libros (es decir, no como en un viaje rápido a una librería).
Jimster
El código de @Jimster Norvig es agradable y claro, cabe en una página IIRC. Sin embargo, no recuerdo si es puro .
Will Ness
De interés: unify_P3.py que es parte de la Tarea 2
Guy Coder