¿Cuáles son las principales diferencias técnicas entre Prolog y miniKanren, con respecto a la programación lógica? [cerrado]

Cuando quiero leer sobre programación lógica, siempre me tropiezo con dos formas "principales" de hacerlo hoy en día:

• miniKanren , un minilenguaje introducido en The Reasoned Schemer y popular en este momento debido a core.logic .
• Prolog , el primer lenguaje de programación lógico "grande".

Lo que me interesa ahora: ¿Cuáles son las principales diferencias técnicas entre los dos? ¿Son muy similares en enfoque e implementación, o adoptan enfoques completamente diferentes para la programación lógica? ¿De qué ramas de las matemáticas proceden y cuáles son los fundamentos teóricos?

Primero, permítame felicitarlo por su excelente ícono pw0n1e.

Esta es una pregunta difícil de responder, en gran parte porque hay muchas variantes tanto de miniKanren como de Prolog. miniKanren y Prolog son realmente familias de lenguajes, lo que dificulta comparar sus características, o incluso cómo se usan en la práctica. Debido a esto, tome todo lo que voy a decir con precaución: si digo que Prolog usa la búsqueda en profundidad, tenga en cuenta que muchas implementaciones de Prolog son compatibles con otras estrategias de búsqueda y que las estrategias de búsqueda alternativas también se pueden codificar en el meta -nivel de intérprete. Aún así, miniKanren y Prolog tienen diferentes filosofías de diseño y hacen diferentes concesiones.

Prolog es uno de los dos lenguajes clásicos para la programación de inteligencia artificial simbólica (el otro lenguaje clásico es Lisp). Prolog sobresale en la implementación de sistemas simbólicos basados ​​en reglas en los que el conocimiento declarativo está codificado en lógica de primer orden. El lenguaje está optimizado para la expresividad y la eficiencia de este tipo de aplicaciones, a veces a expensas de la pureza lógica. Por ejemplo, de forma predeterminada, Prolog no utiliza la "verificación de ocurrencia" en la unificación. Desde un punto de vista matemático / lógico, esta versión de unificación es incorrecta. Sin embargo, la verificación de ocurrencia es costosa y, en la mayoría de los casos, la falta de la verificación de ocurrencia no es un problema. Esta es una decisión de diseño muy pragmática, al igual que el uso de Prolog de la búsqueda en profundidad primero y el uso de cut (!) para controlar el retroceso. Estoy seguro de que estas decisiones eran absolutamente necesarias cuando se ejecutaba en el hardware de la década de 1970, y hoy en día son muy útiles cuando se trabaja en grandes problemas y cuando se trata de espacios de búsqueda enormes (¡a menudo infinitos!).

Prolog admite muchas características "extra-lógicas" o "no lógicas", incluido el corte asserty la retractproyección de variables para aritmética usandois, Etcétera. Muchas de estas características facilitan la expresión de un flujo de control complejo y la manipulación de la base de datos global de hechos de Prolog. Una característica muy interesante de Prolog es que el código de Prolog se almacena en la base de datos global de hechos y se puede consultar en tiempo de ejecución. Esto hace que sea trivial escribir meta-intérpretes que modifiquen el comportamiento del código Prolog bajo interpretación. Por ejemplo, es posible codificar la búsqueda en amplitud en Prolog usando un meta-intérprete que cambia el orden de búsqueda. Esta es una técnica extremadamente poderosa que no es muy conocida fuera del mundo de Prolog. 'The Art of Prolog' describe esta técnica en detalle.

Se ha realizado un enorme esfuerzo para mejorar las implementaciones de Prolog, la mayoría de las cuales se basan en Warren Abstract Machine (WAM). El WAM utiliza un modelo de efectos secundarios en el que los valores se asignan de forma destructiva a las variables lógicas, y estos efectos secundarios se deshacen al dar marcha atrás. Se pueden agregar muchas funciones a Prolog ampliando las instrucciones del WAM. Una desventaja de este enfoque es que los documentos de implementación de Prolog pueden ser difíciles de leer sin un conocimiento sólido de WAM. Por otro lado, el implementador de Prolog tiene un modelo común para discutir los problemas de implementación. Ha habido una gran cantidad de investigación en paralelo Prolog, que culminó en Andorra Prolog en la década de 1990. Al menos algunas de estas ideas viven en Ciao Prolog. (Ciao Prolog está lleno de ideas interesantes, muchas de las cuales van más allá del estándar Prolog).

