Prolog list concat

Question

I am learning Prolog and I have stumbled upon this piece of code and I cannot make sense of it:

Code:

append([],Ys,Ys). 

append([X|Xs],Ys,[X|Zs]):- 
            append(Xs, Ys, Zs).

In the example, the instruction given is:

Code:

append([1,2],[3,4],Ys).

and the output is Ys = [1,2,3,4]

And I don't understand how that happens.

I understand that the values on Xs get removed one by one until it equals [], what I don't understand is 1. Why is Zs being changed; if the fact is append([],Ys,Ys), Zs should be equal to [3,4] so why changing it in any way if it already obeys the fact?
2. How do [1,2] get in the beginning of Zs??

I used trace and the result of that is even more confuse, because Zs is always values like _G5166, _G5112, etc... What are those values? Are those memory addresses?

And why is it that, even if I don't use write(), the console displays Ys = ...? And why Ys and not Xs or Zs?

Answer 1

Regarding your first pair of questions:

1. It's not the same Zs. Initially, when you try append([1,2],[3,4],Ys)., then Prolog says to itself "Hmm, I could do that if the original Ys were in the form [X|Zs], and now I just need to match append(Xs, Ys, Zs)." The next time it says "Hmm, I could do that if the original Zs were in the form [X|OhterZs], and now I just need to match append(Xs, Ys, OtherZs)." Just imagine that with eacy recursion call, it's making new variable names.
2. The 1 and 2 get to the front through the first two invocations, each one to its own version of Zs.

Regarding your other points:

• The strange thingies that are trace are exactly these recursion-local Zs

• Since your query was append([1,2],[3,4],Ys)., and Ys was the only variable, then Prolog interprets your query as asking what match of Ys would evaluate truthfully.