Different behavior when exporting a tabled predicate

Help!
, ,
1

I’m using: SWI-Prolog version 8.4.1

I’m writing a parser with DCGs that exhibits weird behavior, which I’m inclined to believe is a bug on tabling and/or compilation. I can reliably turn the bug on or off by exporting the tabled predicate.

Repro steps

My code is at swifun/kilanone.pl at 6494a5ba24fba328f1510cd0f602c58e537ebe8a · brunokim/swifun · GitHub (sorry I didn’t make it shorter). If you execute tests with

$ swipl -g '(load_test_files([]), run_tests)' -t halt kilanone.pl

it passes all tests. If you remove the operation//3 export in the first line, some tests fail.

% PL-Unit: kilanone ................................
ERROR: /home/bkim/Projects/swifun/kilanone.plt:92:
	test parse prefix operation (forall bindings = [[43,45,97],operation(op(_1010,_1012,"+"),operation(op(_1030,_1032,"-"),id("a")))]): assertion failed
	Assertion: operation(op(500,yfx,"-"),id("+"),id("a"))=operation(op(_196,_198,"+"),operation(op(_216,_218,"-"),id("a")))
A
ERROR: /home/bkim/Projects/swifun/kilanone.plt:92:
	test parse prefix operation (forall bindings = [[45,43,97],operation(op(_13310,_13312,"-"),operation(op(_13330,_13332,"+"),id("a")))]): assertion failed
	Assertion: operation(op(500,yfx,"+"),id("-"),id("a"))=operation(op(_11332,_11334,"-"),operation(op(_11352,_11354,"+"),id("a")))
A. done
% 2 assertions failed
% 2 tests failed
% 33 tests passed

A bit more explanation

I’m writing a parser that, like Prolog, accepts a dynamic list of operators. An operator must be an identifier, and the same symbol may be used as a prefix, suffix or infix position.

These failed cases start in kilanone.plt:82. In essence, I want that a string like “- + a” to be parsed as -(+(a)), but it’s parsed as +(-,a) when operation//3 is not exported.

The operation//3 predicate works on a list of exprs like [id("-"), id("+"), id("a")] and is organized as follows (I’ve coalesced some less important logic into gen_*_op here):

:- table(operation//3).

% Terminal branch
operation(_, _, Expr) --> [Expr].

% Prefix branch
operation(OpSet, MaxPrec, operation(Op, Expr)) -->
   {gen_prefix_op(OpSet, MaxPrec, prefix, Op, Symb, Prec)},
   [id(Symb)],
   operation(OpSet, Prec, Expr).

% Suffix branch
operation(OpSet, MaxPrec, operation(Op, Expr)) -->
   {gen_suffix_op(OpSet, MaxPrec, suffix, Op, Symb, Prec)},
   operation(OpSet, Prec, Expr),
   [id(Symb)].

% Infix branch
operation(OpSet, MaxPrec, operation(Op, Left, Right)) -->
   {gen_infix_op(OpSet, MaxPrec, Op, Symb, Left, LeftPrec, Right, RightPrec)},
   operation(OpSet, LeftPrec, Left),
   [id(Symb)],
   operation(OpSet, RightPrec, Right).

By stepping the execution with the graphical tracer, I see that it correctly picks the prefix branch for “-” and “+”, but when reaching the terminal branch for “a”, it redoes the previous prefix branch instead of accepting the terminal.

Screenshot of GUI tracer stopped on terminal branch

I’ve used the following commands:

$ swipl kilanone.pl
?- gtrace.
[trace] ?- phrase(expression(Tree), `-+a`).

Thanks for your attention.

PS.: I do call abolish_all_tables before every attempt!

2

(BTW, I accidentally closed the tab before publishing and Discourse had saved everything as a draft :sob:)

3

Are you seeking help with Discourse? I don’t understand the statement.

4

I’m just glad that you use Discourse here, because on the olden days of forums, closing a tab made you lose all your work

1 Like
5

Now you don’t have to be annoyed with that bot. :slightly_smiling_face:

I would answer but I don’t use tabling that much.

1 Like
6

This is all a bit hard to figure out. One thing that you may not be aware of when I read this is that a tabled predicate finds all solutions before returning found unique solutions in an undefined order. Thus, if your grammar allows for multiple parses you’ll get the valid parses but while their order is defined under SLD resolution and may contain duplicates, under SLG resolution there are no duplicates and the order is undefined.

As the ordering is typically defined by a hash, subtle changes may flip the order.

P.s. Using clp(fd) or constraints in general are not (yet) supported in SWI-Prolog’s tabling. You better avoid them. Trying to add an answer with constraints should lead to an error. Their may be more subtle errors when there are pending constraints that do not surface in the arguments of tabled predicates.

3 Likes
7

Thanks for your answer, good to know that the order is undefined. Since using tabling is better than removing the left-recursion, I’ll work on yielding just one parse tree.