ok@quintus.UUCP (Richard A. O'Keefe) (02/06/88)
Quicksort Strikes Again!
I recently came across a bug in an otherwise excellent Prolog system.
THE BUG I AM ABOUT TO DESCRIBE DOES NOT EXIST IN
* DEC-10 Prolog,
* C Prolog, or
* Quintus Prolog.
What about other systems? You'll have to check for yourself.
The bug is this: keysort/2 is supposed to be ***STABLE***.
sort/2 and keysort/2 are **indispensable** for efficient Prolog.
The Prolog system I have in mind uses a version of (falsely so-called)
"quick" sort. The code goes something like this:
buggy_key_sort(Raw, Sorted) :-
buggy_key_sort(Raw, Sorted, []).
buggy_key_sort([], L, L).
buggy_key_sort([Key-Val|Pairs], L0, L) :-
key_partition(Pairs, Key, LE, GT),
buggy_key_sort(LE, L0, [Key-Val|L1]),
buggy_key_sort(GT, L1, L).
key_partition([], _, [], []).
key_partition([Pair|Pairs], Key, [Pair|LE], GT) :-
key_less_than_or_equal(Pair, Key),
!,
key_partition(Pairs, Key, LE, GT).
key_partition([Pair|Pairs], Key, LE, [Pair|GT]) :-
key_partition(Pairs, Key, LE, GT).
key_less_than_or_equal(J-_, K) :-
J @=< K.
If you have access to the source code of your Prolog system, and the
implementation of keysort/2 looks something like this, rip it out and
replace it by a stable sort. If you are still hypnotised by the name
"quick" sort, there is a stable version of "quick" sort which is easy
to code in a list-processing language. (Hint: see "fat pivot" in the
index of a good book on internal sorting.) If you aren't hypnotised
by names, replace it by a merge sort; it should be *much* faster, as
well as giving the right answers!
If you haven't got access to the source code of your Prolog system, how
can you tell whether keysort/2 is implemented correctly or not? Here's
how: the reason that we care about the stability of keysort/2 is that
if you sort on several keys, you don't want later sorts to disturb the
order created by the earlier sorts. In the simplest case, we have two
keys. Try this program.
swap_keys_and_values([], []).
swap_keys_and_values([K-V|P], [V-K|S]) :-
swap_keys_and_values(P, S).
test :-
keysort([1-3,1-2,1-1, 2-3,2-2,2-1, 3-3,3-2,3-1], X),
swap_keys_and_values(X, Y),
keysort(Y, [1-1,1-2,1-3, 2-1,2-2,2-3, 3-1,3-2,3-3]).
If 'test' fails, you have the bug.
Once again, just to be clear: QUINTUS PROLOG DOES NOT HAVE THIS BUG.