ijd@otter.hple.hp.com (Ian Dickinson) (02/18/88)
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 Dickinson, Hewlett Packard Laboratories, Bristol, England| |net: ijd@hplb.uucp ijd%idickins@hplabs.HP.COM ..!mcvax!ukc!hplb!ijd| |"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 | | +-----------------------------------------------------+-------------------+
ok@quintus.UUCP (Richard A. O'Keefe) (02/19/88)
In article <1600005@otter.hple.hp.com>, ijd@otter.hple.hp.com (Ian Dickinson) writes: {I have taken the liberty of switching the arguments of reverse/3 into the usual inputs-precede-outputs order. } > 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.
bd@zyx.UUCP (Bjorn Danielsson) (02/23/88)
In article <1600005@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes: > [...] >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. -- Bjorn Danielsson, ZYX Sweden AB, +46 (8) 665 32 05, bd@zyx.SE
mb@camcon.uucp (Mike Bell) (03/02/88)
1>reverse( [], List, List ). 2>reverse( [Head | Tail], List, Accum ) :- > 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. > 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. > ... 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 -- Mike Bell -- or: mb@camcon.uucp | Science Park, Milton Road --------------- Phone: +44 223 358855 | Cambridge CB4 4DW [These opinions aren't necessarily my company's, or even my own!]