Modeling the Problem

From a previous article we already know that we can encode numbers in Prolog terms using Peano numbers. Using these we can match terms that represent at least or exactly some number. Exactly 3 would be s(s(s(z))) while at least 3 would be s(s(s(X))) with the variable X representing the rest of the term for some \(n\) so that \(3 + x = n\).

Let's start with a small example: we have an aunt that gives us apples. We have bob who is willing to exchange an apple for two berries. And we have a cousin who will bake a cake if we give them two apples and five berries.

Let's formalize our rules in some way:

a: / -> 1A
b: A -> 2B
c: 2A, 5B -> 1C

We model this as some kind of inventory(A, B, C) with some slots for Peano encoded numbers. Meaning that inventory(s(z), z, s(C)) means an inventory of exactly one apple, zero berries, and at least one cake. Lucky us.

Let's define our possible exchanges as Prolog facts with exchange(Kind, Pre, Post) meaning we use the exchange method Kind and we get from inventory state Pre to inventory state Post. If we lose an item, we have it in Pre but don't in Post. If we gain one, it's the other way around. Of course, the rest of our inventory should stay the same.

exchange(a, inventory(A, B, C), inventory(s(A), B, C)).
exchange(b, inventory(s(A),B,C), inventory(A, s(s(B)), C)).
exchange(c, inventory(s(s(A)), s(s(s(s(s(B))))), C), inventory(A, B, s(C))).

As we can see, we can encode basically any numeric condition that uses only "just exactly" and "at least", as well as addition and subtraction and "setting" fields to specific values. If we have to give at least three apples, but all of them, to get a cake, the rule would be exchange(c, inventory(s(s(s(_))), B, C), inventory(z, B, s(C)))..

Programming the Solver

We want to create a predicate trades(Start, Goal, Path) where we give a Start inventory and a Goal inventory and want to get a Path of exchanges. The most obvious approach is the following:

trades(Goal, Goal, []).
trades(Start, Goal, [H|T]) :- exchange(H, Start, Temp), trades(Temp, Goal, T).

So we're done when our Goal is reached. And if not, we have to try some exchange. We try it and we quickly learn that...

?- trades(inventory(z, z, z), inventory(_, _, s(z)), Path).
ERROR: Out of local stack

... it doesn't work.

The problem is, that calling the exchange predicate in the recursive call always tries the first rule first and since that basically always works, we get into an infinite loop. Let's reorder the rules and put the generating rule first.

?- trades(inventory(z, z, z), inventory(_, _, s(z)), Path).
ERROR: Out of local stack

It still doesn't work. Let's look at the trace.

[trace]  ?- trades(inventory(z, z, z), inventory(_, _, s(z)), Path).
 Call: (8) trades(inventory(z, z, z), inventory(_700, _702, s(z)), _712) ? creep
 Call: (9) exchange(_960, inventory(z, z, z), _984) ? creep
 Exit: (9) exchange(a, inventory(z, z, z), inventory(s(z), z, z)) ? creep
 Call: (9) trades(inventory(s(z), z, z), inventory(_700, _702, s(z)), _962) ? creep
 Call: (10) exchange(_978, inventory(s(z), z, z), _1002) ? creep
 Exit: (10) exchange(b, inventory(s(z), z, z), inventory(z, s(s(z)), z)) ? creep
 Call: (10) trades(inventory(z, s(s(z)), z), inventory(_700, _702, s(z)), _980) ? creep
 Call: (11) exchange(_1000, inventory(z, s(s(z)), z), _1024) ? creep
 Exit: (11) exchange(a, inventory(z, s(s(z)), z), inventory(s(z), s(s(z)), z)) ? creep
 Call: (11) trades(inventory(s(z), s(s(z)), z), inventory(_700, _702, s(z)), _1002) ? creep
 Call: (12) exchange(_1018, inventory(s(z), s(s(z)), z), _1042) ? creep
 Exit: (12) exchange(b, inventory(s(z), s(s(z)), z), inventory(z, s(s(s(s(z)))), z)) ? creep
 Call: (12) trades(inventory(z, s(s(s(s(z)))), z), inventory(_700, _702, s(z)), _1020) ? creep
 Call: (13) exchange(_1040, inventory(z, s(s(s(s(z)))), z), _1064) ? creep
 Exit: (13) exchange(a, inventory(z, s(s(s(s(z)))), z), inventory(s(z), s(s(s(s(z)))), z)) ? creep
 Call: (13) trades(inventory(s(z), s(s(s(s(z)))), z), inventory(_700, _702, s(z)), _1042) ? creep
 Call: (14) exchange(_1058, inventory(s(z), s(s(s(s(z)))), z), _1082) ? creep
 Exit: (14) exchange(b, inventory(s(z), s(s(s(s(z)))), z), inventory(z, s(s(s(s(s(s(z)))))), z)) ? creep
 Call: (14) trades(inventory(z, s(s(s(s(s(s(z)))))), z), inventory(_700, _702, s(z)), _1060) ? creep
 Call: (15) exchange(_1080, inventory(z, s(s(s(s(s(s(z)))))), z), _1104) ? creep
 Exit: (15) exchange(a, inventory(z, s(s(s(s(s(s(z)))))), z), inventory(s(z), s(s(s(s(s(s(z)))))), z)) ? creep
 Call: (15) trades(inventory(s(z), s(s(s(s(s(s(z)))))), z), inventory(_700, _702, s(z)), _1082) ? creep
 Call: (16) exchange(_1098, inventory(s(z), s(s(s(s(s(s(z)))))), z), _1122) ? creep

