50
Perhapsthemostcriticalfacttonoticeisthatthefrozenvariationsofdynamicopera-
tionsarenotactuallyuseful.Thereissomesmallutilityinfrozenmoveandcopy,butfor
morecomplexoperations,thefrozenversionsarenotveryinteresting.Furthermore,unless
youconsiderdynamicoperations,allthefrozenoperationscanbesimulatedbyappropriate
compositionsofsimpleinsertionanddeletionoperations.Evenmoveandcopyonlychange
thespaceefficiencyofhistories,buthavenoactualeffectontheexpressivepowerofthose
histories.Andofcourse,aswejustnoted,whileversion-completenessissatisfiedbyanyset
offrozenoperations,change-completenessisonlyavailablewhendynamicoperationscanbe
represented.
2.6 Typesofdynamicoperation
Fortheforegoingreasons,differentiationisreallyonlyfoundinthedynamicoperations.
Howeverthereareanumberofinterestingdistinctionswithinthedynamicoperations,and
theseaffectthepotentialconflictsbetweenoperations.Thedistinctionsbetweencontent-
independent,permutationalandcontent-dependentoperationsseparatedthembytheextent
towhichtheydependontheactualcontentofthedatathattheyaffect.
Contentindependentoperationshaveaneffectthatisalwaysthesame,whateverthe
contentsofthesequenceare.Insertanddeletearenoteditingoperationswhoseopera-
tioninanysensedependsontheactualdatainthesequence;deletionsarenotcondi-
tionalonthestateoftheregionslatedfordestruction,norareinsertionsdependenton
thecontentsneartheinsertionpoint.
Permutationaloperationslikemoveandcopy(sometimescalledclone)rearrangeexisting
portionsofasequence.Theexactstringinsertedbyacopyoperationchangeswiththe
contentofthesourceregion,butinaminimalway,sincethatcontentissimplydupli-
catesatanotherlocation.Anykindofoperationthatsimplypermutesorduplicatesthe
elementsofasequencewithoutlookingatthecontentsofthatsequence,isrepre-
51
sentableasacompositionofoperationslikemoveandcopyortransposeandcopy.
2
In-
formally,permutationaloperationsaffectonlytheaddressspaceofacomposite.
Content-dependentoperationsareoneswhosefunctiondependsontheactualvalues
storedinacomposite.Likepurelypermutationaloperations,theymaydependonstruc-
turalpropertiesofacomposite,buttheyaredifferentinkind,becauseoftheireffect
dependsontheactualitemsstoredinthesequence.Examplesareoperationslikesort
paragraphs,transformcharacter-encoding,orsubstitutestring.Theymayonlyaffecta
smallregionofasequence,buttheyfundamentallydependontheexactdatastoredin
thatsequence.Thescopeoftheseoperationsmayalsovaryfromalocalscope,asinthe
sortingasetorparagraphs,toaglobalscopeencompassingtheentirecomposite.This
kindofglobaloperationmightrecordaglobalchangeorasortingconstraintthatshould
beappliedtoasharedobjectinapersistentway.Editinginterfacesthatsupportsuch
operationshavebecomewidelyavailableingraphicaleditorslikePhotoshop,whichcan
saveeditsandintermediatestatesofapictureandreapplythematalatertime.Photo-
shopretainsastaticrecordofallchangesappliedbytheartistandthenallowsthemto
bereapplieddynamicallyonrequest.

2
Forasequence,moveandtransposeareformallyidenticaloperations.Theireffectsarethesame,
butmovedistinguishesoneofthetwotransposedsectionsasthe“onebeingmoved”.Thishasimpli-
cationsformerge,asitprovidesadditionalinformationabouttheuser’sintentinmakinganedit.
Composedtranspositionsarecapableofgeneratingallthepermutationsofasequence.Wehavenot
discussedthepossibilityofmovementbetweensequences,butthisisanexampleofausefuland
straightforwardextensionofthesemanticsofmove,andonethatisnotevensensibleforatranspose
operation.Thiskindofsupportisespeciallyimportantwhencomposedsequencesareusedtorepre-
senthierarchicaldocumentstructures.
Previous Page Next Page