Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!munnari.oz.au!lee
From: lee@munnari.oz.au (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: A Challenge
Message-ID: <2958@munnari.oz.au>
Date: 29 Dec 89 07:09:52 GMT
References: <11500022@hpldoda.UUCP> <1633@uwm.edu>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Organization: Comp Sci, University of Melbourne
Lines: 124

In article <1633@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>
>This one I think is worth posting, because of the style in addition to its
>being a solution.

In the absence of RAOK, I will make some comments...

>
>:- op(50, xf, good).
>:- op(50, xfx, are_length).
>:- op(50, xfx, is_length).
>
>[] good :- !.
>[Xs | Xss] good :- Xs is_length L, Xss are_length L.
>
>[] are_length _ :- !.
>[Xs | Xss] are_length L :- Xs is_length L, Xss are_length L.
>
>[] is_length 0 :- !.
>[_ | Xs] is_length L1 :- Xs is_length L, L1 is L + 1.
>
>You can replace the clauses with cuts in them by unit-clauses.

Then why put the cuts there???
None of the predicates work when their first argument is a variable.
When their first arguments are non-variables, any decent Prolog system
will use clause indexing the make the cuts redundent (they just make the
code confusing and, if the compiler isn't clever, slower).  The cuts do
prevent some infinite loops but at the cost of *incorrect* failure.

The definition of is_length can be made much more efficient by using an
accumulator (so it is tail-recursive).  It would also be nice if it
could be run backwards (not so easy, but possible).

>>'Same length' is defined by:
>>
>>    same_length([], []).
>>    same_length([_|Xs], [_|Ys]) :-
>>        same_length(Xs, Ys).
>
>same_length(Xs, Ys) :- Xs is_length L, Ys is_length L.

As I mentioned in my previous posting on this topic, representing list
lengths by Prolog integers is bad.  Consider the query
?- same_length([], [a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a]).
Using integers, the length of the second list has to be calculated, then
compared with zero.  Using other representations the query can fail
almost immediately.  It is also easier to make the code work when either
or both lists are input (the code above only works if both lists are
iput, since is_length is not reversible).  This makes good/1 less
flexible.

OK, enough criticism.  Here is a version of good/1 which is guaranteed
to finitely fail if (the existential closure of) the query is false in
all models.  The way to ensure this is to make it a binary program (no
clause body has more than one subgoal).  What we really need is a fair
computation rule, and what we have is Prolog's left to right rule.  If
the program is binary then the computation rule never has a choice and
therefore it must be fair.  Turning a non-binary program into a binary
program is always possible, but it can be a bit tricky to develop a
reasonably efficient version which has the right set of models:

good(Oss) :-
        good1(Oss, L, L).

        % First arg is lists of lists
        % Second arg is length of first list
        % Third arg is length of all subsequent list
good1([], _, _).
good1([].Oss, 0, LO) :-
        good1(Oss, LO, LO).
good1((_.Os).Oss, s(L), LO) :-
        good1((Os).Oss, L, LO).

Unfortunately, this version gets into a loop with the following
(relatively simple) query: ?- good([A, [a], [a,b]]). (Several other
posted "solutions" do also).  The reason is that there is an instance
which is true in a (non-Herbrand) model.

Here is a version which does work, though it is very complicated (and
took ages to write/debug).  There are probably simpler binary programs
with the "right" set of models - the challenge is still open I guess.
Alternatively, there might be non-binary programs which work ok even for
Prolog's computation rule.

	% idea is to scan lists in "diagonal" fashion
	% ie, first N elements of first list are scanned
	% in (about) the same time as the first N-1 elements
	% of the second list and the first element of the
	% Nth list (and the N+1th list is not examined at all
	% until after then).
good(Oss) :-
	good1([], L, Oss, [], [], L).

        % Maybe we could do it with fewer args, but.... 
	% First arg is front of outer list, with
	% elements of inner lists trimmed of diagonally.
	% Second arg is length of all elements.
	% Third arg is tail of original list (the bit not in first
	% arg).
	% Fourth+fifth args accumulate first arg with one more diagonal
	% trimmed off until first arg is scanned completely (need two
	% args to stop list being reversed - first is whole list,
	% second is tail).
	% Sixth arg is length of first element of first
	% arg (if first arg is not []).
good1([], _L, [], [], [], _LT).
good1([], s(L), [], TTs.TTss, [], _LT) :-
	good1(TTs.TTss, L, [], TTssA, TTssA, L).
good1([], L, Os.Oss, TTss, [], _LT) :-
	good1(Os.TTss, L, Oss, TTssA, TTssA, L).
good1([].[], L, Oss, TTss, [], 0) :-
	good1([], L, Oss, TTss, [], 0).
good1((_.TTs).Tss, L, Oss, TTss, TTs.TTssT, s(LT)) :-
	good1(Tss, L, Oss, TTss, TTssT, LT).

Its doesn't seem easy to add control information so this program won't
generate infinite answers but still fails when it can.  It also needs
complex clause indexing to run efficiently (ie, without creating choice
points).

I think I prefer the first version I posted :-).

	lee