How to reify Prolog's backtracking state to perform the same task as "lazy seq" from Clojure?

Question

Here is a quicksort algorithm for numbers written in Clojure. It is basically the quicksort algorithm found in "The Joy of Clojure", 2nd edition, page 133. I modified it slightly for (hopefully) better readability, because the original felt a bit too compact:

(defn qsort-inner [work]
   (lazy-seq        
      (loop [loopwork work]
         (let [[ part & partz ] loopwork ]
            (if-let [[pivot & valuez] (seq part)]
                  (let [ smaller? #(< % pivot)
                         smz      (filter smaller? valuez)
                         lgz      (remove smaller? valuez)
                         nxxt     (list* smz pivot lgz partz) ]
                        (recur nxxt))
                  (if-let [[oldpivot & rightpartz] partz]
                          (cons oldpivot (qsort-inner rightpartz))
                          []))))))

(defn qsort [ xs ]
   (qsort-inner (list xs)))

The algorithm is started by a call to qsort, which envelops a passed list of numbers into another list (thus creating a list containing a single list), then calls qsort-inner.

(qsort [10 4 5 88 7 1])     ;; (qsort-inner [[10 4 5 88 7 1]])
;; (1 4 5 7 10 88)

qsort-inner has three noteworthy points:

• It delays actual processing. Instead of returning the result of a complete sorting of the input list, it returns a "lazy-seq", which is an (object? thing? thunk?) that emits the next number of the sorted sequence when queried, i.e. sorts on an as-needed basis. The state of the computation is given by the suspended tail of (cons oldpivot (qsort-inner rightpartz))
• There is a loop + recur tail-recursive part which is used whenever the algorithm wanders down the sorting tree "towards the left" (see below for algorithm details.)
• There is a fully recursive call (qsort-inner rightpartz) which is used when the next least number has been obtained and the sorting tree can be "re-arranged" (see below for algorithm details.)

With the help of the lazy-seq thing, we can make the algorithm emit data one-by-one:

;; the full result is generated on printout
(qsort [10 4 5 88 7 1])
(1 4 5 7 10 88)

;; store the lazy-seq and query it
(def l (qsort [10 4 5 88 7 1]))
(first l)
;; 1
(second l)
;; 4

I was thinking about how to perform this lazy quicksort in Prolog. In fact, laziness, at least in this instance, is given for free in Prolog by backtracking! We can ask for a first result, computation halts and the next result is then obtained by backtracking.

qsort_inner(X, [[],X|_]).
qsort_inner(X, [[],_|WorkRest]) :- qsort_inner(X, WorkRest).
qsort_inner(X, [[Piv|Ns]|WorkRest]) :- 
    pick_smaller(Piv,Ns,SMs),
    pick_notsmaller(Piv,Ns,NSMs),
    qsort_inner(X,[SMs,Piv,NSMs|WorkRest]).

pick_smaller(Pivot,Ins,Outs) :- include(@>(Pivot),Ins,Outs).
pick_notsmaller(Pivot,Ins,Outs) :- exclude(@>(Pivot),Ins,Outs).

qsort(X,Lin) :- qsort_inner(X,[Lin]).

Sort a list "lazily":

qsort(X,[3,2,1]).
X = 1;
X = 2;
X = 3;
false

Gotta get them all:

qsort_fully(Lin,Lout) :- bagof(X, qsort(X, Lin), Lout).

Unfortunately, the data structure that keeps track of the computational state is not apparent: it is on the stack, it cannot be unified to a variable. Thus is can only use this kind of "laziness" when I am on Prolog's top level.

How do I capture the state of the computation and invoke it later?

Note on how the quick sort works

• Given a list of numbers, the algorithm selects the first element of the list as pivot value (light green in the image).
• It then builds a tree with those numbers strictly smaller than the pivot value in a list "on the left", the pivot itself (dark green) and those numbers larger or equal to the pivot value as a list "on the right".
• It then recursively moves down this tree "towards the left".
• This continues until the list of numbers smaller than the pivot value is empty.
• At that point, the pivot value (here, 28) is the least number overall and can be output.
• This makes the list to sort one element smaller. The tree can now be reduced by one level with a trivial rearrangement operation: the right branch of the now left-branch-less and pivot-less "deepest tree-node but one" becomes the left branch of the tree node "deepest tree-node but two".
• Searching for the least element can now proceed again "towards the left".

