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

Question

假设我有这段代码，它使用一个表格来“记录”以前的解决方案或答案。

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 时，值是被“存储”还是“缓存”到表中？

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

Answer 1

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

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