157
%%%
%Nowwewilldefinepredicatesfor"proper"addresses.Theseare
addresses
%thatareactuallyinA'(S),selectedaspartofthefinaladdress
spacefor
%aP-sequence.Properaddressesaredefinedintermsofachangeset,
naturally.
proper_address_for(LIST,A):-
legal_address_for(LIST,A),
proper(LIST,A).
proper(LIST,address([],0)).
proper(LIST,address([I],Index)):-
valid_index(I,Index),
!.
proper(LIST,address([I|T],Index)):-
proper(LIST,address(T,Index)),
operation(I,move(A1,A2,_)),
less_eq(A1,address(T,Index)),
less_eq(address(T,Index),A2),
!.
proper(LIST,address([I|T],Index)):-
proper(LIST,address(T,Index)),
operation(I,copy(A1,A2,_)),
less_eq(A1,address(T,Index)),
less_eq(address(T,Index),A2),
!.
%Printallthelegaladdresses.
print_legal_addresses(LIST):-legal_address_for(LIST,A),display(A),
nl,fail.
%Printalltheproperaddresses.
print_proper_addresses(LIST):-proper_address_for(LIST,A),
display(A),nl,fail.
proper_addresses(LIST,R):-findall(X,proper_address_for(LIST,X),
R).
legal_addresses(LIST,R):-findall(X,legal_address_for(LIST,X),R).
%Definethedestfunction.Thisreturnsthetargetaddressofadata-
creating
%change.Thesepossibilitiesareallmutuallyexclusive.
dest(ID,Where):-operation(ID,insert(Where,_)),!.

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|_],_))),
!.