1

Lately I have started to study Prolog , as soon as I've dealt with it I had issues to understand it.

I'm studying the list and I can't understand how the append/3 predicate, which should merge two list, works. 

book_append([], L, L). 
book_append([X|L1], L2, [X|L3]) :-
    book_append(L1, L2, L3).

Precisely I can't understand how L2 is appended to main list. I try to explain what I have understood so far:

The boundary condition will unify only when the first list is empty and the the second and third will take the same value. is it correct?

First question, maybe it is stupid, when the first list is empty the two list must unify so they will take the same value. But they should be different so I will lose one of their value.

In the second line the head of the first list is appended on the third list and recall the same function.

I usually use this function in this way: book_append([1, 2, 3], [a, b, c], X).

The first line is false because L1 isn't empty.
While the second one should be :

book_append([1|[2, 3], [a, b, c], [1|L3]) :-
    book_append([2, 3], [a, b, c], L3).

What's the value of L3 (I already know it's the tail of the third list) during the first call? Is it empty? Or an uninstantiated variable? Or is it instantiated to L2?

m09
  • 7,490
  • 3
  • 31
  • 58
Giuseppe Pes
  • 7,772
  • 3
  • 52
  • 90

4 Answers4

2

First of all, please see this answer by @Will Ness and this answer (by me). It should already answer your question.

Then let's adress (quickly) your specific concerns:

First question, maybe it is stupid, when the first list is empty the two list must unify so they will take the same value. But they should be different so I will lose one of their value.

You have to consider how values change in Prolog.

Basically values change through unification. And change only once. it means that A can become [5|B] and then will be done changing and will be that for all your program. B can eventually change so that A will change too in some way but the binding occurs only once as said before.

So here, you cannot "lose" value since you can't rebind anything. Unification will just do its best to match List2 and Result by binding the free variables to the correct things. This way if Result is a free variable as in your example then it will just be bound to the value of List2. And if both variables are already bound the only thing unification can do is to test whether they are bound to the same value or not.

For your second question please see in particular my answer that will detail the bindings to get a clearer idea.

Community
  • 1
  • 1
m09
  • 7,490
  • 3
  • 31
  • 58
2

Prolog's logical variables (logvars) are essentially named pointers, which can be instantiated/"set" (assigned a value) only once. Each logvar can be in "not-yet-set" state, or in instantiated/set state.

No binding can be ever changed, while no backtracking has occured (on backtracking, this "setting of pointers" can be undone and the logvars can revert back to their former uninstantiated state, possibly to be instantiated again later on to some other values).

When "set", it can point to an atomic value like numbers (5), symbols ('a'), etc. Or it can point to another logvar (meaning, the two become equivalent).

Or it can point to a compound (struct-like, or named record-like) value, like f(a,B,c) whose sub-entities themselves can be fully instantiated ("ground") values, or they can be/contain not-yet-instantiated logvars themselves.

Now, lists in Prolog appear as compound terms under a name (i.e. functor) of '.' (a dot). A list [A|B] is actually a compound term '.'(A,B) with two sub-entities i.e. "arguments", A and B.

So when we "set" A = [1|B], we make A "point" at the actual bona fide structure in computer's memory, tagged with the name (functor) '.', with two fields. The first field contains a number 1, and second - a logvar named B, not yet instantiated to anything. Or in C++-terms, it's an uninitialized pointer.

And that pointer is what's getting passed (by reference) into the nested recursive call to book_append. And it is that pointer which gets set there. And that is what the second field of a "list node" "pointed to" by A is now pointing at.

So recursive calls do not need to "return" anything back to their "callers" in Prolog. They just instantiate parts of structures that were set up above them, "fleshing out" those structures more and more fully.

But if we have a handle on the top node of the list, we have access to all of its sub-entities, now that they are instantiated fully.

And all this verbose text means, in C++ terms, that append/3 operates by going along its first list while copying the list nodes aside, and when it's arrived at the end of the first list, it sets the next pointer of the last-copied list node - to point to the start of the second list with which it was called. It means that it is tail recursive modulo cons.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Great answer!!! Thanks... I have just one question left... Because all passages are by reference if I modify the second list will I have the same modification on the new list create through the book_append? – Giuseppe Pes Aug 09 '12 at 06:11
  • first, what I said was a metaphor, for C-speakers (I looked at your tags). Apparently this have mislead you if you still think you can *"modify"* anything. **You can't**. You set your logical variables **only once**. Only uninstantiated logvar gets passed "as-if by reference", so that setting it in the callee also sets it in the caller -- **only once**. Logvars represent our knowledge. If we say that `X` is `5`, by `X = 5`, we can't say later that it is 10. We would be liars then, and Prolog is not equipped to deal with lies. – Will Ness Aug 09 '12 at 06:30
  • @GiuseppePes but, if you meant that your 2nd list had holes in it (uninstantiated vars, like `B=[10|Z]`), and you first call `append([1,2,3],B,C)` and only later `Z=[90,100]` - then, yes. Since the base case unifies the 2nd list with the result, `append([],L,L)`, they *are* the same. Try it. – Will Ness Aug 09 '12 at 06:33
  • @GiuseppePes (correction, Prolog *is* equipped to deal with lies - it *rejects them* outright). :) We can't lie to it. **Say `?- X=5, X=10.`, and Prolog replies: `No`.** – Will Ness Aug 09 '12 at 06:39
0

The first line only applies when both the first list is empty and the second and third lists are the same (or one is a variable, etc., which can then take on the value of the other). So you will not lose information.

For understanding the second line, remember that (the way you're demonstrating using it) the third argument is the result (again, this is just one possible usage). So, when used in that manner, the second line says that it will be returning [X|L3], and L3 is mentioned in the body (I don't actually know the proper term) -- where? As the result of a new book_append call. So L3 will be the result of appending the first list without its head to the second list.

Sgeo
  • 85
  • 8
0

The database:

book_append([], L, L).
book_append([X|L1], L2, [X|L3]) :- book_append(L1, L2, L3).

When call: 

?- book_append([1, 2, 3], [a, b, c], A).

the compiler will look into the database to find an unification. Because the first line can not unify ([1, 2, 3] can not unify with []) then the second line will be used and it will become: book_append([1|[2, 3], [a, b, c], [1|L3]) :- book_append([2, 3], [a, b, c], L3). The unification will happen only if the condition from the right of ":-" has an unification too. So it will look again into the database to find an unification for book_append([2, 3], [a, b, c], L3) and so on.

The unifications should look like this ( = is the symbol for unification):

book_append([1, 2, 3], [a, b, c], A) = 
    book_append([1|[2,3]], [a,b,c], [1|L3]) =
    book_append([2|[3]],   [a,b,c], [2|L3]) =
    book_append([3|[],     [a,b,c], [3|L3]] =
    book_append([],        [a,b,c], [a,b,c])  % book_append([], L, L).
=> A = 1|2|3|[a,b,c]

Please correct me if I am wrong, I just starting to learn this for a project.

Robert
  • 1