Palimpsest: Change-oriented Concurrency Control for Collaborative Applications Page 168 (168 of 188)

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

Extracted Text (may have errors)

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

Help

154
proper_addresses([1,2,3,4,5,6],ALL),mergesort(ALL,A).
ALL=
[address([3,2,1],1),address([3,2,1],2),address([2,1],1),address([2,1],2
),address([2,1],3),address([3,1],0),address([3,1],1),address([3,1],2),a
ddress([3,1],3),address([3,1],4),address([1],0),address([1],1),address(
[1],2),address([1],3),address([1],4),address([1],5),address([2,4],0),ad
dress([2,4],1),address([2,4],2),address([2,4],3),address([2,6],0),addre
ss([2,6],1),address([2,6],2),address([2,6],3),address([3,4],0),address(
[3,4],1),address([3,4],2),address([3,4],3),address([3,6],0),address([3,
6],1),address([3,6],2),address([3,6],3),address([4],0),address([4],1),a
ddress([4],2),address([4],3),address([6],0),address([6],1),address([6],
2),address([6],3),address([],0)]
A=
[address([],0),address([1],0),address([1],1),address([1],2),address([4]
,0),address([4],1),address([4],2),address([6],0),address([6],1),address
([6],2),address([6],3),address([4],3),address([1],3),address([1],4),add
ress([2,1],1),address([2,1],2),address([2,4],0),address([2,4],1),addres
s([2,4],2),address([2,6],0),address([2,6],1),address([2,6],2),address([
2,6],3),address([2,4],3),address([2,1],3),address([1],5),address([3,1],
0),address([3,1],1),address([3,1],2),address([3,4],0),address([3,4],1),
address([3,4],2),address([3,6],0),address([3,6],1),address([3,6],2),add
ress([3,6],3),address([3,4],3),address([3,1],3),address([3,1],4),addres
s([3,2,1],1),address([3,2,1],2)]
F F F F iii ig g g gu u u ur r r re e e e AAAA....4444:::: TTTTeeeessssttttiiiinnnngggg tttthhhheeee ffffuuuullllllll sssseeeetttt
%Exampleofaglobalconflict
operation(1,insert(address([],0),[a,b,c,d,e])).
operation(2,move(address([1],0),address([1],3),address([1],4))).
operation(3,move(address([1],3),address([1],5),address([1],1))).
F F F F iii ig g g gu u u ur r r re e e e AAAA....5555:::: AAAAnnnn eeeexxxxaaaammmmpppplllleeee wwwwiiiitttthhhh aaaa gggglllloooobbbbaaaallll ccccoooonnnnfffflllliiiicccctttt

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

Previous Page Next Page

Extracted Text (may have errors)

154
proper_addresses([1,2,3,4,5,6],ALL),mergesort(ALL,A).
ALL=
[address([3,2,1],1),address([3,2,1],2),address([2,1],1),address([2,1],2
),address([2,1],3),address([3,1],0),address([3,1],1),address([3,1],2),a
ddress([3,1],3),address([3,1],4),address([1],0),address([1],1),address(
[1],2),address([1],3),address([1],4),address([1],5),address([2,4],0),ad
dress([2,4],1),address([2,4],2),address([2,4],3),address([2,6],0),addre
ss([2,6],1),address([2,6],2),address([2,6],3),address([3,4],0),address(
[3,4],1),address([3,4],2),address([3,4],3),address([3,6],0),address([3,
6],1),address([3,6],2),address([3,6],3),address([4],0),address([4],1),a
ddress([4],2),address([4],3),address([6],0),address([6],1),address([6],
2),address([6],3),address([],0)]
A=
[address([],0),address([1],0),address([1],1),address([1],2),address([4]
,0),address([4],1),address([4],2),address([6],0),address([6],1),address
([6],2),address([6],3),address([4],3),address([1],3),address([1],4),add
ress([2,1],1),address([2,1],2),address([2,4],0),address([2,4],1),addres
s([2,4],2),address([2,6],0),address([2,6],1),address([2,6],2),address([
2,6],3),address([2,4],3),address([2,1],3),address([1],5),address([3,1],
0),address([3,1],1),address([3,1],2),address([3,4],0),address([3,4],1),
address([3,4],2),address([3,6],0),address([3,6],1),address([3,6],2),add
ress([3,6],3),address([3,4],3),address([3,1],3),address([3,1],4),addres
s([3,2,1],1),address([3,2,1],2)]
F F F F iii ig g g gu u u ur r r re e e e AAAA....4444:::: TTTTeeeessssttttiiiinnnngggg tttthhhheeee ffffuuuullllllll sssseeeetttt
%Exampleofaglobalconflict
operation(1,insert(address([],0),[a,b,c,d,e])).
operation(2,move(address([1],0),address([1],3),address([1],4))).
operation(3,move(address([1],3),address([1],5),address([1],1))).
F F F F iii ig g g gu u u ur r r re e e e AAAA....5555:::: AAAAnnnn eeeexxxxaaaammmmpppplllleeee wwwwiiiitttthhhh aaaa gggglllloooobbbbaaaallll ccccoooonnnnfffflllliiiicccctttt

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

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

Previous Page Next Page

Page 13Chapter 1 : Introduction and Overview click to expand contents

Page 50Chapter 2 : The Change-Oriented Perspective on Collaborative Editing click to expand contents

Page 65Chapter 3 : Operations and Conflicts in Sequences click to expand contents

Page 733.3 Operational conflicts click to expand contents

Page 803.4 Persistent addressing click to expand contents

Page 90Chapter 4 : The Palimpsest Model click to expand contents

Page 934.2 Basic Definitions click to expand contents

Page 994.3 A-sequences and P-sequences click to expand contents

Page 112Chapter 5 : Applying and Evaluating the Model click to expand contents

Page 1125.1 Editing histories and version management click to expand contents

Page 122Chapter 6 : Algorithms for P-sequences click to expand contents

Page 1226.1 The VTML model click to expand contents

Page 1376.7 Putting it all together click to expand contents

Page 149Chapter 7 : Architectural Implications click to expand contents

Page 1497.1 A framework architecture click to expand contents

Page 159Chapter 8 : Summary click to expand contents

Extracted Text (may have errors)

Help

loading

Extracted Text (may have errors)