My last brush with logic programming was when I was working through the original Seven Languages in Seven Weeks back in 2011 and learning a little bit of Prolog. That was an eye opening experience — letting the computer do the work just didn’t feel like any coding I had done before.

The first day of miniKanren was a bit of a faff.

I spent a little while thinking I'd not installed things properly, and then realised that a single quote could also introduce a symbol in Clojure. For it is the Clojure implementation of miniKanren that we are learning. The implementation is called core.logic and, once it was installed, everything became a lot easier.

Here is a quick intro to core logic from its implementor, David Nolen.

I got stuck on one of the harder questions, I couldn’t for the life of me work out how to recurse up and down a tree. I plan to drink beer now, so that may grant me its hoppy insight.

Here are the solutions I did manage to come up with.

Exercises

Easy exercises

Try running a logic program that has 2 membero goals, both with q as the first argument. What happens when the same element exists in both collections?

I wasn’t quite sure what this was after, so I did the simplest possible thing. Clearly q ought to be the thing that is in both collections whether that is an element, an whole collection or nothing, and that is indeed how it behaves.

user=> (run* [q] (membero q [1 2 3]) (membero q [3 4 5])) (3) user=> (run* [q] (membero q [1 2 3]) (membero q [1 2 3])) (1 2 3) user=> (run* [q] (membero q [1 2 3]) (membero q [6 6 6])) ()

appendo is a core.logic built-in that will append 2 lists. Write some logic programs similar to the membero examples to get a feel for how it works. Be sure to use q in each of the argument positions to see what happens.

Oh nice. It can work out what input would be required to create the list in the final place.

user=> (run* [q] (appendo [1 2] [3 4] q)) ((1 2 3 4)) user=> (run* [q] (appendo [1 2] q [3 4])) () user=> (run* [q] (appendo q [1 2] [3 4])) () user=> (run* [q] (appendo [1 2] q [1 2 3 4])) ((3 4)) user=> (run* [q] (appendo q [3 4] [1 2 3 4])) ((1 2)) user=> (run* [q] (appendo q [1 2] [1 2 3 4])) ()

Create languageo and systemo database relations and add the relevant facts based on what category bst classifies the person’s work.

Here is the data base setup form the book. I added some extra gender identities.

