Findall/3 surprise

General
1

I sometimes use findall/3 to instantiate all elements of a list to some constant, for example:

?- Xs = [X,Y,Z], findall(a, member(a,Xs), Xs).
Xs = [a, a, a],
X = Y, Y = Z, Z = a.

But I was surprised to find that when the list is partially ground, the same query fails:

?- Xs = [X,b,c], findall(a, member(a,Xs), Xs).
false.

When I look at the result of the first query, I think of the list Xs as the list [X,Y,Z] with each of its variables bound to a. But that is not right! The list in the last argument of findall/3 is not the same list as the list Xs created before the call to findall/3. Instead, the two lists are unified, or attempted to be unified, when the call to findall/3 exits. This becomes evident when I rename the “output” list:

?- Xs = [X,b,c], findall(a, member(a,Xs), Ys).
Xs = [X, b, c],
Ys = [a].

The list Ys = [a] is the list of all instantiations of the term in the first argument of findall/3. Clearly, [X, b, c] and [a] do not unify!

Note that setof/3 and bagof/3 have the same behaviour:

?- Xs = [X,b,c], setof(a, member(a,Xs), Xs).
false.

?- Xs = [X,b,c], bagof(a, member(a,Xs), Xs).
false.

So it seems I had the wrong idea about the semantics of findall/3 et al. It took me a while to realise my mistake and I’m posting this here just in case someone else has been scratching their head about something similar.

(of course now that I’ve put that down in writing it all sounds trivial and like I’m just dumb : )

2

This is all great but is it so that this should have been a maplist instead?

maplist(=(a), L)

??

Or were you trying to instantiate the variables in the list to some value?

3

I was trying to instantiate all the elements of a list to a value (a constant, a.k.a. a Prolog “atom”). At some point, a list happened to have some of its elements already instantiated to non-variable terms, and my findall/3 trick failed.

What I learned from this was to remember that the third argument of findall/3 is a fresh variable.

I use maplist when I have an appropriate predicate to map over a list, but often it’s simpler to just use findall/3 especially when I need to nest iteration.

I wonder why Prolog doesn’t have a proper list comprehension abstraction. The findall/3 group of predicates doesn’t quite cut it.

4

How about bagof/3 or setof/3? I find that they work just fine for me.

