I’m using: SWI-Prolog version 9.3.20-1-g1ded30f09
I want the code to:
generate alternatives in the following order
D = C, C = T, T = ;
D = C, C = T, T = [1] ;
D = [1], C = [0], T = [2] ;
D = C, C = [0], T = [3] ;
D = [0], C = [1], T = [4] ;
D = C, C = T, T = [1, 1]
…
But what I’m getting is:
D = C, C = T, T = ;
D = C, C = T, T = [1] ;
D = C, C = T, T = [1, 1] ;
D = C, C = T, T = [1, 1, 1] ;
D = C, C = T, T = [1, 1, 1, 1]
…
I think I understand on the theoretical level the issue (DFS) and what’s to be done (BFS, or other complete strategy), but even after reading on the topic I’m still quite mystified as to how to do that in practice. The example that I linked uses a trivial palindrome predicate to demonstrate. How to extend that to my use case ?
Ok, now I am even more mystified… Why does constraining the lists to have the same lengths change the order ? Especially since in my original version yielding only 1s, lists are also all the same lengths ??
@brebs@Boris thank you very much for your kind answers !
That looks like L1 will only ever be an empty list - this is because the alternatives for L2 are being iterated through first, and L2 can be infinitely long.
As evidence, here is L1 being iterated through, when L2 is constrained:
@j4n_bur53 For the sake of clarity: even though I am not educated in math, logic or computer science beyond highschool level, I do understand what depth-first and breadth-first search are.
I should have clarified as such: I’m having technical difficulties switching away from the default Prolog search strategy beyond trivial examples, such as the one from the linked book. Having to deal with the default search while trying to implement an alternative confuses me, although I could certainly do it from scratch in a procedural or functional language. Btw, I’m not looking into Prolog for modern AI. I’m trying to make a constrained sampler with model counting features for a mathematically rather trivial problem.
I’ve been having a similar problem but with multiclauses for BFS.
I was working on a meta interpreter because I want to do SLD-resolution for sets (the proper mathematical relational kind of sets, not the pseudo-list sets swipl has)
I’ve attempted around 20 times (not an exaggeration) to make this handle multiclausal bodies. Tried examples from Simply Logical which was doing something identical. However, because of the way conjunctions and disjunctions work and are structured things become pretty tangled almost immediately, so something like intersection doesn’t work. I wonder if anyone can advise on this
The problem with DFS in this case would be that it will infinitely recur on the union case since that’s a recursive definition on elem. Iterative deepening doesn’t necessarily solve my issue with conjunctions and disjunctions being annoying due to the nature of their data structures and having to still store all combinations, and it’s not clear how each branch of the disjunction/conjunction should be traversed (together? first one first? Do I need subqueues? Should I be thinking about A*?) I’ve tried a lot of different solutions but generally something always ends up getting in the way. Unfortunately I lost some code or I’d show you some of the other attempts where I tried IDDFS and still had similar issues whilst trying to deal with multiclauses. The end goal here is really I want to create a plugin that will allow the user to customise search. Tail recursive DFS and tail recursive BFS are very similar cases so I think I should be able to do that kind of thing.
elem(z, 5) is a predicate that states 5 is an element of the set with the name z. Therefore both together state that 5 and 6 are both elements of z. Another way to do it (as I’ve been doing in Logtalk) is the OOP style where-in one would use single as a constructor for single-valued sets and then combine them together by means of set operations. I’ve opted not to do that here due to wanting to take advantage of the knowledge base to ‘load in’ base sets in the simplest way possible.
Going off into infinity in 1 code path, similar to append(L1, L2, L3).
Symmetry would add unwanted duplicates, e.g. 5 and 6 as answers vs 6 and 5.
A tree structure will just grow to include pointless duplicates
This feels more useful:
set_elems(x, [4]).
set_elems(y, [5]).
set_elems(z, [5, 6]).
% Prevents duplicates, e.g. 5 in union([y, z])
set_action_elem_distinct(A, E) :-
distinct([A, E], set_action_elem(A, E)).
set_action_elem(raw(N), E) :-
set_elems(N, Es),
member(E, Es).
set_action_elem(union(Ks), E) :-
findall(N-Es, set_elems(N, Es), SEs),
% Ensure at least 2 elements
SEsSel = [_, _|_],
selects_from_in_order(SEsSel, SEs),
pairs_keys_values(SEsSel, Ks, Vs),
member(V, Vs),
member(E, V).
set_action_elem(intersect(Ks), E) :-
findall(N-Es, set_elems(N, Es), SEs),
% Ensure at least 2 elements
SEsSel = [_, _|_],
selects_from_in_order(SEsSel, SEs),
pairs_keys_values(SEsSel, Ks, Vs),
Vs = [HVs|TVs],
member(E, HVs),
% Ensure is member of the remainder of the sets also
maplist(member(E), TVs).
selects_from_in_order([], Lst) :-
selects_from_in_order_lst_(Lst).
selects_from_in_order([H|T], Lst) :-
select_forward(H, Lst, Lst0),
selects_from_in_order(T, Lst0).
selects_from_in_order_lst_([]).
selects_from_in_order_lst_([_|_]).
select_forward(E, [H|T], F) :-
select_forward_(T, H, E, F).
select_forward_(T, H, H, T).
select_forward_([H|T], _, E, F) :-
select_forward_(T, H, E, F).
Result:
?- set_action_elem_distinct(A, E).
A = raw(x),
E = 4 ;
A = raw(y),
E = 5 ;
A = raw(z),
E = 5 ;
A = raw(z),
E = 6 ;
A = union([x, y]),
E = 4 ;
A = union([x, y]),
E = 5 ;
A = union([x, y, z]),
E = 4 ;
A = union([x, y, z]),
E = 5 ;
A = union([x, y, z]),
E = 6 ;
A = union([x, z]),
E = 4 ;
A = union([x, z]),
E = 5 ;
A = union([x, z]),
E = 6 ;
A = union([y, z]),
E = 5 ;
A = union([y, z]),
E = 6 ;
A = intersect([y, z]),
E = 5 ;
false.
Whilst I’m aware that your solution is more practical, it defeats the point of what I’m trying to do, which is reflect how mathematicians actually define sets relationally, accurately, and to illustrate the OOP style. I have no problem with the duplicates since equivalence is a basically impossible problem to solve and would prefer to leave that up to the user. I am also hesitant to use findall etc since I at some point in my proper implementation introduce such sets as ‘evens’ for which you cannot simply ‘find all the elems’. Whilst I appreciate your re-evaluation, I am fine with how I basically implemented sets, I just want to do BFS.
It is order-dependent on inputs, so whilst it certainly behaves better, it’s still not really solving the equivalence issue with sets. Moreover, this will fail under combination. For example, taking the intersection of two sets may yield a completely new set, that can’t then be union’d. I tried to get around this once by using gensyms to do dynamic assertions but well as you can imagine that fails horribly. I appreciate your solution but there are also unacceptable drawbacks.
Yes, that’s deliberate in the code I provided, to prevent “explosion” of combinations. Can use e.g. permutation/2 to “explode” if desired, at some point in the code - example:
?- L = [z, x], permutation(L, P).
L = P, P = [z, x] ;
L = [z, x],
P = [x, z] ;
false.
Yes - but how is that useful? Intersection is a filter on individual elements, and individual elements are already returned. Intersection would not create new element values.
Do you have an example mock-up of how this will all come together and perform a demonstrably useful task?
It’s useful because it returns a brand new set which needs to be represented. If the model we’re talking about here can’t represent those combinations then it’s not really producing sets. There are many cases where one needs to combine intersections and unions to produce new sets, such as in the field of topology, which is just one ‘step’ up from sets conceptually. Moreover, I’m thinking less about the practicality of implementation for producing software, and more about pedagogy regarding mathematics and trying to explore the possibilities of logic programming in general. I want to do BFS for this because I think it would be neat.
Here’s a rough implementation of how I was thinking of doing topologies (from my logtalk version)
There are a lot of issues with this implementation and I’ll either need equivalence or normal forms to solve them anyway, but I’d probably rather do this than rehash prolog’s existing implementation of sets
If we try creating a set containing an infinite amount of even numbers, the program will run out of memory. Instead, we could represent evens as e.g. a term, and possibly involve library(clpfd) - but, the code for sets then becomes problem-specific, rather than as abstract as you’d like.
This is why I’m asking for a mock-up of some useful predicate, which would require set-like activities behind-the-scenes to perform some clearly-useful task. We need the context of a particular problem - to be able to add constraints, to prevent going off into infinity - and the code needs to work as a whole, to achieve that in some reasonably performant way.
