Date tis 09 oktober 2018

Tabling or memoization in guile-log is revised and updated to reflect the interface found in swi prolog. The guile-log implementation uses the postpone system in order e.g. basically a use of delimited continuations, used in the swi prolog implementation as well. The idea is that at the first time we enters with a pattern, we establish a collection mechanism that collects all values resulting from the evaluation of the predicate, success as well as fail is recorded. Then at a re evaluation the memoized sequence is reused. If we happen to enter as a subgoal the same function with the same signature, then all memoized results are generated and if not all is generated the state is stored and it will delay until more results is available or all are generated. The idea is to batchwise collect continuation points and then when no more solution is available, the stored solutions are retried. In case of a fixpoint it all fails. This means that recursive definitions that in a depth first search lead to infinity loops, it resolves and the a solution is found in finite times. Note that this is another mechansim appart from the minikanren apprach that tries to do this. The difference is that minikanren is more generally in this mechanism. E.g. cases which lead to infinite recursion with tabling can be finite in minikanren, and all cases which is finite with tabling is finite with the minikanren approach. But the memoization means that the speed of the solution with tabling is much better.

So how does the interface look like? Well there is a lightweight version called memo and used like.

-memo.
fib(0,1).
fib(1,1).
fib(N,F) :-
  N1 is N - 1,
  N2 is N - 2,
  fib(N1,F1),
  fib(N2,F2),
  F is F1 + F2

And an example of execution is,

fib(1000,X).
 X = 703303677114228158218352548771835497701812698363587327...
     426049050871545371181969335797422494945626117334877504...
     492417659910881863632654502236471060120533741212738673...
     39111198139373125598767690091902245245323403501.

That is executed in less than a second. Use memo whan all executions has one solution. The more advanced solution is to use table here one specify a set of in-out varaibles and if the result of the non ignored resto of the arguments is from a unique class of solutions we can take shortcuts ,else if the classes is infinite e.g. all possible paths from a startpoint to an endpoint in a biderctional graph. The idea is to find a candidate for these remaining variables and there is a system to decide what to store in them. So we have a set of modes. '+' means an inout variable. 'min' means that the minimum value is stored, 'max' means maximum values of those values are stored, 'sum' means that the sum of the variabvles is stored, 'last' means that the last value is stored. 'first' means that the first encountered value is stored and the predicate search ends (for the others it can happen that a new predicate appears and then the combination is taken and it backtracks. po(f), with predicate f as f(Old,New) menas take new if f is true else take the old value. Finally we have lattice(f) with f=f(Old,New,Res). Here f combines old and new value and produces res which will be used as the value. Sometimes if whatever value an argument has, it has no influence of the result can be signaled with the ignore modifier. A good example of ignore can be statistics and e.g. a depth value used to cut an infinite recursion.

Sometimes we want to say that for these incomming values the system has only one solution, to save space and limit the amount of recursion continuations stored. E.g. a way to specify that an + argument is ground. The + modifier will be ground if it is ground and has no unbounded variables. all means that all values can be considered ground. An argument with a modifier ground(f), where the user supplied predicate f=f(Arg) tell if the argument is ground or not.

Let's make an example, consider the minlen predicate

minlen(X,Y,Z) :-
  length(X,NX),
  length(Y,NY),
  (
    NX < NY ->
      Z=X;
    Z=Y
  ).

Then we can define the path finder f

-table(+,+,lattice(minlen)).

f(a,b,[a,b]).
f(b,a,[b,a]).
f(b,c,[b,c]).
f(c,b,[c,b]).
f(b,d,[b,d]).
f(d,b,[d,b]).
f(d,f,[d,f]).
f(f,d,[f,d]).
f(c,e,[c,e]).
f(e,f,[e,f]).

f(X,Y,P) :-
  f(X,Z,P1),
  f(Z,Y,P2),   
  append(P1,P2,P).

With solution

> .* f(a,_,X).

X = [a, b].
X = [a, b, b, a].
X = [a, b, b, c].
X = [a, b, b, d].
X = [a, b, b, c, c, e].
X = [a, b, b, c, c, e, e, f].

no.

If we don't care about the actual value of the path we can use the first encountered. Also we show of an ignored depth argument, here is f2

-table(ignore,+,+,first).

f2(_,a,b,[a,b]).
f2(_,b,a,[b,a]).
f2(_,b,c,[b,c]).
f2(_,c,b,[c,b]).
f2(_,b,d,[b,d]).
f2(_,d,b,[d,b]).
f2(_,d,f,[d,f]).
f2(_,f,d,[f,d]).
f2(_,c,e,[c,e]).
f2(_,e,f,[e,f]).

f2(N,X,Y,P) :-
  write(f(N,X,Y)),nl,
  NN is N + 1,
  f2(NN,X,Z,P1),
  f2(NN,Z,Y,P2),   
  append(P1,P2,P).

with solutions,

> .* f2(0,c,_,X).
X = [c, b].
X = [c, e].

  f(0, c, X0)

X = [c, b, b, a].
X = [c, b, b, c].
X = [c, b, b, d].

  f(1, b, X0) 
  f(2, a, X0)

X = [c, b, b, d, d, f].

  f(2, d, X0)
  f(3, f, X0)
  f(1, e, X0)

no.

The system works well under negation and cut's but this is experimental. To make things more efficient a postpone_frame can be issued and then all continuations below that will be managed with it. Else if there is a long path of state changes between the beginning and the actual postpones the system can spend a lot of time restoring and removing that state. The system works in batches however and because we store the tree of state changes moving from one pospone to the next whithin the batch can be lightweight altghough the path from the postpone_frame is long. So it might not be too bad. What doesn't work is if a function is not depending on it's arguments alone e.g. setval/getval is used below.


Comments

comments powered by Disqus

~ Follow me ~