Knowing when a rule almost fires and why it didn't?

Given several rules like this:
scared(Person) :- no_escape(Person), faces_conflict(Person), is_weaker_party(Person).

Is there a way to know when a rule almost fires during a search and why it didn’t fire? For example, if “almost” is defined as all prerequisites except one, the above rule has three almost fired possibilities:

  1. Person would have been scared if there was no escape.
  2. Person would have been scared if he/she faced a conflict.
  3. Person would have been scared if he/she was the weaker party.

Ideally, I’d like to write a single rule to calculate these almost fires, returning an almost with the relevant rule head, a list of true prerequisites and a list of false prerequisites (in the case described just one):
almost(Rulehead,True_prereq[],False_prereq[]) :- I have no idea what to write here.

Could such a rule be referred to as a higher-order rule since it is a rule about rules?

You’d need a meta interpreter (Prolog in Prolog). Simple ones can be found everywhere. One that can do the whole lot (notably cuts) are harder to write, but can be found.

Depending on your task you may also consider s(CASP). s(CASP) handles constructive negation and explanations, so if X is false you can ask for not(X) and look at the explanation. s(CASP) also provides abductive reasoning. This allows you to define you do not know the truth of some literal and it will tell you that the original goal is true if this literal is true/false. s(CASP) is way slower than Prolog though.

Finally, you could generate variations of your program or assumed knowledge about the world and see which ones succeed/fail.

1 Like

How about something like:

goals_succeed_count([], 0).
goals_succeed_count([H|T], Count) :-
    (call(H) -> Inc = 1 ; Inc = 0),
    goals_succeed_count(T, Count0),
    Count is Count0 + Inc.
scared(Person, Level) :-
    goals_succeed_count([no_escape(Person), faces_conflict(Person), is_weaker_party(Person)], Count),
    ( Count >= 3 -> Level = scared
    ; Count = 2 -> Level = almost
    ; Level = not_scared ).

That goals_succeed_count could be extended to provide lists of the succeeding and failing goals.

