Why does my predicate always return true instead of binding the variables?

General
1

Another day, another question!

The book I’m reading gave an exercise to write a predicate dividelist(L1, L2, L3) so that L2 and L3 are the contents of L1 divided, eg dividelist([1,2,3,4,5], [1,3,5], [2,4]). would be true.

My attempt at this wasn’t very elegant, and didn’t work (see below). The author gave a very neat piece of code that does work, which I understand, but I’m interested to know where I went wrong.

My initial thought was to use an auxiliary predicate that has a fourth parameter that indicates if we are to add the head of the first list to the second or third list. I would then have two versions of the auxiliary predicate, one for when the fourth parameter were true and one for when it were false. This led to the following (rather convoluted) code…

dividelist(List, Part1, Part2) :-
  dividelist_(List, Part1, Part2, true).
dividelist_([], _, _, _).
dividelist_([H|T], Part1, Part2, true) :-
  dividelist_(T, [H|Part1], Part2, false).
dividelist_([H|T], Part1, Part2, false) :-
  dividelist_(T, Part1, [H|Part2], true).

However, this always returns true, even if the parameters don’t match. So the following all return true…

dividelist([1,2], L1, L2).
dividelist([1,2,3,4], L1, L2).
dividelist([1,2], [], []).
dividelist([1,2,3,4], [1,2], [3,4]).
% etc...

More to the point, I never get the variables bound, I just get true returned.

Anyone able to explain why this code doesn’t bind the variables?

2

I see this sort of question so often on StackOverflow, that I have a copy-and-paste answer:

Usual reminder: You can step through your program, to see exactly what is happening and where it is going wrong, using e.g. trace. - SWI-Prolog -- Debugging and Tracing Programs

The answer is not to need someone else to explain the code, but rather to understand yourself what’s happening with your code. After all, you wrote it, correct?

At some point I would like to write a howto on debugging Prolog code.

For this particular task, can use:

divide_list([], [], []).
divide_list([H|T], [H|Half1], Half2) :-
    % Swap parameter order
    divide_list(T, Half2, Half1).
4 Likes
3

This means "if the first argument is [], leave everything else alone. I think you want to say "if the first argument is [], then the others are []. (But see below)

