How prolog derivation works in this query?

Question

I tried to write a simple Prolog program with the following ruleset.

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

Then I loaded this in the SWI-Prolog shell and executed the following query in the trace mode.

 ?-conc([2,3],[p,q],[2,3,p,q]).

The output was as follows.

[trace]  ?- conc([2,3],[p,q],[2,3,p,q]).
   Call: (8) conc([2, 3], [p, q], [2, 3, p, q]) ? creep
   Call: (9) conc([3], [p, q], [3, p, q]) ? creep
   Call: (10) conc([], [p, q], [p, q]) ? creep
   Exit: (10) conc([], [p, q], [p, q]) ? creep
   Exit: (9) conc([3], [p, q], [3, p, q]) ? creep
   Exit: (8) conc([2, 3], [p, q], [2, 3, p, q]) ? creep
true.

Now the problem is to draw the derivation tree of this goal, but I can't exactly understand how prolog does this, even by looking at the trace output above.

Can someone explain the derivation tree of the above query with regard to the mentioned ruleset? Helpful answers are highly appreciated.

Answer 1

The derivation tree is the following (considering clauses with renamed variables):