Example: here is the definition of the built-in Prolog predicate member:

member(X, [X | Rest]). % X is a member if its the first element
member(X, [Y | Rest]) :-
    member(X, Rest).   % otherwise, check if X is in the Rest

?- member(X, [a, b, c]).X = a ;X = b ;X = c ;false.

?- member(X, [a, a, a]).X = a ;X = a ;X = a ;false.

?- member(a, [a, a, a]).true ;true ;true ;false.

The term backtracking also applies to seeking several sets of variable bindings to satisfy a single goal.

In some circumstances, it may be desirable to inhibit backtracking, as when only a single solution is required. The Prolog cut goal allows this.

Tracing the execution of a piece of Prolog code that backtracks can be a good way to figure out what happens during backtracking. If you wanted to experiment with backtracking by tracing member, you could achieve this by copying the code for member, given above, changing the name from member to say mem in the three places where it appears, and then tracing your mem procedure.

likes(mary, pizza).
likes(marco, pizza).
likes(Human, pizza) :- italian(Human).
italian(marco).

?- bagof(Person, likes(Person, pizza), Bag).
Person = _G180
Bag = [mary, marco, marco]

Notice that Bag contains the item marco twice, because there are two ways to prove that marco likes pizza - the fact and via the rule. bagof fails if Goal has no solutions.

See also setof, and, for differences between bagof and findall, see findall.

Suppose that the Prolog database contains just the single fact likes(mary, pizza). and that there is a query:

?- likes(mary, What).

Prolog will search the (tiny) database, find that the query can be satisfies if What = pizza, do it will bind What to pizza and report success:

?- likes(mary, What).
What = pizza ;
false.

Now suppose that there is a rule and facts in Prolog's database:

teaches(Teacher, Student):-
    lectures(Teacher, Subject), studies(Student, Subject).
lectures(codd, databases).
studies(fiona, databases).
studies(fred, databases).

and that the user issues the query:

?- teaches(codd, Who).

The Prolog interpreter first matches the head of the rule with the query, and so binds Teacher to codd. It then finds a fact that indicates a subject that Codd lectures - namelylectures(codd, databases). At this point, the variableSubject is bound to databases (Subject = databases). In other words, Subject, perhaps temporarily, has the value databases. Then Prolog tries to satisfy the second goal studies(Student, Subject) with Subject = databases, i.e. it tries to satisfy studies(Student, databases). When it finds the solution, studies(fiona, databases) it will bind Subject to fiona, and report the solution:

?- teaches(codd, Who).
Who = fiona

Notice that the bindingSubject = databases was made in solving the query, but it is not reported, as it is not explicitly part of the query.

Then, if the user types ";", Prolog will backtrack and undo the bindingStudent = fiona and look for another value for Subject that satisfies studies(Student, databases), and find as Student = fred. However, while binding (and unbinding) is involved in this step, it is properly treated under backtracking.

sister_of(X,Y) :-
    female(Y),
    X == Y,
    same_parents(X,Y).