You’re building up the results in reverse order (your appending to the front of the list with [H|Part1] and then passing it in the tail-recursive call. The problem you have is: what to do at the end. This is an accumulator-passing style, and you need to get the result at the end. This will do it (although still returning the results in reverse order, and leaving some choicepoints):

dividelist(List, Part1Result, Part2Result) :-
  dividelist_(List, [], [], Part1Result, Part2Result, true).
dividelist_([], Part1, Part2, Part1, Part2, _).
dividelist_([H|T], Part1, Part2, Part1Result, Part2Result, true) :-
  dividelist_(T, [H|Part1], Part2, Part1Result, Part2Result, false).
dividelist_([H|T], Part1, Part2, Part1Result, Part2Result, false) :-
  dividelist_(T, Part1, [H|Part2], Part1Result, Part2Result, true).

You seem to be using true and false as markers about whether you’re outputting to Part1 or Part2. You can avoid this by having two “dividelist” predicates, one for outputting to Part1, which then calls the one that outputs to Part2, which calls the first one. Notice where the items are added to the list (yes, in the head of the predicates - if you’re used to Lisp or other functional programming languages, this takes some getting used to):

d([], [], []).
d([X|Xs], [X|Ys], Zs) :-
    d2(Xs, Ys, Zs).

d2([], [], []).
d2([X|Xs], Ys, [X|Zs]) :-
    d(Xs, Ys, Zs).
1 Like
4

Clever clever clever!

5

Should have mentioned that I did use trace/0, and while that helped me get some understanding of why the code is returning true every time, it didn’t help me understand why I wasn’t seeing any variables bound, just getting true alone. That was really my main question here. Debugging the code was a secondary issue.

That would be extremely useful for newbies like me. The docs are good as reference, but it’s hard to learn from them.

Whilst reading more about debugging, I came across a few references to graphical debugging. However I couldn’t get any of these to work. For example, both gtrace/0 and guitracer/0 weren’t recognised as valid predicates. Do I need to install something else to get these tools?

Thanks, but as I said originally, my main question here was working out what was wrong with my code (primarily why I wasn’t seeing any variables bound, and second why it always returned true). I have a working version from the solutions in the back of the book.

However, credit where it’s due, your version is shorter and (in my limited experience) easier to read than his…

dl([], [], []).
dl([X], [X], []).
dl([H1,H2|T], [H1|L1], [H2|L2]) :-
  dl(T, L1, L2).

…so well worth seeing!

Thanks

6

Yup, that was what I meant! I did actually start of with something like you suggested, but when that didn’t work, I tried the above.

I know about the reverse order, it was an issue, but paled into insignificance when I wasn’t seeing anything being bound.

Sorry to be a pain, but although I’ve looked at your code, I still don’t see why my doesn’t bind any variables (or at least doesn’t report the binding at the end). That’s why primary issue here. Rewriting the code is only going to be possible when I can see what my faulty code is doing, but if it’s not reporting any binding, then I can’t see that. Please can you explain why my code isn’t giving me any bindings? I think you may have alluded to this with the words “The problem you have is: what to do at the end”, but my Prolog skills aren’t developed enough to understand my problem.

Yup, that was my intention, although I see from the author’s code and from what you and @brebs posted that there are far more elegant ways to do it.

Thanks for that, very neat idea.

Thanks again for all the help. I really appreciated it.

7

(The dividelist/3 predicate is a slightly more complicated version of append/3 … if you understand how append/3 works, you should be able to understand how my code or @brebs’s code works.)

I suggest saying “the predicate succeeded (or failed)” instead of “the predicate returned true (or false)”. Because there could be multiple ways that a predicate succeeds.

The Prolog computation model is similar to solving equations by a series of substitutions, with each substitution being true (these happen to correspond to common idioms in other programming languages, but they look different). For example, in X=Y,X=1, you’ll end up with X=1,Y=1. But if you try X=Y,X=1,Y=2, there’s no substitution that satisfies this, so it fails.

Anyway, getting to your question about why your code didn’t return the answer that you wanted, let me try a slightly different example …

For example, if I’m summing a list in a functional language, I can write something like this (Python syntax):

def sum(list_of_numbers):
  if list_of_numbers == []: return 0
  x, *xs = list_of_numbers
  return x + sum(xs)

This is a bit inefficient, so there’s the “accumulator passing” style, whether the accumulator starts as 0 (notice that this is the answer you get for an empty list):

def sum(list_of_numbers, sum_so_far=0):
  if list_of_numbers == []: return sum_so_far
  x, *xs = list_of_numbers
  return sum(list_of_numbers + x, xs)

A sufficiently clever compiler (which Python isn’t) can execute this as “tail recursive”, in effect, the same as a for-loop.

The equivalents in Prolog are:

sum([], 0).
sum([X|Xs), Sum) :-
    sum(Xs, Sum2),
    Sum is Sum2 + X.

and the tail-recursive (accumulator) form is:

sum(ListOfNumbers, Sum) :-
    sum(ListOfNumbers, 0, Sum).

sum([], SumSoFar, SumSoFar).  % See comment below
sum([X|Xs], SumSoFar, Sum) :-
    SumSoFar2 is SumSoFar + X,
    sum(Xs, SumSoFar2, Sum).

The important step is the line sum([], SumSoFar, SumSoFar). You could write this:

sum([], SumSoFar, Sum) :- Sum = SumSoFar.

It has the same intent as the Python line if list_of_numbers == []: return sum_so_far … there’s nothing more to compute, so the sum (answer) is the sum that we’ve computed so far.

I hope this helps and doesn’t further confuse you. :slight_smile:

2 Likes
8

@peter.ludemann Are you a teacher? If not, you should be! Your answers are excellent!

Thanks for all the info, a lot to take in, but I think I followed most of it.

However, I still don’t understand my #1 problem, which is why I don’t see any variable binding when I call my predicate. I’ve learnt a lot in this (and other) threads, but I’m still puzzled by this question.

To clarify, if I run your code for dividing a list (which I renamed to divide_list_pl to avoid clashing with various other versions I have in the same file), I get the following…

?- divide_list_pl([1,2], L1, L2). 
L1 = [1],
L2 = [2].

However, when I run my code, I get the following…

?- dividelist([1,2], L1, L2).
true ;
false.

I still don’t understand why my code, wrong though it is, doesn’t give me any variable bindings like yours (and indeed every other Prolog predicate I’ve written or run) does.

Sorry to keep on asking, but I really want to understand this.

Thanks again for all the help.

9

“Why” is the trickiest of questions, since you give the other the freedom to interpret your question before answering.

Maybe ask, “what in my predicate definition is different from one that correctly binds the variables”?

Or ask, “if you see this trace, can you spot the problem?”

?- trace(dividelist/3), trace(dividelist_/4).
true.

?- dividelist([1,2], L1, L2).
 T [10] Call: dividelist([1, 2], _48122, _48124)
 T [17] Call: dividelist_([1, 2], _48122, _48124, true)
 T [24] Call: dividelist_([2], [1|_48122], _48124, false)
 T [31] Call: dividelist_([], [1|_48122], [2|_48124], true)
 T [31 +0.3ms] Exit: dividelist_([], [1|_48122], [2|_48124], true)
 T [24 +0.8ms] Exit: dividelist_([2], [1|_48122], _48124, false)
 T [17 +1.2ms] Exit: dividelist_([1, 2], _48122, _48124, true)
 T [10 +1.8ms] Exit: dividelist([1, 2], _48122, _48124)
true

Do you see it?

10

Because you end up with essentially:

?- Part1 = _.
true.

That succeeds, but not with any useful data.

1 Like
11

The other problem is that the H is passed to the recursive call instead of staying in the head.

So instead of:

foo([X|Xs], [X|Ys]) :- foo(Xs, Ys).

OP is doing:

foo([X|Xs], Ys) :- foo(Xs, [X|Ys]).

which isn’t wrong Prolog but it does the wrong thing.

1 Like
12

@Boris To be honest, no I don’t see it! I did try trace before I posted, but I haven’t got my head around how to understand what it shows.

I think I understand the first four lines, as it shows me the calls that are made to each clause, with the variables that have been bound so far. However, I don’t understand what the “Exit” lines tell me.

Can you enlighten me? Thanks

13

@brebs Ah, now I’m beginning to understand! I’ll need to study my duff code more closely and see what it’s doing, but your explanation makes sense.

Thanks

14

I love the way you phrased that!

Thanks for the comment, helps me understand.

15

My explanation may be too late, but anyway…

Look at it as a logic program.

This: dividelist_(, _, _, _)
says that for the empty list the remaining 3 arguments (r3a:) may be anything,
So an answer would have variables here.

This:
dividelist_([H|T], Part1, Part2, true) :-
dividelist_(T, [H|Part1], Part2, false).
says that if the r3a for T are [H|Part1], Part2, false,
then the r3a for [H|T] are Part1, Part2, true.
This clearly leads to arbitrary Part1, Part2.
(If [H|Part1], Part2 are arbitrary then Part1, Part2 are.)
So an answer will have variables at these positions.

1 Like
16

Thanks for the comments