Predicate cache

Question

Is there a Prolog implementation or library that caches predicates?

Or would you implement a, say, FIFO cache using assertz/1 and retract/1, like this:

:- dynamic cache/1.
ccall(G) :- cache(G).
ccall(G) :-
    \+ cache(G),
    call(G),
    ( findall(G0,cache(G0),Gs), length(Gs,N), N =:= 100 -> once retract(cache(_)) ; true ),
    assertz(cache(G)).

In ECLiPSe-CLP, one could at least replace the findall/3 line using extra-logical variables:

...
( getval(cache_size) =:= 100 -> once retract(cache(_)) ; incval(cache_size) ),
...

On my box, 1000 calls to this ccall/1 take >4.00 cpu sec, whereas the actual goal cpu time is negliglible (0.04 cpu sec). So I guess a cache (particularly a LRU cache or so) implemented inside the interpreter would still outperform the assertz/1 and retract/1.

I don't want to have caching for every predicate, of course, only for very few ones. A scenario could be like this: p([H|T], E) :- q(H,E) ; p(T,E) with q/2 having no side effects. p/2 is called for a steadily growing list but always/often for the same E.

Rigney

Answer 1

do you want tabling/memoization?
XSB offers automatic tabling (you declare which predicates you want to have tabling)

and yes, assertz/1 etc are kinda slow

Sanguinaria

Thanks, memoization/tabling were the terms I was looking for. Memoization can be implemented in ECLiPSe-CLP, the dialect I'd prefer, using extra-logical stores. It's so easy if you know the correct keywords :). – Rigney

Mercury, a that combines Prolog with a type system à la Haskell, also supports memoization by simply adding a pragma. – Rigney