Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!vsi1!altnet!uunet!munnari!mulga!harald
From: harald@mulga.oz (Harald Sondergaard)
Newsgroups: comp.lang.prolog
Subject: Re: In defence of difference-lists.
Summary: Representation (difference-lists or -pairs) is not a problem.
	 However, correctness of the transformation is.
Keywords: Difference-lists, Dataflow analysis, Program transformation.
Message-ID: <3005@mulga.oz>
Date: 17 Oct 88 05:01:03 GMT
References: <3002@mulga.oz> <542@quintus.UUCP>
Organization: Comp Sci, Melbourne Uni, Australia
Lines: 81

In article <542@quintus.UUCP>, ok@quintus.uucp (Richard A. O'Keefe) writes:

> I would like to suggest that most of the trouble comes from trying
> to form a single data structure Front\Back and think of this as a
> list in its own right.  If instead you think in terms of
> "difference PAIRS" -- that is, pairs of arguments to a relation
> which makes a statement about the difference between them -- you
> run into less trouble (or at any rate I do).

We agree that the use of "difference pairs" is preferable, but they
do not really solve our problem.  Our concern is with automatic,
correct transformation of programs using lists to programs using
difference-lists (or difference pairs - it makes no difference).
     There seem to be two approaches to transformation using
difference-lists, "folk" and "unfold" (no, no misprints there :-).
The former is exemplified in Sterling and Shapiro's book, the latter
in a recent ECAI paper by Zhang and Grant.
     The example transformation suggested by Richard seems to be of
the "unfold" school. He transforms

>	double(X0,X, Y0,Y) :-
>		append(DX, X, X0),
>		append(DX, Y1, Y0),
>		append(DX, Y,  Y1).

into

>	double(X0, X, Y0, Y) :-
>		double(X0, X, Y0, Y1, Y1, Y).
>
>	double(X, X, Y, Y, Z, Z).
>	double([E|X1], X, [E|Y1], Y, [E|Z1], Z) :-
>		double(X1, X, Y1, Y, Z1, Z).

which seems to follow the unfold-eureka-fold pattern, the "eureka"
part being the definition of double/6.  Unfortunately, folding is
not a safe transformation in general, as it may introduce or eliminate
infinite computations.  Indeed, this happens in Richard's example.
Whereas with the first definition of double, ?- double(X0,X,nil,nil)
does not terminate on backtracking (after having returned an answer),
with the second definition it does.
     It is interesting to note that for similar reasons, the first
definition of double/4 is not "equivalent" to the original definition
we gave of double/2:

	double(X,Y) :- append(X,X,Y).

We became interested in the "folk" variant because of the
following observations:

(1) Even in the presence of occur checks, unification of
    difference-lists does not mimic unification of lists
    faithfully.

(2) Independently of (1), the "rapid append" used for
    difference-lists is not semantically equivalent to
    the usual append.

(3) In spite of (1) and (2), the "folk" transformation
    seems to work well for the majority of useful list-
    processing programs, "double" being an exception.

(4) Moreover, the "folk" transformation is so simple
    that it can readily be made automatic.

We conclude that correctness is a problem for both schools.
However, an additional problem with the "unfold" approach is
the "eureka" step, which makes it harder to automate.
     Note that difference pairs could just as well be used in
the "folk" variant (Sterling and Shapiro mention this themselves).
However, (1) - (4) would still apply, in particular the conditional
safeness.  It therefore seems that representation is not the crux
of the matter.
     One approach to automating the transformation of programs
that use lists to programs that use difference-lists (or difference
pairs) is to find conditions under which the "folk" transformation
is safe.  Dataflow analysis can then be used to determine whether
the transformation is applicable to a given program. This is the
approach taken in our paper.

-- Kim Marriott & Harald Sondergaard