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

Primero, permítame felicitarlo por su fino icono pw0n1e.

Esta es una pregunta difícil de responder, en gran parte porque hay tantas variantes de miniKanren y Prolog. miniKanren y Prolog son realmente familias de idiomas, lo que hace difícil comparar sus características, o incluso cómo se utilizan en la práctica. Debido a esto, por favor tome todo lo que estoy a punto de decir con precaución: si digo que Prolog utiliza la búsqueda en profundidad, tenga en cuenta que muchos Prolog las implementaciones admiten otras estrategias de búsqueda, y que las estrategias de búsqueda alternativas también se pueden codificar a nivel de meta-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 se destaca en la implementación de sistemas basados en reglas simbólicas en los que el conocimiento declarativo se codifica en primer orden lógica. El lenguaje está optimizado para la expresividad y la eficiencia para este tipo de aplicaciones, a veces a expensas de la pureza lógica. Por ejemplo, por defecto Prolog no utiliza el "occur check" en unificación. Desde un punto de vista matemático / lógico, esta versión de unificación es incorrecta. Sin embargo, la comprobación de ocurrencia es costosa, y en la mayoría de los casos la falta de la comprobació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 y el uso de cortar (!) para controlar el retroceso. Estoy seguro de que estas decisiones eran absolutamente necesarias cuando se ejecuta 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 enormes (a menudo infinito!) buscar espacios.

Prolog soporta muchas características "extra-lógicas" o "no-lógicas", incluyendo cut, assert y retract, proyección de variables para aritmética usando is, y así sucesivamente. Muchas de estas características hacen que sea más fácil expresar el flujo de control complejo, y manipular la base de datos global de datos de Prolog. Una característica muy interesante de Prolog es que el código 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 primero 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 está bien conocido fuera del mundo Prolog. 'El arte del Prolog' describe esta técnica en detalle.

Se ha hecho un tremendo esfuerzo para mejorar las implementaciones de Prolog, la mayoría de las cuales están basadas en la Máquina Abstracta Warren (WAM). El WAM utiliza un modelo de efecto lateral en el que los valores se asignan destructivamente a las variables lógicas, con estos efectos secundarios deshaciéndose al retroceder. Se pueden agregar muchas características a Prolog extendiendo las instrucciones del WAM. Una desventaja de esto el enfoque es que los documentos de implementación de Prolog pueden ser difíciles de leer sin una comprensión sólida del WAM. Por otro lado, Prolog implementer 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 Prólogo 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 mucho más allá del estándar Prolog.)

Prolog tiene una hermosa sintaxis de estilo "pattern-matching" basada en unificación que resulta en programas muy sucintos. Los prologers 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 el WAM sea rápido, hay implementaciones de Prolog muy capaces y maduras. Como resultado, muchos grandes sistemas basados en el conocimiento se han escrito íntegramente en Prolog.

MiniKanren fue diseñado como una lógica mínima lenguaje de programación, con una implementación pequeña, fácilmente comprensible y fácilmente hackeable. miniKanren fue originalmente incrustado en Scheme, y ha sido portado a docenas de otros idiomas anfitriones durante la última década. La implementación de miniKanren más popular es ' core.lógica ' en Clojure, que ahora tiene muchas extensiones Prolog-como y una serie de optimizaciones. Recientemente, el núcleo de la implementación de miniKanren se ha simplificado aún más, lo que resulta en un pequeño "micro kernel" llamado "microKanren."miniKanren se puede implementar en la parte superior de este núcleo de microKanren. Portar microKanren o miniKanren a un nuevo idioma host se ha convertido en un ejercicio estándar para los programadores que aprenden miniKanren. Como resultado, los lenguajes de alto nivel más populares tienen al menos una implementación de miniKanren o microKanren.

