Memorising (and caching) solutions found in a Prolog query?

Question

In this question on StackExchange I've asked (and it has been solved) about a Prolog program I have been trying to create. But while it works in principle, it doesn't scale to my real world need.

Before I start learning yet another language (Datalog), I'd like to try my already done work and know how I can implement in Prolog a way to memorise results from earlier queries such that the same query is only executed once. So, I'm looking for a way to add the result of a successful query to a List and if that same query is asked again, it doesn't redo the calculation, but uses the remembered result.

My main problem is that I cannot find a way to keep the result of a successful query in a list that is passed 'up the chain'.

In

% get this out of the way, quickly
isARelation( Source, Relation, Target, _) :-
    isADirectRelation( Source, Relation, Target).

% Structural Chains
isARelation( Source, Relation, Target, Visited) :-
    \+ member( [Source,Relation,Target], Visited),
    structuralOrDependencyRelation( RelationOne),
    structuralOrDependencyRelation( RelationTwo),
    weakest( Relation, RelationOne, RelationTwo),
    isADirectRelation( Source, RelationOne, Intermediate),
    isARelation( Intermediate, RelationTwo, Target, [[Source,RelationOne,Intermediate]|Visited]).
isARelation( Source, Relation, Target, Visited) :-
    \+ member( [Source,Relation,Target], Visited),
    structuralOrDependencyRelation( RelationOne),
    structuralOrDependencyRelation( RelationTwo),
    weakest( Relation, RelationOne, RelationTwo),
    isADirectRelation( Source, RelationTwo, Intermediate),
    isARelation( Intermediate, RelationOne, Target, [[Source,RelationTwo,Intermediate]|Visited]).

How do I implement that the first call

isARelation(A, B, C, []).

does the calculation of the results, and a second call

isARelation(A, B, C, []).

uses the earlier found result, which is kept 'globally'?

Answer 1

This is advice on how to generically do what tabling does. I haven't followed this advice in ages myself so there may be inaccuracies here. Hopefully the rest of the gang will show up and correct me if I'm off-base.

1. You have a predicate foo/4 that is inefficient.

2. Add this to your file:

   :- dynamic(cached_foo/4).
   

3. Rename foo/4 to compute_foo/4 or something.

4. Make a new predicate foo/4 that looks like this:

   foo(X, Y, Z, Q) :-
     cached_foo(X, Y, Z, Q) ; 
     (
       compute_foo(X, Y, Z, Q), 
       assertz(cached_foo(X, Y, Z, Q))
     ).
   

Answer 2

This is not really an answer to your question :(

The other answer has the right idea, but the implementation has a problem. Let's say we want to make a memoized version of squaring a number:

:- dynamic mem_square/2.

square(N, S) :-
    (   mem_square(N, S)
    ;   S is N*N,
        assertz(mem_square(N, S))
    ).

BTW, the parentheses in the other answer are completely unnecessary. These are also unnecessary, but this is how you usually wrap a disjunction, just in case it is part of a conjunction. In other words, this: a ; (b, c) is the same as a ; b, c, but (a ; b), c is not the same.

Now, if I load this program from the toplevel and query:

?- square(3, S).
S = 9. % first time it's fine

?- square(3, S).
S = 9 ;
S = 9. % now there's two

?- square(3, S).
S = 9 ;
S = 9 ;
S = 9. % now three

If you keep on querying a memoized fact, and you backtrack into it, you will keep on computing again and again and adding more and more identical copies of it. Instead, you can try for example this:

:- dynamic mem_square/2.

square(N, S) :-
    (   mem_square(N, S)
    ->  true
    ;   S is N*N,
        assertz(mem_square(N, S))
    ).

Now, there is no choice point.

This is still not a clean implementation if you are meant to have choice multiple solutions. Any solutions after the first will be cut by the ->.