Prolog reverse lookup and input validation at the same time

Question

I have started learning prolog recently and even though it is refreshing to move away from functional programming, things still seem very foreign. I having trouble understanding how I can write a predicate that checks whether its argument adhere to a certain set of rules and also at the same time if given a variable will set it to the possible values that satisfy those rules.

I was trying to solve the circular table seating problem where you define a set of conditions for people to sit next to each other. So the knowledge base contains 10 individuals with the languages they speak and the goal is to seat them in a way such that two people sitting next to each other must speak the same language.

I defined a predicate speaks_same(X, Y) which returns true if both individuals X and Y speak the same language. Now the goal is to write a function table_seating such that table_seating([mark, carl, emily, kevin, oliver]) returns true if each two people sitting next to each other in the list speak a common language. Of course for this to happen each person must speak more than one language. And also table_seating(L). would produce the possible table seatings that satisfy the condition.

The way I see it is I can either write a predicate that checks if a previously defined list satisfies the rules or one the builds a list according to these rules. I don't understand how I can do both with one function.

Any help would be really appreciated, thanks!

Answer 1

In Prolog, generation and validation are one and the same thing: the table_seating predicate does both in any case, unless you deliberately produce non-relational code. i.e. the statement table_seating(X) says “X is a table seating”. if, then, X is bound and is a valid table seating, the “call” will succeed. If X is bound and invalid, the call will fail, if unbound, it will be filled with a valid seating and the call will pass.

i.e. Prolog makes sure that truth always wins. And the “making sure” is the execution/evaluation (which is implemented as a potentially failing search).

So the predicate merely needs to express what it means for something to be a table seating.

Answer 2

I have been doing Prolog for a few years and I feel like my comfort with and understanding of different instantiation patterns has come in several discrete steps. The first significant hurdle is of course recursion, which is all you really need to get your head around for this problem. Basically, you know that your table assignment for two people is correct if they speak the same language, so this is your base case:

table_seating([X,Y]) :- speaksSame(X, Y).

So, what if you add a third person to the mix? You'd do something like this:

% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).

Now hopefully you notice that your new work is speaksSame(A,X) but your old work has remained the same. Let's just worry about the new person and trust that we could have handled it for the remainder of the list.

table_seating([X,Y,Z|Rest]) :- 
   speaksSame(X, Y),
   table_seating([Y,Z|Rest]).

What we're doing here is saying, assume we have at least three items in the list. Then if the first two speak the same language, and the next two plus the rest can be seated, then they can all be seated. You can always take a correctly-seated table and add a person to the front of the table, if they speak the same language as the person currently at the front of the table.

Recursion almost always has this flavor: how can I set up the minimal correct situation, the base case, and then, how can I add one more thing to that situation correctly?

Now what's interesting is that if you supply a list of some length to this predicate, it will "just work" and produce solutions of that length. Try it like so:

?- length(L, 6), table_seating(L).

You will probably get solutions (I assume speaksSame/2 will generate solutions). This is because all Prolog knows about these variables, it knows about because of your speaksSame/2 predicate. So as long as you use predicates that have many instantiation patterns in your predicates and don't force assignments to things or order things strangely, often your predicates will inherit these modes. This is a reason I recommend people use succ/2 instead of N is N0 + 1 or N0 is N - 1, because succ/2 defines a relationship between two numbers rather than performing some arithmetic (clpfd takes this idea much, much further).

Answer 3

I don't understand how I can do both with one function.

Yes, at first this seems odd, but then once you get the hang of it, you miss it in other languages.

The word you want to remember when referencing this is: mode
Also see Mercury Modes reference for more detail related to the Mercury programming language.

In Prolog an argument can be an input, and output, or both used as an input or output depending upon how it is called.

In Type, mode and determinism declaration headers at the bottom is listed 4 examples.

1. length(+List:list, -Length:int) is det.
2. length(?List:list, -Length:int) is nondet.
3. length(?List:list, +Length:int) is det.
4. True if List is a list of length Length.

and the definition of length/2 shows

length(?List, ?Int)

meaning
that for the List argument, the list can be bound or unbound, and
that for the Int argument, the value can be bound or unbound.
So for the two arguments with two options there are four ways to use length/2

Here they are listed again but in actual usage.

1.

length(+List:list, -Length:int) is det.

in this case List is bound and Length is unbound and always gives one answer.

?- length([1,2,3],N).
N = 3.

2.

 length(?List:list, -Length:int) is nondet.

in this case List is unbound and Length is unbound and can return any number of answers.

?- length(List,N).
List = [],
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5 
...

3.

length(?List:list, +Length:int) is det.

