eliminating use of -> operator

[mvolkmann]

I wrote the following rule which relates a list and a predicate to the first element in the list that satisfies the predicate.
It works, but it uses the -> operator.

list_pred_first([], _, []).
list_pred_first([H|T], Pred, Element) :-
  Goal =.. [Pred, H],
  ( call(Goal) ->
    Element = H
  ; list_pred_first(T, Pred, Element)
  ).

On advice from @triska I would like to remove use of the -> operator.
Is the following a reasonable/best way to rewrite it?
It works, but it feels odd to have two clauses that create Goal and call it.

list_pred_first([], _, []).
list_pred_first([H|_], Pred, H) :-
  Goal =.. [Pred, H],
  call(Goal).
list_pred_first([H|T], Pred, Element) :-
  Goal =.. [Pred, H],
  \+ call(Goal),
  list_pred_first(T, Pred, Element).

As a side question, how do you feel about the name of the rule?

[david-sitsky]

The https://www.complang.tuwien.ac.at/ulrich/papers/PDF/indexingdif2.pdf paper has a lot of great material in there relevant to this, and you can see how it implements some of the higher-order monotonic relations like tfilter and so on.

Maybe in this case, if you use if_ instead of -> you'll get a better result?

list_pred_first([H|T], Pred, R) :-
    if_(call(Pred, H), R = H, list_pred_first(T, Pred, R)).

here is some example usages:

?- list_pred_first([1,1,2,3,4], dif(2), R).
   R = 1.
?- list_pred_first([1,1,2,3,4], dif(1), R).
   R = 2.
?- list_pred_first([], dif(1), R).
   false.

[mvolkmann]

@david-sitsky Do you know why this gives an error when I use your implementation above?

L = [foo, Bar, baz],
list_pred_first(L, var, FirstVar).

I expected to get FirstVar = Bar, but instead get error(existence_error(procedure,var/2),var/2).

[triska]

On a general note, to repeat and slightly expand on what was already pointed out in #1958 (reply in thread):

var/1 is not a monotonic predicate, and can therefore not be expressed as a relation in classical first-order predicate logic (which is a monotonic logic): Instantiation of a variable is a meta-logical property and cannot logically be taken into account on the level of a logic program itself. A logic program can only state what holds, i.e., state the conditions that make a relation true. Free variables that occur in clauses are implicitly all-quantified: For all X, Y etc., it holds that ... . And from a logical perspective, each variable stands for anything at all, not only a "variable", but really any term.

Testing for instantiation with var/1 and related meta-logical predicates destroys logical properties we expect from relations. An example was already given in the comment linked above, showing that testing for instantiation in this way destroys commutativity of conjunction, one of the most basic logical properties we expect from logic programs. If this property no longer holds in programs, then these programs can only be understood by thinking about them procedurally, which, as I understand it, is something that we specifically do not want to have to do: A key attraction of pure logic programs is that we do not have to think about them procedurally. Instead, we can rely on logical properties and guarantees that help us understand the code in ways that are easier to perform than procedural reasoning. We can think declaratively about logic programs, and use generalizations and specializations to obtain program fragments that show the reasons for unexpected results. This is something that cannot be done in imperative languages, making them significantly harder to debug and reason about. It is a unique attraction of logic programming languages. If we no longer benefit from this key attraction, then why use a logic programming language at all in the first place?

To benefit most from Prolog and to retain these key properties, I recommend to keep to its pure monotonic core. A nice list of pure predicates was already posted earlier: https://old.reddit.com/r/prolog/comments/10nuwz8/what_exactly_is_the_pure_monotonic_core_of_prolog/. These predicates suffice to express a great number of problems that arise in practice, and I recommend to focus on them, and especially when starting with Prolog.

[david-sitsky]

Using =(1) gives general answers:

?- list_pred_first(L, =(1), 1).
   L = [1|_A]
;  L = [_A,1|_B], dif:dif(1,_A)
;  L = [_A,_B,1|_C], dif:dif(1,_A), dif:dif(1,_B)
;  L = [_A,_B,_C,1|_D], dif:dif(1,_A), dif:dif(1,_B), dif:dif(1,_C)
;  L = [_A,_B,_C,_D,1|_E], dif:dif(1,_A), dif:dif(1,_B), dif:dif(1,_C), dif:dif(1,_D)
...

[david-sitsky]

I was hoping this general query would have given answers, where a list element was different to 1.

?- list_pred_first(L, dif(1), R).

but seemingly it does not terminate.

[triska]

You can use iterative deepening to observe such answers:

?- length(Ls, _), list_pred_first(Ls, dif(1), F).
   Ls = [F], dif:dif(1,F)
;  Ls = [1,F], dif:dif(1,F)
;  Ls = [F,_A], dif:dif(1,F)
;  Ls = [1,1,F], dif:dif(1,F)
;  ... .

[pmoura]

Unrelated to your main question, and as seen in @david-sitsky code, learn (also) about the call/N family of (meta-)predicates that take a closure as first argument. In this particular case, you can replace Goal =.. [Closure, H], call(Goal) with call(Closure, H). Shorter and more efficient, both in time and space (by avoiding the creation of a temporary list that will need to be eventually garbage-collected).

