harald@mulga.oz (Harald Sondergaard) (10/14/88)
Occasionally postings appearing in this newsgroup move to expel
difference-lists from the Herbrand Elysium. It is not quite
clear what this means, but the allegation seems to be that they
do not qualify as terms, or are somehow second-class objects.
Perhaps the reason for this discriminating attitude is that
on the surface they promise to represent lists, but when we start
unifying them, they are sometimes not faithful representatives.
Unification of two difference-lists should correspond to unification
of the lists they represent. However, there are cases where this is
not so. Here are two examples that illustrate the problems:
1) The difference-lists nil\nil and a.nil\a.nil are not unifiable.
But the lists they represent, nil and nil, are unifiable.
2) The difference-lists a.X\Y and Z\Z are unifiable.
But the lists they represent, a.X and nil, are not unifiable.
(Note that difficulties with difference-lists are often ascribed to
the occur check problem, but the examples show that they are
independent).
In the light of the above, it is a bit of a miracle that the
"folk" transformation from programs using lists to programs using
difference-lists seems to work. In fact, sometimes it doesn't.
Consider the program
double(X,Y) :- append(X,X,Y). (*)
The transformation yields
double(X,Y) :- double'(X\nil,Y\nil).
double'(X\X',Y\Y') :- app(X\X',X\X',Y\Y').
app(X\Y,Y\Z,X\Z).
Unfolding the calls to double' and app, we get the program
double(nil,nil).
This program is rather different to (*).
This does not mean that difference-lists are second-class
objects. It just means that we must be careful using them in the
"folk" transformation.
A discussion of the problems with using difference-lists
and how they can be avoided by dataflow analysis can be found in:
Marriott, K. & H. Sondergaard,
Prolog program transformation by introduction of difference-lists,
Proc. Int. Computer Science Conf. '88, Hong Kong (1988) to appear.
Preliminary version as TR 88/14, Dept. of Computer Science, Univ.
of Melbourne (1988).
--- Kim Marriott & Harald Sondergaardok@quintus.uucp (Richard A. O'Keefe) (10/15/88)
In article <3002@mulga.oz> harald@mulga.oz (Harald Sondergaard) writes:
[a lot of sensible things about difference lists]
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).
For example, suppose we want to express
double(X, Y) :- append(X, X, Y)
in terms of differences. I would _think_ and write
% double(X0,X, Y0,Y)
% is true when Y0\Y = (X0\X)<>(X0\X)
double(X0,X, Y0,Y) :-
append(DX, X, X0),
append(DX, Y1, Y0),
append(DX, Y, Y1).
and would start my transformation from that, arriving at
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).
without any false steps.
Using difference pairs rather than "difference lists" also tends to
result in more efficient programs, as you aren't all the time unpacking
Front\Back terms and building new ones.harald@mulga.oz (Harald Sondergaard) (10/17/88)
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
lee@munnari.oz (Lee Naish) (10/18/88)
In article <3005@mulga.oz> harald@mulga.oz (Harald Sondergaard) writes: > 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. I have not seen the paper by Zhang and Grant, but I am also of the "unfold" school (I have tried to convert Kim and Harald without success, so far at least :-). Fold/unfold transformations are fairly well understood and provide a good theoretical framework. I think it can be automated quite easily also, as long as the "eureka" steps are known. For the list-> difference list/pair transformation, the first trick (at least to my mind), is to spot occurrences of .... p(...X...), append(X, Y, Z).... where X doesn't appear anywhere else and "fold" this into ....p'(...Y, Z...).... The definition of p' can be obtained from the definitions of p and append. Often this definition can be simplified, using the transitivity of append (another "eureka"), then folded to get a recursive p' predicate which uses difference pairs rather than simple lists. This last step is the problem as far as preserving semantics is concerned. The two versions have the same least model but in the transformed version generally makes p' true in more models of (the completion of) the program. It is a more complex version of replacing p:-fail by p:-p. This causes infinite loops. Goals which where false in all models in the original version (and hence finitely failed if the computation rule was fair) are true in some but not all models in the transformed version (so they loop). Here is what we get with reverse: % original, after simplifying append(E, [A], F), append(F, C, D) reverse'([], A, A). reverse'(A.B, C, D) :- reverse(B, E), append(E, A.C, D). % folded version reverse'([], A, A). reverse'(A.B, C, D) :- reverse'(B, A.C, D). The first version finitely fails with the goal reverse'(X, [a], [b]), assuming a fair computation rule. The second version loops with the same goal. The reason is that there is a (non-Herbrand) model in which an instance of the goal is true. This also explains why O(N) reverse causes loops when run backwards. I (with Kim and Harald) looked for a transformation which preserves all models without much luck. If you use the trick of keeping the "length" of the difference list around it works for some cases (for reverse you get something like the version which calls same_length and can run backwards). For tree traversals, the benefit of difference lists was lost however (the algorithm was O(N^2) due to manipulation of lengths). I tried using integers and "successor" notation and neither seemed to work. Any ideas, anyone? Also if anyone would like to verify my claim that the d-list "fold" style transformation can be automated, I would encourage it (are you listening Richard? :-). lee
ok@quintus.uucp (Richard A. O'Keefe) (10/19/88)
In article <2502@munnari.oz> lee@munmurra.UUCP (Lee Naish) writes: >Also if anyone would like >to verify my claim that the d-list "fold" style transformation can be >automated, I would encourage it (are you listening Richard? :-). I am listening. I am interested. But I am also _busy_. Just one point about the "unfold" approach: the Eureka steps aren't really all that hard to find. Basically, you are looking for a clump of goals which look as though they can be unfolded together, and you usually have to generalise the clump a little bit to stop the unfold steps getting in each other's way.
gerdeman@clio.las.uiuc.edu (10/20/88)
Did something go wrong in the Eureka step here? What does the variable
X do?
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).
Why not write ;
double(X0,Y0,Y):-
double(X0,Y0,Y1,Y1,Y).
double([],Y,Y,Z,Z).
double([E|X1],[E|Y1],Y,[E|Z1],Z):-
double(X1,Y1,Y,Z1,Z).
ok@quintus.uucp (Richard A. O'Keefe) (10/21/88)
In article <16400002@clio> gerdeman@clio.las.uiuc.edu writes: >Did something go wrong in the Eureka step here? NO. >What does the variable X do? It is called for by the original specification. Namely, the INPUT of double/4 is a difference pair as well as the OUTPUT. > double(X0, X, Y0, Y) :- > double(X0, X, Y0, Y1, Y1, Y). The "input" is the "virtual" list X0\X, just as the "output" is the "virtual" list Y0\Y. > double(X, X, Y, Y, Z, Z). Testing whether there is nothing between the first two arguments is the equivalent of testing whether the "virtual" input is empty. >Why not write ; > double(X0,Y0,Y):- > double(X0,Y0,Y1,Y1,Y). Because it wouldn't meet the original specification, that's why not.
johnson@csli.STANFORD.EDU (Mark Johnson) (10/24/88)
Given all the interest in Unfold/Fold, would anyone care to hear about
a toy program I wrote that uses the Unfold/Fold transformation on the
following input clauses to derive the following output? If so, I will
write a short description for the net.
Mark Johnson
Preferred return address: johnson@csc.brown.edu
Input clauses (assertions in database).
string(n(X,Y),S) <- [ string(X,SX), string(Y,SY), append(SX,SY,S) ].
string(X,[X]) <- [terminal(X)].
terminal(a) <- [].
terminal(b) <- [].
revpairwise([],[]) <- [].
revpairwise([A],[A]) <- [].
revpairwise([A,B|Es],Rs) <- [revpairwise(Es,Ms), append(Ms,[A,B],Rs)].
append([],Cs,Cs) <- [].
append([A|As],Bs,[A|Cs]) <- [ append(As,Bs,Cs) ].
Sample Interaction.
fold(string(_,_)).
% string_f(A,B,C) :-
% string(A,D),
% append(D,B,C).
string_f(n(A,B),C,D) :-
string_f(A,E,D),
string_f(B,C,E).
string_f(A,B,[A | B]) :-
terminal(A).
No
fold(revpairwise(_,_)).
% revpairwise_f(A,B,C) :-
% revpairwise(A,D),
% append(D,B,C).
revpairwise_f([],A,A).
revpairwise_f([A],B,[A | B]).
revpairwise_f([A,B | C],D,E) :-
revpairwise_f(C,[A,B | D],E).
Nojohnson@csli.STANFORD.EDU (Mark Johnson) (10/27/88)
I've received a couple of messages expressing interest in my
toy unfold/folder, so here's a longer description.
Here's a description of my little program: please remember that
it is only a first attempt at applying the Unfold/Fold transformation
automatically, and that as I note at the bottom of the article,
I think it can be improved considerably.
Even so, it is capable of performing the following Unfold/Fold transformations
on programs like (naive) reverse, the program "string" shown below,
and other "simple" recursive programs to yield their difference list
counterparts.
string(n(X,Y),S) :- string(X,SX), string(Y,SY), append(SX,SY,S).
string(X,[X]) :- terminal(X).
terminal(a). terminal(b). terminal(c).
It consists of 3 major predicates. To make things simpler, I describe
each predicates' application to naive reverse as a running example:
Example Input program (as assertions in data base).
reverse([],[]) <- [].
reverse([E|Es],Rs) <- [ reverse(Es,Ms), append(Ms,[E],Rs) ].
1. foldDefn(GoalToFold,FoldDef)
This proposes a definition clause FoldDef for the folding process
based on the clauses for GoalToFold. FoldDef is currently computed
by examining the recursive clauses for GoalToFold.
foldDefn(reverse(_,_),FoldDef).
FoldDef = reverse_f(_2,_820,_8)<-[reverse(_2,_14),append(_14,_820,_8)] ;
FoldDef = reverse_f(_2,_0,_8)<-[reverse(_2,_14),append(_14,[_0],_8)] ;
FoldDef = reverse_f(_2,_0,_830,_8)<-[reverse(_2,_14),append(_14,[_0 | _830],_8)] ;
2. unfoldFoldDefn(FoldDef,GoalToFold,Unfoldeds)
This unfolds all instances of the GoalToFold in FoldDef to yield the
unfolded clauses. It also performs some elementary simplifications on
the result.
unfoldFoldDefn(reverse_f(_2,_820,_8)<-[reverse(_2,_14),append(_14,_820,_8)],
reverse(_,_),Unfoldeds).
Unfoldeds = [
reverse_f([],_4,_4)<-[],
reverse_f([_62 | _64],_4,_6)<-
[reverse(_64,_74),
append(_74,[_62],_12),
append(_12,_4,_6)]] ;
3. fold(Unfolded,Folders,Folded)
This folds the body of Unfolded by the bodies of Folders to yield Folded.
Folders includes equivalences which may be useful in the folding process
as well as FoldDef itself.
In our example, note that there is nothing to fold in the first clause of
Unfoldeds. Note the equivalences involving append that are given to the
folder: only the first of these is used here, the second is required when
folding the unfolded body of the FoldDef for the "string" predicate defined
above.
fold(reverse_f([_62 | _64],_4,_6)<-
[reverse(_64,_74),append(_74,[_62],_12),append(_12,_4,_6)],
[ [reverse_f(A1,B1,C1)]<-[reverse(A1,D1),append(D1,B1,C1)],
[append(X,[A|V],W)] <- [ append(X,[A],Y), append(Y, V, W) ],
[append(B,D,X),append(A,X,E)] <- [append(A,B,C),append(C,D,E)] ],
Folded).
Folded = reverse_f([_0 | _2],_8,_10)<-[append(_28,_8,_10),reverse_f(_2,[_0],_28)] ;
Folded = reverse_f([_0 | _2],_8,_10)<-[reverse_f(_2,[_0 | _8],_10)] ;
Folded = reverse_f([_0 | _2],_8,_10)<-[append(_16,[_0 | _8],_10),reverse(_2,_16)] ;
Folded = reverse_f([_0 | _2],_8,_10)<-[reverse_f(_2,_254,_10),append([_0],_8,_254)] ;
Folded = reverse_f([_0 | _2],_8,_10)<-
[append(_16,_254,_10),append([_0],_8,_254),reverse(_2,_16)] ;
Folded = reverse_f([_0 | _2],_8,_10)<-
[append(_28,_8,_10),append(_16,[_0],_28),reverse(_2,_16)] ;
The second of these answers is the preferred one, because it does not contain
either the original program predicate we are trying to redefine, or the
predicate "append".
The program might be improved in the following ways. First, step 1,
ie. choosing a FoldDef, should incorporate the constraint that
the FoldDef actually be capable of computing the relation to be
folded! This would rule out all but the first proposed FoldDef in step 1
of the example above, and more importantly, may prove useful as a way of
generating possible FoldDefs.
Second, the unfolding step (step 2) could be modified so that it
doesn't just do a single unfold of the FoldDef head, but instead
unfolds all goals that contain a "recursive argument" of the FoldDef.
With this extension, the procedure may be able to Unfold/Fold programs
that are more complicated than the simple "one-level" recursive ones
that it can deal with now.