in this case List is unbound and Length is bound and always gives one answer.

?- length(List,4).
List = [_5332, _5338, _5344, _5350].

4.

True if List is a list of length Length.

in this case List is bound and Length is bound and always acts as predicate to return either true or false.

?- length([1,2,3],3).
true.

?- length([1,2,3],5).
false.

So how is this possible?

Prolog uses syntactic unification (↦) and NOT assignment (=).

If we look at the source code for length/2 using listing/1 we get

?- listing(length/2).
system:length(B, A) :-
        var(A), !,
        '$skip_list'(D, B, C),
        (   C==[]
        ->  A=D
        ;   var(C)
        ->  C\==A,
            '$length3'(C, A, D)
        ;   throw(error(type_error(list, B), context(length/2, _)))
        ).
system:length(B, A) :-
        integer(A),
        A>=0, !,
        '$skip_list'(D, B, C),
        (   C==[]
        ->  A=D
        ;   var(C)
        ->  E is A-D,
            '$length'(C, E)
        ;   throw(error(type_error(list, B), context(length/2, _)))
        ).
system:length(_, A) :-
        integer(A), !,
        throw(error(domain_error(not_less_than_zero, A),
                    context(length/2, _))).
system:length(_, A) :-
        throw(error(type_error(integer, A), context(length/2, _))).

which is too much detail but does do all 4 modes correctly.

To make it easier to understand we will use this version, but it doesn't support 1 of the modes correctly but it does do more than one mode so it works good enough to demonstrate.

length_2([]     , 0 ).
length_2([_|Xs] , L ) :- 
    length_2(Xs,N),
    L is N+1 .

Now to see the unification in action we will use the trace feature of SWI-Prolog and to enable all of the ports for the box model use visible/1 and so as not to stop it when running use leash/1.

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

1.

[trace] ?- length_2([1,2,3],N).
   Call: (8) length_2([1, 2, 3], _2352)
   Unify: (8) length_2([1, 2, 3], _2352)
   Call: (9) length_2([2, 3], _2580)
   Unify: (9) length_2([2, 3], _2580)
   Call: (10) length_2([3], _2580)
   Unify: (10) length_2([3], _2580)
   Call: (11) length_2([], _2580)
   Unify: (11) length_2([], 0)
   Exit: (11) length_2([], 0)
   Call: (11) _2584 is 0+1
   Exit: (11) 1 is 0+1
   Exit: (10) length_2([3], 1)
   Call: (10) _2590 is 1+1
   Exit: (10) 2 is 1+1
   Exit: (9) length_2([2, 3], 2)
   Call: (9) _2352 is 2+1
   Exit: (9) 3 is 2+1
   Exit: (8) length_2([1, 2, 3], 3)
N = 3.

2.

[trace] ?- length_2(List,N).
   Call: (8) length_2(_2296, _2298)
   Unify: (8) length_2([], 0)
   Exit: (8) length_2([], 0)
List = [],
N = 0 ;
   Redo: (8) length_2(_2296, _2298)
   Unify: (8) length_2([_2528|_2530], _2298)
   Call: (9) length_2(_2530, _2550)
   Unify: (9) length_2([], 0)
   Exit: (9) length_2([], 0)
   Call: (9) _2298 is 0+1
   Exit: (9) 1 is 0+1
   Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
   Redo: (9) length_2(_2530, _2550)
   Unify: (9) length_2([_2534|_2536], _2556)
   Call: (10) length_2(_2536, _2556)
   Unify: (10) length_2([], 0)
   Exit: (10) length_2([], 0)
   Call: (10) _2560 is 0+1
   Exit: (10) 1 is 0+1
   Exit: (9) length_2([_2534], 1)
   Call: (9) _2298 is 1+1
   Exit: (9) 2 is 1+1
   Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
   Redo: (10) length_2(_2536, _2556)
   Unify: (10) length_2([_2540|_2542], _2562)
   Call: (11) length_2(_2542, _2562)
   Unify: (11) length_2([], 0)
   Exit: (11) length_2([], 0)
   Call: (11) _2566 is 0+1
   Exit: (11) 1 is 0+1
   Exit: (10) length_2([_2540], 1)
   Call: (10) _2572 is 1+1
   Exit: (10) 2 is 1+1
   Exit: (9) length_2([_2534, _2540], 2)
   Call: (9) _2298 is 2+1
   Exit: (9) 3 is 2+1
   Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3 

3.