user=> (use 'clojure.core.logic.pldb) nil user=> (db-rel mano x) #'user/mano user=> (db-rel womano x) #'user/womano user=> (db-rel transo x) #'user/transo user=> (db-rel intersexo x) #'user/intersexo user=> (db-rel genderqueero x) #'user/genderqueero user=> (db-rel vitalo p s) #'user/vitalo user=> (db-rel turingo p y) #'user/turingo user=> (db-rel languageo p l) #'user/languageo user=> (db-rel systemo p m) #'user/systemo user=> (def facts #_=> (db #_=> [mano :alan-turing] #_=> [womano :grace-hopper] #_=> [transo :laverne-cox] #_=> [mano :leslie-lamport] #_=> [mano :alonzo-church] #_=> [womano :ada-lovelace] #_=> [womano :barbara-liskov] #_=> [womano :frances-allen] #_=> [mano :john-mccarthy])) #'user/facts user=> (def facts #_=> (-> facts #_=> (db-fact vitalo :alan-turing :dead) #_=> (db-fact vitalo :grace-hopper :dead) #_=> (db-fact vitalo :laverne-cox :alive) #_=> (db-fact vitalo :leslie-lamport :alive) #_=> (db-fact vitalo :alonzo-church :dead) #_=> (db-fact vitalo :ada-lovelace :dead) #_=> (db-fact vitalo :barbara-liskov :alive) #_=> (db-fact vitalo :frances-allen :alive) #_=> (db-fact vitalo :john-mccarthy :dead) #_=> (db-fact turingo :leslie-lamport :2013) #_=> (db-fact turingo :barbara-liskov :2008) #_=> (db-fact turingo :john-mccarthy :1971) #_=> (db-fact turingo :frances-allen :2006)))

Now that I have that base, adding some extra facts is pretty trivial (note that I set up the relations already).

#'user/facts user=> (def facts #_=> (-> facts #_=> (db-fact languageo :alan-turing :turing) #_=> (db-fact languageo :grace-hopper :cobol) #_=> (db-fact languageo :grace-hopper :fortran) #_=> (db-fact languageo :leslie-lamport :tla) #_=> (db-fact languageo :alonzo-church :lambda-calculus) #_=> (db-fact languageo :ada-lovalace :note-g) #_=> (db-fact languageo :barbara-liskov :clu) #_=> (db-fact languageo :frances-allen :fortran) #_=> (db-fact languageo :frances-allen :autocoder) #_=> (db-fact languageo :john-mccarthy :lisp) #_=> (db-fact systemo :alan-turing :pilot-ace) #_=> (db-fact systemo :alan-turing :bombe) #_=> (db-fact systemo :alan-turing :turing-machine) #_=> (db-fact systemo :grace-hopper :univac) #_=> (db-fact systemo :ada-lovelace :analytical-engine)))

And now I can find living women who worked on CLU or the languages of all living folk in the database.

#'user/facts user=> (with-db facts #_=> (run* [q] #_=> (womano q) #_=> (vitalo q :alive) #_=> (languageo q :clu))) (:barbara-liskov) user=> (with-db facts #_=> (run* [q] #_=> (fresh [p l] #_=> (vitalo p :alive) #_=> (languageo p l) #_=> (== q [p l])))) ([:frances-allen :fortran] [:frances-allen :autocoder] [:barbara-liskov :clu] [:leslie-lamport :tla])

Medium exercises

Use conde to create scientisto, which suceeds for any of the men or women.

This was quite a hard exercise until I realized it actually wasn’t. We are just making a relation that is either man or woman. And that is pretty much what you write. Albeit in a Lisp-ish manner.

user=> (defn scientisto [e] #_=> (conde #_=> [(womano e)] #_=> [(mano e)] #_=> )) #'user/scientisto user=> (with-db facts (run* [q] (scientisto q))) (:grace-hopper :leslie-lamport :frances-allen :john-mccarthy :barbara-liskov :alonzo-church :ada-lovelace :alan-turing)

Construct a logic program that finds all the scientists who’ve won Turing Awards.

This seemed straightword enough and worked right away.

user=> (with-db facts #_=> (run* [q] #_=> (fresh [p y] #_=> (turingo p y) #_=> (== q [p y])))) ([:leslie-lamport :2013] [:barbara-liskov :2008] [:frances-allen :2006] [:john-mccarthy :1971])

Hard exercises

Create a genealogy system using a family tree database and relations like childo and spouseo. Then write functions that can traverse the tree like ancestro, descendanto, and cousino.

Creating the database for this was boring work. As you can see I created some redundant relationships. Child is just parent back to front after all.

user=> (db-rel childo p c) #'user/childo user=> (db-rel spouseo p s) #'user/spouseo user=> (db-rel parento p r) #'user/parento user=> (db-rel persono p) #'user/persono user=> (def family #_=> (db #_=> [persono :fred-flintstone] #_=> [persono :wilma-flintstone] #_=> [persono :barney-rubble] #_=> [persono :betty-rubble] #_=> [persono :bamm-bamm-rubble] #_=> [persono :pebbles-flintstone] #_=> [persono :roxy-rubble] #_=> [persono :chip-rubble] #_=> #_=> [spouseo :fred-flintstone :wilma-flintstone] #_=> [spouseo :barney-rubble :betty-rubble] #_=> [spouseo :pebbles-flintstone :bamm-bamm-rubble] #_=> #_=> [parento :chip-rubble :pebbles-flintstone] #_=> [parento :chip-rubble :bamm-bamm-rubble] #_=> [childo :pebbles-flintstone :chip-rubble] #_=> [childo :bamm-bamm-rubble :chip-rubble] #_=> #_=> [parento :roxy-rubble :pebbles-flintstone] #_=> [parento :roxy-rubble :bamm-bamm-rubble] #_=> [childo :bamm-bamm-rubble :roxy-rubble] #_=> [childo :pebbles-flintstone :roxy-rubble] #_=> #_=> [parento :bamm-bamm-rubble :barney-rubble] #_=> [parento :bamm-bamm-rubble :betty-rubble] #_=> [childo :betty-rubble :bamm-bamm-rubble] #_=> [childo :barney-rubble :bamm-bamm-rubble] #_=> #_=> [parento :pebbles-flintstone :fred-flintstone] #_=> [parento :pebbles-flintstone :wilma-flintstone] #_=> [childo :fred-flintstone :pebbles-flintstone] #_=> [childo :wilma-flintstone :pebbles-flintstone])) #'user/family

At this point I got stuck working out how to do recursion properly and had to content myself with doing some grandparent/grandchild relations.

user=> (defn grandparento [gc gp] #_=> (fresh [p] #_=> (parento gc p) #_=> (parento p gp))) #'user/grandparento user=> (with-db family (run* [q] (grandparento :bamm-bamm-rubble q))) () user=> (with-db family (run* [q] (grandparento :roxy-rubble q))) (:fred-flintstone :wilma-flintstone :betty-rubble :barney-rubble) user=> (defn grandchildo [gp gc] #_=> (fresh [c] #_=> (parento c gc) #_=> (parento gp c))) #'user/grandchildo user=> (with-db family (run* [q] (grandchildo q :fred-flintstone))) (:chip-rubble :roxy-rubble) user=> (with-db family (run* [q] (grandparento q :fred-flintstone))) (:chip-rubble :roxy-rubble)

Write a relation called extendo, which works like the bult-in appendo, mentioned in the easy problems.

I am pretty sure this is right and I found it a shitload easier to write than the ancestor stuff. Let me know in the comments if it is wrong somehow.

user=> (defn extendo [a b l] #_=> (conde #_=> [(== a ()) (== b l)] #_=> [(fresh [h t t2] #_=> (conso h t a) #_=> (conso h t2 l) #_=> (extendo t b t2))]) #_=> ) #'user/extendo user=> (run* [q] (extendo [1 2] [3 4] q)) ((1 2 3 4)) user=> (run* [q] (extendo [1 2] q [1 2 3 4])) ((3 4)) user=> (run* [q] (extendo q [3 4] [1 2 3 4])) ((1 2))