Prolog, permutation code understanding

Question

I'm trying to understand how this program works.

Code from Daniel Lyons' solution(from the link above)

takeout(X,[X|R],R).  
takeout(X,[F |R],[F|S]) :- takeout(X,R,S).

perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).

I'm trying ti understand how it works with this list [1,2,3] So, I have perm([1,2,3],X).

It's easy to understand at first, Y = [2,3] then Y = [3] and then Y = []

After that perm([],[]). is called and it gives us W = []

Now, takeout is called for the first time - takeout(3, Z, []). It returns Z = [3]

Now, we are going back, where perm([],[]). gives us W = [3], (because Y was [3] at this point)

Same as above, takeout(2, Z, [3]) and Z = [2, 3].

Again perm([], []). and W = [2, 3].

And takeout(1, Z, [2, 3]), which gives us first answer Z = [1, 2, 3]

Here I don't know why program don't end , recursion is done, so why takeout and perm are working again ?

After that takeout is called takeout(1, [2,3]).

Which now works with takeout(X,[F |R],[F|S]) and not with takeout(X,[X|R],R). and that's my second question, why?

Answer 1

In Prolog, a predicate's behavior is quite unlike that of a function in procedural languages. A function is called to perform a task, it executes, and then comes back returning some values or having performed some side effects, or both.

A predicate defines a relation and/or set of facts that establish a logical connection between it's arguments. When a query is made to a predicate in Prolog, Prolog will attempt to find every instantiation of the argument variables that will make that predicate succeed (be true).

In a very simple case, I might have the following facts:

likes(tom, mary).    % Tom likes Mary
likes(fred, mary).   % Fred likes Mary

Here I have one predicate or fact, likes, which defines a relation between two people. We call the above facts because they each specify a precise, concrete relation with fully instantiated arguments. I can make a query to determine Who likes Mary? as follows:

| ?- likes(Person, mary).

Person = tom ? ;

Person = fred

yes

The query first comes back with Person = tom but indicates it has more options to check once it has found that Person = tom satisfies the query. Entering ; tells Prolog to continue with the next solution (if there is one), and it finds it: Person = fred.

Now let's consider takeout/3. This is a predicate which defines a relation between a set of variables.

1. takeout(X,[X|R],R).
2. takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

The takeout/3 predicate has two predicate clauses or rules for the relation. It's helpful to try to read them:

1. R is what you get if you take X out of [X|R].
2. [F|S] is what you get if you take X out of [F|R] if S is what you get when you take X out of R.

Prolog looks at multiple clauses in a disjunctive way. That is, a query or call to the predicate will succeed if any one of the rules can hold true. When a query on takeout/3 is made, Prolog will look for instantiations of the given variables in the query which will make it true, and it will attempt to find every such instantiation that does so. In other words, if there's more than one way to satisfy the condition, it will backtrack and attempt to find those variables instantiations that do so.

Consider the query:

?- takeout(X, [1,2,3], R).

Prolog is able to match this to the first predicate clause: takeout(X, [X|R], R) as takeout(1, [1,2,3], [2,3]) by instantiating X = 1 and R = [2,3]. So this query will succeed with the following result:

R = [2,3]
X = 1 ?

But we see that Prolog is indicating there are more options to explore. That's because there's another clause: takeout(X,[F|R],[F|S]) which matches the query, takeout(X, [1,2,3], R). Prolog therefore backtracks and attempts the second clause, which matches:

takeout(X, [1|[2,3]], [1|S]) :-    % F = 1, R = [2,3]
    takeout(X, [2,3], S).

Prolog will then follow the recursive call takeout(X, [2,3], S) and start from the first clause again and attemp to match takeout(X, [2,3], S) with takeout(X, [X|R], R), which succeeds with X = 2 and S = [3] (takeout(2, [2|[3]], [3]).. The recursion unwinds or returns (as it would in any language), and the previous call head, takeout(X, [1|[2,3]], [1|S]) then ends up instantiating as: takeout(1, [1|[2,3]], [1|[3]]). So we get:

R = [2,3]
X = 1 ? ;

R = [1,3]    % that is, [1|[3]]
X = 2 ? 

And so on. Similar behavior applies to perm. In the context of the query perm, the calls to takeout backtrack to produce additional results, so perm produces additional results (since its calls to takeout backtrack, just like they do when you query takeout by hand).

---

As noted by @false, the predicate takeout/3 is implemented as a standard predicate in Prolog as select/3.