You Can't Always Get What You Want

I'm slowly working my way through Bruce Tate's Seven Languages in Seven Weeks, starting with Prolog. Prolog is a purely declarative language, meaning that you tell it what you want rather than how to get it. This is a completely different paradigm from that of mainstream languages like Java or C++, which grew out of the imperative paradigm. A Java or C++ program consists of a series of steps that must be executed. A Prolog program is defined by a set of facts, a set of rules, and queries upon an abstract world outlined by rules and facts. Working in Prolog has stretched the limits of my understanding of a 'program.'

Though the basics are simple, the trick in programming Prolog is mastering recursion. One or two lines have a great deal of power. For example, you could define a function to reverse a list with the following:

reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).

You can quickly see how powerful this paradigm is for a certain set of problems. For example, Tate's program to solve Sudoku puzzles is only about 20 lines long. It simply describes the relationship between the squares on an abstract board. After you declare a board, Prolog takes care of the rest.

Once I understood Prolog's power, I immediately thought of a puzzle invented by Douglas Hofstadter. It has come to be called the MU puzzle, and it can be found in his book Gödel, Escher, Bach. Basically, there are four rules which involve the manipulation of strings composed of the characters M, I, and U. The question is whether or not these rules can be used to turn the string MI into MU. It took me some time to come up with a solution, and I'll admit I had to check mine with another one I was able to find. (Note: lower case letters are literals; upper case are variables.)

% rule 1: add u to any i
rule1([i], [i,u]).
rule1([H|X], [H|Y]) :- rule1(X, Y).

% rule 2: anything after m can be doubled
rule2([m|X], [m|Y]) :- append(X, X, Y).

% rule 3: replace any iii with u
rule3([i,i,i|X],[u|X]).
rule3([H|X], [H|Y]) :- rule3(X, Y).

% rule 4: remove any uu
rule4([u,u|X],X).
rule4([H|X], [H|Y]) :- rule4(X, Y).

% the setup
map(X,Y,0) :- X=Y.
map(X,Y,1) :- rule1(X,Y).
map(X,Y,2) :- rule2(X,Y).
map(X,Y,3) :- rule3(X,Y).
map(X,Y,4) :- rule4(X,Y).

% the solution
solve([m,i],[m,i],0).
solve(X,Y,N) :- map(Z,Y,N), solve(X,Z,M).

Prolog's strength is in abstracting the implementation of the code from the world it defines, but this can also be its weakness. The problem with the MU puzzle, and with many other problems, is that it will recurse infinitely along the left branch of the tree, since there is no way to create MU from MI using the first rule. For this reason, my program results in a stack overflow. (The code linked above limits the depth of recursion). Even if your recursive stack eventually bottoms out, a complicated program could churn for hours and simply return the result: no.

It's hard for me to think of many business applications for which Prolog would be useful besides scheduling. However, it has helped me understand SQL better. All the books say that SQL is a declarative and not imperative language, but I'm not sure I truly understood what this meant until now. SQL is the most widespread declarative language today, and it shares many of the same advantages and pitfalls as Prolog. It's very easy to query a database, but it is just as easy to do so in a horribly inefficient way. Without understanding database architecture--such as indexes, execution plans, memory management, and data files--you are likely to make major mistakes. For this reason, it is difficult to completely abstract what you want from how the program provides it for you.

SWI-Prolog does have an ODBC interface that I will have to experiment with some day. Until the data I'm working with has relationships that could be explored recursively, however, I'll probably to stick with SQL.

A few links:
-Download GNU Prolog or SWI-Prolog
-Check out some detailed tutorials
-An excerpt from Tate's book