158
dest(ID,Where):-operation(ID,move(_,_,Where)),!.
dest(ID,Where):-operation(ID,copy(_,_,Where)),!.
dest_star(ID,Where):-dest(ID,Where).
dest_star(ID,Where):-dest(ID,address([I|_],Index)),dest_star(I,
Where).
%ThefollowingdefinestheorderingonPalimpsestaddresses.The
orderingiswell-
%definedforthelegaladdresses,asupersetoftheaddressesthat
wouldactually
%appearinaP-sequence.
%TheseclausescorresponddirectlywiththedefinitionsinChapter4.
less(address([],0),X):-X\=address([],0).
less(X,address([I|_],_)):-dest_star(I,S),S=X.
less(address([I1],Index1),address([I1],Index2)):-Index1<Index2,
!.
less(A,B):-
first_change_of(A,C1),
first_change_of(B,C2),
C1\=C2,
dest_llb(A,B,D1,D2),less(D1,D2),!.
less(address([I|T1],X1),address([I|T2],X2)):-
less(address(T1,X1),address(T2,X2)),!.
%less_eq/2isthereflexiveclosureofless/2.
less_eq(X,X):-!.
less_eq(X,Y):-less(X,Y).
%Calculatethecausallowerboundfortwoinsertions,sothattheycan
becompared.
%Firstwecalculatethechainofchangesalongourdestinationpath.
destinations(X,[X|T]):-
dest(X,address([I|_],_)),!,
destinations(I,T).
destinations(X,[X]):-
not(dest(X,address([I|_],_))),
!.

159
%Wewantitinorderfromtheinitialchange,totheleafchange.
dest_path(X,Y):-
destinations(X,Z),
reverse(Z,Y).
%wecanthencalculatetheaddressesinthecommonlowerboundofboth
changes.
%Wecalculatethegreatestcommonchangeinbothhistories,andthen
returnthe
%resultoftracingeachaddresstothatparticularchangeonit's
destination
%chain.
%Thesemustexist,andmusthavedifferentindices.
dest_llb(address([I1|T1],Index1),address([I2|T2],Index2),X1,
X2):-
dest_path(I1,P1),
dest_path(I2,P2),
last_common(P1,P2,R),
dest_trace(address([I1|T1],Index1),R,X1),
dest_trace(address([I2|T2],Index2),R,X2).
%Thisfunctiontracesanaddressuptoaparticularchangeinthe
destination
%chain,returningit'sfinalpositionwithinthatchange.
dest_trace(address([I|T],Index),I,address([I|T],Index)):-!.
dest_trace(address([I|T],_),I2,X):-
dest(I,D),
dest_trace(D,I2,X).
%Findthelastcommonelementinapairoflistswithacommonprefix.
last_common([A],[A|T],A).
last_common([A|T],[A],A).
last_common([R,B1|T1],[R,B2|T2],R):-
B1\=B2,!.
last_common([A|T1],[A|T2],R):-
last_common(T1,T2,R).
%well_defined_forchecksthatasetofchangesiserrorfree.It
checksthatall
%pairsofaddressesaretotallyordered,andthattheminimalelement
isNIL.This
%doesn'tguaranteethatsomeothersetofchangesis_not_well-
defined,butit