Prolog tiene una hermosa sintaxis de estilo de "coincidencia de patrones" basada en unificación que da como resultado programas muy sucintos. Los prólogos aman su sintaxis, al igual que los Lispers aman sus expresiones-s. Prolog también tiene una gran biblioteca de predicados estándar. Debido a toda la ingeniería que se ha invertido en hacer que WAM sea rápido, existen implementaciones de Prolog muy capaces y maduras. Como resultado, muchos grandes sistemas basados ​​en el conocimiento se han escrito completamente en Prolog.

miniKanren fue diseñado como un lenguaje de programación lógico mínimo, con una implementación pequeña, fácilmente comprensible y fácilmente pirateable. miniKanren se incorporó originalmente a Scheme y se ha adaptado a docenas de otros lenguajes host durante la última década. La implementación de miniKanren más popular es 'core.logic' en Clojure, que ahora tiene muchas extensiones similares a Prolog y una serie de optimizaciones. Recientemente, el núcleo de la implementación de miniKanren se ha simplificado aún más, dando como resultado un pequeño "micro kernel" llamado "microKanren". Luego, miniKanren se puede implementar sobre este núcleo de microKanren. Portar microKanren o miniKanren a un nuevo idioma anfitrión se ha convertido en un ejercicio estándar para los programadores que aprenden miniKanren. Como resultado,

Las implementaciones estándar de miniKanren y microKanren no contienen mutaciones ni otros efectos secundarios, con una sola excepción: algunas versiones de miniKanren usan la igualdad de punteros para comparar variables lógicas. Considero que esto es un "efecto benigno", aunque muchas implementaciones evitan incluso este efecto pasando un contador a través de la implementación. Tampoco existe una base de datos global de hechos. La filosofía de implementación de miniKanren está inspirada en la programación funcional: deben evitarse las mutaciones y los efectos, y todas las construcciones del lenguaje deben respetar el alcance léxico. Si observa detenidamente la implementación, es posible que incluso detecte un par de mónadas. La implementación de la búsqueda se basa en combinar y manipular flujos perezosos, una vez más sin usar mutación. Estas opciones de implementación conducen a compensaciones muy diferentes a las de Prolog. En Prolog, la búsqueda variable es un tiempo constante, pero el retroceso requiere deshacer los efectos secundarios. En miniKanren, la búsqueda de variables es más cara, pero el retroceso es "gratuito". De hecho, no hay retroceso en miniKanren, debido a cómo se manejan las transmisiones.

Un aspecto interesante de la implementación de miniKanren es que el código es inherentemente seguro para subprocesos y, al menos en teoría, trivialmente paralelizable. Por supuesto, paralelizar el código sin hacerlo más lento no es trivial, dado que cada hilo o proceso debe recibir suficiente trabajo para compensar la sobrecarga de la paralelización. Aún así, esta es un área de implementación de miniKanren que espero reciba más atención y experimentación.

miniKanren usa la verificación de ocurrencia para la unificación y usa una búsqueda intercalada completa en lugar de una búsqueda en profundidad. La búsqueda entrelazada utiliza más memoria que la búsqueda en profundidad, pero puede encontrar respuestas en algunos casos en los que la búsqueda en profundidad divergerá / repetirá para siempre. miniKanren hace soportar unos pocos operadores extralógicos --- conda, conduy project, por ejemplo. conday conduse puede utilizar para simular el corte de Prolog, y projectse puede utilizar para obtener el valor asociado con una variable lógica.

La presencia de conda, conduyproject--- y la capacidad de modificar fácilmente la estrategia de búsqueda --- permite a los programadores usar miniKanren como un lenguaje integrado similar a Prolog. Esto es especialmente cierto para los usuarios de 'core.logic' de Clojure, que incluye muchas extensiones similares a Prolog. Este uso "pragmático" de miniKanren parece explicar la mayor parte del uso de miniKanren en la industria. Los programadores que desean agregar un sistema de razonamiento basado en el conocimiento a una aplicación existente escrita en Clojure o Python o JavaScript generalmente no están interesados ​​en reescribir toda su aplicación en Prolog. Incrustar un pequeño lenguaje de programación lógica en Clojure o Python es mucho más atractivo. Una implementación de Prolog integrada funcionaría igual de bien para este propósito, presumiblemente.

