Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!mcsun!unido!ecrcvax!micha
From: micha@ecrcvax.UUCP (Micha Meier)
Newsgroups: comp.lang.prolog
Subject: Re: Challenge
Message-ID: <803@ecrcvax.UUCP>
Date: 9 Jan 90 16:19:11 GMT
References: <1990Jan4.102648.15154@gorgo.ifi.unizh.ch>
Reply-To: micha@ecrcvax.UUCP (Micha Meier)
Organization: ECRC, Munich 81, West Germany
Lines: 89

>Some weeks ago John G. Cleary (University of Calgary) wrote
>
>  ... However, I tried to reverse quicksort
>  and came across a problem. It goes into an infinite loop after giving the
>  first solution and I was quite unable to concoct a set of delays which
>  prevented this.
>
>  The challenge is to use NU-Prolog (or some other Prolog with delays) to run
>  quicksort backward ( and forward).

Writing a set of delays that make quicksort work backwards
is indeed not straightforward. Here is a Sepia solution:

%------------------------
delay qsort(A, B) if var(A), var(B).
 
qsort([], []).
qsort([X|L], S) :-
        partition(L, X, L1, L2), 
        qsort(L1, R1),
        qsort(L2, R2),
        append(R1, [X|R2], S).
 
delay partition(A, B, C, D) if var(B), A \== [], C \== [], D \== [].
delay partition(A, _, C, D) if var(A), var(C).
delay partition(A, _, C, D) if var(A), var(D).
 
partition([],_,[],[]).
partition([X|L],Y,[X|L1],L2) :- X =< Y,
        partition(L,Y,L1,L2).
partition([X|L],Y,L1,[X|L2]) :- X > Y,
        partition(L,Y,L1,L2).
 
delay append(A, B, C) if var(A), var(C).
delay append(A, _, [_|E]) if var(A), var(E).
 
append([], L, L).
append([X|L1], L2, [X|L3]) :-
        append(L1, L2, L3).
%------------------------

(The semantics of delay clauses is simple - delay the call if the clause
succeeds, but use one-way matching instead of unification in the head.)
The only tricky one is the second delay clause for append/3, which prevents
looping when a goal is a variant of its ancestor. MU-Prolog also runs
with similar declarations.

This code not only runs backwards, but also in the mixed way, e.g.

[sepia]: qsort([2, A, _], [1, X, Y]).

A = 1
X = _d96
Y = 2

Delayed goals:
        _d96 =< 2
        _d96 > 1     More? (;) 
 
A = _d74
X = _d74
Y = 2

Delayed goals:
        _d74 =< 2
        1 =< _d74     More? (;) 

A = 1
X = 2
Y = _d96

Delayed goals:
        _d96 > 2     More? (;) 

A = _d74
X = 2
Y = _d74
 
Delayed goals:
        _d74 > 2     More? (;) 

no (more) solution.

The delayed goals printed for each answer binding are in fact constraints
placed on some variables.

--Micha

{pyramid,mcvax!unido}!ecrcvax!micha