Prolog Database Recording

Question

I have this factorial predicate.

fact(0, 1).
fact(N, F) :- N > 0, 
        N1 is N-1,
        fact(N1, F1),
        F is F1 * N.

How do I change this predicate such that every time a query is issued, the result of the calculation is stored in the database? New queries should use then the stored results if available.

Answer 1

What you are looking for is generally called memoization, but is referred to as tabling in the context of Prolog. Conveniently, there is a library for this called tabling for SWI Prolog.

:- use_module(library(tabling)).
:- table fact/2.

fact(0, 1).
fact(N, F) :- N > 0,
              N1 is N-1,
              fact(N1, F1),
              F is F1 * N.

You can verify that the memoization works by running trace before your calls to fact. Note that the two :- lines are called directives and are run by the compiler, so running them in a repl will not work.

Edit

If you don't want to use the tabling library, you can accomplish this with asserta. This will insert a fact at the top of the database, as if you had entered it into the file yourself.

fact(0, 1).
fact(N, F) :-
              N > 0,
              N1 is N-1,
              fact(N1, F1),
              F is F1 * N,
              asserta(fact(N, F)).

Prolog will see the new predicate first and will use it instead of recomputing your factorial. Once again, you can check this by tracing.

Answer 2

As jcolemang said, what you want is tabling/memoization. While there are indeed libraries which is the recommended and efficient (not just time-wise, but mainly performance-wise) way of doing things, it is understandable that you may want to implement it on your own.

It is possible to use assert to add dynamic facts in the prolog database, but you'll need to declare them as such, by having :-dynamic(fact) in the file which will allow you to add/remove facts.

However, there's a performance penalty in doing that. An alternative would be to have a lookup table/cache that will be persisted across calls. The dictionary could be stored using global mutable variables (yikes!), which are more efficient than using dynamic facts. As always, it's a good idea to minimize the code that uses variables/side-effects directly - in your factorial example, you could simply have a wrapper predicate that fetches the dictionary and puts it back at the end of the call e.g.

factorial(N, F):-
get_global_dict(D),
real_factorial(N, F, D, DF),
store_global_dict(DF).