Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!mit-eddie!uw-beaver!ubc-cs!alberta!calgary!cpsc!cleary
From: cleary@cpsc.ucalgary.ca (John Cleary)
Newsgroups: comp.lang.prolog
Subject: delayed computation challenge
Keywords: NU-Prolog delays quicksort
Message-ID: <2235@cs-spool.calgary.UUCP>
Date: 13 Dec 89 04:50:14 GMT
Sender: news@calgary.UUCP
Lines: 31


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