Chap11c

Chap11c: memoisation

Database manipulation is a useful technique. It is especially useful for storing the results to computations, so that if we need to ask the same question in the future, we don’t need to redo the work: we just look up the asserted fact. This technique is called memoisation, or caching, and in some applications it can greatly increase efficiency. Here’s a simple example of this technique at work:

:- dynamic lookup/3. add_and_square(X,Y,Res):- lookup(X,Y,Res), !. add_and_square(X,Y,Res):- Res is (X+Y)*(X+Y), assertz(lookup(X,Y,Res)).

What does this program do? Basically, it takes two numbers X and Y, adds X to Y, and then squares the result. For example we have:

?- add_and_square(3,7,X).

But the important point is: how does it do this? First, note that we have declared lookup/3 as a dynamic predicate. We need to do this as we plan to change the definition of lookup/3 during run-time. Second, note that there are two clauses defining add_and_square/3 . The second clause performs the required arithmetic calculation and asserts the result to the Prolog database using the predicate lookup/3 (that is, it caches the result). The first clause checks the Prolog database to see if the calculation has already been made in the past. If it has been, the program simply returns the result, and the cut prevents it from entering the second clause.

Here’s an example of the program at work. Suppose we give Prolog another query

?- add_and_square(3,4,Y).

If we now ask for a listing we see that the database now contains

?- listing(lookup/3).

Should we later ask Prolog to add and square 3 and 4, it wouldn’t perform the calculations again. Rather, it would just return the previously calculated result.