# Are there :- table ordering guarantees? **URL:** \ **Category:** Help!\ **Created:** [January 6, 2021, 4:56pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458 "2021-01-06T16:56:59Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![ericzinda](https://avatars.discourse-cdn.com/v4/letter/e/b3f665/32.png) [@ericzinda](https://swi-prolog.discourse.group/u/ericzinda)\ **Post date:** [January 6, 2021, 4:57pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/1 "2021-01-06T16:57:00Z")
[Edit to add examples] I’m trying to table a predicate of specializations (like a class hierarchy) where the order of backtracking matters: ```prolog :- 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: ```prolog ?- specializes(idWorld, X). X = idThing ; X = idPhysicalObject ; X = idPlace. ``` After tabling: ```prolog ?- specializes(idWorld, X). X = idPhysicalObject ; X = idPlace ; X = idThing. ``` ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [January 6, 2021, 8:04pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/2 "2021-01-06T20:04:13Z")
> [@ericzinda](#): > > Is this by design Good question 🙂 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 ☹ P.s. A funny observation I’ve learned with tabling is that you should typically reverse the order of subgoals, e.g., ```prolog 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 🙂 ---
**Author:** ![ericzinda](https://avatars.discourse-cdn.com/v4/letter/e/b3f665/32.png) [@ericzinda](https://swi-prolog.discourse.group/u/ericzinda)\ **Post date:** [January 6, 2021, 8:57pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/3 "2021-01-06T20:57:19Z")
[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: ```prolog 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). ``` ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [January 6, 2021, 9:11pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/4 "2021-01-06T21:11:22Z")
Considering you table /2 and define /3, this seems unlikely 🙂 I guess this is a typo? ---
**Author:** ![ericzinda](https://avatars.discourse-cdn.com/v4/letter/e/b3f665/32.png) [@ericzinda](https://swi-prolog.discourse.group/u/ericzinda)\ **Post date:** [January 6, 2021, 9:14pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/5 "2021-01-06T21:14:12Z")
> [@jan](#): > > I guess this is a typo? Yep! Fixed. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 6, 2021, 9:41pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/6 "2021-01-06T21:41:15Z")
> [@jan](#): > > P.s. A funny observation I’ve learned with tabling is that you should typically reverse the order of subgoals, e.g., > > ```prolog > specializesAll(Type, BaseType) :- > specializesAll(Type, IntermediateType), > rel(IntermediateType, specializes, BaseType). > > ``` Doesn’t this defeat tail-call optimization? ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 6, 2021, 9:46pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/7 "2021-01-06T21:46:34Z")
> [@ericzinda](#): > > backtracking order isn’t preserved 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. ---
**Author:** ![ericzinda](https://avatars.discourse-cdn.com/v4/letter/e/b3f665/32.png) [@ericzinda](https://swi-prolog.discourse.group/u/ericzinda)\ **Post date:** [January 6, 2021, 10:40pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/8 "2021-01-06T22:40:19Z")
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? ---
**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\ **Post date:** [January 7, 2021, 6:49am UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/9 "2021-01-07T06:49:15Z")
> [@ericzinda](#): > > it seems like Prolog does a good job in general of preserving order in a bunch of places. Prolog is just an inference engine, as described here: [SLD resolution - Wikipedia](https://en.wikipedia.org/wiki/SLD_resolution) 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. > [@jan](#): > > As is, answers are returned in more or less arbitrary order from a _trie_ that uses a hash table for non-deterministic nodes. 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. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [January 7, 2021, 7:42am UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/10 "2021-01-07T07:42:23Z")
> [@peter.ludemann](#): > > Doesn’t this defeat tail-call optimization? That is in the tabled case irrelevant 🙂 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 🙂 ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [January 10, 2021, 10:49pm UTC](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458/11 "2021-01-10T22:49:41Z")
BTW, see this paper for an implementation of tabling that guarantees ordering: > [@Tabling: Linear Resolution (SLT)](https://swi-prolog.discourse.group/t/tabling-linear-resolution-slt/838): > > This may be of interest given the new tabling work: [SLT-Resolution for the Well-Founded Semantics](https://arxiv.org/pdf/cs/0002016.pdf)