Understanding scasp and wfs

[swi]

@jan

Trying to get my head around the advantages and disadvantages of WFS, ASP and sCASP …

@jan, I was trying to do the same.

So far I find sCASP extremely useful, whereas WFS leaves a lot to be desired. Taking the moth example: “something is a moth if it does not fly during daylight”. Let’s say we have incomplete knowledge. Let’s try to code it with sCASP and WFS:

% First sCASP
:- use_module('../../prolog/scasp/embed').
:- use_module('../../prolog/scasp/human').

% something is a moth if it does not fly during daylight.
%
:- begin_scasp(moth, [moth_scasp/1]).

moth_scasp(X) :- not flies_during_day(X).

flies_during_day(B) :- bird(B).

bird(eagle).
bird(hummingbird).
bird(bluejay).

:- end_scasp.

% Now WFS
moth_wfs(X) :- tnot(flies_during_day_wfs(X)).

:- table flies_during_day_wfs/1.
flies_during_day_wfs(B) :- bird_wfs(B).

bird_wfs(eagle).
bird_wfs(hummingbird).
bird_wfs(bluejay).

Now let’s try it with WFS:

5 ?- moth_wfs(X).
false.

Uhh? This is useless. In WFS negation is not really handled the way a human would expect.

Now let’s look at the beauty of sCASP:

4 ?- moth_scasp(X).
sCASP model: [not bird(X),not flies_during_day(X),moth_scasp(X)],
sCASP justification
   query ←
      moth_scasp(X) ←
         not flies_during_day(X) ←
            not bird(X) ∧
      o_nmr_check,
X ∉ [bluejay,eagle,hummingbird] ;
false.

WOW! It told me X could be a moth if it is not a bluejay or eagle or hummingbird. Much more useful! It uses all the information I gave in the code. Notice the “could be”.

Not only that, but it told me why: because something is a moth if it doesn’t fly during the day. And it also told me that something doesn’t fly during the day if it is not a bird, even though I never said this explicitly in the code

This is quite amazing, and I can see that it solves the negation problem in a satisfactory manner (of course the issue now is performance).

Question
I am trying to figure out what ‘o_nmr_check’ means, could you explain it?

EDIT: just for the sake of completeness, we can add the following line to the scasp code above an it will give us the ‘closed world model’ answer that moth_wfs(X) gives us:

-bird(_).

[jan]

Glad you like it (and stay tuned with he latest version) The difference is of course that tabled Prolog still adheres to the closed world semantics and s(CASP) uses the open world semantics. We can also create programs that have a conflict. Now s(CASP) will tell me “no models” without any clue why. Tabled Prolog with WFS may give a partial answer, claiming some things are true, others are false and for some it cannot tell and marks them as undefined with as annotation the minimal (well, not always minimal) program that tells you why. There is also something left to be desired when it comes to scalability and s(CASP). In part that is just the implementation as a Prolog meta interpreter. I fear there are also more fundamental reasons though.

@swi

I am trying to figure out what ‘o_nmr_check’ means, could you explain it?

Those are the global constraints. They may appear in two ways: as a result from the user adding :- Constraint to the program or as a side effect from negation. There is a nice Best Practices document by the s(CASP) people.

Please keep posting your findings!

[swi]

@jan

The difference is of course that tabled Prolog still adheres to the closed world semantics and s(CASP) uses the open world semantics.

From what I understand you can also make closed world assertions in sCASP.

@jan

We can also create programs that have a conflict. Now s(CASP) will tell me “no models” without any clue why. Tabled Prolog with WFS may give a partial answer,

Yes, I could see this, but I really see it as a major advantage that sCASP can deal with open world and closed world semantics at the same time. Much of human knowledge, when it comes to negation, tends to follow the ‘open world’ semantics.

@jan

There is also something left to be desired when it comes to scalability and s(CASP). In part that is just the implementation as a Prolog meta interpreter. I fear there are also more fundamental reasons though.

hmmm…yes, I do suspect some more fundamental reasons; especially for scalability, because it has to build the negation of the program and this can easily lead to combinatorial explosion.

@jan

There is a nice Best Practices document by the s(CASP) people.

Thanks for pointing this out!

Human justification

By the way, how do you enable the human justification output in embedded sCASP code?
Those #pred directives are very nice to produce human output, but I didn’t figure out how to enable that in embedded code.

[jan]

@swi

how do you enable the human justification output in embedded sCASP code?

That is work in progress. The original implementation made a direct translation of the engine’s stack to the justification. We now have an intermediate representation and I’d like to generate the various justifications using DCGs, just like SWI-Prolog’s message system. As is though, the old translation is still in use for the scasp application and there is no ready to use alternative for the embedded version. I hope that will change soon. I do have some problems dealing with this in a systematic way though. I’d love to have a set of test programs that cover all the basic reasoning patterns and (thus) their explanations. I’m not sure how to get there though

@swi

Those #pred directives are very nice to produce human output, but I didn’t figure out how to enable that in embedded code.

#pred directives work fine in embedded code. As long as there is no human output they are useless though

[swi]

@jan

We now have an intermediate representation and I’d like to generate the various justifications using DCGs, just like SWI-Prolog’s message system.

This is great, it will allow easy multi-language support in the future. Among other things.

@jan

As is though, the old translation is still in use for the scasp application and there is no ready to use alternative for the embedded version. I hope that will change soon. I do have some problems dealing with this in a systematic way though. I’d love to have a set of test programs that cover all the basic reasoning patterns and (thus) their explanations. I’m not sure how to get there though

