Why is Prolog unifying a free variable to another free?

Question

maxmin([X|L], Max, Min) :-
    maxmin(L, X, X, Max, Min),
    !.

maxmin([], CurrentMax, CurrentMin, Max, Min) :-
    Max is CurrentMax,
    Min is CurrentMin,
    !.
maxmin([X|L], CurrentMax, CurrentMin, Max, Min) :-
    CurrentMax2 is max(X, CurrentMax),
    CurrentMin2 is min(X, CurrentMin),
    maxmin(L, CurrentMax2, CurrentMin2, Max, Min).

Upon performing the query ?- maxmin([2],Max,Min)., it will return Max = Min, Min = 2..

Why? I have several variation of this and none of them seems to work. How it is possible that it is assigning a free to another free? Is this some reflection stuff in Prolog I am not aware of?

Tracing does not show anything particularly interesting either. Namely, it exits from Exit: (8) maxmin([2], 2, 2) ? creep which looks perfectly fine to me. This will only happen when I have a list of 1.

I am obviously not understanding Prolog but I can't figure out for the life of me where I am wrong. Any pointers?

It's saying Max and Min are both bound to 2. It would be no different if it said Max = 2, Min = 2. SWI does this for some reason. — Daniel Lyons
@Hanif Bin Ariffin Prolog makes a variable chain - the last variable will reffer to value. — Anton Danilov
In Prolog if you have Max = Min, Min = 2 then Max is also unified to 2. That's why it is called "unification" and not "assignment". — Enigmativity
Maybe you could explain how it does not work, as it seems to make sense. Both the maximum and minimum of a list of one will be that one value. Your cuts are pointless: maxmin/3 has only one clause, and in maxmin/5 the pattern-matching on the first parameter will discriminate. There is no reason to use is instead of = unless you are evaluating mathematical expressions. — Tomas By

Guy Coder Guy Coder · Accepted Answer · 2019-03-07T10:46:37

How it is possible that it is assigning a free to another free?

Your use of the word assigning is telling us a secret about how you think about Prolog. When you see = in Prolog, that is not assignment, but unification, see: =/2. Prolog works by unification or more specifically syntactic unification.

If Prolog can unify two free variables together, for example A and B and when one of them then becomes bound, the other is also bound at the same time because they were unified before.

While not entirely accurate, another way to think about this is as pointers.

If you start off with one pointer pointing to A and a different pointer pointing to B, which are different locations and latter find that A and B are unified, the pointers to both A and B will be adjusted to now point to the same location. However the location they point to is still an unbound location as neither A or B have a value. When either A or B are bound to a value, then they both become bound at the same time because the pointers are pointing to the same location.

Here is some test code the demonstrates the details.

test_01 :-
    format('A: ~w~n',[A]),
    format('B: ~w~n',[B]),
    A = B,
    format('A: ~w~n',[A]),
    format('B: ~w~n',[B]),
    A = 5,
    format('A: ~w~n',[A]),
    format('B: ~w~n',[B]).

Running this returns the following. I added the comments in after the fact by hand.

?- test_01.
A: _480      % Line 1
B: _486      % Line 2
A: _480      % line 3
B: _480      % line 4
A: 5         % Line 5
B: 5         % Line 6
true.

In line 1 the variable A is internally referenced as an unbound variable: _480
In line 2 the variable B is internally referenced as an unbound variable: _486
Note that _480 and _486 represents two different unbound variables.
Note that A and B are not internally referencing the same.

Next the code executes A = B

then

In line 3 the variable A is internally referenced as _480
In line 4 the variable B is internally referenced as _480

Note that now A and B are internally referencing the same: _480.

Next the code executes A = 5

In line 5 the variable A internally references _480 which is now bound with the value 5.
In line 6 the variable B internally references _480 which is now bound with the value 5.

When this happened, there were not two separate bindings, but one binding to one location, which because of unification, and thus the reference to the same location, two variables became bound to a value with one action.

So when you see B = A, A = 2. it is can mean that B and A were unified, (referencing the same location), and that the bound value in the location for B is 2, which is also the same bound value for B since A and B were unified.

However in your specific example since Max and Min were never unified it is just the particular way the SWI-Prolog displays them.

I ran a trace of your example to see exactly what your were noting.

?- leash(-all),visible(+all),trace.
true.

[trace]  ?- maxmin([2],Max,Min).
   Call: (8) maxmin([2], _4408, _4410)
   Unify: (8) maxmin([2], _4408, _4410)
   Call: (9) maxmin([], 2, 2, _4408, _4410)
   Unify: (9) maxmin([], 2, 2, _4408, _4410)
   Call: (10) _4408 is 2
   Exit: (10) 2 is 2
   Call: (10) _4410 is 2
   Exit: (10) 2 is 2
   Exit: (9) maxmin([], 2, 2, 2, 2)
   Exit: (8) maxmin([2], 2, 2)
Max = Min, Min = 2.

It might be that SWI-Prolog is keeping a table of display values and that it notices that both Max and Min have the same value so displays them that way, but I don't want to take the time to dig into the code find the details.

Is this some reflection stuff in Prolog I am not aware of?

I would not use the word Reflection to describe it.

Some test cases for your code. I used to make sure your code was working in case you had a bug and forgot to ask about it.

:- begin_tests(maxmin_tests).

maxmin_test_case([1],1,1).
maxmin_test_case([1,2],2,1).
maxmin_test_case([2,1],2,1).
maxmin_test_case([1,2,3],3,1).
maxmin_test_case([3,2,1],3,1).
maxmin_test_case([2,3,1],3,1).
maxmin_test_case([3,1,2],3,1).

test(1,[forall(maxmin_test_case(Input,Expected_max,Expected_min))]) :-
    maxmin(Input,Max,Min),
    assertion( Max == Expected_max ),
    assertion( Min == Expected_min ).

test(2,[fail]) :-
    maxmin([],_,_).

:- end_tests(maxmin_tests).

Example run

?- run_tests.
% PL-Unit: maxmin_tests ........ done
% All 8 tests passed
true.

Why is Prolog unifying a free variable to another free?

1 Answers