We're still running into an infinite loop since we're just getting apples and trading them for berries.

There's a trick if our solution is a list. If the length(List, Length) predicate is called with both predicates free (length(L, _) for example), we get lists of increasing length as solutions. So if we can bind our solution to lists of increasing length, we won't get infinite loops of apple-berry-exchanges without ever trying short solutions.

So our query now looks like this:

?- length(Path,_), trades(inventory(z, z, z), inventory(_, _, s(z)), Path).
Path = [a, b, a, b, a, b, a, a, c] ;
Path = [a, b, a, b, a, a, b, a, c] ;
Path = [a, b, a, b, a, a, a, b, c] ;
Path = [a, b, a, a, b, b, a, a, c] ;
Path = [a, b, a, a, b, a, b, a, c] ;
Path = [a, b, a, a, b, a, a, b, c] ;
Path = [a, b, a, a, a, b, b, a, c] ;
Path = [a, b, a, a, a, b, a, b, c] ;
Path = [a, b, a, a, a, a, b, b, c] ...

As it turns out, there are a few ways to do it, but nothing shorter than 9 trades. We can even look, whether we have anything left over after we got our cake:

?- length(Path,_), trades(inventory(z, z, z), inventory(A, B, s(z)), Path).
Path = [a, b, a, b, a, b, a, a, c],
A = z,
B = s(z) .

Yeah. As it turns out, we have a berry to spare.

Conclusion

This is how you do it. And of course, you could simulate a shop with that, as one inventory slot could be the number of coins. If the inventory gets too large, you can split it into item types so you don't have to copy every unchanged item from the pre-condition to the post-condition. Then you can copy a term that might represent any number of items.

But beware: this algorithm (with Prolog's evaluation scheme) has not so good complexity. For a solution of length \(n\) and \(m\) rules it has a run time of \(O(m^n)\). We create every possible solution list permutation but break early, if no rules are applicable.

Depending on our instantiation of Start and Goal, this algorithm doesn't terminate (if the system isn't terminating, the algorithm isn't either). Our system doesn't terminate as we can always apply a again and again. We're creating increasingly longer partial solutions which might turn out to be no solution at all. If there is no solution, you won't know. The algorithm just tries longer and longer lists trying to find a solution.

If you have any other conditions on your solution (some exchanges might be limited or necessary) you can put most of them after the trades call. Some conditions, like membership, can be put before.

Let's say we have a terminating system by taking away the a rule. If our Start is fully instantiated, then our algorithm terminates. Let's try another query and find out, with how many apples we need to start to get a cake:

?- trades(inventory(A, z, z), inventory(_, _, s(z)), Path).
ERROR: Out of local stack

Through the unification rules, it is possible that a rule creates terms on the left side of the rule. In this case, the algorithm tries to give us increasing amounts of berries to match that with the starting condition (only rule b is applied in reverse, always leaving us with one cake, which doesn't match the starting condition). There we need the length predicate.

?- length(Path,_), trades(inventory(A, z, z), inventory(_, _, s(z)), Path).
Path = [b, b, b, c],
A = s(s(s(s(s(_2334))))) .

We need at least five apples for a cake. But we knew that.

To recap:

• We saw again how useful it is, to encode the natural numbers in a term structure.
• A solver is easily written but the algorithm isn't fast.
• The rules can be applied in both directions because of Prolog's evaluation scheme. This leaves queries that would intuitively work divergent.
• By using the length predicate we can simulate breadth-first evaluation, while the default evaluation scheme is depth-first.

I think, there's a different approach using linear programming. I might try that in the future.