Thoughts about Prolog

The most advertised feature of Prolog is its ability to run computations both forwards and backwards. This is a simplification. More accurately, Prolog doesn’t have functions which return values. It has predicates. In order to model a traditional function in Prolog, the programmer can treat one of the predicate’s arguments as its return value. E.g. the following predicate models the function f(x) = 2x:

:- use_module(library(clpfd)).

f(X, Y) :- Y #= 2 * X.

Now we can ask Prolog to run this “function” forwards by asking for valid substitutions of Y:

?- f(1, Y).
Y = 2.

But we may also run it backwards by asking for valid substitutions of X instead:

?- f(X, 2).
X = 1.

We can also ask Prolog for the general solution:

?- f(X, Y).
2*X#=Y.

With more arguments, we’ll have many more directions we can run the computation in and which one is forwards is just a matter of convention.

Unfortunately, this works only for the most trivial programs. It breaks down on things as simple as quicksort. With the following definition:

:- use_module(library(clpfd)).

quicksort_forwards([X|Xs], Ys) :-
    partition(Xs, X, Littles, Bigs),
    quicksort_forwards(Littles, Ls),
    quicksort_forwards(Bigs, Bs),
    append(Ls, [X|Bs], Ys).
quicksort_forwards([], []).

partition([X|Xs], Y, [X|Ls], Bs) :- X #=< Y, !, partition(Xs, Y, Ls, Bs).
partition([X|Xs], Y, Ls, [X|Bs]) :- X #> Y, !, partition(Xs, Y, Ls, Bs).
partition([], Y, [], []).

We can run this quicksort implementation forwards with no issues:

?- quicksort_forwards([2, 1], L).
L = [1, 2] .

But running it backwards fails due to the program hitting the stack limit:

?- quicksort_forwards(L, [1, 2]).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 2Kb, global: 1.0Gb, trail: 66.4Mb
ERROR:   Stack depth: 1,053,286, last-call: 100%, Choice points: 7
ERROR:   In:
ERROR:     [1,053,286] clpfd:left_right_linsum_const(_104836684, _104836686, _104836688, _104836690, _104836692)
ERROR:     [1,053,285] clpfd:clpfd_geq_(_104836710, _104836712)
ERROR:     [1,053,284] clpfd:clpfd_geq(_104836730, _104836732)
ERROR:     [1,053,283] user:partition([length:1|_104836762], _104836752, [length:1|_104836768], _104836756)
ERROR:     [12] user:quicksort_forwards([length:1,053,272|_104836794], [length:2])
ERROR: 
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.
^  Exception: (1,053,283) partition(_104836436, _174{clpfd = ...}, _104836442, _114) ? abort
% Execution Aborted

Why is that? Prolog traverses the search tree in depth-first order, starting with the first clause. In this case, the first clause of quicksort_forwards is partition(Xs, X, Littles, Bigs). At this point the only variables bound are X and Xs. Littles and Bigs are unbound. Going deeper into partition, Prolog is going to begin infinite recursion, generating all possible lists that it could substitute for Littles and Bigs in quicksort_forwards. It’s never going to reach the recursive clause quicksort_forwards in quicksort_forwards. The stack is going to be filled with calls to partition.

We can fix this by reordering the clauses so that the length of the generated list is established first, preventing infinite recursion:

quicksort_backwards([X|Xs], Ys) :-
    append(Ls, [X|Bs], Ys),
    quicksort_backwards(Littles, Ls),
    quicksort_backwards(Bigs, Bs),
    partition(Xs, X, Littles, Bigs).
quicksort_backwards([], []).

The append call, which is placed first, is going to recursively establish possible contents of Ls and Bs (along with their lengths). After that we recurse into quicksort_backwards, which is going to establish similar splits for progressively smaller lists comprising the input. Finally the call to partition is going to establish how the smaller lists are synthesised into bigger lists.

Lo and behold, it works:

?- quicksort_backwards(L, [1, 2]).
L = [1, 2] ;
L = [2, 1] ;
false.

But only backwards. We can’t run it forwards anymore:

?- quicksort_backwards([2, 1], L).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.8Gb, global: 0.2Gb, trail: 53.9Mb
ERROR:   Stack depth: 2,353,978, last-call: 0%, Choice points: 4,707,935
ERROR:   Possible non-terminating recursion:
ERROR:     [2,353,978] user:quicksort_backwards(_42391182, [])
ERROR:     [2,353,977] user:quicksort_backwards([length:1|_42391210], [length:1|_42391216])
   Exception: (2,352,548) quicksort_backwards(_42365378, _42365374) ? abort
% Execution Aborted

That experience forms my general impression of Prolog. The promise of being able to run computations in multiple directions is false. The programmer needs to think about a specific direction anyway and even after reordering the clauses to get quicksort_backwards, what we get is not Heap’s algorithm, but something much less efficient. At that point one might as well pick a more standard algorithmic language, where the direction is explicit and the language is more efficient in general.