Understanding this implementation of reverse list in prolog

Question

I have written the following small knowledge base for reversing a given list,

reverse_list([],[]).
reverse_list([X|L1], [L2|X]) :-
   reverse_list(L1, L2).

Currently, when executed

reverse_list([a,b,c,d], X).

It produces,

X = [[[[[]|d]|c]|b]|a].

An explanation of why it happens would be much appreciated. And, how can I get around this problem?

I think at last step L2 becomes [] and during back propagation it becomes like that. How can I get the output like , X = [d,c,b,a] using a modification of this approach.

P.S: I am new at Prolog.

Answer 1

You can reason algebraically about Prolog programs.

To show you one way, let us consider a simpler goal that also shows the problem:

?- reverse_list([a], Ls).
Ls = [[]|a].

Why does this hold?

Because this holds if the following holds:

?- [a] = [X|L1], Ls = [L2|X], reverse_list(L1, L2).
L1 = L2, L2 = [],
Ls = [[]|a],
X = a.

I have simply plugged in the definition of reverse_list/2, making this equivalent to the original query and therefore of course still showing the problem.

Now the point: We can generalize the query (simply leave out some goals), and still see the problem:

?- [a] = [X|L1], Ls = [L2|X].
L1 = [],
Ls = [L2|a],
X = a.

So it is clear that the clause head contains a mistake: You are describing terms of the form [Ls|a]. This is not a list, because a is an atom.

+1 for a good naming convention! list_reversed/2 would be even better (avoiding an imperative to suggest that other modes of use also make sense), and there may be even better names.

Answer 2

You have observed a problem with your program and @mat showed you why the answer given was incorrect. Here is another way to localize the problem: Simply stick to what you expect! In your case, this would be:

?- reverse_list([a,b,c,d], [d,c,b,a]).
   false.  % unexpected failure

So here you state that this should be the case, but it is not. Therefore, your program is too specialized for the query. It lacks this solution.

To find the responsible part in your program, you can now generalize your program such that the goal still fails.

:- op(950, fy, *). % prefix *, see this for more.
*(_).

reverse_list([],_/*[]*/).
reverse_list([X|L1], [L2|X]) :-
   * reverse_list(L1, L2).

So I have removed the goal in the rule and the second argument in the fact - and still the program fails! You now need to modify something in the remaining visible part in order to fix the problem.

reverse_list([X|L1], [L2|X])
              ^          ^

The X occurs once as an element and as a list.

There is an easy convention to avoid such errors: Name lists preferably with an added plural-s. So if you have an element X, call the list Xs and together this would be [X|Xs]. In this manner the problem would be easier to spot:

  reverse_list([X|Xs], [Ys|X]) :- ...
                           ^ suspicious!

Answer 3

To reverse a list you need three parameters :

reverse_list(L,L1):-reverse_list(L,[],L1).
reverse_list([],ACC,ACC).
reverse_list([X|L], ACC,L1):- reverse_list(L,[X|ACC],L1).

First you call reverse_list(L,L1) which calls reverse_list(L,[],L1). where second parameter is working as an accumulator storing all the element in reverse order of your first list. So it calls reverse_list([X|L1], ACC,L). where in the first call ACC (accumulator) is empty list, then you call recursively reverse_list(L1,[X|ACC],L). which is the same thing but you moved X from first list and stored to accumulator. Finally the process stops when the first list is empty and all element are passed to ACC with reverse order and then you unify the third List with ACC.

As an example: L=[1,2,3],ACC=[],L isn't evaluated. call reverse_list([2,3],[1],L). in the next recursive step call reverse_list([3],[2,1],L). call reverse_list([],[3,2,1],[3,2,1]). last list is unified with ACC=[3,2,1].

Querying the above example gives:

?- reverse_list([1,2,3],L).
L = [3, 2, 1].