Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!munnari.oz.au!lee
From: lee@munnari.oz.au (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: delayed computation challenge
Keywords: NU-Prolog delays quicksort
Message-ID: <2948@munnari.oz.au>
Date: 21 Dec 89 02:23:54 GMT
References: <2235@cs-spool.calgary.UUCP>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Organization: Comp Sci, University of Melbourne
Lines: 92

In article <2235@cs-spool.calgary.UUCP> cleary@cpsc.ucalgary.ca (John Cleary) writes:
>
>The challenge is to use NU-Prolog (or some other Prolog with delays) to run
>quicksort backward ( and forward).

Here is the output of 'nac' (which automatically adds control
information) applied to the non- difference list version of quicksort:

% the following code has been nac'ed
% 
% procedure qsort/2 is locally deterministic.
% clause altered: qsort(A.B, C.D) :-  . . .

?- pure qsort/2.
?- qsort(A, B) when A or B.
qsort([], []).
qsort([A|B], [C|D]) :-
        append(E, [A|F], [C|D]),
        part(A, B, G, H),
        qsort(G, E),
        qsort(H, F).

?- pure part/4.
?- part(A, B, C, D) when (B or C) and (B or D).
part(A, [], [], []).
part(A, [B|C], [B|D], E) :-
        A >= B,
        part(A, C, D, E).
part(A, [B|C], D, [B|E]) :-
        A < B,
        part(A, C, D, E).

It could be made a bit better (eg, the when declaration for part/4 could
be simplified more, and I think the sub-goals of the qsort clause could
be reordered without losing anything).  Some sample goals:

5?- qsort([1, 3, 2, 5, 0], X).
X = [0, 1, 2, 3, 5] ;
fail.
6?- qsort(X, [1, 3, 2]).
fail.
7?- qsort(X, [1, 2, 3]).
X = [1, 2, 3] ;
X = [1, 3, 2] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
fail.

Well, the main thing is that it works!

I suspect the reason why John Cleary had trouble getting things to work
was he was using the difference list version.  I have not studied this
in detail, but if its like the difference between naive reverse and
normal "difference list" reverse, the reason is as follows.  The
difference list version is not logically equivalent to the append
version.  When running the program backwards there are instances of the
goal which are true in some models (non-Herbrand models) but not all
models.  The SLD tree must therefore be infinite, whatever computation
rule is used.  The best you can do is find all solutions then get into
an infinite loop.  For programming, this is not much better than getting
into a loop immediately, though it is an advantage when you are
initially trying to get the logic right.

When nac is applied to the difference list version (part of) the output
is as follows:

?- pure qsort1/3.
?- qsort1(A, B, C) when A.
qsort1([], A, A).
qsort1([A|B], C, D) :-
        part(A, B, E, F),
        qsort1(F, C, G),
        qsort1(E, [A|G], D).

Nac is smart enough not to allow it to run backwards.

9?- qsort([1, 3, 2, 5, 0], X).
X = [0, 1, 2, 3, 5] 
10?- qsort(X, [1, 3, 2]).
Warning: Goal floundered.
X = X 

It would be nice to run the goal backwards inside the debugging
environment, which has a facility for testing goals using a fair search
strategy.  Unfortunately it doesn't seem to work for this exmple -
possibly because you need a smarter computation rule as well as search
rule (I'll have to look into this and perhaps modify the debugging
environment :-).

	lee