Logic programming is overrated

Logic programming is experiencing something of a resurgence in the Clojure community, sparked by core.logic, a port of miniKanren, an embedding of Prolog in Scheme. When Clojure programmers first hear about core.logic, they go rushing off for a problem to solve like a hammer in search of a nail.

This means that every few months, we see a new blog post demonstrating how to use core.logic to solve a logic puzzle. The latest one to catch my attention was this blog post by Kris Jenkins detailing a logic puzzle tackled by the London Clojure group. The blog post begins by describing the puzzle and says:

It cries out, "Logic Programming", doesn't it?

NO, NO, NO!!!! It doesn't cry out logic programming, for reasons I'll get into in a moment. The blog post explains that the London group was unable to solve the puzzle in a single session, and goes on to explain the complications they ran into -- for example, negation rules and rules involving inequalities prove harder than expected to encode. They also needed to introduce macros to make it more readable. You'd think that after detailing all these problems, the post would end with the observation that logic programming turned out to be a convoluted way to express the logic puzzle, and failed to live up to expectations; yet amazingly, it does not.

The reason why logic programming is so rarely useful is that, essentially, core.logic is just a complex DSL for doing exhaustive search. Clojure already has an elegant, compact DSL for doing exhaustive search -- it is called the for comprehension.

So let's take a look at just how much more cleanly and easily this logic puzzle can be solved just using Clojure's built-in for comprehension. Take a look at this code. To run it, you'll need to:
(use 'clojure.math.combinatorics)
for the permutations function.

As you read the code, I want you to look at how clear and concise the translation is from the English constraints to Clojure. You've got a few lines setting up the variables, and then every single line of Clojure code is a straightforward expression of the original problem statement. Notice how trivial it is to handle things like negation, ordering, and inequalities.

	(defn solve-logic-puzzle []
	(let [people [:amaya :bailey :jamari :jason :landon]]
	(first
	(for [[fortune time cosmopolitan us-weekly vogue] (permutations people) ; magazines
	[asiago blue-cheese mascarpone mozzarella muenster] (permutations people) ; cheeses
	; We bind the reservations in two steps, so we have a name for the overall order
	reservations (permutations people)
	:let [[five six seven seven-thirty eight-thirty] reservations]
	; THE CONSTRAINTS IN PLAIN ENGLISH
	; Of Landon and Jason, one has the 7:30pm reservation and the other loves mozzarella.
	; The blue cheese enthusiast subscribed to Fortune.
	; The muenster enthusiast didn't subscribe to Vogue.
	; The 5 people were the Fortune subscriber, Landon, the person with a reservation at 5:00pm, the mascarpone enthusiast, and the Vogue subscriber.
	; The person with a reservation at 5:00pm didn't subscribe to Time.
	; The Cosmopolitan subscriber has an earlier reservation than the mascarpone enthusiast.
	; Bailey has a later reservation than the blue cheese enthusiast.
	; Either the person with a reservation at 7:00pm or the person with a reservation at 7:30pm subscribed to Fortune.
	; Landon has a later reservation than the Time subscriber.
	; The Fortune subscriber is not Jamari.
	; The person with a reservation at 5:00pm loves mozzarella.
	; THE CONSTRAINTS IN CLOJURE (in the same order)
	:when (= (set [seven-thirty mozzarella]) (set [:landon :jason]))
	:when (= blue-cheese fortune)
	:when (not= muenster vogue)
	:when (= (count (set [fortune :landon five mascarpone vogue])) 5)
	:when (not= five time)
	:when (< (.indexOf reservations cosmopolitan) (.indexOf reservations mascarpone))
	:when (> (.indexOf reservations :bailey) (.indexOf reservations blue-cheese))
	:when (#{seven seven-thirty} fortune)
	:when (> (.indexOf reservations :landon) (.indexOf reservations time))
	:when (not= fortune :jamari)
	:when (= five mozzarella)]
	; RETURN THE ANSWER
	(array-map
	:fortune fortune :time time :cosmopolitan cosmopolitan :us-weekly us-weekly :vogue vogue
	:asiago asiago :blue-cheese blue-cheese :mascarpone mascarpone :mozzarella mozzarella :muenster muenster
	:five five :six six :seven seven :seven-thirty seven-thirty :eight-thirty eight-thirty)))))

view raw Logic1.clj hosted with ❤ by GitHub

Now go back and read the core.logic version. Admit it, it's ugly in comparison.

I think a lot of people mistakenly believe that core.logic is working some magic behind the scenes to solve puzzles in some amazingly efficient manner. On the contrary, it's just brute force search, using complex machinery which just slows it down versus a for comprehension. Not only is the for version elegant, but it's also faster.

But the disadvantages of core.logic for solving logic puzzles don't end there. core.logic is very sensitive to the way that goals are ordered, in a bad way. Certain orderings, for example, will cause the program to go into an infinite loop, and the DSL is complex enough that this is not always readily apparent.

The for comprehension version is also sensitive to ordering, but in a good way. In the for version, the code is evident and there is no mystery about how it will execute, so it is a trivial matter to rearrange the rules to improve the program's running time. The rule of thumb is simple: move each constraint up so that it occurs just after the definition of any variables it depends on. Here is a version where the rules have been shifted around in this straightforward way, making the search run ten times faster.

	(defn logic-puzzle []
	(let [people [:amaya :bailey :jamari :jason :landon]]
	(for [[fortune time cosmopolitan us-weekly vogue] (permutations people) ; magazines
	:when (not= fortune :jamari)
	[asiago blue-cheese mascarpone mozzarella muenster] (permutations people) ; cheeses
	:when (= blue-cheese fortune)
	:when (not= muenster vogue)
	reservations (permutations people)
	:let [[five six seven seven-thirty eight-thirty] reservations]
	:when (not= five time)
	:when (= five mozzarella)
	:when (#{seven seven-thirty} fortune)
	:when (= (set [seven-thirty mozzarella]) (set [:landon :jason]))
	:when (= (count (set [fortune :landon five mascarpone vogue])) 5)
	:when (< (.indexOf reservations cosmopolitan) (.indexOf reservations mascarpone))
	:when (> (.indexOf reservations :bailey) (.indexOf reservations blue-cheese))
	:when (> (.indexOf reservations :landon) (.indexOf reservations time))]
	(array-map
	:fortune fortune :time time :cosmopolitan cosmopolitan :us-weekly us-weekly :vogue vogue
	:asiago asiago :blue-cheese blue-cheese :mascarpone mascarpone :mozzarella mozzarella :muenster muenster
	:five five :six six :seven seven :seven-thirty seven-thirty :eight-thirty eight-thirty))))

view raw Logic2.clj hosted with ❤ by GitHub

So all this is to say that I think logic programming is overrated, at least for solving logic puzzles. I write logic puzzles for a living, and I haven't yet found a practical use for core.logic. So far, every blog post I've seen that demonstrated core.logic on a logic puzzle could have been solved just as easily or better with a for comprehension.

Does that mean core.logic is useless? Of course not. Logic programming is good for running programs backwards (I've seen some wonderful toy examples of this, like the program that generates Quines, but have yet to find a real-world example where this is useful), unification is important for writing type checkers, and the new constraint programming piece of core.logic based on cKanren has wonderful potential to be directly useful to me for the kinds of things I program (although probably not until it comes with tools for guiding and visualizing the search strategy).

So the purpose of this article is not to demean core.logic, but rather, to elevate the level of discourse surrounding it. Can we move past solving logic puzzles which would be better solved with a for comprehension? Please, show me things I can do with core.logic that would be hard to express any other way. I look forward to it!