[triska]

On a general note, (\+)/1 is not a monotonic predicate, and so, in general, predicates that use it lose declarative properties we expect from relations. For instance, in this case, if we define:

p(a).

Then we get:

?- list_pred_first(Ls, p, F).
   Ls = [], F = []
;  Ls = [a|_A], F = a
;  false, unexpected, incomplete.

A nice overview of pure monotonic predicates was recently posted in other discussions, the link is: https://old.reddit.com/r/prolog/comments/10nuwz8/what_exactly_is_the_pure_monotonic_core_of_prolog/ To benefit most from Prolog, I recommend to keep to this pure core, where you can benefit from strong logical properties that are useful for debugging and reasoning about your code.

[mvolkmann]

I'd like to clear up a possible misunderstanding I have with if_. It's my understanding that when the first argument is a predicate, its last argument should be an uninstantiated variable and the predicate must set it to true or false.

It was suggested that I can implement my list_pred_first predicate like this:

list_pred_first([], _, []).
list_pred_first([H|T], Pred, R) :-
    if_(call(Pred, H), R = H, list_pred_first(T, Pred, R)).

But when I test it like this:

L = [foo, Bar, baz],
list_pred_first(L, var, FirstVar).

expecting to get FirstVar = Bar I instead get error(existence_error(procedure,var/2),var/2).
This is of course because var/2 doesn't exist, but var/1 does.
if_ is trying to pass two arguments to its first argument predicate instead of one.
I don't know how to get if_ to work in this case.

[mvolkmann]

One issue is that I haven't been able to find a definitive list of what is in the pure monotonic core. I have read several posts on this and have arrived at the list below (which is probably not correct). I gather that some predicates are definitely in and others are only in if they are used in specific ways. I think it would be very helpful if some of the top people in the Prolog community came to an agreement on exactly what is in the pure monotonic core and posted that list.

• true/0, false/0, fail/0
• (=)/2, unify_with_occurs_check/2 (sound alternative to =/2)
• conjunction (A, B) and disjunction (A; B) if A and B are pure
• repeat/0
• is/2?
• call(Goal) if Goal is pure
• predicates in library(clpfd/clpz) such as (#=)/2 and (#\=)/2
• dif/2 in library(dif)
• dif_si/2 in library(si)
• number_chars/2, number_codes/2
• if-then-else with (;)/2
• maplist(Goal, Ls) if Goal is pure
• user-defined predicates that only use predicates listed above

[UWN]

See this comment. It seems you haven't read it. Just one example: number_chars/2 needs a lot of preconditions.

[UWN]

And, to begin with, just stick to 1..4 only. There, all the deeper issues like termination already appear.

[mvolkmann]

I did read that. Would you agree that there is currently no single web page that is a definitive list of what is in the pure monotonic core? I was hoping to find a list of predicates where each is either definitely in or is only in when used in a certain way. The link in that comment certainly contains some of what I suggested, but even it says "The precise core ... is somewhat difficult to define since there is a lot of fine print required". So you can see why it is hard for beginners to following the advice of "stick to the pure monotonic core" when experts can't fully describe it.

[UWN]

The outer borders are difficult to describe. The inner core, which is 1..4, is not. Just because there is no 100% clear condition when, say, !/0 may still be part of it, or when side-effects may be ignored, does not question the inner core, which always has been like that. Just look at textbooks from the 1980s.

[pmoura]

expecting to get FirstVar = Bar I instead get error(existence_error(procedure,var/2),var/2). This is of course because var/2 doesn't exist, but var/1 does. if_ is trying to pass two arguments to its first argument predicate instead of one. I don't know how to get if_ to work in this case.

You need to reify var/1:

$ scryer-prolog
?- use_module(library(reif)).
   true.
?- [user].
list_pred_first([], _, []).
list_pred_first([H|T], Pred, R) :-
    if_(call(Pred, H), R = H, list_pred_first(T, Pred, R)).

var(X, T) :- (var(X) -> T = true; T = false).

?- L = [foo, Bar, baz], list_pred_first(L, var, FirstVar).
   L = [foo,Bar,baz], Bar = FirstVar.
?- 

But note Ulrich's observations on var/1...

[mvolkmann]

Thanks @pmoura! That works, but has the downside that Pred must always be a reified predicate. Do you feel that adding that requirement makeslist_pred_first less generally useful?

[UWN]

Clearly, @pmoura did not understand what reification is about. Sic pereat.

[pmoura]

Thanks @pmoura! That works, but has the downside that Pred must always be a reified predicate. Do you feel that adding that requirement makeslist_pred_first less generally useful?

Yes, Pred must always be a closure for a reified predicate. Look into the reification of the (=)/2 predicate in the paper. To avoid using an if-then-else construct in higher-level code (for better logical properties), we end up using this construct in lower-level code that the user may also need to write. A curated library of reified predicates would improve the reusability of definitions like your list_pred_first/3 predicate.