Aggregation with scasp?

Help!
1

I’m playing around a little with lists and aggregate functions in scasp, and running into problems.

As demonstrated in this swish file, sum_list works fine, but length fails, and bagof fails, both with different permission errors, when run inside the scasp solver. (I ran it locally to make sure I get the same errors, and I do.)

It’s not a problem to re-implement things like length and other aggregations in an scasp-friendly way, if necessary. I tested that with my_length/2 in the file.

I can’t figure out how to replicate the behaviour of findall/3 or bagof/3, or similar predicates that encapsulate the backtracking in a list of bindings.

So if I want to do something like this in s(CASP), how do I do it?

:use_module(library(scasp)).
person(bob).
person(jane).
how_many_people(N) :-
  bagof(P,person(P),Bag),
  length(Bag,N).

?- ? how_many_people(X).
2

You will find it hard to redo those predicates for scasp. Even in prolog they are very tricky. I would suggest you model the problem letting scasp do what it does best: negation and justification, and letting prolog do the rest. Otherwise you will find yourself trying to rebuild prolog within scasp. For example, to get a list of Xs that can’t fly:

:- use_module(library(scasp)).


% SCASP code
% ----------
bird(sam).
bird(tweety).
bird(john).
bird(brokenleg).

penguin(tweety).
wounded_bird(brokenleg).

% penguins and wounded birds are abnormal
ab(X) :- penguin(X).
ab(X) :- wounded_bird(X).

% birds that are not abnormal can fly
flies(X) :- bird(X), not ab(X).

%% Prolog code
%% ------------
non_flying_things(NonFlyingXs) :-
    findall(X, scasp(not flies(X),[]), NonFlyingXs).





?- non_flying_things(X).
X = [_A, tweety, brokenleg],
_A ∉ [brokenleg,john,sam,tweety].

Notice prolog is the one building the list wirh findall/3. In this way you let prolog do what it does best (list manipulation) and scasp do what it does best (negation).

You can even model your problem by interleaving prolog and scasp in different steps letting each do what it does best.

EDIT: By the way, you can use scasp_assert/1, scasp_retract/1 and scasp_retractall/1 within prolog to dynamically build up the facts for the scasp part of your program, for example you could use prolog to get a list of birds from some website using http_get/3 and then assert the facts within scasp using scasp_assert/1. Something like this:

:- use_module(library(scasp)).
% SCASP code
% ----------
:- scasp_dynamic bird/1.

bird(sam).
bird(tweety).
bird(john).
bird(brokenleg).
penguin(tweety).
wounded_bird(brokenleg).

% penguins and wounded birds are abnormal
ab(X) :- penguin(X).
ab(X) :- wounded_bird(X).

% birds that are not abnormal can fly
flies(X) :- bird(X), not ab(X).

%% Prolog code
%% ------------
non_flying_things(NonFlyingXs) :-
    scasp_assert(bird(crow)),
    findall(X, scasp(not flies(X),[]), NonFlyingXs).

?- non_flying_things(X).
X = [_A, tweety, brokenleg],
_A ∉ [brokenleg,crow,john,sam,tweety].

Notice crow was added dynamically using scasp_assert/1, and declared with :- scasp_dynamic ...

1 Like
3

Thanks @swi. Do I understand correctly that this interleaving approach will really only work a) if I know in advance what listifications are going to be used as sub-goals, b) the context in which they will be run (including the relevant constraints at the time, and all the derivable answers for the aggregated query).

I think none of those are true in my use case. I want to be able to do aggregation inside s(CASP), without knowing in advance where or how it is being used, or what elements might be derivable at the time, based on e.g. the constraints in the store.

As much as I might wish it wasn’t so, rebuilding Prolog inside s(CASP), for some small portion of Prolog, may be my best option. But is that even feasible? Or is there something about the way findall is implemented that relies on the Prolog negation style and isn’t available inside s(CASP)?

4

It strikes me that to be able to build a list, you need to use a closed-world assumption that the list is finished if you cannot prove that any more elements belong to it.

I can’t get s(CASP) to do that, because either a) it loops infinitely on one answer trying to find an element not already in the list to add, or b) it returns infinite results as it hypothesizes longer and longer lists.

Which makes me think either a) it’s not possible due to the semantics, or b) this is another instance of the known problems with the forall algorithm.

I’m hoping it’s the latter.

5

I note that in Gopal Gupta’s best practices document he notes that as a workaround, you can use Prolog’s findall, which is exposed. That doesn’t seem to be the case in the SWI-Prolog version. Not sure if it’s true in the Ciao implementation, either.

Is that something that we could make available in the sCASP library as a workaround? pinigng @jan…

6

There are traces of this in the sCASP code. @Xuaco might have some history. AFAIK it didn’t make this into the Ciao implementation and (thus) not in the SWI-Prolog version. That might be related to semantic issues in the presence of constraints, or possibly merely technical issues. SWI-Prolog’s findall/3 can return attributed variables. This still may upset several constraint libraries. I assume the rather simple sCASP inequality will be fine. I’m less sure about arithmetic constraints by clpq.