Las implementaciones estándar de miniKanren y microKanren no contienen mutaciones u otros efectos secundarios, con una sola excepción: algunas versiones de miniKanren usan puntero igualdad para la comparación de variables lógicas. Considero esto un "efecto benigno", aunque muchas implementaciones evitan incluso este efecto al pasar un contador a través de la implementación. Tampoco existe una base de datos global fact. La filosofía de implementación de miniKanren se inspira 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 miras cuidadosamente la implementación, incluso podrías ver un par de mónadas. Búsqueda la implementación 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 que en Prolog. En Prolog, la búsqueda variable es tiempo constante, pero retroceder requiere deshacer los efectos secundarios. En miniKanren, la búsqueda de variables es más cara, pero retroceder es "gratis"."De hecho, no hay retroceso en miniKanren, debido a cómo se manejan los arroyos.

Un aspecto interesante de los miniKanren la implementación 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 a cada subproceso o proceso se le debe dar suficiente trabajo para compensar la sobrecarga de la paralelización. Sin embargo, este es un área de implementación de miniKanren que espero reciba más atención y experimentación.

MiniKanren usa la comprobación de ocurrencia para la unificación, y usa completa la búsqueda intercalada en lugar de la búsqueda en profundidad. El intercalado de búsqueda 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 desviará/bucle para siempre. miniKanren soporta algunos operadores extra-lógicos---conda, condu, y project, por ejemplo. conda y condu se pueden usar para simular el corte de Prolog, y project se puede usar para obtener el valor asociado con una variable lógica.

La presencia de conda, condu, y project---y la capacidad de modificar fácilmente la estrategia de búsqueda---permite a los programadores usar miniKanren como un lenguaje similar al Prolog incrustado. Esto es especialmente cierto para los usuarios del núcleo de Clojure.logic', que incluye muchas extensiones tipo 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 lo son interesado 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. Sospecho que miniKanren se ha vuelto popular como un lenguaje lógico incrustado debido a la implementación pequeña y pura del núcleo, junto con las charlas, publicaciones de blog, tutoriales y otros materiales educativos que han salido desde que 'The Reasoned Schemer' fue publicado.

Además del uso de miniKanren como un lenguaje de programación lógico integrado pragmático similar en espíritu a Prolog, miniKanren se está utilizando para la investigación en programación "relacional". Es decir, en la escritura de programas que se comportan como relaciones matemáticas en lugar de funciones matemáticas. Por ejemplo, en Scheme la función append puede anexar dos listas, devolviendo una nueva lista: la función call (append '(a b c) '(d e)) devuelve la lista (a b c d e). Sin embargo, también podemos tratar append como un relación de tres lugares en lugar de una función de dos argumentos. La llamada (appendo '(a b c) '(d e) Z) asociaría entonces la variable lógica Z con 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 (appendo X '(d e) '(a b c d e)) asocia X con (a b c), mientras que la llamada (appendo X Y '(a b c d e)) asocia X y Y con pares de listas que, cuando se adjuntan, 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), que producirá infinitos triples de listas X, Y, y Z tal que anexar X a Y produce Z.

Esta versión relacional de append se puede expresar 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 usar al menos algunas características extra-lógicas, como cut, que inhiben la capacidad de tratar el programa resultante como una relación. Por el contrario, miniKanren está explícitamente diseñado para apoyo este estilo de programación relacional. Las versiones más recientes de miniKanren tienen soporte para la resolución de restricciones simbólicas (symbolo, numbero, absento, restricciones de desequilibrio, programación lógica nominal) para hacer más fácil escribir programas no triviales como relaciones. En la práctica nunca uso ninguna de las características extra-lógicas de miniKanren, y escribo todos mis programas de 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 de Esquema que evalúan a la lista (I love you), o trivialmente generar quines (programas que evalúan a sí mismos).

MiniKanren hace 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 una programación lógica de restricciones orientada simbólicamente idioma. En muchos casos, estas restricciones simbólicas hacen que sea práctico evitar el uso de operadores extra-lógicos como condu y project. En otros casos, estas limitaciones simbólicas no son suficientes. Un mejor apoyo a 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 es vale la pena aprender las ideas de ambos idiomas. Hay otros lenguajes de programación lógicos muy interesantes, como Mercury, Curry y Gödel, cada uno de los cuales tiene su propia versión de la programación lógica.

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

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

Will Will