Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!munnari.oz.au!lee
From: lee@munnari.oz.au (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: the great split up
Message-ID: <3178@munnari.oz.au>
Date: 13 Feb 90 05:18:48 GMT
References: <EIVERSON.90Feb11221732@hades.nmsu.edu> <3176@munnari.oz.au>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Distribution: comp
Organization: Comp Sci, University of Melbourne
Lines: 52

In article <3176@munnari.oz.au> I wrote:
>built_template(Cat, TS, TA, TB) :-
>	half_length(Cat, HLen),
>	built_template_len(HLen, Cat, TS, TA, TB).

As Richard has pointed out, its possible to halve things without
building a separate representation of half the length.  This is how
build_template (built was a typo) can be coded:

        % this version uses halving technique pointed out
        % by ROK - Cat is uses as a representation of its
        % length, as well as being used for its elements
build_template(Cat, TS, TA, TB) :-
        build_template_len(Cat, Cat, TS, TA, TB).
 
build_template_len([], Cat, TS, [], TS) :-
       append(Cat, _Tail, TS).
build_template_len([_], C.Cat, C.TS, [C], TB) :-
       append(Cat, _Tail, TS).
build_template_len(_._.Len, C.Cat, C.TS, C.TA, TB) :-
       build_template_len(Len, Cat, TS, TA, TB).

The disadvantage of this coding is that with first argument, top level
functor indexing only, a choice point is created for each call (except
the last, for even length lists), and a choice point is left on the
stack for odd length lists.

The extra choice point can be removed by adding a cut to the second clause,
(as Richard did), but the code is still inefficient.

If your Prolog system allows fancier indexing (so the second and third
clauses can be distinguished) then no choice points are created, and the
cut is unnecessary.  In NU-Prolog, the follwing when declarations will
do the trick:

?- build_template_len([], _, _, _, _) when ever.
?- build_template_len(_.Len, _, _, _, _) when Len.

In systems without fancy indexing its best to rewrite the code so there
are two procedures, each one being indexed properly:

build_template_len([], Cat, TS, [], TS) :-
       append(Cat, _Tail, TS).
build_template_len(_.Len, C.Cat, C.TS, C.TA, TB) :-
       build_template_len_1(Len, Cat, TS, TA, TB).

build_template_len_1([], Cat, TS, [], TS) :-
       append(Cat, _Tail, TS).
build_template_len_1(_.Len, Cat, TS, TA, TB) :-
       build_template_len(Len, Cat, TS, TA, TB).

	lee