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: <2947@munnari.oz.au>
Date: 21 Dec 89 01:37:15 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: 50

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).

The following 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).

a
a
>a proposal for a delay semantics which is capable of doing this.
>
>It seems to me that any prolog which is fair (all goal calls will eventually
>be attempted) must work, however it is not clear to me how this can be 
>arranged efficiently.
>
>	John G. Cleary
>	Department of Computer Science
>	University of Calgary
>	2500 University Drive 
>	N.W. Calgary
>	Alberta T2N 1N4
>	Canada
>
>	cleary@cpsc.UCalgary.ca
>	Phone: (403)282-5711 or (403)220-6087