Applying a predicate to a subset of a list in Prolog: requesting implementation guidance
Change: . Apparently I had an understandable confusion using the terms 1st and 2nd implementations, referencing them in the order they were listed, after I mentioned that the second one, I first tried to implement, so I revised the relevant paragraphs. Sorry for the confusion.
Some motivational prerequisites: I am building a constraint solver in SWI Prolog, and in order to significantly optimize space and time, I built an inverse index on the underlying constraint data structures. Whenever a value is assigned to a "variable" on my system (not a Prolog variable), I want to make sure that the assignment does not make any other constraints unsatisfactory. I have an index from variables to constraints to quickly select constraints to check. At some point, it boils down to applying a try_check / 2 predicate to the given left side (LHS) and to all elements of the right list (RHS_L) whose indices appear in the list (IdxL). Here's my current implementation:
%% FORALL Implementation
try_check_filtered(LHS, IdxL, RHS_L) :-
forall((member(Idx, IdxL), nth0(Idx, RHS_L, RHS)),
try_check(LHS, RHS)).
I also have an earlier implementation that does the same, but takes a second argument at the second position to keep track of the current index of the list (the list of indices is sorted in ascending order):
%% Tail-Recursive Implementation
%%try_check_filtered(+LHS, +Idx, +IdxL, +RHS_L)
try_check_filtered(_LHS, _Idx, [], _RHS_L) :- !. % Stop when index list is empty
try_check_filtered(LHS, Idx, [Idx|Ti], [H|T]) :- !, % If at next index -> check
try_check(LHS, H),
Inext is Idx+1,
try_check_filtered(LHS, Inext, Ti, T).
try_check_filtered(LHS, Idx, IdxL, [_H|T]) :- % If not at next index -> skip
Inext is Idx+1,
try_check_filtered(LHS, Inext, IdxL, T).
try_check_filtered(_LHS, _Idx, _IdxL, []). % Done when at the end of RHS_L
I have two questions:
- Is there a better way to implement this that I cannot think of?
- I was surprised to find that forall's implementation is better than tail-recursive. In my opinion, tail-recursive has linear time dispatch (going down the list once to "call" all the try_checks needed), whereas the forall implementation has quadratic dispatch (linear number of calls to a member, each one calling a different linear call nth0 ). (If you're curious about the performance improvement I've seen in execution that takes ~ 44s, using forall's implementation on tail-recursive while saving about 4 seconds).
It seemed to me that tail recursion optimization was not applied to my tail recursive implementation, forcing multiple copies of lists onto stack frames, thus making it slower. To (hopefully) enable tail recursion optimizations for my tail recursive implementation, I tried to make my try_check / 2 predicate deterministic by adding a slash (!) Right at the end of the rule. It's enough? Does it matter that the try_check / 2 rule has temporary side effects: it asserts some facts, which it clears out before the end, thereby leaving the body of facts unchanged. The performance I reported above was due to the truncation of the try_check / 2 predicate.
Hope I have provided enough information for a constructive discussion. Thanks in advance for your answers!
Edit: Here's a (high-level) implementation of try_check. The whole code is 2600 lines, many of which (probably half) are indirectly used by this check, so it is not possible to post here.
%% try_check_eni(+E1:effect, +E2:effect)
try_check_eni(E1, E2) :-
push_trying,
check_no_try,
( is_non_interfering(E1, E2)
-> (clear_try, pop_trying)
; (clear_try, pop_trying, fail))
, !.
push_trying/0
and pop_trying/0
assert and defer a predicate trying/0
that slightly changes how some of the other predicates work, so I don't need to duplicate the code used to test predicates for try_check predicates. is_non_interfering/2
is not deterministic. In mode, trying
is_non_interfering
places the generated variables as try/1
such so that the instance can be assigned to clear_try/0
after checking the constraint.
source to share
nth0/3
has linear costs. Thus, the combination with member/2
and forall/2
has a quadratic cost. In fact, the second version of the code has no advantage in that the index list is in ascending order, while the first is.
Try not to override at this point in development: do the right first, then (and only then) do the quick steps.
Focus on clean readable code, choose the right data structures, make the right choice of library ... If circumstances warrant, you can replace random reads in lists, for example with some compound plus structures arg/3
.
Also, your code can profit from indexing the first argument. Be careful when using cut and / or assert / retract, both can easily drag around correctness and performance.
source to share