Need help understanding Prolog append/3 and inverse/2 and trace output

Question

This is the question

find value A.

---

inverse([],[]).

inverse([H|T],D) :-
  inverse(T,Z),
  append(Z,[H],D).

append([],X,X).

append([X|L],M,[X|N]) :-
  append(L,M,N).

---

This is the answer:

Plese help me to understand this!

Answer 1

The images of the Prolog code you posted show some unusual or very old Prolog, in particular for list the use of [H:T] is now done as [H|T], notice the change from : to |, and <= is more common as :-.

To understand the Prolog code it is easier to start from the bottom up. I will not cover unification or backward chaining in this as going to that level of detail would require a chapters worth here.

The first predicate to understand is append/3. Normally you never see the code for append given as it is a built-in predicate, but here it is given.

Append/3 has three parameters which are all list. The first two are appended together to form the third.

?- append_01([],[],R).
R = [].

?- append_01([a],[],R).
R = [a].

?- append_01([],[a],R).
R = [a].

?- append_01([a],[b],R).
R = [a, b].

but Prolog predicates can have other modes of operation which can bind values to what would be considered input parameters in other programming languages, e.g.

?- append(X,[b],[a,b]).
X = [a] ;
false.

?- append_01([a],Y,[a,b]).
Y = [b].

?- append(X,Y,[a,b]).
X = []    , Y = [a, b] ;
X = [a]   , Y = [b]    ;
X = [a, b], Y = []     ;
false.

or can just be used to verify the arguments

?- append([a],[b],[a,b]).
true.

?- append([a],[c],[a,b]).
false.

Next is the predicate inverse/2 which is more commonly known in Prolog as reverse/2, and again the source code is given here.

This simply takes one list and reverses it, e.g.

?- inverse([],X).
X = [].

?- inverse([a],X).
X = [a].

?- inverse([a,b],X).
X = [b, a].

however this version of the source code does not do well in other modes, e.g.

?- inverse(X,[]).
X = [] ;

Action (h for help) ? abort
% Execution Aborted

but that doesn't matter to answer the question.

---

The next part of what you posted is a trace of the execution of the query

?- inverse([[1,2,3],[5,4]],A).

In order to use the trace on your code, since there is a built-in predicate for append/3 I had to rename the predicate. Here is the code I used.

inverse([],[]).

inverse([H|T],D) :-
  inverse(T,Z),
  append_01(Z,[H],D).

append_01([],X,X).

append_01([X|L],M,[X|N]) :-
  append_01(L,M,N).

Using SWI-Prolog

set up the trace

?- visible(+all),leash(-all). 

start the trace

trace.

execute the query

[trace] ?- inverse([[1,2,3],[5,4]],A).

returns

   Call: (8) inverse([[1, 2, 3], [5, 4]], _7548)
   Unify: (8) inverse([[1, 2, 3], [5, 4]], _7548)
   Call: (9) inverse([[5, 4]], _7794)
   Unify: (9) inverse([[5, 4]], _7794)
   Call: (10) inverse([], _7794)
   Unify: (10) inverse([], [])
   Exit: (10) inverse([], [])
   Call: (10) append_01([], [[5, 4]], _7802)
   Unify: (10) append_01([], [[5, 4]], [[5, 4]])
   Exit: (10) append_01([], [[5, 4]], [[5, 4]])
   Exit: (9) inverse([[5, 4]], [[5, 4]])
   Call: (9) append_01([[5, 4]], [[1, 2, 3]], _7548)
   Unify: (9) append_01([[5, 4]], [[1, 2, 3]], [[5, 4]|_7792])
   Call: (10) append_01([], [[1, 2, 3]], _7792)
   Unify: (10) append_01([], [[1, 2, 3]], [[1, 2, 3]])
   Exit: (10) append_01([], [[1, 2, 3]], [[1, 2, 3]])
   Exit: (9) append_01([[5, 4]], [[1, 2, 3]], [[5, 4], [1, 2, 3]])
   Exit: (8) inverse([[1, 2, 3], [5, 4]], [[5, 4], [1, 2, 3]])
A = [[5, 4], [1, 2, 3]].

I will not explain the details of a trace as other SO Q&A do that.

---

The trace you posted also has more detail than generated by using the trace, e.g. the bindings (θ).

To see the bindings use gtrace/0

?- gtrace.
% The graphical front-end will be used for subsequent tracing
true.

then execute the query

[trace]?- inverse([[1,2,3],[5,4]],A).

and press space bar to single step. You will have to experiment with it to learn how it works; AFAIK there is no posted documentation on how to use it.

---

From OP comment:

There are some replacements from letters to numbers and theta symbol that make me hard to understand.

While the bindings (θ) are more specific to logic languages, the numbers are also seen in stack based functional languages, see De Bruijn index. Also instead of writing the bindings using vertical line separator (---) , I prefer to use (↦) as seen here.

The lines 1 -4 are just the source code stated again.

Normally with a trace the goal is to covey a tree structure of the executions (calls) but with these lines unless you know how Prolog works it is really hard to see that there is a tree structure.

The lines with the over-bars are meant to help understand what is going on, but if you just follow the flow of the executions (calls) then you may find as I do that they just cause confusion and can be ignored.

At you noted in the comments the Res(_,_) are referring to previous lines in the trace. So Res(5,2) on line 6 can be read as Line 6 is the result of a call from line 5 and which then calls line 2.

The unifications or bindings (θ) are show as as sets. I am not exactly sure what the super and sub script numbers represent but they are clearly linked to De Bruijn indexes. You will have to ask your teacher to explain the super and sub scripts.

After trying several times to explain this with just text, I finally resorted to using Microsoft Visio to do it as graphical tree which was much easier, faster and more accurate.

Even though it was not needed, I added the line trace output from SWI-Prolog into the image and then placed only the call lines in the corresponding places in the tree so that if you want to correlate the two you can. I did it for myself as a check to make sure it was correct.

I would not be surprised if there are a few typo mistakes as I had to redo parts of it many times to make it easy to comprehend. Hopefully I achieved that goal.