If I think of Python’s ys = [y+1 for y in range(0,5) as being the same as Prolog’s

bagof(P1, X^(between(0,4,X), P1 is X+1), Ys).

Slightly more verbose; but there are other situations where Prolog is more concise, so it all evens out.

See also library(aggregate) and library(solution_sequences).

5

Oh, I’m fine with findall/3, bagof/3 and setof/3. I’m just wondering whether there is some historical reason why Prolog doesn’t have a special list comprehension syntax, perhaps syntactic sugar like DCGs. I seem to remember Erlang has it and it basically took its syntax from Prolog. Maybe list comprehensions weren’t a thing in programming language design when Prolog was created.

6

I think the reason is that list comprehension only works for functional languages and comes from set theory notation: {y+1: y ∈ ℕ ∧ 1 ≤ y ∧ y ≤ 5} corresponds to Python’s (y+1 for y in range(0,5)).

The bagof/3 notation is essentially the same (it even has ^ as an equivalent of ∃, something that the Python syntax doesn’t have), but it has a 3rd argument because it’s describing a relationship rather than a function. You can backtrack and get multiple results:

?- between(5,6, Max), bagof(X, between(1,Max, X), Xs).
Max = 5,
Xs = [1, 2, 3, 4, 5] ;
Max = 6,
Xs = [1, 2, 3, 4, 5, 6].

compared with

?- bagof(X, Max^(between(5,6, Max), between(1,Max, X)), Xs), writeln(Xs).
Xs = [1,2,3,4,5,1,2,3,4,5,6].
1 Like
7

Note that ∈ and ≤ are relations not functions: the membership relation over sets and a disequality relation :slight_smile:

I’m not sure where list comprehension notation comes from, to be honest. I’ve seen it in countless papers and textbooks but it is not defined in FOL syntax.

Set theory is the standard semantics for FOL. I don’t like it. It complicates things too much and ends up creating paradoxes, that require even more complications to resolve. But it’s useful to consider, for exampe, the Herbrand base of a predicate as a set. And I think I can only understand and explain quantifiers in terms of sets.

8

Exactly. Prolog already has list comprehension, with bagof/3, setof/3, etc. Functional languages need something additional to allow relations, e.g. (Python): (x+1 for x in range(1,99) if is_prime(x)), which could also be done by the less readable map(lambda x:x+1, filter(is_prime, range(1,99))).

1 Like
9

I still wonder why not:

maplist(=(Constant), List)

??

Note that this fails in the exactly same fashion as the findall/3 in your original example. I am not convinced that the fresh variable in the third argument of findall/3 has anything to do with it.

Yes, it is clumsy to nest your code on the syntactical level, in Prolog, but there are usually better ways to achieve the same. Very hard to discuss such topics without concrete examples though.

10

findall/3 and friends aggregate over non-deterministic goals. That can do things similar to list comprehension, but I think it is a different beast. Joachim Schimpf’s Logical Loops as provided by ECLiPSe and SICStus probably get closer. Possibly we should still add these. I ported the version of the original paper long ago, but there are problems with it that are fixed in the ECLiPSe version. That code is tightly connected to ECLiPSe though, so some work is needed …

Next, we have the maplist/N and foldl/N families together with two alternative lambda implementations. There is a lot, but it is still not as clean as functional languages can do. I think there are two problems: the relational nature of Prolog and lack of typing or lacking reserved syntax for code that make it hard to distinguish code from data. That makes the required code transformation rather fragile.

Bottom line, Prolog can do some things way better than functional languages and others worse. Choose the right tool and use its strong points.

3 Likes
11

Is this the right paper: http://eclipseclp.org/reports/loops.pdf ?

1 Like
12

Yes. If someone likes to pick it up, please contact me first as I already made a good start.

1 Like
13

Well, who said “not”? I usually don’t do it that way but if you say it’s failing in exactly the same ways as findall/3 then it’s the same thing and there’s no reason to chose one over the other, except for personal taste. And, I guess, habit?

To clarify, the reason that this query fails:

?- Xs = [X,b,c], findall(a, member(a,Xs), Xs).
false.

Is not that the third argument of findall/3 is a fresh variable. The reason is that the list, [a], of bindings of the term a in the first argument, for which the goal member(a,Xs) in the second argument succeeds, does not unify with the list Xs = [X,b,c]. By putting Xs as the last argument of findall/3 we are saying that [X,b,c] and [a] must unify, which is not true.

I don’t have any concrete examples because I do it (nesting findall/3 loops) rarely, and only when efficiency is not a consideration. I could look through my code and see if I can find an example but that would take some time. Should I do that? What is the concrete question we are investigating here that requires examples?

14

Could I propose a simpler notation than the foreach/do loops in the Eclipse paper, or is it too late for that?

Suppose we could write the following:

% With 'for', 'in' and 'call' declared as infix operators of appropriate precedence
for X in Xs call P(X)

Then X is an element of Xs and P is a call to a predicate that takes X as an argument; and P(X) is called nondeterministically on every X that is a member of Xs. Xs doesn’t have to be a list: it can be a nondeterministic goal run as a generator, for example we could write:

for I in between(1,inf,I) call write('Oh, look, another':I)

To implement mapping of arbitrary depth (as in Section 3.3 in the Eclipse paper) the syntax can be nested with conjunction :

% With 'and' declared as an infix operator of appropriate precedence
for X in Xs and Y in Ys and Z in Zs call P(X,Y,Z)

In implementation terms these can be syntactic sugar over recursive skeletons (in the sense of Leon Sterling’s paper on “Patterns for Prolog programming [1]”; a similar notion is program schemata in program synthesis).

More complex syntax would nest conjunctions in selecting members of a list and add even more special-purpose operators, for example:

for X and Y in Xs such that P(X,Y,Z) where Z in Zs call (Q(X,Y,Z) -> Q(Y,X,Z))

Personally I’d love to be able to write (some!) Prolog code like that because it looks a lot like the formal notation I find in papers that I want to implement, but it starts to get a bit tricky to explain to the already confused imperative programmer.

[1] Patterns for Prolog Programming | SpringerLink

15

Yes, I agree, bad choice of words. It doesn’t “fail in the same way”. What I should have said is: it fails for the same reason. The reason is that a = b fails. The mechanism of getting to that is not identical, but the reason is the same, and the end result is the same.

There is a reason to chose the one over the other: a maplist… well, it maps a predicate to all elements of a list. findall does way more than that.

The question is: what uses of findall/bagof/setof cannot be replaced by simpler, easier constructs?

The underlying assumption is that findall/bagof/setof are complex and using them is error-prone; and avoiding them whenever possible is a “good thing”.

1 Like
16

Yeah, that’s a religious war like vim vs. emacs and I don’t see the point in it.

17

I don’t know how critical I can afford to be of this paper, especially the Motivation part. I am not fully buying it, which means I am missing something.

How often does “client code” contain explicit iteration/loops/recursion? (My knee-jerk answer would be, not at all that often…)

We have library(apply); we have forall/2; we have library(aggregate). There are also the engines which in fact let us combine sequences of solutions in trivial and non-trivial ways.

I will spend some time collecting the real pain-points I have experienced lately with Prolog programming. The one common topic seems to be keeping state through backtracking but engines cover that, at least provide the low-level tools.

1 Like
18

There is nothing religious about it. Simple things are simple and complicated things are complicated. For example, we both know that this:

maplist(=(a), [A, B, C]).

Means this:

A = a, B = a, C = a

In this exact order.

I admit that I don’t know what exactly this means:

findall(a, member(a, [A, B, C]), [A, B, C])

I can kinda figure out what will happen but I would have to start digging quite deep to understand and appreciate the subtleties…

PS: we can probably empirically measure how confusing different constructs are to people of different backgrounds and levels of expertise. In this way, we can quite safely move this from the realm of opinions to the realm of science.

2 Likes
19

It means “find all the bindings of a such that a is a member of the list [A,B,C] and the list of all bindings unifies with the list [A,B,C]”.

20

It seems to me your experiment would still only measure opinion. The opinion of people from different backgrounds and levels of expertise, but, still, opinion.

1 Like