cleary@cpsc.ucalgary.ca (John Cleary) (12/13/89)
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
gupta@CompSci.Bristol.AC.UK (G. Gupta) (12/19/89)
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
lee@munnari.oz.au (Lee Naish) (12/21/89)
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
lee@munnari.oz.au (Lee Naish) (12/21/89)
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
lee@munnari.oz.au (Lee Naish) (12/21/89)
In article <2948@munnari.oz.au> lee@munmurra.UUCP (Lee Naish) writes: >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 example It seems I was using an out of date version of the debugging environment. It actually does work: 8?- test qsort(X, [1, 2, 3]). Do static analysis? n Test known valid instances? Test known satisfiable atoms? Test known unsatisfiable atoms? Generate solutions to goal? Solution found: qsort([3, 2, 1], [1, 2, 3]). qsort([3, 2, 1], [1, 2, 3]) Valid? Solution found: qsort([3, 1, 2], [1, 2, 3]). qsort([3, 1, 2], [1, 2, 3]) Valid? Solution found: qsort([2, 1, 3], [1, 2, 3]). qsort([2, 1, 3], [1, 2, 3]) Valid? Solution found: qsort([2, 3, 1], [1, 2, 3]). qsort([2, 3, 1], [1, 2, 3]) Valid? Solution found: qsort([1, 3, 2], [1, 2, 3]). qsort([1, 3, 2], [1, 2, 3]) Valid? Solution found: qsort([1, 2, 3], [1, 2, 3]). qsort([1, 2, 3], [1, 2, 3]) Valid? It gets into the (unavoidable) infinite loop after this. lee