At least one problem with this is that (call(H) -> prunes the choice points of H. You can probably instrument goals to find “how far it got” in a conjunction using e.g., global variables. It remains a bit tricky though. It is easier to use such instrumentation to obtain the proof tree for a successful derivation.

s(CASP) creates a dual rule, basically by applying De Morgan’s law to a predicate. That allows it to create a proof why (and when) something is not provable.

1 Like

Use *-> instead?

Thank you everyone. @brebs , I understand the intent of your code, but not the details. So, @jan, I don’t understand why call(H) prunes the choice points of H or, @peter.ludemann , how *-> might fix the problem. I’ve never seen *-> syntax. How is that wildcard (*) different from a logic variable? I’m also looking into s(CASP) & Clingo, though I’m not sure if the latter is relevant.

call(H) does not prune choicepoints of H. ->/2 prunes choicepoints, and *->/2 does not. * is not a wildcard here. Rather, *-> is a single operator that’s like -> except for not pruning choicepoints.

To be more explicit:
A -> B calls A, discards any choices in A, then decides what to do about B based on whether A passes or fails. Backtracking thus will never return to A because alternatives have been discarded.

A *-> B calls A, keeps any choices in A, then decides what to do about B based on whether A passes or fails. If A passes and B fails, backtracking will back into A looking for another solution.

1 Like

@abaljeu , thank you. I need to explore this topic more.

@jan , I’ve started to experiment with s(CASP). Are you familiar at all with Clingo, which includes a (grounded) version of CASP? I ask because there is some evidence that Clingo can be compiled down to a shared library that I could embed in an application. I’d be very surprised if Ciao Prolog, which s(CASP) depends upon, can compile down this way, since it appears to only run on flavors of Unix–I had to use the Windows Subsystem for Linux to get it working on my computer.

Yes. It is a quite different beast. I don’t think it will be any good for your original problem. It is good for many problems s(CASP) is not good for :slight_smile:

I don’t know the details of the portability for Ciao. s(CASP) has been ported to SWI-Prolog. The port is actively maintained. You find it at GitHub - JanWielemaker/sCASP: top-down interpreter for ASP programs with constraints. Eventually it is planned to become a standard SWI-Prolog package.

Thanks @jan. The problem described in my post that started this thread was part of an ad-hoc solution to explainability. s(CASP) has built-in tools to help with explaining both why and why not in human-readable language (just like you said). Perhaps this is accomplished with a meta interpreter? If not, that is OK because my primary goal is explainability. However, if I can’t embed ciao’s s(CASP), then I’m in the same boat as with SWI-Prolog. I would have selected SWI-Prolog long ago for this project if not for my desire to create a self-contained app. As for SWI-Prolog’s s(CASP) implementation, I remember reading a post on this forum that suggested the explanations in the ciao version were clearer. However, I cannot seem to locate that post now. Did I imagine it? If all else fails, I can either try @brebs approach in a version of Prolog I can embed or switch to a server/client architecture–about which I know nothing

You could say so. s(CASP) implements a different resolution technique than Prolog based in the ASP stable model semantics. Unlike e.g. Clingo, it does so using a top-down process (like Prolog SLD resolution) which results in a proof tree. Clingo grounds the program and uses a SAT solver to find models (simplified). That finds models, but it is hard to provide an explanation.

We redesigned the explanation mechanism. That has caused some regression. That will be addressed in the coming months. The main idea is to introduce an intermediate step between the hard to interpret s(CASP) solver data and the human explanation. That allows machines to reason about the explanation and rewrite the explanation, for example by rewriting commonly reappearing low level patterns to more abstract explanations.

We have hinted at several possibilities if I recall correctly. Roughly embed the SWI-Prolog shared object or using a client-server architecture with the Prolog server either locally or on some server. Porting s(CASP) to a very minimal Prolog system is probably possible, but unlikely to make you happy. Note that the s(CASP) reasoning is quite involved. It is pretty easy to make it really slow on small problems. It takes time to learn how to use it :slight_smile:


Here is goals_succeed_count, extended with the lists of successful and failed goals (and with *->/2 ):

goals_succeed_count([], 0, [], []).
goals_succeed_count([H|T], Count, LstSucc, LstFail) :-
    (call(H) *->
        Inc = 1,
        LstSucc = [H|LstSucc0],
        LstFail = LstFail0
    ;   Inc = 0,
        LstSucc = LstSucc0,
        LstFail = [H|LstFail0]
    goals_succeed_count(T, Count0, LstSucc0, LstFail0),
    Count is Count0 + Inc.
1 Like

Thanks @brebs !

@Jan, I may owe you an apology. My initial goal (obsession?) was to identify a Prolog-like language written in C# or otherwise easily embeddable in a C# application. I’ve since come to understand the importance of a large and friendly user community like we have here with SWI-Prolog, especially for a lone developer like me. I’ve also come to accept that I may need to learn to embed C or C++ code, adopt a client/server architecture, or even leave C# entirely to find the right tools. So, if you previously proposed embedding SWI-Prolog–I may not have been ready to listen at that time. I’m sorry for that. Can the BSD-licensed core (./configure --without-lgpl) run the Apache-licensed sCASP? There are no licensing conflicts between these, right? LGPL components are likely an option, too. I was also thinking about the WASM port, possibly with a non-web embedding.

No reason to be sorry. The only minor thing is that SWI-Prolog is not in C# and will most likely never be in C# (no clue whether it is easy to make a large C code base compile under C#). So, as long C# only is your target we can do nothing for you. That seems to have changed. If you want a single language native executable with Prolog, C and C++ are the obvious choices. JavaScript could work with the WASM version of SWI-Prolog. That version is still a demonstrator though and anyway is significantly slower (~3 times) and limited, surely as long as there is no 64-bit WASM. Also, C# can use native shared objects, no?

I should update the license page as configure is replaced by CMake since. Anyway. Not if you want to use (numerical) constraints. s(CASP) constrains are based on library(clpq) (constraints over rational numbers) and rational numbers are provided by libgmp from GNU, LGPL thus. The only other GNU library in the default system is library(readline) which provides commandline editing for POSIX systems (and has a replacement based on BSD libedit).

LGPL should be fine, provided users are capable of replacing the LGPL component (possibly with some effort).

AFAIK there is no sensible alternative to the GMP library when it comes to comprehensive support of unbounded integers and rational numbers. Especially not when performance is an issue (won’t matter for s(CASP)). There have been projects aiming at a source and even binary compatibility under a permissive license. Last time I checked (couple of years ago) they were not yet very promising.

There is

Windows InteropServices for libswipl.dll

but as the topic notes the code is not production quality. If InteropServices, API wrappers, etc. are not in your regular vocabulary then don’t consider this, it is a very deep rabbit hole because you might get some early positive results but then run into a memory leak bug or something and no one will be around to help.

Also this will get you only part of the way there, you still have to write the interop code for the other things you wish to call.

I don’t know exactly what you mean by “native shared objects”. I know some C++ code can compile down to a dynamic link library (DLL as opposed to an EXE file). Then the C# application accesses those classes and methods directly. It is also possible to call C functions from C# but I’m less familiar with this approach.

I mean exactly that. SWI-Prolog ships as libswipl.dll (.so/.dylib/…, depending on the platform) with one or two wrappers, swipl[.exe] and odptionally swipl-win[.exe]. There is a C# wrapper for using libswipl.dll. No clue how good or complete it is.

@jan, this is very promising! I’ll check out the C# wrapper.