CODEWITHSUNDEEP
prologdynamic-programming
Diskun Zhu
Diskun Zhu

Reputation: 115

Assert Intermediate Result in Prolog

This is the question.

Define a predicate sigma(N,S) such that S = 1+2+...+N. And remember every new intermediate result in the query. For example, after query sigma(3,S), it will store some thing like sigma(2,3),sigma(3,6) to database such that we needn't do duplicate and useless work later.

I tried the following method to solve it.

sigmares(1,1).

mysigma(N,A,Sum) :-
    sigmares(N,SN),
    Sum is SN+A,
    !.

mysigma(N1,Acc,Sum) :-
    N is N1-1,
    A is Acc + N1,
    mysigma(N,A,Sum),
    assertz(sigmares(N1,Sum)). % <<<<<<<<<< This line doesn't work properly.

sigma(N,X) :-
    mysigma(N,0,X).

There is some problem with assertz line. Since sum can be only initialized once which is the value of sum from 1 to N, sigma(2,6),sigma(3,6) for query sigma(3,S) will be inserted. Is there any other way to store new intermediate sigmares?

Upvotes: 0

Views: 474

Answers (2)

Paulo Moura
Paulo Moura

Reputation: 18663

First, it's good coding style to always declare the dynamic predicates that your code uses using the standard dynamic/1 directive. Simply add at the beginning of the file:

:- dynamic(sigmares/2).

An interesting aspect of your definition of the mysigma/3 predicate is that it is a non tail-recursive with the consequence that it requires space linear on its inputs. But that allows it to cache all intermediate results as you intend. A fixed version of your code will be:

:- dynamic(sigma_cache/2).

sigma_cache(1, 1).

sigma(N, S) :-
    sigma_cache(N, S),
    !.
sigma(N, S) :-
    N > 1,
    M is N - 1,
    sigma(M, SM),
    S is SM + N,
    assertz(sigma_cache(N, S)).

Sample call:

?- sigma(5, S).
S = 15.

?- listing(sigma_cache/2).
:- dynamic sigma_cache/2.

sigma_cache(1, 1).
sigma_cache(2, 3).
sigma_cache(3, 6).
sigma_cache(4, 10).
sigma_cache(5, 15).

true.

Upvotes: 1

Paulo Moura
Paulo Moura

Reputation: 18663

This alternative answer provides a solution based on the tabling mechanism found in some Prolog systems, including B-Prolog, Ciao, SWI-Prolog, XSB, and YAP:

:- table(sigma/2).

sigma(1, 1).
sigma(N, S) :-
    N > 1,
    M is N - 1,
    sigma(M, SM),
    S is SM + N.

Let's test it with the help of SWI-Prolog handy time/1 library predicate that reports the time and number of inferences taken to prove a goal:

?- time(sigma(5, S)).
% 166 inferences, 0.000 CPU in 0.006 seconds (2% CPU, 1238806 Lips)
S = 15.

?- time(sigma(5, S)).
% 5 inferences, 0.000 CPU in 0.000 seconds (68% CPU, 208333 Lips)
S = 15.

Note that I used a non tail-recursive definition for the sigma/2 predicate on purpose so that all intermediate results are cached (as per the requirements in your question). For example:

?- time(sigma(4, S)).
% 5 inferences, 0.000 CPU in 0.000 seconds (70% CPU, 217391 Lips)
S = 10.

You can see that, after the first call, the result is cached by the tabling mechanism, resulting in a much lower number of inferences when we repeat the query.

?- time(sigma(6, S)).
% 32 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 727273 Lips)
S = 21.

?- time(sigma(6, S)).
% 5 inferences, 0.000 CPU in 0.000 seconds (70% CPU, 217391 Lips)
S = 21.

Note again the number of inferences. The first query reuses the cached result for sigma(5, S) and caches the result for sigma(6, S), making the repeated query again faster as it just reuses the cached result.

Upvotes: 0

Related Questions