Question about tabling

Help!
1

Hi every one,

I am using SWI-Prolog version 8.4.2 and I do not understand a case of tabling execution. First I give an example that is ok for me :

:- table u/1 as incremental.

u(1).

u(X) :- 
    u(X),
    write("step 1"), write("  X = "), writeln(X).

The execution gives

2 ?- u(X).
step 1  X = 1
X = 1.

No problem here for me. My interpretation (maybe wrong) is the following :

  • resolving u(X) leads to suspending the inner recursive atom u(X)
  • when u(1) is found in the table, X is instanciated to 1 and the execution resumes.

Now I do not understand the following example :

:- table t/1 as incremental.

t(1).

t(X) :- 
    (t(X)
    ->
        write("step 1"), write("  X = "), writeln(X)
    ;
        write("step 2"), write("  X = "), writeln(X)
    ).

which gives the following execution :

3 ?- t(X).
step 2  X = _11416
step 1  X = _11846
step 1  X = 1     
true ;
X = 1.

Here, I do not understand :

  • why do we go through step 2 ?
  • why do we go through step 1 with X not instanciated ?
  • why don’t we only go through step 1 with X=1 ?

Cheers

2

This is invalid code for two reasons. One is the result of SWI-Prolog implementation based on delimited continuations. Continuations in general do not correctly handle a subsequent commit (they do under some conditions). As the t/1 call in the if-then-else performs a (continuation based) suspend, the -> doesn’t do its job. That explains step 2 becomes reachable. Now there is an answer with an unbound X, which causes the continuation in the then branch. That is SWI-Prolog’s limitation.

But, without this limitation this still doesn’t work. The -> cuts through an incomplete node of the tabled evaluation, potentially loosing answers. In that sense, SWI-Prolog’s above restriction is not a real restriction. When using tabling one must make sure commits do not prune answers from incomplete tables. Some Prolog systems check for that. This verification is not implemented yet (not sure it can be done realistically in the current design).

The rule of thumb is that a strongly connected component (a set of mutually recursive predicates in which some goal may lead to a variant of the same goal) should avoid cuts (and ->).

1 Like
3

Thanks a lot Jan. I will get ride of cuts in my program.
Best regards

4

Cuts a are useful, although the new single sided unification (=>) is often a good replacements. Cuts should typically be avoided in combination with tabling and constraints.

1 Like
5

In this context, what do you mean by “constraints” and can you give an example where problems arise?

6 
    (   dif(X,Y)
    ->  A
    ;   B
    ).

Now, if X and Y are not sufficiently instantiated to decide, dif/2 succeeds while adding constraints to variables in X and Y. This causes A to be executed while eventually X and Y may become definitely different.

The general rules is that if there are attributed variables around that may later cause failure a cut is unsafe.

7

OK. Although I would interpret this as if the constraint dif(X,Y) can be applied then execute A else execute B rather than if X is different from Y then execute A else execute B. Perhaps that’s a bit subtle but I’m not sure I would call that unsafe; just something any programmer using constraints has to understand.

8

Surely there is a procedural meaning that makes sense. The nice thing about tabling and constraints is that they extend the domains in which Prolog is fully declarative. All I’m saying is that while cuts are still fairly easy to understand in plain Prolog, they get a lot harder to understand with tabling and constraints. Note that the dif/2 code also depends on the strength of the propagation, i.e. one implementation may delay while another may already decide to fail.

1 Like
9

Surely cuts are all about the procedural meaning, whether in “plain Prolog” or CLP. And I’m not convinced they’re all that easy to understand in plain Prolog if my recollections of learning Prolog are to be trusted.

Another procedural meaning issue, i.e., affects cut semantics?

Bottom line: although constraints may allow one to write code that is somewhat more declarative, you can’t escape the procedural interpretation in a Prolog context. Maybe some future logic programming language will sort this out.

10

ASP is declarative (I think). It also comes with its problems, such as the need for grounding. s(CASP) avoids that, but has other pitfalls. That aside, a purely declarative language that has no procedural semantics is a bit hard to use if you want things to happen in some order or you want to implement a particular algorithm. That, IMO, is one of the powers of Prolog: it can do both. You can of course also call it a weakness, claiming Prolog is a lousy imperative language as well as a lousy declarative one :slight_smile:

1 Like