Findall/3 surprise

General
21

No, I meant, what does it mean in terms of obvious Prolog code? Using natural language to describe what machines might do is not a road I want to take too often :smiley: and yes I do get religiously zealous over that

22

Not quite. We are already far off topic but I will explain how this is not at all opinion.

People have opinions. But we do not want to ask them, “what is your opinion”. Instead, we would like to measure, regardless of people’s own opinion, how do they in fact behave; how they understand and misunderstand. So, this is attempting to discover how people behave, not what their opinions are. At least in my opinion (and experience) those are not at all the same. (I should probably back up this claim with a citation. I promise to try!)

23

In that case it’s obvious what it means because it is Prolog code. I know you as an experienced Prolog programmer from your posts here so I don’t understand what you mean that you don’t understand what it means.

Which brings me to the other part of our conversation: I do not believe that we can measure with any accuracy how or what people “understand”, or “misunderstand”. Let’s leave aside the incessant debate around what it means to understand that erupted recently around Large Language Models, and which reveals we really have no good definition of what “understanding” is, let alone any good way to measure it. I think that making any assumption about why someone understands or misunderstands hides away a ton of assumptions that make any sort of measurement wildly inaccurate.

For example, if I were to try and explain findall/3 to you in Greek you wouldn’t understand a word, but only because you (I’m guessing) don’t speak a word of Greek. In order to learn anything about the understandability of findall/3 we’d have to assume at least a common language.

But what is a common language? Prolog itself is notoriously hard for most programmers to learn. I remember a colleague who told me that 35 students in his Master’s class were taught Prolog and not one of them understood anything. Is that the fault of “confusing” constructs in Prolog, or the fault of poor instruction? The fault of poor background? A combination of all those?

Human communication is hard. It’s a miracle we can communicate at all. We don’t understand how it works, or when it doesn’t work, why it doesn’t. Trying to put numbers on it and treat it as a measureable quantity that we can use to answer scientific questions is premature. We need to develop the science of understanding, and of human intelligence in general, first.

1 Like
24

The only significant problems I’ve had with findall/bagof/setof is with the “exists” markers (^), and I can easily avoid that by using a single auxiliary predicate, e.g.

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

becomes

... bagof(P1, between_plus_one(0,4, P1), Ys) ...

between_plus_one(Min, Max, Xplus1) :-
    between(Min, Max, X),
    Xplus1 is X + 1.

There can be some “interesting” situations when there’s a free variable in the bagof “goal”, which allows backtracking to give a different set of answers; but that’s something I often encounter in non-bagof situations.

2 Likes
25

I actually agree with everything said in this thread. One last point on findall for filling a list of three elements with the constant a:

?- findall(a, member(_, [findall, still, confusing]), Xs).

You could also take the more structured approach and just tell how many as you want in the list:

?- findall(a, between(1, 3, _), Xs).

Once I grokked it, I started looking for idiomatic ways to say “succeed N times” and eventually found this:

?- findall(a, limit(3, repeat), Xs).

Is there a still better way?

26

I think you’re trying to make a point :stuck_out_tongue:

Not necessarily better but more pure Prolog I suppose:

bind_all(_X,[]).
bind_all(X,[X|Xs]):-
        bind_all(X,Xs).

Then you can do:


?- Ls = [X,Y,Z], X = a, bind_all(X,Ls).
Ls = [a, a, a],
X = Y, Y = Z, Z = a ;
false.

And if you want to have some fun:

?- Ls = [X,Y,Z|T], X = a, bind_all(X,Ls).
Ls = [a, a, a],
X = Y, Y = Z, Z = a,
T = [] ;
Ls = [a, a, a, a],
X = Y, Y = Z, Z = a,
T = [a] ;
Ls = [a, a, a, a, a],
X = Y, Y = Z, Z = a,
T = [a, a] ;
Ls = [a, a, a, a, a, a],
X = Y, Y = Z, Z = a,
T = [a, a, a] ;
Ls = [a, a, a, a, a, a, a],
X = Y, Y = Z, Z = a,
T = [a, a, a, a] ;
Ls = [a, a, a, a, a, a, a, a],
X = Y, Y = Z, Z = a,
T = [a, a, a, a, a] ;
Ls = [a, a, a, a, a, a, a, a, a],
X = Y, Y = Z, Z = a,
T = [a, a, a, a, a, a] .
% And on and on
2 Likes
27

Yes, great! Now check this out:

?- maplist(=(a), L).
L = [] ;
L = [a] ;
L = [a, a] ;
L = [a, a, a] ;
L = [a, a, a, a] . % and so on

But it gets still better!

?- [user].
|: foo(A, B, C) :- maplist(=(a), [A,B,C]).
|: ^D% user://1 compiled 0.01 sec, 1 clauses
true.

?- listing(foo/3).
foo(A, B, C) :-
    maplist(=(a), [A, B, C]).

true.

?- use_module(library(apply_macros)).
true.

?- [user].
|: bar(A, B, C) :- maplist(=(a), [A,B,C]).
|: ^D% user://2 compiled 0.01 sec, 2 clauses
true.

?- listing(bar).
bar(a, a, a). % whoa dude

true.

This last one is actually very impressive. I need to figure out how it happened.

28

That is funny. I don’t grok macros. Prolog just doesn’t have enough silly parentheses for them I guess.

29

This is not only macro expansion, this is something else happening during compilation. But the macro expansion through library(apply_macros) enables the lifting of the body into the head, for maplist:

?- [user].
|: foo(A) :- A = a.
|: ^D% user://1 compiled 0.01 sec, 1 clauses
true.

?- listing(foo).
foo(a). % trivial unification in the body is now in the head!

true.

?- [user].
|: bar([A]) :- A = a.
|: ^D% user://2 compiled 0.00 sec, 1 clauses
true.

?- listing(bar).
bar([A]) :-
    A=a. % did not happen when the variable is in a list!

true.

?- use_module(library(apply_macros)).
true.

?- [user].
|: baz([A,B]) :- maplist(=(a), [A,B]).
|: foobar(A, B) :- maplist(=(a), [A,B]).
|: ^D% user://3 compiled 0.01 sec, 3 clauses
true.

?- listing(baz).
baz([A, B]) :-
    A=a,
    B=a. % maplist was indeed "unrolled"!

true.

?- listing(foobar).
foobar(a, a). % the unrolling and the lifting together

true.

EDIT: apparently unrolling of maplist happens for lists up to, and including, 9 elements.

@jan Do you mind giving a pointer to where this is documented or implemented? I can try to guess what is going on but how do I explain this to others?

1 Like
30

Magic :slight_smile: maplist/2,3 using a fixed (short) list is expanded to a sequence of calls. Then we end with a head and some unifications that follow the head immediately. Such unifications are moved into the head to allow for clause indexing as well as reuse of a head term. So,

foo(X) :- X = f(Y), ..., baz(X).

moves the unification into the head and passes the head term directly to baz/1.

2 Likes