Ordering residual goals in query answers

Help!
#1

Variable unifications in top-level answers appear to be in ordered as the variables appear in the query (term compare order of variables?):

?- [X,Y,W,Z]=[1,2,3,4].
X = 1,
Y = 2,
W = 3,
Z = 4.

However residual goals (as generated by attribute_goals) appear in pseudo random order, probably the order generated by term_attvars:

?- {X+Y+Z+W==10000}.
X::real(-1.0Inf, 1.0Inf),
W::real(-1.0Inf, 1.0Inf),
Z::real(-1.0Inf, 1.0Inf),
Y::real(-1.0Inf, 1.0Inf).

Kind of a picky issue, but is there a possibility the “attvars” could be sorted somewhere such that the attribute goals would be in the same natural order as the unification goals?

#2

Nope. Lexical ordering in the term that is read. Just swap some around.

This should also happen for attvars that also this too walks the term looking for attvars top-down left-right. Not really sure what happens. Goal rewriting?

#3

Not rewriting as such, but they are “compiled” so the order is affected by operator precedence:

?- [X,Y,W,Z]::real.
X::real(-1.0e+16, 1.0e+16),
Y::real(-1.0e+16, 1.0e+16),
W::real(-1.0e+16, 1.0e+16),
Z::real(-1.0e+16, 1.0e+16).

?- [X,Y,W,Z]::real,{X+Y+W+Z==1}.
X::real(-1.0e+16, 1.0e+16),
Z::real(-1.0e+16, 1.0e+16),
W::real(-1.0e+16, 1.0e+16),
Y::real(-1.0e+16, 1.0e+16).

?- [X,Y,W,Z]::real,{X*Y+W*Z==1}.
X::real(-1.0e+16, 1.0e+16),
W::real(-1.0e+16, 1.0e+16),
Z::real(-1.0e+16, 1.0e+16),
Y::real(-1.0e+16, 1.0e+16).

Digging down a level:

?- [X,Y,W,Z]::real,T=X*Y+W*Z,{T==1},term_attvars(T,AVs),sort(AVs,SVs).
T = X*Y+W*Z,
AVs = [X, _156384, _156390, W, Z, Y],
SVs = [X, Y, W, Z, _156384, _156390],
X::real(-1.0e+16, 1.0e+16),
_156384::real(-1.0e+32, 1.0e+32),
_156390::real(-1.0e+32, 1.0e+32),
W::real(-1.0e+16, 1.0e+16),
Z::real(-1.0e+16, 1.0e+16),
Y::real(-1.0e+16, 1.0e+16).

I’m speculating that if attribute_goals was called from the top level in SVs (sorted) order rather than AVs order, the desired output would consistently be produced. (This doesn’t have to be done in term_attvars if anybody is depending on the current order.)

Wouldn’t this be hard to distinguish since variables would normally be numbered in lexical order?

#4

This discussion seems to have died so some motivation to see if a solution can be found:

The top level prints out answers as variable bindings in lexical order. This is natural and easy to understand. Any attributed variables are listed after the variable bindings as residual goals (as generated by attribute_goals) but are not listed in lexical order and include additional “attvars” which don’t appear in the the top level goal, but are referenced by other attvars. Presumably they are generated in the order in which the attvar tree (or graph) is walked, but the end result appears to be quite random to the end-user.

This is a non-issue for programs which don’t use attributed variables, or even those which do, but end up “resolving” most or all of the residual goals before the answer is generated. A few attvars at the end of the bindings list is no big deal. But if there’s more than that, the ability to easily “read” the answer is impacted quite a bit.

Usually intervals of real numbers, implemented as attvars, are never be resolved due to floating point rounding. The answers to programs using interval arithmetic are usually dominated by these attvars (as opposed to variable bindings). Another answer example: analysis of a simple D.C. circuit (details unimportant)

?- LI=[Is,I1,I2,I3,I4,I5,I6,I7,I8,I9],simpleCircuit(LI),solve(LI).
LI = [Is, 10, I2, I3, I4, I5, I6, I7, I8|...],
I1 = 10,
Is:: 10.8282986...,
I8:: 0.2592087...,
I2:: 0.5690898...,
I5:: 0.2572598...,
I9:: 0.0389787...,
I3:: -0.3118300...,
I4:: 0.5320600...,
I6:: 0.2962385...,
I7:: 0.8282986... ;
false.

The Ix's are intervals with one exception; I1 has be unified with the point value 10. IMO the readability of the answer would be significantly improved if the lexical order of the query was preserved in the answer. The ideal order would be the lexical order independent of whether the original query var is bound to a value or remains an attvar.

How might this be achieved? While the output format of an attvar is determined by the module that defines it (via a call to attribute_goal), the order is determined by the SWIP top level. One simple fix I’ve tested is modifying copy_term/3 to sort the attvars prior to generating the residual goals. While not a pure lexical ordering of the anser (bindings still before residual goals), it’s a big improvement:

