miniKanren, programación lógica diminuta

Cuando hablamos de programación lógica, lo primero que se nos viene a la mente es Prolog, un lenguaje del que ya he hablado varias veces, y que fue uno de los primeros lenguajes lógicos así como uno de los más populares. Hoy vengo a hablaros de una familia de lenguajes, llamada miniKanren, que demuestra que cualquier lenguaje de programación puede adoptar el paradigma lógico con solo 3 instrucciones. miniKanren está disponible como DSL en muchos lenguajes: Scheme, Haskell, Clojure (llamado core.logic), Python, C#, Elixir, Go, JavaScript, Rust, ... y prácticamente cualquier lenguaje.

Historia

miniKanren surgió originalmente en el libro The Reasoned Schemer, escrito por Daniel P. Friedman, William E. Byrd, Oleg Kiselyov, and Jason Hemann y publicado por MIT Press siendo la última edición la de 2018. miniKanren se implementa originalmente en Scheme (algo bastante habitual para el MIT) pero sus principios básicos se pueden implementar en cualquier lenguaje de programación de tipo general.

Así, es posible añadir el paradigma lógico a cualquier lenguaje añadiendo únicamente 3 funciones. Este conjunto de 3 funciones se denomina microKanren y normalmente las implementaciones de miniKanren implementan microKanren en el lenguaje de destino y el resto de miniKanren se implementa usando las funciones definidas en microKanren. Así miniKanren es una familia de lenguajes que no comparten sintaxis (la sintaxis depende del lenguaje de destino) aunque generalmente es muy parecida. Yo usaré miniKanren para Python, ya que es una implementación completa en un lenguaje bastante popular.

Las funciones de microKanren son las siguientes:

• ==
  • Realiza la operación de unificación, que ya comenté en la ihttps://blog.adrianistan.eu/introduccion-a-prolog-tutorial-en-espanolntroducción a Prolog y básica en programación lógica
• fresh
  • Introduce un nuevo scope, definiendo variables lógicas. A su vez, realiza la conjunción de las relaciones que se definen.
• conde
  • Introduce la posibilidad de múltiples respuestas, definiendo varios conjuntos independientes donde todas los predicados tienen que ser ciertos a la vez. Esto es una mezcla de AND y OR a la vez. Veremos un ejemplo más abajo.

Tutorial básico de miniKanren

Para el pequeño tutorial voy a usar LogPy, un dialecto de miniKanren para Python. Se instala fácilmente a través de PyPI.

Una vez lo tengamos instalado, vamos a ejecutar nuestro primer programa en miniKanren. 

from kanren import run, eq, var

x = var()
sol = run(1,x,eq(x,42))
print(sol[0])

En la primera línea importamos las funciones que vamos a usar, run, eq y var. var nos permite crear variables lógicas, que podemos usar en nuestros programas miniKanren. Cumple la misma función que fresh. run ejecuta el programa miniKanren. Tiene varios argumentos. El primero es el número de soluciones a buscar, el segundo es sobre qué variables vamos a buscar soluciones. El resto de argumentos, son predicados del programa miniKanren. En este caso usamos eq que es == pero como Python no admite la sintaxis, se modifica el nombre. Básicamente estamos pidiendo que X unifique con 42. La solución, que es un array de soluciones, nos indica claramente que para que X unifique con 42, X tiene que ser 42.

Si te acuerdas de Prolog, probablemente te estés preguntando como hacer relaciones, por supuesto miniKanren las soporta:

from kanren import run, var, Relation, facts

x = var()
parent = Relation()
facts(parent,("Homer","Bart"),
        ("Homer","Lisa"),
        ("Abe","Homer"))

sol = run(2,x,parent("Homer",x))
print(sol[0])
print(sol[1])

Para definir relaciones, primero creamos una relación. Después insertamos hechos correspondientes a esa relación. Esa relación la podemos usar en el código miniKanren de forma muy similar a Prolog. En este caso pedimos dos soluciones, ya que sabemos que existen dos posibles valores de X: Bart y Lisa.

