Meta domain predicates and addons

[MaxOstrowski]

Proposition Domain Predicate

I think it would be helpful to have a meta domain predicate.
Given the following program (example taken from here)

a(X) :- b(X,Y), c(Y).
{d(X)} :- b(X,Y), c(Y).
e(X) :- a(X).
{f(X)} :- d(X), a(X).
{g(X)} :- d(X), a(Y), X <= Y.
h(a(X), X+1, 42) :- g(X), not f(X).

it can be sometimes hard and cumbersome to compute the domain of a predicate, e.g. the possible value combinations that are used in grounding. (A domain is always an over approximation of the values that actually occur in answer sets)
Computing the domain for h/3 manually could look like:

dom_d(X) :- b(X,Y); c(Y).",
dom_f(X) :- dom_d(X); a(X).",
dom_g(X) :- dom_d(X); a(Y); X <= Y.",
dom_h(a(X),(X+1),42) :- dom_g(X); not dom_f(X).

It would be much nicer to be able to access the information that is already stored in gringo directly with a construct like:
#domain(h/3, X,Y,Z) so in a logic program you can write something like:

{ fail(X,Y,Z) } :- #domain(h, X,Y,Z), not foo(X).

Also the manual example shown could be wrong if the instance contains a fact like h(1,2,3). In this case only the #domain predicate would give the correct combinations.

Limitations

Of course this new construct is not allowed to be derived and only to be used in the body and conditions.
Furthermore an error might be raised if it is used in a cyclic definition, although I'm not sure if this is strictly necessary (but could ease implementation):

p(X+1) :- #domain(p,X). 

Proposition Domain Ordering

While the domain predicate can be seen as an ease of life feature, the real advantage would come with additional features that can not be achieved with a manual translation (within the same complexity).
When using chaining rules, sometimes computing and ordering the domain can become the new bottleneck of computation. Given the following example from here

{person(a);person(b)}.
{
skill(a, ("some",1), 3);
skill(a, ("thing",1), 5);
skill(a, ("programming",1..10), 10);
skill(a, ("knitting",1..10), 100);
skill(b, t("cooking",1..10), 10);
skill(b, t("knitting",1..10), 1)
}.
max(P, X) :- X = #max {V, ID : skill(P, ID, V)}, person(P), random(Y).

The domain order for the aggregate can be "manually" computed like this:

__dom_skill(a,("some",1),3).
__dom_skill(a,("thing",1),5).
__dom_skill(a,("programming",(1..10)),10).
__dom_skill(a,("knitting",(1..10)),100).
__dom_skill(b,t("cooking",(1..10)),10).
__dom_skill(b,t("knitting",(1..10)),1).
__dom_person(a).
__dom_person(b).
__dom___max_0_11(V) :- __dom_skill(P,ID,V); __dom_person(P).
__min_0_0__dom___max_0_11(X) :- X = #min { L: __dom___max_0_11(L) }; __dom___max_0_11(_).
__max_0_0__dom___max_0_11(X) :- X = #max { L: __dom___max_0_11(L) }; __dom___max_0_11(_).
__next_0_0__dom___max_0_11(P,N) :- __min_0_0__dom___max_0_11(P); __dom___max_0_11(N); N > P; not __dom___max_0_11(B): __dom___max_0_11(B), P < B < N.
__next_0_0__dom___max_0_11(P,N) :- __next_0_0__dom___max_0_11(_,P); __dom___max_0_11(N); N > P; not __dom___max_0_11(B): __dom___max_0_11(B), P < B < N.

This is not very efficient and could be improved if the problem knowledge would state that the required domain is continuous. But in the worst case this grounding can be cubic. So it would be nice to have a meta #order predicate for the ordering.
About the syntax I'm not yet sure, as this predicate needs a lot of information:

• domain of which predicate to access
• which position inside the predicate do I want to order, e.g. given foo/2=foo(P,X) I want an ordering for X (position 1)
• how to bind the other positions inside foo, e.g. P
• how to return the ordered domain

Maybe one way to achieve this could be a syntax like:
(Prev, Next) = #order(foo,P,*)

This would allow for the following program to be written:

{person(a);person(b)}.
{
skill(a, ("some",1), 3);
skill(a, ("thing",1), 5);
skill(a, ("programming",1..10), 10);
skill(a, ("knitting",1..10), 100);
skill(b, t("cooking",1..10), 10);
skill(b, t("knitting",1..10), 1)
}.
%%% max(P, X) :- X = #max {V, ID : skill(P, ID, V)}, person(P).
foo(P,V) :- #domain(skill/3, P, ID, V), #domain(person, P).
chain(P,V) :- skill(P,ID,V); person(P).
chain(P,PREV) :- chain(P,NEXT); (PREV, NEXT) = #order(foo,P,*).
max(P,PREV) :- chain(P,PREV); not chain(P,__NEXT): (PREV, NEXT) = #order(foo,P,*).
max(P,#inf) :-  X = #min { L: #domain(foo, P, L) }; #domain(foo, P, _), not chain(P,X); person(P).

which should be superior to all other possibilities currently available for clingo to express this problem.

Limitations

• Only one * should be used inside the predicate, although maybe ordering of tuples could be interesting ?
• the same limitations than for the #domain predicate are in order, as it directly uses its functionality

[rkaminsk]

This are actually things I already thought about. The reason why there is no #dom or #domain yet is because there is no way to give it a clean semantics. But since it popped up in quite some applications, some way to do this (with a big warning) should be added.

I also thought about sorting. On way to sort in ASP is writing:

d(1..10).
chain(X,Z) :- d(X), d(Z), X<Z, not X<Y<Z: d(Y).

My idea was to introduce an aggregate that has the same meaning as the body of the rule defining chain/2:

d(1..10).
chain(X,Y) :- (X,Y) = #sort { Z: d(Z) }.

If you want to apply it to the domain of a predicate, you would have to write something like

5 { d(1..10) }.
chain(X,Y) :- (X,Y) = #sort { Z: #dom d(Z) }.

[MaxOstrowski]

I definitely like the aggregate style of #sort statement. ❤️
Maybe dom could also use a similar syntax.

{ fail(X,Y,Z) } :- (Y,Z) = #dom { Y,Z : h(X,Y,Z), not foo(X) }.

No new syntax would need to be introduced. Just more aggregates.

Btw, this still does not solve the problem/need of nested aggregates. 😉

[rkaminsk]

We could also high jack externals in a similar fashion to what Javier is proposing below:

#external dom(X) : p(X). [fact]

Like this, there would no new keywords. Just an additional external type. It even makes a little sense.

[javier-romero]

I agree that it would be nice to have those features.

For now, one hack that works for computing the domain of a predicate is the following.

In the example:

a(X) :- b(X,Y), c(Y).
{d(X)} :- b(X,Y), c(Y).
e(X) :- a(X).
{f(X)} :- d(X), a(X).
{g(X)} :- d(X), a(Y), X <= Y.
h(a(X), X+1, 42) :- g(X), not f(X).

just write

#external domain(h,A,B,C) : h(A,B,C). [true]
{ fail(X,Y,Z) } :- domain(h,X,Y,Z), not foo(X).

I think this even works with recursion.

Then, to simplify the domain atoms, one may have to use the API to gather the externals and add them as facts.

[rkaminsk]

Just as a warning. This can have a huge performance impact on large programs because externals are not simplified. There are other hacks available that introduce facts. However, they do not work in the recursive case.