?- LI=[Is,I1,I2,I3,I4,I5,I6,I7,I8,I9],simpleCircuit(LI),solve(LI).
LI = [Is, 10, I2, I3, I4, I5, I6, I7, I8, I9],
I1 = 10,
Is:: 10.8282986...,
I2:: 0.5690898...,
I3:: -0.3118300...,
I4:: 0.5320600...,
I5:: 0.2572598...,
I6:: 0.2962385...,
I7:: 0.8282986...,
I8:: 0.2592087...,
I9:: 0.0389787... ;
false.

This is more than acceptable (to me) and seems to have no affect on the dif and clpfd residual goals on simple examples. (It’s hard to imagine how any code could depend on the attvar ordering produced by term_attvars.) Alternatives would be to change term_attvars to produce an ordered list; a small gain in efficiency which probably isn’t worth the trouble. Or to modify the top-level code, which would be an opportunity to output the pure lexical order. My guess is that this would be somewhat more complicated for not a lot of gain.

Any other suggestions for solving my admittedly niche problem?

#5

A lexical ordering throughout is a bit hard as constraints may involve multiple toplevel variables. So, if we define

t(A,B,C) :- dif(A,C).

and call

?- t(A,B,C).

we have B and diff(A,C). What should be the order?

I don’t think there is a need to change copy_term/3. I see no reason to be against the toplevel calling sort/2 on the list produced by copy_term/3.

Anyone who sees a possible problem with that?

#6

Sorting the goals produced by copy_term/3 is quite different than sorting the attvars inside copy_term. In particular it will depend on the structure of the goal constructed by attribute_goals. So I think it’s the list of attvars that must be sorted to match the lexical order of variables in the query. Maybe that can be done at the toplevel but I’m not familiar enough with it to suggest how.

#7

My guess: the lexical order is A,B,C. B is unbound, which isn’t output. A and C both have residual goals and they’re identical. But suppose B was bound to 42. The lexically ordered (by variable) output would be:

dif(A,C) ,
B = 42 ,
dif(A,C) .

It’s up to dif to chose one (A or C), or return two goals (which it doesn’t but it could).

“Verbose” output for an interval arithmetic example:

?- {X*Y+W*Z==1}.
X::real(-1.0Inf, 1.0Inf),
(_18314::real(-1.0Inf, 1.0Inf), {_18314==X*Y, 1==_18314+_18368}),
(_18368::real(-1.0Inf, 1.0Inf), {_18368==W*Z}),
W::real(-1.0Inf, 1.0Inf),
Z::real(-1.0Inf, 1.0Inf),
Y::real(-1.0Inf, 1.0Inf).

Note that the constraints in curly brackets could be “attached” to any of the referenced variables so the implementation of attribute_goals picks one, somewhat aribitrarily. (For everyday use there’s a non-verbose mode which just outputs toplevel query variables with their domains, so this isn’t an issue.)

The point is there’s only one lexical order for the variables and any given constraint involves multiple variables. It’s up to the attribute owner implementation of attribute_goals to choose which variables get associated with which constraint goals.

But, for me, this has a really low priority. The status quo works well other than attvar ordering.

#8

It is an interesting topic. I’m not a fan of repeating constraints, also as some may involve a lot of variables, leading to many copies. I don’t know what to think about interleaving concrete answers and constraints. For your application that seems to make sense, but in general?

Note that you can redefine answer printing by defining

prolog:message(query(QueryResult)) -->

See prolog_message(query(QueryResult)) in boot/messages.pl

I don’t see principal reasons to not sort the attvars in copy_term/3, though variable sorting is a rather strange and unpredictable process. I’m unsure whether your encouraging results are just luck or stable. I’d have to be able to play with the code for that.

#9

Agreed. I was just trying to make the point that a lexical order is defined, but I totally agree you don’t want multiple copies. It’s a separate issue, controlled by the attribute owner, which of many attvars gets to “own” the constraint. For things like dif this may mean there are gaps in the attvar list, like those for unbound variables in the sequence of concrete answers.

But the status quo, i.e., no interleaving of concrete answers and residual goals, is fine (in general).

My reasoning for the sort in copy_term/3 is that it seems to generally do what is needed (simulate the lexical oder of variables in the query) and unlikely to cause any harm since copy_term doesn’t specify that the list of goals is in any particular order. At worst, it’s as good as the current order.

Whether lexical order of variables in the query is reliably the same as sorted variable order is a good question, and, I guess, depends on how the the Prolog parser builds terms. (I worried a bit about garbage collection but concluded it couldn’t “reorder” variables or two successive sorts would not be guaranteed to produce the same result.)

Thanks for the tip; I’ll look into it.

#10

Agree. term_attvars/2 is not random of course. It walks the term top-down/left-right as most predicates that walk over terms. If it encounters an attvar, it descents into the attvar first. If we start with a term G (the initial goal), that is constructed using read/1, the addresses of the variables are typically in lexical order (I guess you can create counter examples using operators). Adding attvars does not change the sorting order of variables (indeed, neither does GC). So, yes, sorting them in copy_term/3 will restore the original lexical order for the toplevel scenario (not in general as constructed terms may not have their variables sorted in lexical order). As it should do no harm (I can think of) otherwise, I’ll push a patch to do so.

Thanks for the input!

#11

Good outcome. Thanks for your support.