Como hemos dicho, miniKanren no es un lenguaje independiente, es más bien un lenguaje ad-hoc al lenguaje que estamos usando. Por eso podemos combinar funciones de Python con miniKanren.

from kanren import run, eq, conde, var, Relation, facts

x = var()

parent = Relation()
facts(parent,("Homer","Bart"),
        ("Homer","Lisa"),
        ("Abe","Homer"))

def grandparent(x,z):
    y = var()
    return conde((parent(x,y), parent(y,z)))

sol = run(1,x,grandparent(x,"Bart"))
print(sol[0])

Obteniendo como respuesta "Abe". Aquí usamos conde. Conde hemos dicho antes que es un OR y AND a la vez. En un primer nivel es un OR, es decir, conde(A,B) es verdadero si A o B son verdaderos. Sin embargo si A y B son predicados compuestos, entre ellos se aplica la relación AND. Por ejemplo, conde((A,B,C),(D,E)) significa que o bien A, B y C son ciertos o D y E son ciertos para que el predicado sea cierto.

Con esto ya estamos listos para recrear el Hola Mundo del paradigma lógico, la mortalidad de Sócrates.

from kanren import run, var, fact, Relation

x = var() 
human = Relation()

fact(human,"Socrates")

def mortal(x):
    return human(x)

sol = run(1,x,mortal(x))
print(sol)

Así de simple y sencillo y sin tener que cambiar de lenguaje de programación.

Un predicado que suelen llevar las implementaciones de miniKanren que no es estrictamente necesario es membero que es cierto cuando X pertenece a la lista.

from kanren import run, membero, var

x = var()
sol = run(1,x,
    membero(x,[1,2,3]),
    membero(x,[2,3,4])
    )
print(sol)

En este caso habría dos posibles respuestas (2 o 3) ya que ambos números cumplen la condición de estar en ambas listas a la vez. La respuesta final vendrá dada por la implementación de miniKanren (en LogPy da 2).

Diferencias con Prolog

Una vez visto miniKanren, quizá haga falta saber las diferencias que tiene respecto a Prolog. En primer lugar, Prolog es un lenguaje independiente, con el que podemos diseñar aplicaciones desde cero. Esto sin embargo suele ser un problema, ya que aunque para ciertas tareas la programación lógica es muy buena, para otras es un verdadero infierno. Además, esto ha hecho que el número de librerías que existen para Prolog sean muy limitadas. Con miniKanren no tenemos ese problema. Básicamente estamos usando el lenguaje base y cuando queramos realizar programación lógica usamos las funciones de miniKanren.

Prolog también es un lenguaje que se deriva del sistema lógico en varios puntos, como los cortes, o la base de datos modificable de hechos (assert y retract). Esto otorga flexibilidad, pero pierde en limpieza. Además, Prolog no realiza el chequeo de ocurrencias en la unificación, paso matemáticamente necesario pero computacionalmente costoso y que no suele suponer grandes diferencias de resultados en la práctica. Además Prolog soporta operaciones aritméticas. Esto no significa que en miniKanren no se puedan usar, pero dependen del lenguaje base, son por tanto indiferentes de cara a este DSL. Por otro lado en miniKanren no existe mutabilidad y todo código escrito es thread-safe, aunque no existen muchas implementaciones que aprovechen el paralelismo. En las búsquedas, Prolog suele usar el método primero en profundidad mientras que miniKanren suele ser primero en anchura.

Conclusión

Si bien Prolog es un lenguaje muy interesante, el hecho de ser algo separado lo ha hecho perder mucho interés durante los años y aunque se puede empotrar, esto no es fácil. miniKanren es un lenguaje lógico puro, que si bien es algo más limitado, la experiencia de uso es mejor. Quizá la mejor opción a día de hoy para realizar programación lógica en sistemas en producción. No obstante a día de hoy sigue faltando mucha documentación sobre miniKanren, aunque si tienes experiencia con Prolog, lo entenderás rápidamente.