delayed computation challenge 
Author Message
 delayed computation challenge

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


        Phone: (403)282-5711 or (403)220-6087



Wed, 19 May 1993 04:50:00 GMT  
 delayed computation challenge

Quote:

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



Wed, 19 May 1993 18:45:00 GMT  
 delayed computation challenge

Quote:

>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

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


>    Phone: (403)282-5711 or (403)220-6087



Wed, 19 May 1993 01:37:00 GMT  
 delayed computation challenge

Quote:

>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



Wed, 19 May 1993 02:23:00 GMT  
 delayed computation challenge

Quote:

>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



Wed, 19 May 1993 07:31:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Delays, verilog ignores my delays?

2. Unit Delay vs. Zero Delay

3. Avoiding inertial delay in delay lines

4. Transport Delay and Inertial Delay

5. delay until vs. delay relative

6. QSCGZ delay problem (was: strange memory-access-delay)

7. Transport Delay Vs Inertial Delay

8. CLP(R): delay or not delay?

9. Julia/Mandelbrot Computations in J; was series

10. Helsinki Workshop on Symbolic and Numeric Computation

11. Array Computation + Graphics Package Sought

12. 3270 screen buffer address computation

 

 
Powered by phpBB® Forum Software