Confused thoughts on ASP, WFS, strong negation, and explicit uncertainty

I’ve been trying to wrap my head about how to shoehorn my application/problem into a more “proper” logic programming formulation.

OOAnalyzer is a system of positive and negative rules for various properties. As an example, consider constructor(X) and destructor(X) where both are closed over the atoms m1, m2, m3, m4. There are conditions under which we know constructor(X) must be true. There are conditions under which we know constructor(X) cannot be true. But there are also conditions under which constructor(X) might be true.

There are also global constraints. For example, constructor(X) and destructor(X) cannot both be true.

Ideally, we’d like to know for each X, is constructor(X) and destructor(X) definitely true, definitely false, or ambiguous?

For example, let’s say we know constructor(m1), destructor(m2), maybe constructor(m3), maybe destructor(m3), and maybe constructor(m4). We also know the constraints: not((constructor(M), destructor(M)) (a method cannot be both a constructor or destructor), and constructor(m3) implies not(constructor(m4)).

Ideally, I’d like to know:

  • constructor(m1)
  • destructor(m2)
  • constructor(m3): maybe
  • destructor(m3): maybe
  • constructor(m4): maybe

It seems like I need the following to describe my problem:

  • Strong negation
  • Constraints (the ability to specify constraints seems like it implies the ability to specify strong negation)
  • Explicit uncertainty

Strong negation and constraints are present in ASP. Explicit uncertainty (at least how I am thinking about it) is present in WFS.

This is mostly just rambling, but I guess I’ll throw out a few specific questions:

Is there a way to express explicit uncertainty in ASP? Like undefined/0 in WFS?

Is there a way to incorporate strong negation into WFS or regular prolog code?

You should check s(CASP), maybe a good fit for your use case.
Not a light reading, anyway…
I hope it will not increase too much the your entropy :slight_smile:
My hint, start with News -- s(CASP) + SWI-Prolog = 🔥, Jason’ spell and his use case are both interesting.

1 Like

I recently became aware of s(CASP) and ASP, which is why I’ve been trying to reconcile how to encode uncertainty in it. I’m certainly missing some basic understanding, but I can’t quite figure out what it is.

I’ve been working through a few ASP examples and I’ve seen the following a few times:

move(T, P1, P2) :-
    not negmove(T, P1, P2).
negmove(T, P1, P2) :-
    not move(T, P1, P2).

This appears to introduce move/3 as a boolean property. So perhaps that is what I need to do for the “maybe” cases.

Before you get too enthusiastic about s(CASP) :slight_smile: : yes, it can do interesting reasoning. But … It doesn’t combine with many Prolog built-ins and it scales pretty poorly at the moment. As is, it is notably interesting to reason about human created rule sets such as found in legal and medical domains. These problems are typically small in computer terms and s(CASP) provides nice properties such as a justification, dealing with default reasoning, abductive reasoning, etc.

As much as I know about your problem, it could be interesting to reason about small sub-problems.

1 Like

This is disappointing, but very useful to know.

These are interesting references. I wasn’t familiar with either, but both seem related to OOAnalyzer’s reasoning. We often talk about assuming things unless there is any evidence to the contrary, which sounds like default reasoning. It also sounds a bit like abductive reasoning, in that we’re trying to find an explanation for the properties that we can observe.

This quote from Abductive logic programming - Wikipedia also reminds me of OOAnalyzer…

Once an explanation has been chosen, then this becomes part of the theory, which can be used to draw new conclusions. The explanation and more generally these new conclusions form the solution of the problem.

If you know of any s(CASP) examples for these, I’d appreciate a pointer. I’ve been working through the examples but it’s hard to make sense of some of them.

This is quite a nice resource explaining ASP and various ways of thinking about reasoning and how to encode them:

2 Likes

That looks worthy of being a topic in the Nice to Know category.

1 Like

Hi :slight_smile:

For reasoning with strong negation, uncertainty and missing information I have found a combination of CLP(R) and meta interpreters very powerful. Not sure though whether such an approach benefits your problem or whether something like s(CASP) is better.

Here is an example with output (numbers, underscores and Xs represent probabilities):

:-include('theoryToolbox2.pl').
cond1(m1, 1).
cond1(m2, 0).
cond2(m1, 1).
cond2(m2, 1).
cond3(m1, _).
cond3(m2, _).

itsa(constructor, M, X1):- cond1(M, X2), cond2(M, X3), {X1 = X2 * X3}.
itsa(destructor, M, X1):- cond3(M, X1).

what:- itsa(constructor, M, X1), itsa(destructor, M, X2), {X1 + X2 = 1}.

q:- prove(what, [], R), showProof(R, color).

Running ?-q. yields:

PROOF

what ⇐
     itsa(constructor,m1,1.000) ⇐
          cond1(m1,1) ⇐ true
          cond2(m1,1) ⇐ true
          {1.000=1*1} ⇐ true
     itsa(destructor,m1,0.000) ⇐
          cond3(m1,0.000) ⇐ true
     {1.000+0.000=1} ⇐ true
true ;

PROOF

what ⇐
     itsa(constructor,m2,0.000) ⇐
          cond1(m2,0) ⇐ true
          cond2(m2,1) ⇐ true
          {0.000=0*1} ⇐ true
     itsa(destructor,m2,1.000) ⇐
          cond3(m2,1.000) ⇐ true
     {0.000+1.000=1} ⇐ true
true ;
false.

Note that unknown probability is represented as an underscore (anonymous variable). Even if the probability of cond3 for m2 is unknown, the program can figure out that m2 has to be a destructor (because constructor and destructor are mutually exclusive).

CLP systems such as CLP(R), CLP(FD), CLP(BNR) are really powerful because they can be used bidirectionally and with missing information in some cases.

The example above uses prove/3 which is a meta interpreter that generates a proof tree. More info about this predicate is here. Another great source of info about meta interpreters is Markus Triska’s page.

And here are some links to CLP(R), CLP(FD), and CLP(BNR).

Good luck!

/JCR

2 Likes

There are a lot of interesting ideas here, thanks! I’ll try to unpack some of them explicitly (mostly for my own understanding).

  • Explicitly representing confidence. Instead of constructor(Method), you explicitly represent confidence with constructor(Method, Probability). Obviously if the Probability is unbound, our confidence is unknown.
  • My colleague will like the idea of using probability. He always advocated for rules to have confidence levels. But I could not figure out how to integrate this idea well.
  • Using constraints. Our problem does have a lot of natural constraints. The example that a method cannot be a constructor and a destructor is one, but there are many. At the moment, these constraints are implemented as a check at the end of the reasoning process. I suppose the advantages of using actual constraints are that they actually become part of the reasoning process itself. For example, if we have the constraint constructor(M, CTruth), destructor(M, DTruth), CTruth xor DTruth, then proving constructor(M, true) or constructor(M, 1.0) would immediately establish destructor(M, false). Whereas at the moment we actually need explicitly written rules for these kind of things.

Thoughts on constraints

I really appreciate the small example. I had looked at constraints before, particular at clp(b). I tried to convert your example to clp(b) and it did not go well. It seems to me that clp(b) and clp(fd) have a radically different API than clp(r) in that clp(r) lets you add constraints locally using {}, but clp(b) and clp(fd) require you to accumulate all constraints and explicitly solve them. The latter is actually very disappointing and doesn’t seem like it integrates with prolog all that well. Might as well integrate with z3 or something if you’re going to do that?

The documentation for clp(fd) even says:

Using CLP(FD) constraints to solve combinatorial tasks typically consists of two phases:

  1. Modeling. In this phase, all relevant constraints are stated.
  2. Search. In this phase, enumeration predicates are used to search for concrete solutions.

Although it makes it sound like this is optional, the behavior is weird.

See this small example: SWISH -- SWI-Prolog for SHaring The first query constrains Y to 0 as expected. But the second does not. Huh? It seems like the constraint is added to the variable in the call to sat/1, but doesn’t actually unify with the argument of constructor/2. When we talk about bidirectionality, I would expect the second example to constrain Y to 0.

So maybe clp(b) really doesn’t have bidirectionality?

Glad to be able to help!

I tried this with clp(fd):

:- use_module(library(clpfd)).

cond1(m1, 1).
cond1(m2, 0).
cond2(m1, 1).
cond2(m2, 1).
cond3(m1, _).
cond3(m2, _).

itsa(constructor, M, X1):- cond1(M, X2), cond2(M, X3), X1 #= X2 * X3.
itsa(destructor, M, X1):- cond3(M, X1).

With the query

?-itsa(constructor, M, X1), itsa(destructor, M, X2), X1 + X2 #= 1.

I get the expected results.

Not sure, but should the example queries in your SWISH code be like this instead (reversing the order of constructor and destructor)?

?- constructor(m2, X), destructor(m2, Y), sat(X#Y).
?- check(m2), constructor(m2, X), destructor(m2, Y).

With this i get Y = 0 in both cases.

I don’t know so much about Z3. I have heard of it though :slight_smile:

1 Like

Are you aware of Constraint Handling Rules (CHR)?

(intro)

Constraint Handling Rules (CHR) is a committed-choice rule-based language embedded in Prolog. It is designed for writing constraint solvers and is particularly useful for providing application-specific constraints. It has been used in many kinds of applications, like scheduling, model checking, abduction, and type checking, among many others.

Again I have no practical experience using it just noting it for the record.

Yes, but no binding for X.

Let me try my clpb example in clpfd.

Same behavior: SWISH -- SWI-Prolog for SHaring

Here’s a further simplified example: SWISH -- SWI-Prolog for SHaring

Your clpfd example works (I think) because the constraints are in the query.

I am aware of its existence, but I thought it was more for creating constraint solvers like clp(X).

Hm, not sure why this happens…

Glad it’s just not me :wink:

I don’t know much about this problem domain, so my thoughts are probably equally confused. As you quoted clp(fd):

the first step is modelling, and your “model” is a bit unclear to me. You say:

From a CLP perspective (which may or may not be relevant) the rules may be modelled by constraints on logic variables - any unification of those variables are subject to those rules. If a “property” value is “uncertain”, its associated logic variable just hasn’t been unified (yet).

Prolog atoms themselves don’t have properties as you’ve defined. But you could define “objects” as Prolog terms with an argument representing each property, e.g., obj(ID,Cons,Dest) where ID is a member of the set [m1,m2,m3,m4] and Cons and Dest are the “constructor” and “destructor” properties.

So how might the latter properties be modelled in a CLP? That depends on the CLP’s “domain of discourse”. Using CLP(BNR), I would choose a boolean variable (constrained to be 0 or 1, so a predicate to define one of these objects and constrain the properties such that only one of constructor/destructor properties could be set, might look like:

obj(ID, obj(ID,Cons,Dest)) :-
	[Cons,Dest]::boolean,
	{Cons == ~Dest}.

If I add an accessor predicate for isolating the properties by name and another predicate for setting one of the properties to true :

property(constructor, obj(_,C,_), C).
property(destructor,  obj(_,_,D), D).

is_true(Prop, Obj) :- property(Prop,Obj,1).

I end up with a simple program which can model instances of such systems, possibly adding new constraints between object instances (like constructor(m3) implies not(constructor(m4)). Basic system with objects m1, m2, m3, m4:

?- obj(m1,M1), obj(m2,M2), obj(m3,M3), obj(m4,M4).
M1 = obj(m1, _A, _B),
M2 = obj(m2, _C, _D),
M3 = obj(m3, _E, _F),
M4 = obj(m4, _G, _H),
_A::boolean,
_B::boolean,
_C::boolean,
_D::boolean,
_E::boolean,
_F::boolean,
_G::boolean,
_H::boolean.

Note all the constructor/destructor properties have “uncertain” values. Now specify m1 is a constructor and m2 is a destructor:

?- obj(m1,M1), obj(m2,M2), obj(m3,M3), obj(m4,M4), 
is_true(constructor,M1), is_true(destructor,M2).
M1 = obj(m1, 1, 0),
M2 = obj(m2, 0, 1),
M3 = obj(m3, _A, _B),
M4 = obj(m4, _C, _D),
_A::boolean,
_B::boolean,
_C::boolean,
_D::boolean.

Now m1 and m2 have been defined but m3 and m4 are still uncertian. Now add the constraint that ‘m3’ being a constructor implies that m4 is not a constructor:

?-obj(m1,M1), obj(m2,M2), obj(m3,M3), obj(m4,M4),
is_true(constructor,M1), is_true(destructor,M2),
property(constructor,M3,C3), property(constructor,M4,C4), {C3 -> ~C4}.
M1 = obj(m1, 1, 0),
M2 = obj(m2, 0, 1),
M3 = obj(m3, C3, _A),
M4 = obj(m4, C4, _B),
C3::boolean,
_A::boolean,
C4::boolean,
_B::boolean. 

The state of m3 and m4 is still uncertain, until additional information is added, e.g., set m3 to be constructor.

?- obj(m1,M1), obj(m2,M2), obj(m3,M3), obj(m4,M4),
is_true(constructor,M1),is_true(destructor,M2),
property(constructor,M3,C3),property(constructor,M4,C4),{C3 -> ~C4}, 
is_true(constructor,M3).
M1 = obj(m1, 1, 0),
M2 = obj(m2, 0, 1),
M3 = obj(m3, 1, 0),
M4 = obj(m4, 0, 1),
C3 = 1,
C4 = 0.

So that’s how I would model your simple example using a CLP. The next question is, given such a model, what are the questions you want to ask?

Hope this might be useful for your bigger problem and not just more “rambling” on my part.

2 Likes

Thank you for the ideas. I’ll play around with this and CLP(BNR). I think part of the reason my “model” is confusing is that it’s not totally a constraint problem, but it does have some constraints. So I want the regular prolog reasoning to interact with the constraints.

One other thing is that I am not always making queries from the top level, so I would like to have my constraints be global. I can’t tell if your solution will allow that or not, but I’ll give it a shot.

For this simple example program, CLP(BNR) doesn’t have any particular advantage over clp(fd) or (I suspect) clp(b). It’s just that I’m not as familiar with those.

Based on your other comments, I don’t think we’re using the term constraint in quite the same way, but I won’t speculate on what the difference may be. I was just attempting to model your simple example in a CLP; not trying to turn it into a “constraint problem”. CLP is just a tool in the larger Prolog LP framework. Maybe’s it’s useful to you in the bigger picture; maybe not.

I’m also not sure what “global constraint” means. Prolog constraints are attached to logic variables (see SWI-Prolog -- Constraint Logic Programming) - they are in effect wherever the variable is “visible” during program execution.