Day 1: Unified Theories of Code

Three days is all we have to get you using logic productively, but because core.logic is embedded in Clojure, the more familiar functional programming is always nearby to help.

On the first day we’ll learn about unification and the basic logic operations. We’ll build a database of facts and see how core.logic can reason about them. Finally we’ll take a peek at conditionals in logic.

Day 2 will add some pattern matching and other macro sugar to the previous day’s topics. We’ll see how to unify and work with maps as well.

Finally, on the last day we’ll wrap up by learning about finite domains. By then you’ll be ready for some more complex examples too.

We’ll move fast, but by the end you should be able to explore on your own and start using logic in your own work.

Installing core.logic

To install core.logic you’ll need a Java Virtual Machine (JVM) and the Leiningen build tool. Leiningen will do all the hard work of fetching libraries for your project and managing Java’s library paths.

You can find a JVM for your platform in your system’s package manager or at Oracle’s Java download page.^[73] Leiningen and instructions to install it on most platforms can be found on its home page.^[74]

Once these are working, you can create a project with lein new:

This will create a project skeleton in the logical directory. In order to use core.logic in this project, you’ll need to add a few dependencies to the project’s project.clj file. Edit logical/project.clj to look like this:

Now inside the project’s directory, you should be able to fire up the Clojure REPL and load core.logic:

Logic is now at your fingertips. Note that the warning is benign and just lets you know that one of core.logic’s symbols has replaced one of the default ones.

Your Goal Is to Succeed

Logic programs are like puzzles where only some information is given and the solution to the puzzle is to find the rest of the information. Imagine a Sudoku square where at the start of the puzzle only the rules and a few numbers are known. Or think of a jigsaw puzzle, where only pieces of the picture and shapes are visible.

Programming with logic means providing some starting data and the rules of the puzzle. Core.logic does the actual work of solving the puzzle and provides the resulting solutions.

Let’s jump right in and look at some simple logic programs. We’ll be working at the REPL, which makes exploration easy. Try the following:

This may look like a simple program, but a lot is going on.

run* runs a logic program and returns the set of solutions. q is a logic variable. When logic variables are created, they are unbound or free. They have no value and could represent anything at all. The set of solutions will be the values of q that solve our puzzle. q seems to be the name most often used for the main logic variable, perhaps standing for “query.”

Every square in Sudoku would be a logic variable. Some of the squares are empty (free, unbound), and some are filled in (bound).

This logic program contains a single expression, (== q 1), which is not the equality test you are used to. == in core.logic is the unification function, and this expression attempts to unify the logic variable q with the number 1.

Unification is similar to pattern matching. You’re asking the language to try to make the left and right sides the same, assuming that’s possible. The left and right sides are compared as in normal equality tests, and any unbound logic variables are bound to values that would make the two sides match. In this example, q is bound to 1, which is a solution because there are no other rules. It may seem a bit strange, but we’ll see some more examples shortly that should give you an intuitive feel for what’s going on.

The expressions in a logic program are goals. They don’t return true or false but succeed or fail. It’s possible that success is achieved multiple times in different ways or not at all. This brings us to the last bit of our example: the result.

Our example returned (1). run* returns the values of q that result in success. In our example, unifying q with 1 binds q to the number 1 and succeeds. Our result is the list containing the single binding for q.

Let’s look at a failed goal:

This program has two expressions, each a goal. A program with multiple goals will succeed only if all of the goals succeed, similar to && or and operators in other languages. Here, the first unification will bind q to the number 1 just as before and succeed. The second unification will fail, since q is bound to 1 and 1 does not unify with 2. Because no binding of q can cause both goals to succeed, the resulting list is empty.

Getting Relational

It’s time for a look at logical functions:

membero is a relation. membero says that its first argument is a member of the collection given in the second argument. It is a goal, so it will either succeed or fail, and in doing so will bind q to values for which the goal succeeds. The result of our example shows that values of 1, 2, or 3 result in success. Note that we’ve not told core.logic how to solve a puzzle, only the rules.

run* will return all the possible bindings for q that result in success, so this is a complete list. It’s easy to look at this small program and convince yourself that the answer is correct. This is kind of an amazing trick.

You can use run to get a set number (or fewer) answers:

This is handy to know about because there might be an infinite number of ways to satisfy a goal.

Logic programming has even more magic up its sleeve. Let’s see what happens when we reverse the order of the arguments to membero:

You may find this result surprising, so let’s dig into it. Our original goal formulation, (membero q [1 2 3]), asked what the possible members of the collection are. The new formulation, (membero [1 2 3] q) asks what collections contain [1 2 3] as a member. There are an infinite number of possible collections that could contain [1 2 3]; thankfully we only asked for five answers.

The first answer is ([1 2 3] . _0). The . is the list construction operator. To the left of the . is the first element of the list (the head), and to the right of the . is the rest of the list (the tail). The weird _0 is the notation for an unbound logic variable. In this case it means the tail of the list could be anything. In other words, the first answer is that any list where [1 2 3] is the first element would satisfy the goal.

Now you can probably understand the other answers, too. The next answer is that any list with [1 2 3] as the second element would satisfy the goal, no matter what the first element and the rest of the list are.

This is like taking a fully solved Sudoku and asking for the possible starting states. I think it’s pretty cool, and I’ve never seen other languages able to run programs backward.

Programming with Facts