Además del uso de miniKanren como un lenguaje pragmático de programación lógica embebida similar en espíritu a Prolog, miniKanren se está utilizando para la investigación en programación "relacional". Es decir, al escribir programas que se comporten como relaciones matemáticas en lugar de funciones matemáticas. Por ejemplo, en Scheme, la appendfunción puede agregar dos listas, devolviendo una nueva lista: la llamada a la función (append '(a b c) '(d e))devuelve la lista (a b c d e). Sin embargo, también podemos tratarlo appendcomo una relación de tres lugares en lugar de como una función de dos argumentos. La llamada (appendo '(a b c) '(d e) Z)luego asociaría la variable lógica Zcon la lista (a b c d e). Por supuesto, las cosas se vuelven más interesantes cuando colocamos variables lógicas en otras posiciones. La llamada se (appendo X '(d e) '(a b c d e))asocia Xcon (a b c), mientras que la llamada(appendo X Y '(a b c d e))asociados Xy Ycon pares de listas que, cuando se agregan, son iguales a (a b c d e). Por ejemplo, X= (a b)y Y= (c d e)son uno de esos pares de valores. También podemos escribir (appendo X Y Z), lo que producirá un número infinito de triples de las listas X, Yy Zde tal manera que anexar Xa Yproduce Z.

Esta versión relacional de appendpuede expresarse fácilmente en Prolog y, de hecho, se muestra en muchos tutoriales de Prolog. En la práctica, los programas Prolog más complejos tienden a utilizar al menos algunas características extralógicas, como cortar, que inhiben la capacidad de tratar el programa resultante como una relación. Por el contrario, miniKanren está diseñado explícitamente para admitir este estilo de programación relacional. Las versiones más recientes de miniKanren tienen soporte para resolución de restricciones simbólica ( symbolo, numbero,absento, restricciones de desigualdad, programación lógica nominal) para facilitar la escritura de programas no triviales como relaciones. En la práctica, nunca utilizo ninguna de las características extra-lógicas de miniKanren y escribo todos mis programas miniKanren como relaciones. Los programas relacionales más interesantes son los intérpretes relacionales para un subconjunto de Scheme. Estos intérpretes tienen muchas habilidades interesantes, como generar un millón de programas Scheme que evalúan a la lista (I love you), o generar trivialmente quines (programas que se evalúan a sí mismos).

miniKanren realiza una serie de compensaciones para habilitar este estilo relacional de programación, que son muy diferentes de las compensaciones que hace Prolog. Con el tiempo, miniKanren ha agregado más restricciones simbólicas, convirtiéndose realmente en un lenguaje de programación de lógica de restricciones con orientación simbólica. En muchos casos, estas restricciones simbólicas hacen que sea práctico evitar el uso de operadores extralógicos como conduy project. En otros casos, estas limitaciones simbólicas no son suficientes. Un mejor soporte para las restricciones simbólicas es un área activa de la investigación de miniKanren, junto con la cuestión más amplia de cómo escribir programas más grandes y complejos como relaciones.

En resumen, tanto miniKanren como Prolog tienen características, implementaciones y usos interesantes, y creo que vale la pena aprender las ideas de ambos lenguajes. También hay otros lenguajes de programación lógica muy interesantes, como Mercury, Curry y Gödel, cada uno de los cuales tiene su propia versión de la programación lógica.

Terminaré con algunos recursos de miniKanren:

El sitio web principal de miniKanren: http://minikanren.org/

Una entrevista que di sobre programación relacional y miniKanren, incluida una comparación con Prolog: http://www.infoq.com/interviews/byrd-relational-programming-minikanren

Salud,

--Será

Respuesta tentativa:

AFAIK, "The Reasoned Schemer" introdujo la programación lógica básica en una sintaxis Scheme-y y un estilo de programación funcional, agregando en particular los objetivos constantes "#u" (falla) y "#s" (exitoso) a los valores booleanos "#t "y" #f ". Utilizaba el mismo enfoque de programación lógica que Prolog: búsqueda de unificación y retroceso. Veré si tengo algo de tiempo para recuperar ese libro de mi estante durante el fin de semana. La rama de las matemáticas es una lógica de primer orden de forma restringida, en este caso cláusulas de Horn y la Unificación de Resolución. Ver: Lógica computacional: Memorias del pasado y desafíos para el futuro de John Alan Robinson y Los primeros años de programación lógica de Robert Kowalski para un comienzo en frío.