The way to understand how Prolog handles multiple procedure definitions is first to think of how a deterministic procedural machine executes a procedural program. It maintains a state (usually a stack of activation records) and executes instructions which update that state, calling subprocedures, performing the indicated operations, and returning from subprocedures. To introduce nondeterminism into this picture, we consider what happens when a machine encounters a procedure that has multiple definitions. At this point it duplicates itself, creating a copy for each definition, and each copy continues by executing the definition it is assigned to. Recall that an execution may fail when it does a unification that discloses an inconsistency. When this happens, we can think of the machine as simply disappearing. So we can think of a Prolog execution as a set of executing deterministic machines; whenever any one of them encounters a procedure call of a multiply defined procedure, it forks into multiple machines; whenever a machine fails, it disappears out of existence. The answer to a Prolog program is the set of answers returned by all the individual machines that make it to the final instruction of the program, i.e., that return successfully from the initial procedure call.
So if we invoke the a_sqrt procedure defined above with the
following procedure call statement:
:- a_sqrt(13,Y).
we will get two answers:
X = 3.6055;
X = -3.6055;
Let's revisit the append program we wrote above. Instead of using an if-then-else construct there, we can now use nondeterminism. Consider:
append(L1,L2,L3) :-
L1 = [],
L3 = L2.
append(L1,L2,L3) :-
L1 = [X|L1t],
append(L1t,L2,L3t),
L3 = [X|L3t].
Notice that for whatever the list that is assigned to the variable
L1, exactly one of the two procedure definitions will fail, and
the other will succeed. The first will succeed only if L1 is
the empty list, and the second will succeed only if L1 is a
nonempty list. This program is essentially equivalent to the one
above with the if-then-else.
Actually we can now improve this new append program. Consider how a
normal procedural programming language passes parameters to
procedures. One way is to do it by assignment: local variables are
allocated for each formal parameter and the actual parameters are
assigned to local variables on invocation. So assignment is used for
passing parameters. Prolog can pass parameters this way as well, but
instead of using assignment, it uses its symmetric assignment
operation, unification (or matching.) So rather than doing a
unification in the body of a procedure definition, we can simply put
the values to be unified in the place of the formal parameters. So,
for example, in the first procedure definition for append,
rather than assigning the actual parameter to a local variable
L1 and then checking it against the empty list, we can directly
check the first argument against the empty list as follows:
append([],L2,L3) :-
L3 = L2.
This looks very odd for a conventional procedural language, having a
constant in the place of a formal parameter, but with Prolog's
symmetric assignment, it works fine. It simply unifies the empty list
with the first actual parameter at the time of invocation.
As a matter of fact, whenever we have an explicit unification of a
variable with another term, we can replace all occurrences of the
variable with the term and eliminate the explicit unification. So we
can replace L3 by L2 in the above clause and we get simply:
append([],L2,L2).
(When a definition has no body operations, we don't even write the
:-.) This procedure definition has no operations in its body. In a
traditional procedural language, it would be a no-op, but in Prolog it
actually does some work through the unification of its arguments when
it is invoked.
The same idea for eliminating explicit unifications can be used on the
second clause for append, and we obtain the usual Prolog
definition of append:
append([],L2,L2).
append([X|L1t],L2,[X|L3t]) :-
append(L1t,L2,L3t).