Explorations in logic programming
Out of Storybook, a side project I’ve been doing for a friend, I had the opportunity to model the problem domain as a constraint satisfaction problem (CSP). It goes:
A set of students are assigned a book a week. Write plan generator to create a set of studentbook assignments for that week, given the following constraints:
 All students must receive a book.
 Each book may only be assigned to one student at a time.
 A student may not be assigned a book s/he has received before.
Being that this was a Rails app, I put Amb, a Rubybased CSP solver, to use. Amb is derived off Jim Weirich’s original source code, implementing a simple backtracking algorithm. (More interesting reading on the original idea behind the amb
operator, proposed in a paper by LISP founder John McCarthy in 1963.)
Not having written any CSP logic since my university days, I tried to come up with a naive solution. It goes something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

Well this would work for 2 students and 2 bags, 3 and 3, 4 and 4, but would blow up and overflow the stack when we got to 5 students and 5 bags. Why? I was forcing Ruby to generate the full solution space before starting the CSP search problem:
1 2 3 4 5 

Then I was taking that cross product and bruteforce generating all possible permutations internal to that:
1 2 3 4 5 6 7 

The most obvious thing that stood out to me like a sore thumb was how I wasn’t simply trusting the constraintbased nature of the problem and expressing the problem in terms of the constraints, instead of attempting to imperatively generate the solution. Usage of Enumerable#permutation
resulted in an O(n!) algorithm, which is unacceptable. Back to the drawing board:
1 2 3 4 5 6 7 8 9 10 11 12 

Note the main difference here is how I’ve retooled the solver to assign variables one at a time (in L5) and check constraints after each assignment. This simplifies the domain of the problem as a graph search and helps us more easily reason about this program.
Further explorations
Follow my cspsolvers project, where I attempt to rewrite this in Prolog and Clojure in an attempt to see how language affects how we reason about problems like these. It’s gonna be fun.
Further reading
 Artificial Intelligence: A Modern Approach (3rd Edition)
 http://aima.cs.berkeley.edu/2nded/newchap05.pdf
 Ruby Forum – Using Amb
 SchemeWiki: amb
Comments