We’ve played a little with the basics of core.logic and seen that it finds bindings for q that satisfy the program’s goals. We also examined membero, a built-in relation that relates a member with a collection. Now we’ll try to write some relations of our own.

Core.logic includes a database, pldb, that allows us to construct simple relations built up with lists of facts. This is similar to a table in traditional database systems. For example, we can build two relations called mano and womano. We do this using db-rel. The first argument is the name of the relation, and the remaining arguments are placeholders.

Here we’ve created the two relations, which both take a single argument and will succeed if that argument is a man or a woman respectively.

We populate the relation by giving a list of facts to the db function and binding it to the variable facts. Each fact is a vector containing the relation and its arguments.

Querying our database is easy. Let’s find all the women:

The with-db function sets the data source for the database relations. It allows multiple databases to be used together or separately. Our logic program succeeds when q is one of the women, and so the answer is the list of women.

Let’s add some more relations, vitalo and turingo, which will relate men and women to their vital status and whether they’ve received the Turing Award:

We have enough facts to ask some interesting questions:

The goal succeeds for living women. Note that when a successful goal causes the logic variable q to be bound, that binding must hold in further relations.

To express more complicated programs, we often need more logic variables. The fresh function can create new, unbound logic variables:

​①​

We use fresh to create two new logic variables that are unbound.

​②​

Passing p to vitalo will cause it to be bound to a deceased person.

​③​

With p bound to something, we can now use turingo to bind to the year the person won the Turing Award. Note that only people who’ve won the Turing Award will satisfy the relation.

​④​

Finally, we bind q to a vector containing the person and the year.

The previous example can be summarized as “Which deceased people won the Turing Award?” One interesting property of logic programs is that the order of the goals is not important. In the previous example, it may appear that first we bind p, then y, and finally q, but these are declarative goals, not procedural steps—they can be satisfied regardless of their ordering:

Now we’ve shuffled the order of the goals. Specifically, q is unified before the goal that binds p. Core.logic will fill in the unbound placeholders when those variables are eventually bound. Or, as we saw previously, they may never get bound and will show up as _0, _1, and so on.

Parallel Universes

One macro remains for us to have all the logical ingredients for our programs: conde. You’ve seen that run, run*, and fresh all succeed only when all their goals succeed. This is similar to and and && in other languages. conde is a bit like or and ||.

Like or, conde succeeds if any of its goals succeed. However, unlike or, conde succeeds for every goal that succeeds independently. It’s a bit like running your program in parallel universes, where each branch of a conde runs in a new universe and you can detect all the possible successes.

Let’s see it in action:

Each branch of the conde is a list of goals. The branch succeeds if all its goals succeed, but the conde succeeds once for every branch that succeeds. The first branch succeeds and binds q to 1. In another universe, the second branch fails. In yet another universe, the third branch succeeds, binding q to :abc. The result is the list of successful bindings for q across all universes.

Dissecting a Spell

Earlier today you saw membero, which relates members to their collections. You’re almost ready to construct such a relation yourself, but first you need to learn about conso.

cons is the list construction function in Lisp, and unsurprisingly, conso is its relational cousin. conso relates the head and tail of a list to the whole list. Because it is a relation, it takes three arguments instead of two— Passing a logic variable as the last argument results in list construction very similar to cons.

We can pull out just the tail of the list as well.

Running conso backward destructures the list into its head and its tail. Here we create two new logic variables to hold these, and then we bind q to a vector of the results.

Now that you know how to pull apart and put together lists relationally and how to manipulate space-time with conde, we can build powerful recursive relations.

Let’s build insideo, which is equivalent to the built-in membero:

​①​

The first branch deconstructs the collection with conso and succeeds if the head is the same as the element that was passed in.

​②​

The second branch recursively calls insideo, looking for the element in the tail.

We can check that insideo works as we expect:

insideo works forward and backward, and in the last example, it can even figure out what element is required for it to succeed.

What We Learned in Day 1

If you’ve made it this far, you’re well on your way to mastering logic as well as space and time. You must formulate problems and constraints, but you needn’t worry about step-by-step solutions.

Today we covered a lot of logical ground. We learned how to write logic programs using run* and run. We also learned how logic variables and unification work. It’s a bit like having the computer solve a puzzle for you given some data and the rules. Using these, we were able to see the first bits of logic programming’s unique style by running the membero relation both forward and backward. If only functions in every language were so flexible!

Databases of facts can help build up bases of knowledge for your logic programs to reason over. You can use them to make inferences and queries. Databases can be combined and extended with new relations.

conde gives you power over multiple universes where all possibilities are calculated and observed. It’s the logical equivalent of branching like if and cond in other languages. Unlike traditional branching, all the branches get taken, but only the successful paths contribute to the answer.

Finally we learned how to create our own relations, even recursive ones. It may not seem like a lot of parts, but with just these pieces you can build a great many things.

Your Turn

Now’s your chance to practice solo with core.logic. Don’t worry, though, it starts off easy.

Find…

• The core.logic home page

• One of the many wonderful talks on core.logic or miniKanren by David Nolen or Dan Friedman and William Byrd

• A core.logic tutorial

• What other projects are doing with core.logic

Do (Easy):

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

• appendo is a core.logic built-in that will append two 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 three argument positions to see what happens.

• Create languageo and systemo database relations and add the relevant facts based on which category best classifies the person’s work.

Do (Medium):

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

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

Do (Hard):

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

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