Path: utzoo!attcan!uunet!mcsun!ukc!reading!cf-cm!csisles!gupta
From: gupta@CompSci.Bristol.AC.UK (G. Gupta)
Newsgroups: comp.lang.prolog
Subject: Re: delayed computation challenge
Keywords: NU-Prolog delays quicksort
Message-ID: <1309@csisles.Bristol.AC.UK>
Date: 18 Dec 89 18:45:47 GMT
References: <2235@cs-spool.calgary.UUCP>
Organization: Dept of Computer Science, University of Bristol, UK.
Lines: 77

In article <2235@cs-spool.calgary.UUCP>, cleary@cpsc.ucalgary.ca (John Cleary) writes:
> 
> Recent postings here about NU-Prolog and the use of delayed computation
> have reminded me of a problem which I have never quite been able to solve.
> The background is that in NU-Prolog it is possible to permute a list of objects
> with many different programs.  For example a straightforward permute can be 
> driven backward by instantiating its 'output' and seeing what appears on its
> 'input'.  Similalrly any sorting program can be driven backward to generate
> permutations.  Well almost any sort program.  It works fine for simple ones
> like insertion sort or merge sort.  However, I tried to reverse quicksort
> and came accross 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).  If this isnt possible I would like
> 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


It is possible to generate permutations of a sorted list by
using quicksort in the reverse directions. I can very simply
do it on my EqL interpreter (which has semantics very simlar to 
that of Prolog) which delays equations (equivalent to Prolog
subgoals) involving operators with uninstantiated arguments.

Given the following traditional definition of quicksort using 
difference lists:

sort(l)   => answer where [answer | []] = qsort(l).

qsort([]) => [x|x].

qsort([p | l]) =>  [sorta | tail]
                        where
                                [a | b] = part(l,p);
                                [sorta | [p| sortb]] = qsort(a);
                                [sortb | tail] = qsort(b).

part([],p) => [[] | []].

part([h|t],p) => if p>h then [[h|a] | b] else [a | [h|b]]
                        where 
			    [a | b] = part(t,p).

and the query:

?- sort(l) = [1,2,3].

I can get all six different permutations by typing semicolons.
However, on typing a semicolon after the last permutation has
been reported, the computation goes into an infinite loop. The 
reason for which, perhaps, is that the interpreter tries to solve 
goals with all arguments uninstantiated (e.g. qsort([_ | _])).

The above would work even if we use append to concatenate the
two partitioned lists (instead of using difference lists). 

Thus, it is possible to get all permutations  of a
list by using quicksort in the reverse direction by use of
a simple delay mechanism (i.e. delay evaluation of a strict operator
until all its operands are instantiated). 

Note that the above should also work for CLP(R) system since
it also has a delaying mechanism built into the run-time system.

Gopal Gupta,
Parallel Logic Programming Research Group,
Department of Computer Science,
University of Bristol,
Bristol, BS8 1TR.
email : gupta%compsci.bristol.ac.uk@NSS.Cs.Ucl.AC.UK