The tree structure does not need to be explicitly kept as it holds no information. Instead, the sequence of alternating "leaf lists" and "pivot numbers" is kept in a list. Which is why we the intial "list of a lits of numbers".

Answer 1

Prolog is a very reifiable language. Just turn your code into data:

qsort_gen(Lin, G) :- 
    % G is the initial generator state for Lin's quicksorting
    G = qsort_inner([Lin]).

    %    This_State                   Next_Elt      Next_State
next( qsort_inner([[], X    | WorkRest]), X, qsort_inner(WorkRest) ).
next( qsort_inner([[Piv|Ns] | WorkRest]), X, G ) :-
    pick_smaller(  Piv, Ns, SMs),
    pick_notsmaller(Piv, Ns, NSMs),
    next( qsort_inner([SMs, Piv, NSMs | WorkRest]), X, G).

pick_smaller(  Pivot, Ins, Outs) :- include( @>(Pivot), Ins, Outs).
pick_notsmaller(Pivot, Ins, Outs) :- exclude( @>(Pivot), Ins, Outs).

That's all.

15 ?- qsort_gen([3,2,5,1,9,4,8], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
X = 1,
G2 = qsort_inner([[], 2, [], 3, [5, 9, 4|...]]),
X2 = 2,
G3 = qsort_inner([[], 3, [5, 9, 4, 8]]),
X3 = 3,
G4 = qsort_inner([[5, 9, 4, 8]]).

16 ?- qsort_gen([1,9,4,8], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[1, 9, 4, 8]]),
X = 1,
G2 = qsort_inner([[9, 4, 8]]),
X2 = 4,
G3 = qsort_inner([[8], 9, []]),
X3 = 8,
G4 = qsort_inner([[], 9, []]).

17 ?- qsort_gen([1,9,4], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[1, 9, 4]]),
X = 1,
G2 = qsort_inner([[9, 4]]),
X2 = 4,
G3 = qsort_inner([[], 9, []]),
X3 = 9,
G4 = qsort_inner([[]]).

For easier interfacing, we can use take/4:

take( 0, Next, Z-Z, Next):- !.
take( N, Next, [A|B]-Z, NextZ):- N>0, !, next( Next, A, Next1),
  N1 is N-1,
  take( N1, Next1, B-Z, NextZ).

Then,

19 ?- qsort_gen([3,2,5,1,9,4,8], G), take(6, G, L-[], _).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
L = [1, 2, 3, 4, 5, 8].

20 ?- qsort_gen([3,2,5,1,9,4,8], G), take(7, G, L-[], _).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
L = [1, 2, 3, 4, 5, 8, 9].

21 ?- qsort_gen([3,2,5,1,9,4,8], G), take(10, G, L-[], _).
false.

take/4 obviously needs tweaking to close the output list gracefully when next/3 fails. It was written with the infinite lists in mind, originally. This is left as an exercise for a keen explorer.

Answer 2

This isn't standardized, but a number of Prologs nowadays provide facilities to maintain and manipulate multiple independent backtrackable states, often known as engines.

For example, using the corresponding primitives in ECLiPSe, you might write

init(Vars, Goal, Engine) :-
    engine_create(Engine, []),
    engine_resume(Engine, (true;Goal,yield(Vars,Cont),Cont), true).

more(Engine, Vars) :-
    engine_resume(Engine, fail, yielded(Vars)).

and use that as follows (with qsort/2 as defined by you)

?- init(X, qsort(X,[3,2,1]), Eng),
   more(Eng, X1),
   more(Eng, X2),
   more(Eng, X3).

X = X
Eng = $&(engine,"9wwqv3")
X1 = 1
X2 = 2
X3 = 3
Yes (0.00s cpu)

Here, the variable Eng is bound to an opaque engine-handle. This engine executes a nondeterministic goal that yields a new solution to the caller every time it is resumed and instructed to backtrack.