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).
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,_)),!.
Previous Page Next Page