semantica - ¿Cuáles son las principales diferencias técnicas entre Prolog y miniKanren, con respecto a la programación lógica?
red semantica de animales en prolog (2)
Cuando quiero leer sobre programación lógica, siempre me encuentro 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ógica "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 provienen y cuáles son los fundamentos teóricos?
Primero, permíteme felicitarte por tu excelente icono pw0n1e.
Esta es una pregunta difícil de responder, en gran parte porque hay muchas variantes de miniKanren y Prolog. miniKanren y Prolog son realmente familias de idiomas, lo que hace que sea difícil comparar sus características, o incluso cómo se usan en la práctica. Debido a esto, tome con precaución todo lo que voy a decir: si digo que Prolog usa una búsqueda profunda primero, tenga en cuenta que muchas implementaciones de Prolog admiten otras estrategias de búsqueda, y que las estrategias de búsqueda alternativas también se pueden codificar en el meta -interpretador nivel. Aún así, miniKanren y Prolog tienen diferentes filosofías de diseño y realizan diferentes compensaciones.
Prolog es uno de los dos lenguajes clásicos para la programación simbólica de inteligencia artificial (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 expresividad y eficiencia para 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 el 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, como lo es el uso de Prolog de búsqueda en profundidad y el uso de corte (
!
) Para controlar el retroceso.
Estoy seguro de que estas decisiones fueron absolutamente necesarias cuando se ejecutaban en el hardware de la década de 1970, y hoy 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", incluyendo cortar,
assert
y
retract
, la proyección de variables para el uso aritmético
is
, y así sucesivamente.
Muchas de estas características hacen que sea más fácil expresar un flujo de control complejo y manipular 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 metainterpretadores que modifiquen el comportamiento del código Prolog bajo interpretación.
Por ejemplo, es posible codificar la búsqueda de amplitud en Prolog utilizando un metainterpretador 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 han realizado enormes esfuerzos 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 retroceder. Se pueden agregar muchas características a Prolog extendiendo las instrucciones de WAM. Una desventaja de este 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, el implementador de Prolog tiene un modelo común para discutir 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 mucho 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 concisos. 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 dedicado a hacer que el 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 integró originalmente en Scheme y se ha portado a docenas de otros idiomas de 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 varias 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". miniKanren se puede implementar sobre este núcleo microKanren. Portar microKanren o miniKanren a un nuevo lenguaje anfitrión 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 miniKanren o microKanren.
Las implementaciones estándar de miniKanren y microKanren no contienen mutación u otros efectos secundarios, con una sola excepción: algunas versiones de miniKanren utilizan la igualdad de puntero para la comparación de variables lógicas. Considero que es un "efecto benigno", aunque muchas implementaciones evitan incluso este efecto al pasar un contador a través de la implementación. Tampoco hay una base de datos global de hechos. La filosofía de implementación de miniKanren se inspira en la programación funcional: se deben evitar las mutaciones y los efectos, y todas las construcciones del lenguaje deben respetar el alcance léxico. Si observa cuidadosamente la implementación, incluso podría detectar un par de mónadas. La implementación de búsqueda se basa en combinar y manipular flujos diferidos, 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 el retroceso requiere deshacer los efectos secundarios. En miniKanren, la búsqueda variable es más costosa, 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 paralelo. Por supuesto, paralelizar el código sin hacerlo más lento no es trivial, dado que a cada hilo o proceso se le debe dar 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 completa de entrelazado en lugar de una búsqueda de profundidad primero.
La búsqueda entrelazada utiliza más memoria que la búsqueda de profundidad primero, pero puede encontrar respuestas en algunos casos en los que la búsqueda de profundidad primero divergerá / se repetirá para siempre.
miniKanren admite algunos operadores extra lógicos:
conda
,
condu
y
project
, por ejemplo.
conda
y
condu
pueden usarse para simular el corte de Prolog, y el
project
puede usarse 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 incrustado 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ía 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.
Sospecho que miniKanren se ha vuelto popular como un lenguaje lógico incrustado debido a la implementación básica pequeña y pura, junto con las charlas, publicaciones de blog, tutoriales y otros materiales educativos que han salido desde que se publicó ''The Reasoned Schemer''.
Además del uso de miniKanren como un lenguaje pragmático de programación lógica incrustado 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 comportan como relaciones matemáticas en lugar de funciones matemáticas.
Por ejemplo, en Scheme, la función
append
puede agregar dos listas, devolviendo una nueva lista: la llamada a la función
(append ''(abc) ''(de))
devuelve la lista
(abcde)
.
Sin embargo, también podemos tratar
append
como una relación de tres lugares en lugar de como una función de dos argumentos.
La llamada
(appendo ''(abc) ''(de) Z)
asociaría la variable lógica
Z
con la lista
(abcde)
.
Por supuesto, las cosas se ponen más interesantes cuando colocamos variables lógicas en otras posiciones.
La llamada
(appendo X ''(de) ''(abcde))
asocia
X
con
(abc)
, mientras que la llamada
(appendo XY ''(abcde))
asocia
X
e
Y
con pares de listas que, cuando se agregan, son iguales a
(abcde)
Por ejemplo,
X
=
(ab)
e
Y
=
(cde)
son uno de esos pares de valores.
También podemos escribir
(appendo XYZ)
, que producirá infinitos triples de listas
X
,
Y
y
Z
modo que agregar
X
a
Y
produzca
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 utilizar al menos algunas características extra lógicas, como el corte, que inhiben la capacidad de tratar el programa resultante como una relación.
En contraste, miniKanren está diseñado explícitamente para soportar 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 desigualdad, programación lógica nominal) para facilitar la escritura de 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 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 la lista
(I love you)
o generar quines trivialmente (programas que 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 restricción orientado simbólicamente.
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 restricciones 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 pregunta 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 idiomas. 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 visión de la programación lógica.
Terminaré con algunos recursos 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 estilo de programación funcional, agregando en particular los objetivos constantes "#u" (error) y "#s" (suceeed) a los valores booleanos "#t "y" #f ". Utilizaba el mismo enfoque para la programación lógica que Prolog: unificación y búsqueda de 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, las cláusulas de Horn y la Unificación de la Resolución. Ver: Lógica computacional: recuerdos 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 frío.