在 Prolog 中制表，什么时候存储值？

Question

所以假设我有这段代码使用 table 来获取 'note' 以前的解决方案或答案。

first_rule:-
   doSomething,
   recursive_call(A,B,C). %where A and B are lists of character codes

:- table recursive_call(_,_,min).

recursive_call([],B,C):- doSomething.
recursive_call(A,[],C):- doSomething.

我的问题是，每次调用 recursive_call 时，值是 'stored' 还是 'cached' 进入 table？

注意（只是为了向这段代码添加更多上下文以防它可能有所帮助）：这实际上是 Prolog 中编辑距离算法实现的片段代码。所以 :- table recursive_call(_,_,min) 的目的是将解决方案或答案添加到 table 中，同时保持最小值。

Answer 1

也许这个例子会有所帮助（它使用“格子”而不是“最小值”，但它们是相似的；如果你正在做编辑距离，你可能想要保留一个编辑列表） : https://www.swi-prolog.org/pldoc/man?section=tabling-mode-directed

“在此执行模型中，一个或多个参数未添加到 table。相反，我们记得单个聚合这些参数的值。"

Answer 2

我认为以下程序有助于理解 table 何时更新。

% This predicate shows updates that are triggered by the query.

show_updates :-
    abolish_all_tables,
    nl,
    cost(a, e, _),
    show_table(cost/3).

% This predicate shows the current state of a table.

show_table(Name/Arity) :-
    writeln('-- table --'),
    functor(Term, Name, Arity),
    forall( ( get_calls(Term, Trie, Return),
              get_returns(Trie, Return) ),
            writeln(Term)),
    writeln('-----------\n').

% This predicate is called each time a new solution cost must be
% compared with a previous one. It selects the minimum cost and informs
% whether the table should be updated or not.

mincost(Old, New, Min) :-
    Min is min(Old, New),
    show_table(cost/3),
    compare(R, New, Old),
    format('new_cost(~w) ~w previous_cost(~w) => ', [New, R, Old]),
    ( New < Old -> format('update with ~w\n\n', [New])
    ;          format('don\'t update\n\n', []) ).

%          B
%       ^  |  \
%      /   |   \
%     3    4    6
%    /     |     \
%   /      v      v
% A --8--> C --1--> E
%   \      ^      ^
%    \     |     /
%     7    5    9
%      \   |   /
%       v  |  /
%          D

:- table cost(_, _, lattice(mincost/3)).

link(a, b, 3).
link(a, c, 8).
link(a, d, 7).
link(b, c, 4).
link(b, e, 6).
link(c, e, 1).
link(d, c, 5).
link(d, e, 9).

cost(U, W, C) :- link(U, W, C).
cost(U, W, C) :- link(U, V, Cuv), cost(V, W, Cvw), C is Cuv + Cvw.

执行结果：

?- show_updates.

-- table --
cost(c,e,1)
cost(b,e,6)
-----------

new_cost(5) < previous_cost(6) => update with 5

-- table --
cost(c,e,1)
cost(a,e,8)
cost(b,e,5)
-----------

new_cost(9) > previous_cost(8) => don't update

-- table --
cost(d,e,9)
cost(c,e,1)
cost(a,e,8)
cost(b,e,5)
-----------

new_cost(6) < previous_cost(9) => update with 6

-- table --
cost(d,e,6)
cost(c,e,1)
cost(a,e,8)
cost(b,e,5)
-----------

new_cost(13) > previous_cost(8) => don't update

-- table --
cost(d,e,6)
cost(c,e,1)
cost(a,e,8)
cost(b,e,5)
-----------

true.

在 Prolog 中制表，什么时候存储值？

Tabling in Prolog, when are values stored?

prolog