7

Dear Jan and Jason,
I agree findall/3 is a useful predicate for manipulate list in Prolog and s(CASP). In fact, s(CASP) provides a “built-in” findall/3. However, its current implementation does not distinguish between different models. E.g.:

p :- not q.
q :- not p.

s(1) :- p.
s(2) :- p.
s(3) :- q.

l(L) :- findall(V, s(V), L).

?- l(L).        %% returns L = [1,2,3]
?- p, l(L).     %% returns L = [1,2]

It is important to understand that findall/3 is a 2nd order predicate and therefore care must be taken when integrating it into the semantics of s(CASP).
To use it correctly you have to make sure that there are not multiple models involved and that the call is stratified.

8

Unfortunately findall/3 is not in the SWI-Prolog version of s(SCASP) . Testing with the sample code provided by Xuaco:

$ scasp /tmp/s.pl 
Warning: scasp_predicate `findall/3' does not exist
% Query
?- p,
l(L).
% 861 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 3853349 Lips)
ERROR: No rule matches assoc:get_assoc(l/1,_272,_274,_276,[l([])|_274])
ERROR: In:
[...]
1 Like
9

@jan is it possible to expose findall/3 in the scasp library? The absence is a major obstacle in my use cases. I don’t have lists as a data type, so without findall/3 aggregation is completely impossible. Thanks!

10

I’d be happy to give it a go and try implementing findall/3 for the SWI-Prolog port of s(CASP), but at least to me it is not yet clear what the intended semantics are in the context of s(CASP). If we can get a specification of some sort and/or more test cases for the intended behavior that would help a lot. There is also the question of representation in the justification tree and natural language explanation…

I’ll have a look at the original implementation as a starting point.

11

I had a look. The implementation is indeed in the Ciao version. The associated test was not activated. I am as far as findall/3 working in the stand alone version, giving the same model as Ciao. Added the test case. That is now in master.

But, the “dynamic calling” used for embedding does not work. I pushed one fix already, but somehow it still fails. I don’t have time to look at this today. For @oskardrums, if you want to have a look, this is the test program:

:- use_module(library(scasp)).

validate(L) :-
    findall(X, member(X,L), LL),
    LL = L.

member(X1, [X2|_]) :- X1 #= X2.
member(X, [_|R]) :- member(X, R).

Then this is supposed to give a model, but it simply fails.

 ?- ? validate([1,2,3]).
12

AFAICT the problem lies in predicate_calls/2 in dyncall.pl, where the pushed fix only handled body_calls/2 which is invoked from predicate_calls/2.

Currently we have:

predicate_calls(Head0, PI) :-
    generalise(Head0, M:Head),
    @(clause(Head, Body), M),
    body_calls(Body, M, Callee),
    pi_head(PI, Callee).

This throws if Head = findall(_,_,_), so we should probably add a clause above this one for handling that special case.

EDIT: I’m not sure that’s actually the issue, testing.

EDIT2: That probably wasn’t the issue, sorry for the noise.
it seems that solving for member/2 under findall/3 fails and we get an empty list unified with the third argument of findall/3. Still not sure why though.

13

Could you please give two examples where it is not used properly? e.g. 1) an example where there are multiple models involved, and 2) and example where the call is not stratified. Thanks!

14

I’m happy to announce that findall/3 in s(CASP) now works the same as the Ciao version (as far as I can tell). See https://swish.swi-prolog.org/p/solve_findall.pl for a demo embedded in SWISH.

4 Likes
15

The example above from @Xuaco shows a resulting logically inconsistent model when there are multiple models involved with the findall.

:- use_module(library(scasp)).

p :- not q.
q :- not p.

s(1) :- p.
s(2) :- p.
s(3) :- q.

l(L) :- findall(V, s(V), L).

?- l(L).        %% returns L = [1,2,3]
%?- p, l(L).     %% returns L = [1,2]

Query:

 1 ?- ? l(L).
L = [1, 2, 3],
% s(CASP) model
{ p,           not p,       q,           not q,       l([1,2,3]),  s(1),        s(2),        s(3)
} ;
false.

Notice that p and not p are in the same model, as well as q and not q. This is inconsistent.

The reason is because there are multiple models involved in the
l(L) query. The model where p holds and the model where q holds are both present, but these two models are mutually exclusive and sCASP is not able to handle this with findall.

If instead we do the other query:

2 ?- ? p,l(L).
L = [1, 2],
% s(CASP) model
{ p,         not q,     l([1,2]),  s(1),      s(2)
} ;
false.

Then the model is consistent, because we excluded q by conjunction with p in the query: p, l(L).

I would still like to see an example where findall is inconsistent if the call is not stratified. Anyone?