Date sön 12 februari 2017

Las time swi prolog tabling was introduced together with some small extensions. The next level up on this is to make tabling work with interleaving constructs that derive it's roots from kanren. Shorts story is that ,, is an interleaving conjunction and ;; is an interleaving disjunction and once_i(Goal) execute Goal with 0 or 1 success. The system introduces an interleaving frame inside the predicate f when it executes and hence f behaves like a normal predicate and you can use ! to cut it and not need once_i. if f is a recursive table it will guarranteingly execute interleaving construts but also inside the definition of f you may find the inteleaving constructs catched by the predicate and not seen outside it. The tabling interleaving constructs comes in two forms.

table_i, this as arguments just as with table but it also allows interleaving construts in the defenition. Let's see some example: first a non interleaving construct.

-table.
fe(a).

fe([A,B]) :-
  fe(A),
  fe(B).

ff([U,V]) :- fe(U),!,fe(V).

The execution is not optimal, here is the sequence found,

> .10 ff(X).

X = [a, a].
X = [a, [a, a]].
X = [a, [a, [a, a]]].
X = [a, [a, [a, [a, a]]]].
X = [a, [a, [a, [a, [a, a]]]]].
X = [a, [a, [a, [a, [a, [a, a]]]]]].
X = [a, [a, [a, [a, [a, [a, [a, a]]]]]]].
X = [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]].
X = [a, [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]]].
X = [a, [a, [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]]]].
X = [a, [a, [a, [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]]]]].

The problem with this sequence is that there is finit solutions that are never found. It's with these problems interleaving constructs are well used. So let's hot this example up and define:

-table_i.
fe2(a).

fe2([A,B]) :-
  fe2(A),,
  fe2(B).

ff2([U,V]) :- fe2(U),!,fe2(V).

Note the interleaving ,, in the definition of fe2 and this function behaves just the same as any other predicate with infinit solutions and here are them,

> .10 ff2(X).

X = [a, a].
X = [a, [a, a]].
X = [a, [a, [a, a]]].
X = [a, [[a, a], a]].
X = [a, [a, [a, [a, a]]]].
X = [a, [[a, a], [a, a]]].
X = [a, [a, [[a, a], a]]].
X = [a, [[a, [a, a]], a]].
X = [a, [a, [a, [a, [a, a]]]]].
X = [a, [[a, a], [a, [a, a]]]].

We see that the cut works and that we will generate any finite seqence in finite time.

table_rec, We could try find all recursive solutions to the predicate and any solution with finite number of symbols should be found in finite time. Soo with,

-table_rec.
fe3(a).

fe3([A,B]) :-
  fe3(A),,
  fe3(B).

ff3([U,V]) :- fe3(U),!,fe3(V).

We find the solutions,

> .rec .20 ff3(X).

X = [a, a].
X = [a, {0}[ref[0], ref[0]]].
X = [a, {0}[a, ref[0]]].
X = [a, {1}[{0}[ref[0], ref[0]], ref[1]]].
X = [a, {0}[ref[0], a]].
X = [a, [a, a]].
X = [a, {0}[ref[0], {1}[ref[1], ref[1]]]].
X = [a, [a, {0}[ref[0], ref[0]]]].
X = [a, {1}[{0}[a, ref[0]], ref[1]]].
X = [a, [{0}[ref[0], ref[0]], a]].
X = [a, {0}[ref[0], {1}[a, ref[1]]]].
X = [a, [a, {0}[a, ref[0]]]].
X = [a, [{0}[ref[0], ref[0]], {1}[ref[1], ref[1]]]].
X = [a, {0}[ref[0], {2}[{1}[ref[1], ref[1]], ref[2]]]].
X = [a, [a, {1}[{0}[ref[0], ref[0]], ref[1]]]].
X = [a, {0}[ref[0], {1}[ref[1], a]]].
X = [a, [a, {0}[ref[0], a]]].
X = [a, {2}[{1}[{0}[ref[0], ref[0]], ref[1]], ref[2]]].
X = [a, {0}[ref[0], [ref[0], ref[0]]]].
X = [a, {0}[a, [ref[0], ref[0]]]].

Let's see another example where all solutions are recursive, here it is

-table_rec.
fd([A|B]) :- (A=1;A=0),,fd(B).

With 20 solutions,

> .rec .20 fd(X).

X = {0}[1|ref[0]].
X = {0}[0|ref[0]].
X = [1|{0}[1|ref[0]]].
X = [1|{0}[0|ref[0]]].
X = [0|{0}[1|ref[0]]].
X = [0|{0}[0|ref[0]]].
X = [1, 1|{0}[1|ref[0]]].
X = {0}[1, 1|ref[0]].
X = [1, 1|{0}[0|ref[0]]].
X = [0, 1|{0}[1|ref[0]]].
X = {0}[0, 1|ref[0]].
X = [1, 0|{0}[1|ref[0]]].
X = [0, 1|{0}[0|ref[0]]].
X = [1, 0|{0}[0|ref[0]]].
X = [0, 0|{0}[1|ref[0]]].
X = [1, 1, 1|{0}[1|ref[0]]].
X = {0}[1, 0|ref[0]].
X = [0, 0|{0}[0|ref[0]]].
X = {0}[0, 0|ref[0]].
X = [1|{0}[1, 1|ref[0]]].

To note, for complex construct it can be a good idea to make use of logical variable that follows like an assoc along the calculation, normal prolog variables is heavily set and unset, which is not needed if one make use of assoc variables.

The idea is to continue to examine this system. Happy Hacking!


Comments

comments powered by Disqus

~ Follow me ~