Subject: Re: [SWIPL] sorting database?

From: "Richard A. O'Keefe" <[email-masked]>
Date: Thu, 10 May 2001 12:32:07 +1200 (NZST)

I wrote:
	"Richard A. O'Keefe" wrote:
	> In general, relying on the order in which solutions are returned is
	> unwise.  Occasionally it is extremely unwise.
	
Paul Singleton replied:
	Since Prolog's execution strategy is well-defined and deterministic,
	it is surely legitimate and in some cases clearly useful that the spec
	of a library procedure (etc.) might define the order in which solutions
	are returned, and that code which calls such a procedure might rely on
	this?
	
I said that it is UNWISE, not that it is IMPOSSIBLE.

	I bet there's lotsa code out there which relies on e.g.
	
	    (   member(X, List) ->
	
	committing to the frontmost element of List which unifies with X (rather
	than e.g. the rearmost).
	
But it's not in the SPECIFICATION.  Transcript:

    ?- help(member).
    member(?Elem, ?List)
	Succeeds  when Elem can be unified with one of the members  of List.
	The predicate can be used with any instantiation pattern.

The specification available to SWI Prolog programmers promises nothing about
the order in which the solutions are reported.

In Quintus Prolog,
    | ?- manual(k-2-4-1).
    k-2-4-1
				       Library

		       Section k-2-4-1: member(?Element, ?List)

    member(?Element, ?List)  is true when List is a (possibly partial) list, and
    Element is one of its elements.  It may be used to check whether a particular
    element occurs in a given list, or to enumerate all of the elements of a list
    by backtracking.  member/2 may also be used to generate a list.

is followed by examples which strongly suggest (without _quite_ promising)
a left-to-right search order, and then goes on to say

    If L is a proper list of length n, member(X, L) has at most n solutions,
    whatever X is.  But if L is a partial list, member/2 will backtrack
    indefinitely, trying to place X ever farther to the right.  ...

which still doesn't quite promise any order for proper lists, but does say
something about partial lists.

	Could SWI-Prolog legitimately implement member/2 as
	
	  member(X, [_|Xs]) :-
	      member(X, Xs).
	  member(X, [X|_]).
	
Without breaching its own "contract", yes it certainly could.

	Would this break legacy apps, and whose fault would it be? :-)
	
Some of them, and everybody's.

	Isn't the problem that: while we can formally state some mode, type and
	determinacy properties of code, such that we can statically (& mechanically)
	check that the specified behaviour of a called procedure satisfies the
	assumptions of a call, it is less easy (infeasible?) to specify and check
	solution-order assumptions and properties?
	
Yes.  And if we don't understand something well enough to be able to specify
it and verify it, it is UNWISE (not IMPOSSIBLE) to rely on it in code.

	Perhaps if we disregard the actual orders of solutions, and merely note
	whether a procedure's solution order is defined or not, then we could
	statically check code for some degree of consistency, and e.g. generate
	
	  wARNING: The semantics of ->(p(A,B),_) is dependent on the solution
	  order of p/2, which is undefined.
	
If-then-else is like negation, and should either be suspended until the
test is effectively ground (that is, no variables shared with the rest of
the clause are unbound) or should be diagnosed at compile time by a mode&
determinism system like Mercury's.

This problem is not restricted to Prolog.  If you write parsers &c in
Haskell, with combinators such as

    nxt :: Parser s1 t -> Parser s2 t -> Parser (s1,s2) t
    nxt p1 p2 t0 = [((s1,s2),t2)
		   | (s1,t1) <- p1 t0
		   , (s2,t2) <- p2 t1]

it quickly gets _very_ hard to figure out what order things will be tried in.

I have often found it useful to write grammars as Prolog DCGs and then
interpret them using a different strategy (generally by transforming to
Prolog in a different way).  The same grammar might be processed left-
corner or top-down.  If I rely on the order of solutions, I can't do that.

In the case of someone wanting to have the clauses in a particular order,
the obvious thing to do is to maintain a binary search tree as facts in the
data base and have code that _explicitly_ walks the tree in small->large
order.  You would have to have an interface like

    asserto(Key, Val, Body)	instead of assert(( p(Key, Val) :- Body ))

    retracto(Key)		instead of retractall(p(Key, _))

    callo(Key, Val)		instead of p(Key, Val)

but you would get a lot of benefits.  For one thing, for a large table,
with complex keys, you might even get faster lookup than using the
standard search.  For another, it is just as easy to try the keys in
large->small order, or to enumerate the keys in a range, all of which
are things you can't do just by inserting into the middle of a standard
predicate.

One of the least obvious and most important lessons for Prologgers is
"don't touch the data base directly".  Write wrapper predicates that
enforce whatever additional integrity constraints you need.