[trace] ?- length_2(List,3).
   Call: (8) length_2(_5534, 3)
   Unify: (8) length_2([_5724|_5726], 3)
   Call: (9) length_2(_5726, _5746)
   Unify: (9) length_2([], 0)
   Exit: (9) length_2([], 0)
   Call: (9) 3 is 0+1
   Fail: (9) 3 is 0+1
   Redo: (9) length_2(_5726, _5746)
   Unify: (9) length_2([_5730|_5732], _5752)
   Call: (10) length_2(_5732, _5752)
   Unify: (10) length_2([], 0)
   Exit: (10) length_2([], 0)
   Call: (10) _5756 is 0+1
   Exit: (10) 1 is 0+1
   Exit: (9) length_2([_5730], 1)
   Call: (9) 3 is 1+1
   Fail: (9) 3 is 1+1
   Redo: (10) length_2(_5732, _5752)
   Unify: (10) length_2([_5736|_5738], _5758)
   Call: (11) length_2(_5738, _5758)
   Unify: (11) length_2([], 0)
   Exit: (11) length_2([], 0)
   Call: (11) _5762 is 0+1
   Exit: (11) 1 is 0+1
   Exit: (10) length_2([_5736], 1)
   Call: (10) _5768 is 1+1
   Exit: (10) 2 is 1+1
   Exit: (9) length_2([_5730, _5736], 2)
   Call: (9) 3 is 2+1
   Exit: (9) 3 is 2+1
   Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736] 
Action (h for help) ? abort

% Execution Aborted

4.

[trace] ?- length_2([1,2,3],3).
   Call: (8) length_2([1, 2, 3], 3)
   Unify: (8) length_2([1, 2, 3], 3)
   Call: (9) length_2([2, 3], _2058)
   Unify: (9) length_2([2, 3], _2058)
   Call: (10) length_2([3], _2058)
   Unify: (10) length_2([3], _2058)
   Call: (11) length_2([], _2058)
   Unify: (11) length_2([], 0)
   Exit: (11) length_2([], 0)
   Call: (11) _2062 is 0+1
   Exit: (11) 1 is 0+1
   Exit: (10) length_2([3], 1)
   Call: (10) _2068 is 1+1
   Exit: (10) 2 is 1+1
   Exit: (9) length_2([2, 3], 2)
   Call: (9) 3 is 2+1
   Exit: (9) 3 is 2+1
   Exit: (8) length_2([1, 2, 3], 3)
true.

[trace] ?- length_2([1,2,3],5).
   Call: (8) length_2([1, 2, 3], 5)
   Unify: (8) length_2([1, 2, 3], 5)
   Call: (9) length_2([2, 3], _2442)
   Unify: (9) length_2([2, 3], _2442)
   Call: (10) length_2([3], _2442)
   Unify: (10) length_2([3], _2442)
   Call: (11) length_2([], _2442)
   Unify: (11) length_2([], 0)
   Exit: (11) length_2([], 0)
   Call: (11) _2446 is 0+1
   Exit: (11) 1 is 0+1
   Exit: (10) length_2([3], 1)
   Call: (10) _2452 is 1+1
   Exit: (10) 2 is 1+1
   Exit: (9) length_2([2, 3], 2)
   Call: (9) 5 is 2+1
   Fail: (9) 5 is 2+1
   Fail: (8) length_2([1, 2, 3], 5)
false.

and to turn the trace off

[trace] ?- notrace.
true.

[debug] ?- nodebug.
true.

I won't go through each of the lines in the trace output, but if you understand syntactic unification and can follow the trace, after working through the examples given you will see how variables in Prolog are unified resulting in different modes when compared to imperative programming.

Remember that variables are only bound once in Prolog, and never reassigned, and that the numbers on the left in the trace in parenthesis, e.g. (10), are the stack level, so when a call is made to a predicate again, a new set of variables are made available, and while it may seem the are being reassigned a value, it is actually another variable in the stack, just in a different stack frame.

As an aside when learning Prolog one piece of advise I give is that it is easier to learn if you set aside what you know about imperative and functional programming, except for maybe recursion, and start from the ground up with unification and then backward chaining.

If you can read OCaml, here is a simplified version of unification and backward chaining. Note that this is not a Prolog as it does not have list or the cut operator but if you can understand it, then the ways of unification and backward chaining become apparent.

I have to add that I am not totally satisfied with my answer as I know you are a beginner and this answer is to much information to digest and requires a lot of work on your part to work through the 4 trace examples. However it does answer the question and gives a practical example with more than enough meat on the bone. I am working on trying to think of a better example which would include logical purity and that demonstrates that not only unification but relationships are key to how multiple modes can be accomplishes in one predicate. Be glad I didn't use general relativity as paraphrased by the relativist John Archibald Wheeler, spacetime tells matter how to move; matter tells spacetime how to curve.