Tabling in Prolog, when are values stored?

user_15526701 0
Viewed 127

So let's say I have this code that uses a table to take 'note' of previous solutions or answers.

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.

My question is, are the values being 'stored' or 'cached' into the table each time recursive_call is called?

Note (just to add more context to this code in case it might help): This is actually a snippet code of edit distance algorithm implementation in Prolog. So the purpose of :- table recursive_call(_,_,min) is to add the solutions or answers into the table while keeping the minimum value.

prolog
2 Answers

Maybe this example will help (it uses a "lattice" rather than "min", but they're similar; and if you're doing edit distance, you might want to keep a list of the edits anyway): https://www.swi-prolog.org/pldoc/man?section=tabling-mode-directed

"In this execution model one or more arguments are not added to the table. Instead, we remember a single aggregated value for these arguments."

user_91434020

I think the following program helps to understand when a table is updated.

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

Execution result:

?- 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.
user_115359400
Related