| Chip Eastham 2007-09-15, 7:07 pm |
| On Sep 15, 11:11 am, Stefan <s.bruin...@gmail.com> wrote:
> Thanks for your reply.
>
> Hmmm.. i still dont fully understand it :$
>
> Why is the concatanation of List1 (with 'Elem' prepended) and List2,
> equal to List 3 with 'Elem' prepended. ?
> How does prolog run this code and get to its answer?
> concat_lists is called with 2 lists as argument for example:
> ?- concat_lists([1,2,3], [4,5,6], X).
>
> The base case says the first list must be empty. And i assume its
> because the head is taken off everytime form the first list? but i
> dont really see how its "added" to the third list.. but probably im
> thinking operationally again.
>
> Hope you can explain me some more :)
> I guess when you get used to this way of programming it will go
> automatically, but i really have a hard time understanding it at this
> point. :O
>
> thanks.
>
> concat_lists([], List, List).
> concat_lists([Elem | List1], List2, [Elem | List3]) :-
> concat_lists(List1, List2, List3).
Understanding how a Prolog engine applies these clauses
to get the right answer is a bit more involved than the
explanation of what the rules "mean".
Here we have two rules for one predicate, concat_lists/3.
The second of these rules has a "neck" that connects its
"head" to a "body".
The procedural implementation of Prolog involves three
algorithms:
1. matching a stated goal (or subgoal) to the "head" of
a rule (this is called unification)
2. sequentially attempting, for a "unified" head, any
subgoals stated in the "body" of that rule (which can
involve recursion if one of the subgoals is or leads
to another subgoal of the same predicate)
3. backtracking, if some subgoal initially fails, to
a previous subgoal that might be satisfied in some
alternative way, so that ultimately failure will
represent an exhaustive search for solutions
The present case doesn't require backtracking to
understand, but I list it here for your future
reference.
Suppose the initial goal is your example:
?- concat_lists([1,2,3],[4,5,6],X).
The Prolog engine first tries to unify this goal
with the first clause for predicate concat_lists:
concat_lists([], List, List)
but this attempted unification fails because the
first argument in the stated goal is a nonempty
list, [1,2,3]. So the Prolog engine passes to
the second clause:
concat_lists([Elem | List1], List2, [Elem | List3]) :-
concat_lists(List1, List2, List3).
Unification is successful, with these bindings of
the formal parameters in that clause head:
Elem = 1
List1 = [2,3]
List2 = [4,5,6]
List3 is not yet determined, except as it is
unified with part of the "output" parameter X:
[Elem|List3] = X
The engine then passes to the body of that clause
and tries to solve the subgoal:
concat_lists(List1, List2, List3)
which is equivalent because of the unification step
to this goal:
?- concat_lists([2,3],[4,5,6],List3)
Notice that this is a recursive call to the same
predicate as before.
Again the Prolog engine tries to unify this with
the first clause for concat_lists/3, but fails
because the first argument is not (yet) an empty
list. Therefore the unification to the head of
the second clause now amounts to this subgoal:
?- concat_lists([3],[4,5,6],List3')
I stuck a prime onto List3' just to emphasize
that the variable represented in the subsequent
calls to concat_lists/3 are not identified
directly with the same parameter in previous
invocations. Instead what we get is a chain
of partial bindings:
X = [1|List3]
List3 = [2|List3']
List3' = [3|List3"]
At that point in the "stack" of recursive calls
to concat_lists/3, the body of the second rule
will amount to this goal:
?- concat_lists([]. [4,5,6], List3")
which the reader will recognize as unifying now
with the first clause, because of the empty list
in the first argument, giving this solution:
List3" = [4,5,6]
The chain of partial bindings now completes to:
List3' = [3|List3"] = [3,4,5,6]
List3 = [2|List3'] = [2,3,4,5,6]
X = [1|List3] = [1,2,3,4,5,6]
Incidentally, there is no backtracking needed
in this example because the unification step
will always succeed for one but not the other
of the two rules for concat_lists/3. I.e.,
the first argument is either an empty list or
a nonempty list.
Behind the scenes many Prolog implementations
manage the chain of partial bindings for the
output parameter X in a very clever way that
allows the final result to be calculated "in
place" without actually running up the stack
allocation. This feature is known as tail
recursion or "last call" optimization, and
is only available under the limited case as
we have here that the recursive call of a
predicate to itself occurs as the last call
and when there are no alternatives/backtrack
points still available to consider.
regards, chip
|