155
well_defined_for([1,2,3]).
yes
proper_addresses([1,2,3],ALL),mergesort(ALL,A).
ALL=
[address([2,3,1],3),address([2,3,1],4),address([2,3,1],5),address([3,2,
1],0),address([3,2,1],1),address([3,2,1],2),address([3,2,1],3),address(
[2,1],0),address([2,1],1),address([2,1],2),address([2,1],3),address([3,
1],3),address([3,1],4),address([3,1],5),address([1],0),address([1],1),a
ddress([1],2),address([1],3),address([1],4),address([1],5),address([],0
)]
A=
[address([],0),address([1],0),address([1],1),address([3,1],3),address([
3,1],4),address([3,2,1],0),address([3,2,1],1),address([3,2,1],2),addres
s([3,2,1],3),address([3,1],5),address([1],2),address([1],3),address([1]
,4),address([2,1],0),address([2,1],1),address([2,3,1],3),address([2,3,1
],4),address([2,3,1],5),address([2,1],2),address([2,1],3),address([1],5
)]
F F F F iii ig g g gu u u ur r r re e e e AAAA....6666:::: TTTThhhheeee rrrreeeessssoooolllluuuuttttiiiioooonnnn ooooffff tttthhhheeee gggglllloooobbbbaaaallll ccccoooonnnnfffflllliiiicccctttt

156
F F F F iii ig g g gu u u ur r r re e e e AAAA....7777:::: LLLLiiiissssttttiiiinnnngggg ooooffff PPPPrrrroooolllloooogggg tttteeeesssstttt pppprrrrooooggggrrrraaaammmm
%thesepredicatestestthetypeofanoperation,givenitsID.
is_insert(ID):-operation(ID,insert(_,_)).
is_move(ID):-operation(ID,move(_,_,_)).
is_copy(ID):-operation(ID,copy(_,_,_)).
is_delete(ID):-operation(ID,delete(_,_)).
first_change_of(address([X|_],_),X).
%Herewedefinethenotionof"legal"addresses,onesthatmeetthe
%syntacticandoperationtyperestrictionsonthelegalPalimpsest
%addresses.Someoftheserestrictionsactuallycarryimportant
%semanticweight.Thepossibilityofcyclicstructureswhere
%dataisrepeatedlymovedispreventedbythefactthat
%addressesarefiniteinsizeandthatnochange-IDcanappear
%morethanonceinagivenaddress.
legal(address([],0)).
legal(address([I],X)):-valid_index(I,X).
legal(address([I|T],X)):-
operation(I,_),
not(is_insert(I)),
not(is_delete(I)),
legal(address(T,X)).
%Thispredicatetests(andenumerates)thevalidindiceswithinan
insertion.
%Thesearethepositionsofgapsinthesequencethattheinsertion
addstothe
%P-sequenceinquestion.
valid_index(I,Index):-
operation(I,insert(_,SEQ)),
append(A,B,SEQ),
length(A,Index).
%Thispredicatereturnsalegaladdressforagivensetofchanges.On
failureit
%willproduceanotheruntiltheentirelisthasbeenenumerated.
legal_address_for(LIST,A):-
permutation_dropping(LIST,P),
A=address(P,Index),
legal(A).