#15 non-deterministic value selection during grounding

open
rkaminski
gringo (13)
5
2012-10-21
2011-10-11
Martin Gebser
No

I was asked for a non-deterministic construct to pick an arbitrary value during grounding. The chosen value may serve as a representative for some class of values, and the desired language construct should be understood as a pure grounding feature, making an arbitrary selection without further constraints. Here's an example that illustrates the idea:

{ p(1), p(2) }.
q(X) :- X = #choose[ p(Y) = Y ].

The second rule should have two possible instantiations, and which one we get is "don't care":

a) q(1).
b) q(2).

Observe that the grounder should just pick some value from the (here invented) aggregate #choose and assign the value to a variable. The #choose aggregate itself should never appear in the grounding. In particular, we do not want to check whether atoms (here over the predicate p/1) of the #choose aggregate hold in an answer set. Rather, all such atoms are only "abused" to take candidate values for #choose from their domains.

Note that the desired construct for non-deterministic value selection during grounding isn't supposed to be "sound" in any way. It would be just a pragmatic way to let the grounder do some kind of disambiguation among terms, without the need to encode any particular disambiguation strategy.

Cheers,
Martin

PS: I just pass on a request a got, but do not claim that using #choose would be a clean way to write ASP programs ;-)

Discussion


  • Anonymous
    2011-10-19

    Maybe I misunderstand the request, but can't you accomplish this with this?

    p(1). p(2).
    1 { q(X) : p(X) } 1.

     
  • Martin Gebser
    Martin Gebser
    2011-10-25

    A choice rule like

    1 { q(X) : p(X) } 1.

    represents a "real" constraint, which is handled in an ASP solver. The construct described in my request should instead be evaluated by the grounder. It should pick an arbitrary instantiation from a collection of possibilities, but without passing any information about the remaining possibilities on to the solver. For instance, consider the following program:

    selection(1..3).

    selectable(a;b;c,1).
    selectable(X,N) :- selection(N), selectable(X,N-1), not selected(X,N-1).

    selected(X,N) :- selection(N), X = #choose[ selectable(Y,N) = Y ].

    A possible (simplified) instantiation would be this:

    selection(1). selection(2). selection(3).
    selectable(a,1). selectable(b,1). selectable(c,1).
    selectable(a,2). selectable(c,2).
    selectable(a,3).
    selected(b,1). selected(c,2). selected(a,3).

    Observe that "b", "c", and "a" in facts over selected/2 are arbitrarily picked among the possibilities in selectable/2. The (simplified) instantiation contains only facts, so there is no information anymore that a selection took place. That would be non-determinism in the grounder, whatever it may be good for ;-)

    Regards,
    Martin

     
  • -1'

     
  • 1

     
  • rkaminski
    rkaminski
    2011-12-18

    You could try something in lua for now. (Still I do not think we should pollute the language with such things)

    %{ p(1), p(2) }.
    %q(X) :- X = #choose[ p(Y) = Y ].

    % at the moment you could write it this way

    begin_lua

    chosen = {}
    function choose(tag,x)
    if chosen[tag] == nil then
    chosen[tag] = x
    end
    return chosen[tag]
    end

    function get_chosen(tag)
    if chosen[tag] == nil then
    return {}
    else
    return chosen[tag]
    end
    end

    end_lua.

    { p(1), p(2) }.

    % not quite the above but at least this is clean!
    q(Tag,@choose(Tag,X)) :- p(X), Tag = 0.

    % one way to do this
    % warning: this way there may not be recursion through p and q
    chosen(Tag) :- p(X), _ := @choose(Tag,X), Tag = 1.
    q(Tag,@get_chosen(Tag)) :- { chosen(Tag) }, Tag = 1.