如何具体化 Prolog 的回溯状态以执行与 Clojure 中的 "lazy seq" 相同的任务？

Question

这是一个用 Clojure 编写的数字快速排序算法。它基本上是在 "The Joy of Clojure"，第 2 版，第 133 页中找到的快速排序算法。为了（希望）更好的可读性，我稍微修改了它，因为原来的感觉有点太紧凑了：

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

该算法通过调用 qsort 开始，它将传递的数字列表封装到另一个列表中（从而创建一个包含单个列表的列表），然后调用 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有三点值得注意：

它延迟了实际处理。它不是返回输入列表的完整排序的结果，而是 returns a "lazy-seq"，它是一个 (object?thing?thunk?) 发出排序的下一个数字查询时的顺序，即根据需要排序。计算的状态由 (cons oldpivot (qsort-inner rightpartz))
有一个 loop + recur 尾递归部分，每当算法沿着排序树向下移动时都会使用它 "towards the left"（算法详情见下文。）
有一个完全递归调用(qsort-inner rightpartz)，当获得下一个最小数并且排序树可以"re-arranged"时使用"re-arranged"（算法细节见下文）

借助 lazy-seq 东西，我们可以让算法一个接一个地发出数据：

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

我在考虑如何在 Prolog 中执行这种惰性快速排序。事实上，惰性，至少在这种情况下，在 Prolog 中是通过回溯免费提供的！我们可以要求第一个结果，计算停止，然后通过回溯获得下一个结果。

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

排序列表 "lazily":

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

必须把它们全部拿走：

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

不幸的是，跟踪计算状态的数据结构并不明显：它在堆栈上，不能统一为一个变量。因此我只能在Prolog的顶层使用这种"laziness"。

如何捕获计算状态并在以后调用它？

注意快速排序的工作原理

给定一个数字列表，算法选择列表的第一个元素作为主元值（图像中的浅绿色）。
然后构建一棵树，这些数字严格小于列表中的枢轴值"on the left"，枢轴本身（深绿色）和那些大于或等于列表中的枢轴值的数字"on the right"。
然后递归地向下移动这棵树"towards the left"。
这一直持续到小于枢轴值的数字列表为空。
此时，枢轴值（此处为28）是最小的数字，可以输出。
这使得要对一个元素进行排序的列表变小了。现在可以通过简单的重新排列操作将树减少一级：现在无左分支和无主元的 "deepest tree-node but one" 的右分支成为树节点 "deepest tree-node but two" 的左分支。
搜索最小元素现在可以再次进行"towards the left"。

不需要明确保留树结构，因为它不包含任何信息。相反，交替 "leaf lists" 和 "pivot numbers" 的序列保存在列表中。这就是为什么我们最初 "list of a lits of numbers".

Answer 1

这不是标准化的，但现在许多 Prolog 提供了维护和操作多个独立的可回溯状态的工具，通常称为引擎。

例如，使用对应的primitives in ECLiPSe，你可以写

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

并按如下方式使用（使用您定义的 qsort/2）

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

此处，变量 Eng 绑定到不透明的 engine-handle。这个引擎执行一个不确定的目标，每次恢复并指示回溯时，都会为调用者产生一个新的解决方案。

Answer 2

Prolog 是一种非常具体化的语言。只需将您的代码转换为数据即可：

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

就这些了。

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([[]]).

为了更容易连接，我们可以使用 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).

然后，

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 显然需要调整以在 next/3 失败时优雅地关闭输出列表。它最初是在考虑无限列表的情况下编写的。这是留给敏锐探索者的练习。

如何具体化 Prolog 的回溯状态以执行与 Clojure 中的 "lazy seq" 相同的任务？

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

clojure

prolog

quicksort

lazy-sequences

reify