Prolog - Whats the logic behind this

I tried to understand how this code works but i failed. It concatenates two lists and then it reverses the result.

reverse(L, RL):- reverse(L, [], RL).
reverse([], RL, RL).
reverse([H|T], S, RL):- reverse(T, [H|S], RL).


concat([], L, L).
concat([H|T1], L2, [H|T]):- concat(T1, L2, T).


concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L)

My teacher told me to go to debug mode and trace the query to understand but it didnt helped.

here is an example

5 ?- trace,concat_reverse([1,3],[4,5],S).
   Call: (7) concat_reverse([1, 3], [4, 5], _G1444) ? creep
   Call: (8) concat([1, 3], [4, 5], _G1569) ? creep
   Call: (9) concat([3], [4, 5], _G1564) ? creep
   Call: (10) concat([], [4, 5], _G1567) ? creep
   Exit: (10) concat([], [4, 5], [4, 5]) ? creep
   Exit: (9) concat([3], [4, 5], [3, 4, 5]) ? creep
   Exit: (8) concat([1, 3], [4, 5], [1, 3, 4, 5]) ? creep
   Call: (8) reverse([1, 3, 4, 5], _G1444) ? creep
   Call: (9) reverse([1, 3, 4, 5], [], _G1444) ? creep
   Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep
   Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep
   Call: (12) reverse([5], [4, 3, 1], _G1444) ? creep
   Call: (13) reverse([], [5, 4, 3, 1], _G1444) ? creep
   Exit: (13) reverse([], [5, 4, 3, 1], [5, 4, 3, 1]) ? creep
   Exit: (12) reverse([5], [4, 3, 1], [5, 4, 3, 1]) ? creep
   Exit: (11) reverse([4, 5], [3, 1], [5, 4, 3, 1]) ? creep
   Exit: (10) reverse([3, 4, 5], [1], [5, 4, 3, 1]) ? cre开发者_如何学Cep
   Exit: (9) reverse([1, 3, 4, 5], [], [5, 4, 3, 1]) ? creep
   Exit: (8) reverse([1, 3, 4, 5], [5, 4, 3, 1]) ? creep
   Exit: (7) concat_reverse([1, 3], [4, 5], [5, 4, 3, 1]) ? creep
S = [5, 4, 3, 1].

Let's look at this bit by bit.

You used:

concat_reverse([1,3],[4,5],S).

Prolog attempts to unify this.

concat_reverse(L1,L2,L)

Matches. L1 unifies with [1,3] and L2 unifies with [4,5]. So we look at the right hand side:

concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L)

Prolog does a depth first search for unification, so it checks concat(L1,L2,LN), again with the unified L1 and L2.

Let's look at the two concats together:

concat([], L, L).
concat([H|T1], L2, [H|T]):- concat(T1, L2, T).

If it helps, think of this pattern matching as fall-through if logic. The first will match an empty list, something, and the same something. This is actually a stopping condition for the depth first search that Prolog does.

The second matches a list with a head and tail, something, and a list with the same head and possibly different tail. At this point, we match this because of how unification works. Nothing important is bound to the third list. During unification, we will change that "nothing important" to something. For now, we match, so we traverse down with the next concat, passing in the tail of the first list, the second list, and another "nothing important".

On the next level, we match the same condition. We do this again, and we hit the stopping condition. Our nothing important is the second list. So we try to crawl back up out of the depth first search via unification. We prepend the head of the first list of the match above us in the search tree. That unifies. We climb up again. We prepend the next level up. That unifies. What do you know, we were able to unify the concat term of the first concat_reverse match.

Now we look at the reverse part of the concat_reverse match. This is Exit(8)/Call(8) in your stack trace. Down we go again, doing a depth first search with these:

reverse(L, RL):- reverse(L, [], RL).
reverse([], RL, RL).
reverse([H|T], S, RL):- reverse(T, [H|S], RL).