The way I see embedding sCASP within prolog is summarized by the following sentence: “I want to reason about sCASP programs, their execution and output within prolog”.

We could break this down into an easier conceptual model: what are the inputs and outputs that I want to reason about within prolog?

Inputs:

1. Input #1: the sCASP program itself
   1.1. Input of static sCASP code: I think you solved this nicely using the begin_scasp/end_scasp pair.
   1.2. Input of dynamic sCASP code generated from prolog: there should be some way of adding sCASP clauses programmatically from prolog, there is no way to do this as of now. This will be extremely useful for example to programmatically generate variable domains from prolog facts. We would like to keep homiconicity here too, so that sCASP programs are simply prolog data.
   1.3. Include prolog predicates within sCASP: this may be difficult to do, but it would be useful to be able to call prolog predicates directly from within an sCASP program.

2. Input #2: query of the sCASP program
   2.1. sCASP queries should be just like prolog queries, then we can reason about them using prolog. I think you are already doing this for the most part.

Outputs from the execution of an sCASP query

1. Output #1: variable bindings
2. Output #2: model
3. Output #3: justification
4. Output #4: variable conditions (e.g. X must be different from [A,B,C])

We would like to reason about these outputs within a prolog program. So the question is how do we represent these four outputs in a prolog program? I think we have two options:

Option #1: Use attributed variables to store output

1. binding: we simply bind the variable as in prolog.
2. model, justification and conditions: these could be stored in attributes.

Option #2:

1. binding: we simply bind the variable as in prolog.
2. model and justification: use an extra argument for every sCASP query, which
   contains the model, justification and perhaps even the variable conditions.
3. conditions: use variable attributes for conditions such as
   X ∉ [bluejay,eagle,hummingbird], to allow proper unification in case the variable is bound later within prolog. Store the condition also in the extra argument in #2 to be able to reason about it later, even if X is bound.

I think option #1 is not good, because the attributes dissappear when the variable is bound, since there is no variable anymore.

Option #2 seems reasonable to me; with this option moth_scasp(X) above would become moth_scasp(X,Out). Every (exported?) sCASP predicate would have an extra argument to represent its output. Where Out would be a term similar to scasp(model(M), justification(J), conditions(C)). Then we can reason about the output of an sCASP program within prolog, including testing using plUnIt. ‘J’ in the justification would be the intermediate representation that could be converted to human language using DCGs or we could reason about the Justification within prolog.

These are just some thoughts for now.

[jan]

That pretty accurately describes what I have in mind and what the current status is It is good to see you arrive at pretty much the same results. I’m not sure about calling ordinary Prolog from sCASP. That might be problematic if negation is involved and as negation is typically the reason to consider sCASP it might not be that easy. As for providing the results, I came to this after discussion with Joaquin Arias:

• Bindings are natural in Prolog as you claim too.
• Conditions are the usual Prolog constraints represented by attributes. You can use copy_term/3 to make them explicit.
• The model is accessible as a list of atoms, optionally embedded in not() and -() and is accessible using scasp_model/1 after a successful sCASP result is proven.
• The justification is accessible as the model using scasp_justification/2, where the second argument allows some control about the justification (notably the level of detail). The justification is a Prolog tree justifying each atom of the model. You can inspect that and there shall be several DCGs to turn this Prolog term into text or HTML.

Both the model and justification may contain variables that may share with the bindings and may contain attributes. As the model and justification is stored in a backtrackable global variable (using b_setval/2), all sharing is retained.

[swi]

@jan

That pretty accurately describes what I have in mind and what the current status is It is good to see you arrive at pretty much the same results.

I figured you had thought about all this before I even blinked

@jan

That might be problematic if negation is involved and as negation is typically the reason to consider sCASP it might not be that easy.

ahh…yes, it did cross my mind that calling prolog might be problematic. One of the main use cases I had in mind is to have the ‘facts’, stored in prolog, since prolog is much better suited to communicate with the outside world and establish the facts from network connections, sensors, user input, files, etc.

Perhaps there is a better solution if we can dynamically generate scasp code.

@jan

• Bindings are natural in Prolog as you claim too.
• Conditions are the usual Prolog constraints represented by attributes. You can use copy_term/3 to make them explicit.
• The model is accessible as a list of atoms, optionally embedded in not() and -() and is accessible using scasp_model/1 after a successful sCASP result is proven.
• The justification is accessible as the model using scasp_justification/2, where the second argument allows some control about the justification (notably the level of detail). The justification is a Prolog tree justifying each atom of the model. You can inspect that and there shall be several DCGs to turn this Prolog term into text or HTML.

what advantage did you see for scasp_model(M) and scasp_justification(J,Opts), compared to adding an extra Out argument to the scasp predicates?

If the model and the justification are not used, we can simply have term_expansion that turns moth_scasp(X) into moth_scasp(X,_). The extra Out argument also works with all the shared variables.

The advantage that I see of using moth_scasp(X,Out) is that naturally, in prolog, outputs are modeled as arguments which are part of the predicate, keeping the ‘this is a relation’ mindset for scasp predicates. That is, an scasp predicate establishes a relationship between the model, the justification, the conditions and the other arguments in the predicate. Separating it into scasp_model/1 and scasp_justification/2 breaks this logic programming mindset. What is the advantage of breaking it out into separate predicates?