Are there :- table ordering guarantees?

Help!
#1

[Edit to add examples] I’m trying to table a predicate of specializations (like a class hierarchy) where the order of backtracking matters:

:- table specializesAll/2.

specializesAll(Type, BaseType) :-
    rel(Type, specializes, BaseType).

specializesAll(Type, BaseType) :-
    rel(IntermediateType, specializes, BaseType),
    specializesAll(Type, IntermediateType).

When I table and then query it, it seems the backtracking order isn’t preserved. Is this by design or am I doing something wrong?

Before tabling:

?- specializes(idWorld, X).

X = idThing ;
X = idPhysicalObject ;
X = idPlace.

After tabling:

?- specializes(idWorld, X).

X = idPhysicalObject ;
X = idPlace ;
X = idThing.
Tabling changes order of solutions - Expected?
#2

Good question :slight_smile: As is, answers are returned in more or less arbitrary order from a trie that uses a hash table for non-deterministic nodes. Sure, we could preserve order (at some cost). Note that predicates that need tabling (as otherwise they would not terminate) may produce answers in a quite hard to understand order that depends on the scheduling for resuming suspended goals.

I’m afraid I do not have a good answer :frowning:

P.s. A funny observation I’ve learned with tabling is that you should typically reverse the order of subgoals, e.g.,

specializesAll(Type, BaseType) :-
    specializesAll(Type, IntermediateType),
    rel(IntermediateType, specializes, BaseType).

This looks odd. But, using this schema more recursive calls are a variant of each other and thus you build fewer tables. Tabling is a lot of fun :slight_smile:

1 Like
#3

[edit: fixed typo] OK, thanks @jan (and thanks for the tip!). I’ve been working around it with an approach like this. It still gives me some great performance gains:

specializesAll(Type, BaseType) :-
   specializesAllSet(Type, BaseType, Set),
   member([Type, BaseType], Set).

:- table specializesAllSet/3.
specializesAllSet(Type, BaseType, Set) :-
   findall([Type, BaseType], specializesImp(Type, BaseType), Set).

specializesImp(Type, BaseType) :-
    rel(Type, specializes, BaseType).

specializesImp(Type, BaseType) :-
    rel(IntermediateType, specializes, BaseType),
    specializesAll(Type, IntermediateType).
#4

Considering you table /2 and define /3, this seems unlikely :slight_smile: I guess this is a typo?

#5

Yep! Fixed.

1 Like
#6

Doesn’t this defeat tail-call optimization?

#7

I wouldn’t expect ordering of either goal calls or backtracking to be preserved, and I’m wondering why a program should depend on the backtracking ordering. In a “pure” Prolog program, order shouldn’t matter (as long as the program still terminates); and reordering can have drastic effects on performance – e.g., using something dif/2 to interleave generating results and testing them.

1 Like
#8

Yes, this isn’t a “pure” Prolog program. The part I’m describing above regards inheritance hierarchies, and the order matters because I want the inheritance hierarchy to go from most specific to least specific. It is used for natural language, so you almost always want to match the most specific one first, often using once/1.

I could certainly add an “order” argument somewhere and sort it when I care about order, and that’s where I go, I guess, if I start hitting ordering issues that can’t be worked around.

[edit] I should note that the reason I expected ordering to be preserved is that it seems like Prolog does a good job in general of preserving order in a bunch of places. It kind of seemed like a pretty central assumption, but maybe that’s just historical and the edges have been worn off that over time?

#9

Prolog is just an inference engine, as described here: SLD resolution - Wikipedia

There are many places where the ordering becomes less obvious. If I understood Jan’s answer above, for tabling, the reason is the trie data structure.

The order is still pre-determined, in theory, but in practice it is arbitrary. You will get the same effect with many data structures. Anything that involves hashing, at least, I guess? This is the reason why almost any container library out there has different implementations for “set” and “ordered set”. Python, Java, C++ come immediately to mind.

#10

That is in the tabled case irrelevant :slight_smile: What happens is that the recursive call calls a variant of itself. Immediately for a (?,-) moded call and on the second iteration for any call. This causes the call to be suspended. When completing the tables the system runs a failure driven loop that effectively performs bottom-up reasoning until fixed point is reached. This code runs in bounded (even pretty low) stack space :slight_smile:

3 Likes
#11

BTW, see this paper for an implementation of tabling that guarantees ordering:

2 Likes