- Don't do it.
- Don't do it again.

In this text, we discuss option 2, that is ways to not do it

Different Prolog systems provide tabling in various forms and with different characteristics. XSB Prolog is one of the pioneering systems in this area, and some of its techniques are now becoming more widely available also in other systems. Your Prolog system's manual should contain the exact details.

For example, to enable tabling in Scryer Prolog, you need to:

- Use
`library(tabling)`via the directive`:- use_module(library(tabling)).`in your source file. - Enable tabling via the
`table/1`directive.

In this case, tabling has made the predicate:- use_module(library(tabling)). :- table adjacent/2.adjacent(a, b). adjacent(e, f). adjacent(X, Y) :- adjacent(Y, X).

?- adjacent(X, Y), false.As the second example, let us consider the series offalse.

fibonacci(0, 1). fibonacci(1, 1). fibonacci(N, F) :- N #> 1, N1 #= N - 1, N2 #= N - 2, fibonacci(N1, F1), fibonacci(N2, F2), F #= F1 + F2.The relation works as intended in the most general case:

?- fibonacci(N, F). N = 0, F = 1 ; N = 1, F = 1 ; N = 2, F = 2 ; N = 3, F = 3 ; N = 4, F = 5 ; ...It can also be used for more specific queries:

?- fibonacci(17, F). F = 2584 ; false.However, the computation runs out of stack or takes too long for larger arguments:

?- fibonacci(100, F).We can easily enable tabling by adding the following directives to the file:ERROR: Out of local stack

:- use_module(library(tabling)). :- table fibonacci/2.Using SLG resolution, the answer to the previous query is now readily found:

?- fibonacci(100, F).Tabling also allows you to use left-recursive DCGs for parsing. For example, you can add the directive:F = 573147844013817084101.

:- table tree_nodes//1.to apply tabling to the DCG nonterminal

Scryer Prolog implements tabling via

Consider for example the following definition of

:- dynamic memo_/1. memo(Goal) :- ( memo_(Goal) -> true ; once(Goal), assertz(memo_(Goal)) ).

As long as

Note that this is less powerful than tabling: First, it requires

Applied to

fibonacci(0, 1). fibonacci(1, 1). fibonacci(N, F) :- N #> 1, N1 #= N - 1, N2 #= N - 2,Sample query and answer:memo(fibonacci(N1, F1)),memo(fibonacci(N2, F2)), F #= F1 + F2.

?- fibonacci(100, F).F = 573147844013817084101.

We can use semicontext notation to carry around the state

As an example, we present the calculation of the

min_edit(As, Bs, Min-Es) :- empty_assoc(Assoc0), phrase(min_dist(As, Bs, Min-Es), [Assoc0], _). min_dist([], [], 0-[]) --> []. min_dist(As, Bs, Min-Es) --> ( state(S0), { get_assoc(store(As,Bs), S0, Min-Es) } -> [] ; { findall(option(Action,Cost,As1,Bs1), edit_option(As, Bs, Action, Cost, As1, Bs1), Options) }, assess_options(Options, CostOptions), state(S0, S), { keysort(CostOptions, [Min-Es|_]), put_assoc(store(As,Bs), S0, Min-Es, S) } ). assess_options([], []) --> []. assess_options([option(Action,Cost,As,Bs)|Options], [Min-[Action|Es]|Rest]) --> min_dist(As, Bs, Min0-Es), { Min #= Min0 + Cost }, assess_options(Options, Rest).This code is quite flexible, and can be adapted to various use cases by providing a suitable definition of

edit_option([A|As], Bs, drop(A), 1, As, Bs). edit_option(As, [B|Bs], insert(B), 1, As, Bs). edit_option([A|As], [A|Bs], use(A), 0, As, Bs).This means that there are three possible actions (dropping, inserting and using an element), with associated costs of one, one and zero, respectively.

Example query and answer:

?- min_edit([a,b,c,e,f], [a,x,b,d,e,f], Min).If it were implemented naively,Min = 3-[use(a), insert(x), use(b), drop(c), insert(d), use(e), use(f)]; false.