Embarrassingly simple problem 
Author Message
 Embarrassingly simple problem

I have just returned to writing Prolog code again, after an absence of a few
years (and what a joy it is :-).  Since my library of useful predicates has
dissappeared in the mists of time, I thought I'd bash out a new one.  Nothing
fancy, just the usual append/3 etc, and including reverse/2.  First year
undergraduate stuff really, or so I thought.

My first attempt at reverse/2 looked like:
%
% reverse( ?List1, ?List2 )
% True when List2 is the same as List1 with the elements reversed.
reverse( List1, List2 ) :-
        reverse( List1, List2, [] ).

reverse( [], List, List ).
reverse( [Head | Tail], List, Accum ) :-
        reverse( Tail, List, [Head | Accum] ).

So far, so good.  Works fine for goals like
        reverse( [a,b,c], X ).

It fails, however, for
        reverse( X, [a,b,c] ).
I mean, it gives one (correct) solution, but then goes into infinite loop on
backtracking.  Bad news.

OK, in the declarative reading there is exactly one reverse of each list (it
is a one-to-one relation), so we could cheat by:

reverse( [], List, List ) :-
        !.
reverse( [Head | Tail], List, Accum ) :-
        reverse( Tail, List, [Head | Accum] ).

The problem then is that you only get one solution to:
        reverse( X, Y ).
instead of infinitely many.

I don't remember reverse/2 being asymmetrical before, so what am I doing
wrong?  Has my brain atrophied completely in three years?  Help, somebody,
please!

Thanks in advance,
Ian.

+-------------------------------------------------------------------------+
|Ian{*filter*}inson,           Hewlett Packard Laboratories,  Bristol,  England|

|"I've been to every single book I know               +-------------------+
| To soothe the thoughts that plague me so"  -Sting   | voice: 0272-799910|
|Nevertheless,  my opinions are entirely my own fault |                   |
+-----------------------------------------------------+-------------------+



Mon, 20 Jul 1992 16:18:00 GMT  
 Embarrassingly simple problem

{I have taken the liberty of switching the arguments of reverse/3 into
 the usual inputs-precede-outputs order.

Quote:
}
> reverse(List1, List2) :-
>    reverse(List1, [], List2).

> reverse([], List, List).
> reverse([Head|Tail], Accum, List) :-
>    reverse(Tail, [Head|Accum], List).

> So far, so good.  Works fine for goals like
>    reverse([a,b,c], X).

> It fails, however, for
>    reverse(X, [a,b,c]).
> I mean, it gives one (correct) solution, but then goes into infinite loop on
> backtracking.  Bad news.

> I don't remember reverse/2 being asymmetrical before, so what am I doing
> wrong?  Has my brain atrophied completely in three years?  Help, somebody,
> please!

You have lost your memory, but not your mind (:-).
What you have coded is the operation the Quintus Prolog library
calls rev/2, and it is and has always been asymmetric like this.
The basic reason is that reverse/3 is trying to guess its first
argument, and it never gives up hope that a longer guess might
work.

There is a standard workaround for things like this.

reverse(List, Reversed) :-
        same_length(List, Reversed),
        rev(List, [], Reversed).

rev([], R, R).
rev([H|T], L, R) :-
        rev(T, [H|L], R).

same_length([], []).
same_length([_|X], [_|Y]) :-
        same_length(X, Y).

I think it was Ed Stabler who showed me this solution, in the
context of the N-Queens program.  The same dodge works very
nicely for permutation/2 (just as we have both rev/2 for speed
and reverse/2 for purity, we have perm/2 and permutation/2),
and for several other cases.



Mon, 20 Jul 1992 04:05:00 GMT  
 Embarrassingly simple problem

Quote:

> [...]
>I don't remember reverse/2 being asymmetrical before, so what am I doing
>wrong?  Has my brain atrophied completely in three years?  Help, somebody,
>please!

The problem is not as trivial as it seems.
One symmetrical solution is:

     reverse(X, Y) :- reverse(X, [], Y, []).

     reverse(X, X, Y, Y).
     reverse([A|X1], X2, Y1, Y2) :-
            reverse(Y1, [A|Y2], X1, X2).

The arguments to reverse/4 are difference pairs for the two lists.
The second clause may look a little strange, but the logical meaning is
simply that if the last element of list Y is A, and the reversal of all but
the last element is X, then the reversal of Y is [A|X].
The reason for swapping the argument pairs in the recursive call is to ensure
that the second clause is used on both of the lists, to avoid infinite loops.
The runtime behaviour is not particularly good if all you want is fast
reversal of fixed-length lists. A choice-point is created and removed at each
recursive call, and one choice-point is left on the stack after succeeding.
Some heap garbage may be created, although not in the typical case when
one of the arguments is uninstantiated.

--



Mon, 20 Jul 1992 22:38:00 GMT  
 Embarrassingly simple problem
1>reverse( [], List, List ).
2>reverse( [Head | Tail], List, Accum ) :-

Quote:
>    reverse( Tail, List, [Head | Accum] ).

The problem arises with clause 2 of your reverse/3 method.  Giving it an
uninstantiated variable as a first argument causes lists of increasing length
to be generated. The only return is via clause 1, and there is nothing to
prevent continued backtracking after this solution has been generated.

Zanconato[1] uses the following method to solve this problem:

reverse( List1, List2 ) :-
    gen_list( List1, List2 ),
    reverse( List1, List2, [] ).

reverse( [], List, List ).
reverse( [H|T], List, Accum ):-
    reverse( T, List, [H|Accum] ).

gen_list( [], [] ).
gen_list( [H1|T1], [H2|T2] ) :-
    gen_list( T1, T2 ).

The trick here is to pre-instantiate List1/2 to a list with the correct
number of elements (a symmetric operation) *before* the call to
reverse/3.  By doing this, of course, neither list can change in side,
so reverse/3 can only generate *one* solution. gen_list/2 is the procedure
which generates the multiple solutions.

Quote:
> I don't remember reverse/2 being asymmetrical before, so what am I doing
> wrong?  

Reverse is *inherently* asymmetrical. One of the lists must be reversed
and unified with the other. You can't reverse both the lists. Hence a
loss of symmetry is inevitable.

Quote:
> ...     Has my brain atrophied completely in three years?  Help, somebody,
> please!

No Comment!

-- Mike --

[1]. RAMBO, Rule Based Access to ODDS, CCL Technical Report C2585-UM-001a,
     Zanconato,R., 1987.

--
---------------  UUCP:  ...!ukc!camcon!mb | Cambridge Consultants Ltd

---------------  Phone: +44 223 358855    | Cambridge CB4 4DW
[These opinions aren't necessarily my company's, or even my own!]



Mon, 17 Aug 1992 11:16:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. mine embarrassingly simple problem

2. rdoc: embarrassingly minor complaint

3. Simple problem, simple solution.

4. Queens Problem -- A simple look

5. A very simple question on SED or AWK for a GURU, and an enjoyable problem

6. A simple but tricky problem

7. Challenge problem - a simple spreadsheet

8. developing in J with simple tools and simple minds

9. Very simple awk for a simple user

10. Simple courses in J for simple (ordinary) people

11. Simple courses in J for simple (ordinary) people

12. Simple courses in J for simple (ordinary) people

 

 
Powered by phpBB® Forum Software