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

160
%doesprovidethoroughcheckingforsmallexamples.(Giventhe
combinatorics,large
%examplesareoutofthequestion.
well_defined_for(LIST):-
not(ordering_counterexample(LIST,A1,A2)),
not(nil_minimal_counterexample(LIST,A)).
%Ifthereisanelementnotgreaterthannil,thispredicate
determinesitsidentity.
nil_minimal_counterexample(LIST,A):-
legal_address_for(LIST,A),
A\=address([],0),
not(less(address([],0),A)).
%Ifthereisapairofaddressesthatisnotproperlyordered,this
predicatefinds
%them.
ordering_counterexample(LIST,A1,A2):-
legal_address_for(LIST,A1),
legal_address_for(LIST,A2),
A1\=A2,
not(less(A1,A2)),
not(less(A2,A1)).
ordering_counterexample(LIST,A1,A2):-
proper_address_for(LIST,A1),
proper_address_for(LIST,A2),
A1\=A2,
not(less(A1,A2)),
not(less(A2,A1)).
%Thispredicatechecksifachangesetisconflicted.
conflicted(LIST):-
member(X,LIST),
member(A,LIST),
X\=A,
dest(X,Y),
dest(A,B),
Y=B.
%Isaregionoftheaddressspacedeletedbyanychangeinthechange
setS?
deleted(A1,A2,S):-
member(X,S),
operation(X,delete(B,E)),
less_eq(B,A1),