Control & the database · Lesson 30 of 43

The dynamic database

assert, retract, counters and memoisation.

A Prolog program is also a database that can change while it runs. assertz(Clause) adds a clause at the end, asserta at the front, retract(Clause) removes one. Predicates you modify must be declared dynamic:

:- dynamic stock/2.

stock(apple, 5).
stock(pear, 2).

?- assertz(stock(plum, 9)), findall(I-N, stock(I, N), L)

?- retract(stock(apple, _)), findall(I, stock(I, _), L)

?- retractall(stock(_, _)), \+ stock(_, _)

listing/1 prints the current clauses, which is a great way to see what happened:

?- assertz(stock(kiwi, 1)), listing(stock/2)

A counter

State changes are a retract followed by an assert. Here is a counter that hands out ticket numbers:

:- dynamic counter/1.
counter(0).

next_ticket(N) :-
    retract(counter(Old)),
    N is Old + 1,
    assertz(counter(N)).

?- next_ticket(A), next_ticket(B), next_ticket(C)

Memoisation: remember what you've computed

Remember the slow naive Fibonacci? Store each result the first time you compute it, and look it up afterwards:

:- dynamic memo/2.

fib(N, F) :- memo(N, F), !.                % already known
fib(N, F) :- N < 2, !, F = N.
fib(N, F) :-
    A is N - 1, B is N - 2,
    fib(A, FA), fib(B, FB),
    F is FA + FB,
    assertz(memo(N, F)).                   % remember it

?- fib(30, F)

?- fib(200, F)

The naive version needs millions of calls for fib(30); this one needs about sixty.

SWI-Prolog can do this for you with tabling: just declare :- table fib/2. and write the naive definition.

:- table fib/2.
fib(0, 0).
fib(1, 1).
fib(N, F) :- N > 1, A is N - 1, B is N - 2, fib(A, FA), fib(B, FB), F is FA + FB.

?- fib(300, F)

The dynamic theory

A Prolog program is actually made of two "theories" (sets of predicates and clauses):

the static one, typically provided at the beginning of the computation session: the one written in the IDE;
a dynamic one, initially empty, where you can add and remove clauses while running. Clauses are terms, hence the API is straightforward.

Some Prologs have a single theory, and it is dynamic. Not surprisingly, a Prolog theory can be inspected programmatically.

The predicates for changing programs

predicate	meaning
`assert(+Clause)`	adds a clause, always succeeds, never binds. E.g. `assert(p(1))`, `assert((p(X) :- q(X)))`
`asserta`, `assertz`	assert on top / at the bottom
`retract(+Clause)`	retracts a matching clause if one exists, and possibly binds
`retractall(+Clause)`	retracts all matching clauses, always succeeds, never binds
`clause(?Head, ?Body)`	queries for a clause (possibly with many solutions, and binds). `Body` is `true` for a fact, or `(G1,...,Gn)` in general

Note the double parentheses in assert((p(X) :- q(X))): the operator :- binds looser than an argument allows, so a rule being asserted must be wrapped in its own parentheses.

:- dynamic p/1, q/1.
q(5).

?- assert(p(1)), assert((p(X) :- q(X))), findall(Y, p(Y), L)

?- assert((p(X) :- q(X))), clause(p(A), Body)

?- assert(p(1)), clause(p(1), Body)

?- asserta(p(0)), assertz(p(9)), findall(Y, p(Y), L)

Example: caching factorial in the theory

File factorial-cache.pl. withcache(P) first looks for P among the cached results; if it is not there, it solves P once and asserts the result. (withcache can be understood as a metainterpreter for single-result predicates, adding caching to the standard interpretation: more on that in the metainterpreter lesson.)

cached/1 must be declared dynamic: in SWI-Prolog, calling an undefined predicate is an error, not a failure.

:- dynamic cached/1.

factorial(0, 1).
factorial(X, Y) :- Xm is X-1, factorial(Xm, Y2), Y is Y2*X.

withcache(P) :- cached(P), !.
withcache(P) :- once(P), assert(cached(P)).

?- cached(X)

?- once(factorial(3, N))

Calling factorial(3, N) directly (here under once/1, see the warning below) caches nothing. Now a sequence of goals: because each run of this notebook starts from a clean slate, we ask them as one conjunction, in the same order (cached(X) first fails, withcache(factorial(3,N)) fills the cache, and so on):

?- \+ cached(_), withcache(factorial(3, N)), cached(X), clause(cached(X2), B), withcache(factorial(4, N4)), findall(C, cached(C), L)

Exercise: A stack with assert

A stack is stored as dynamic facts item(X). The declaration is provided. Write:

push(X): add X as the new top.
pop(X): remove the top item and return it (fail on an empty stack).

(Hint: asserta adds at the front.)