Fun with Prolog: write an algorithm, then run it backwards
Sunday 10 November 2013 21:21
Compared to most other languages, Prolog encourages you to write code in a highly declarative style. One of the results is that you can write an algorithm, and then run the same algorithm "backwards" without any additional code.
For instance, suppose you want to find out whether a list is a palindrome or not. We write a predicate like so:
palindrome(L) :- reverse(L, L).
We can read this as: palindrome(L) is true if reverse(L, L) is true.
In turn, reverse(L1, L2) is true when L1 is the reverse of L2.
We try out the palindrome predicate in the interpreter:
?- palindrome([]).
true.
?- palindrome([1]).
true.
?- palindrome([1, 1]).
true.
?- palindrome([1, 2]).
false.
?- palindrome([1, 2, 1]).
true.So far, not that different from any other programming language. However, if we set some of the elements of the list to be variables, Prolog tries to fill in the blanks -- that is, it tries to find values for those variables so that the predicate is true. For instance:
?- palindrome([1, A]).
A = 1.
In the above, Prolog tells us that the list [1, A] is a palindrome if A has the value 1.
We can do something a bit more fancy if we use a variable for the tail of the list, rather than just one element.
[1 | A] means a list with 1 as the first element,
with any remaining elements represented by A.
?- palindrome([1 | A]).
A = [1]
Prolog tells us that [1 | A] is a palindrome if A has the value [1].
However, if we hit the semicolon in the interpreter,
Prolog gives us another value for A that satisfies the predicate.
?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1]
Now Prolog is telling us that [2, 1] is another value for A that satisfies the predicate.
If we hit semicolon again, we get another result:
?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1] ;
A = [_G313, 2, 1]
This time, Prolog says A = [_G313, 2, 1] satifies the predicate.
The value _G313 means that any value would be valid in that position.
Another hit of the semicolon, and another possibility:
?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1] ;
A = [_G313, 2, 1] ;
A = [_G313, _G313, 2, 1]
We still have _G313, but this time it appears twice.
The first and second element of A can be anything so long as they're the same value.
We can keep hitting semicolon, and Prolog will keep giving us possibilities:
?- palindrome([1, 2 | A]).
A = [1] ;
A = [2, 1] ;
A = [_G313, 2, 1] ;
A = [_G313, _G313, 2, 1] ;
A = [_G313, _G319, _G313, 2, 1] ;
A = [_G313, _G319, _G319, _G313, 2, 1] ;
A = [_G20, _G26, _G32, _G26, _G20, 2, 1] ;
A = [_G20, _G26, _G32, _G32, _G26, _G20, 2, 1]In each of these possibilities, Prolog correctly determines which of the elements in the list must be the same. Now for one last example: what if we don't put any constraints on the list?
?- palindrome(A).
A = [] ;
A = [_G295] ;
A = [_G295, _G295] ;
A = [_G295, _G301, _G295] ;
A = [_G295, _G301, _G301, _G295] ;
A = [_G295, _G301, _G307, _G301, _G295] ;
A = [_G295, _G301, _G307, _G307, _G301, _G295] ;
A = [_G295, _G301, _G307, _G313, _G307, _G301, _G295]Once again, Prolog generates possibilities for palindromes, telling us which elements need to be the same, but otherwise not putting any restrictions on values.
In summary, we wrote some code to tell us whether lists were palindromes or not, but that same code can be used to generate palindromes. As another example, we might want to implement run-length encoding of lists:
?- encode([a, a, a, b, b, a, c, c], X).
X = [[3, a], [2, b], [1, a], [2, c]] .
Once we've written encode,
to work in one direction (turning ordinary lists into run-length-encoded lists),
we can use the same predicate to work in the other direction (turning run-length-encoded lists into ordinary lists):
?- encode(X, [[3, a], [2, b], [1, a], [2, c]]).
X = [a, a, a, b, b, a, c, c] .
For the interested, the implementation can be found as a GitHub gist.
One caveat is that the implementation of encode has to be written carefully so that it works in both directions.
Although this might be harder (and much less efficient) than writing two separate predicates,
one for encoding and one for decoding,
using a single predicate gives a high degree of confidence that
the decode operation is correctly implemented as the inverse of the encode operation.
Writing a version of encode that actually works in both directions is an interesting challenge,
and also the topic of another blog post.
(Thanks to Ninety-Nine Prolog Problems for inspiration for examples.)
Topics: Prolog, Language design