Well, there's only one match, the one with two terms. But now we search both of the three-term choices for reverse. Our list isn't empty, so we don't match the first (again, this is going to be our stopping condition). We can match the second one.

I'm going to stop because continuing this won't add anything new. Basically, the working of the prolog interpreter is one of matching, unification, and depth first search.

Hopefully you will have or have already had a lesson on why prolog does a depth first search and why that means that it fails to be refutation complete (and what you can do as a programmer to prevent infinite depth searches).

Basically, when you write prolog code, you write it as you would an inductive proof or a recursive function. Start with your stopping condition, then handle the general case in terms of the stopping condition. Define things in terms of composition, like concat_reverse.

I think you should take a look at a simpler example to understand unification a little better. This example has unnecessary complications (though those complications will invariably help you when it comes time to write your own prolog code for homework). Try looking at reverse in isolation, without concat and concat_reverse.

Disclaimer: I do not know your teacher, so maybe you will have to put this differently...

Tell you had many difficulties and ask why the code did not read:

concat_reverse(L1,L2,L):-reverse(L2,R,L),reverse(L1,[],R).

And then:

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

iseq([]) -->
   [].
iseq([E|Es]) -->
   iseq(Es),
   [E].

concat_reverse2(L1,L2,L) :-
   phrase( ( iseq(L2), iseq(L1) ), L).

In general, I would not suggest using a debugger to understand a predicate.

When reading (or writing) Prolog, I like to tell a little story.

For example, when reading concat_reverse, this is how I explain it: "L is the concat_reverse of L1 and L2 if firstly LN is the concatenation of L1 and L2, and secondly, L is the reverse of LN".

When I read concat, I say: "The concatenation of [] and L is L." "The concatnation of [H|T1] and L2 is [H|T] if the concatenation of T1 and L2 is T."

Basically, the explanation should somehow simplify the expression. If I were to write "concat", I would think "what is a trivial truth about concat? Concatenating any list to the empty list is the original list. What about the general case of [H|T]? Concatenating L to this is M if the head of M is H and the rest of M is the concatenation of T to L. In other words, concat([H|T], L) is M if M is [H|RM] and concat(T, L) is RM."

As for reverse, the story is a bit more complicated, because there is no simple of saying "RL is the reverse of L if ...". But we can still come up with a story. For example, we can say "S is the suffix of the reverse of L (called RL) if the appropriate suffix of L is reversed and then S is concatenated to the result."

So for the empty suffix, we have reverse([], RL, RL) - RL is the suffix of RL if the empty suffix of L is reversed and RL is concatenated to it.

In the general case, if suffix of L is [H|T], then the suffix of RL is S only if [H|S] is also a suffix of RL.

This is a bit confusing, and especially when the predicate is called "reverse". We have to use some imagination. But what if we called it something like:

concat_of_reversed_suffix_and_S([H|T], S, RL) :- concat_of_reversed_suffix_and_S(T, [H|S], RL).

This is a bit clearer - the reverse of [H|T] is the reverse of T followed by H. If [H|T] is the suffix of L and S is the suffix or RL, then the reverse of T followed by H followed by S is exactly RL. We say this long sentence in this way:

reverse([H|T], S, RL) :- reverse(T, [H|S], RL).

A debugger can show you the process, but it's better to have a story in your head that explains it, and then you can confirm it with the debugger.

In this case, you can see:

   Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep
   Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep

[3,4,5] is a suffix of L, [1] is a suffix of RL. This is true only if [3,1] is also a suffix of RL, leaving [4,5] as the (smaller) suffix of L to be considered.

concat_reverse(L1,L2,L) :-
        concat_reverse(L1,L2,[],L).

concat_reverse([],[],L,L).
concat_reverse([],[B|R2],L3,L) :-
        concat_reverse([],R2,[B|L3],L).
concat_reverse([A|R1],L2,L3,L) :-
        concat_reverse(R1,L2,[A|L3],L).