42
functionallanguagelikeML(Milner,Tofteetal.1990;MilnerandTofte1991)oranalgebraic
specificationlanguage(Bergstra,Heeringetal.1989).Forthegenerallevelofdiscussionin
thischapterweshallnotneedaformaldefinitionofdatatype,beyondthegenericnotionof
structureddatathatmustsatisfysomeadditionalconstraints.Weshallgenerallyignorethe
distinctionbetweentypesandtypeconstructors,andthetypesweshallconsider,likese-
quence,orcell,areinfacttypeconstructors(fortypeslikesequenceofintegers,string-
containingcell,etc.).Typeconstructorsareverygeneral,andcorrespondcloselytothe
kindsofgeneric“container”objectsusedinmanyobject-orienteddesigns.Thisgenericity
accountsforthefocusontypeconstructors,sincetheycoveraverywiderangeofpotential
application.Whiletherearemanyexamplesofinterestingtype-specificoperationsweshall
notconsidertheseinanydetailhere.
Thesimplesttypeofdataobjectisasinglecellthatcanholdsomeparticularvaluegiven
somehistory.Therearetwosortsofoperationthatcanbedefinedonsuchanobject.Ifthe
typeofthecontaineddataisignored,onlyachange-valueoperationmakessenseonacell.
Ifthetypeofthecontaineddataisknown,type-specificoperationsmightapply.Forexam-
ple,anintegercouldbesubjectedtoarithmeticoperationsthatupdateitsvalue,e.g.,incre-
ment,add20,ordouble.Astringmightbesubjectedtooperationslikechangecase,append
text,orstringreplacement.Palimpsestdoesnotaddressthequestionofrepresentingsuch
operations,thoughsomeextensionmightbepossible.
Onceweleavethecellbehind,wemoveintothebroaderrealmofcompositedatastruc-
turesingeneral.Thinkofacompositestructureasasetofcellswithaccessfunctions(possi-
blyaugmentedwithextraargumentstoserveasaddresseswithinthecomposite).Anaccess
functionreturnseitheranotherstructure,orthecontentsofaparticularcell.Astructure
mayconstraintherelationshipsofcellsinarbitraryways.Forinstance,anarraymighthave
afixednumberofcells,accessibleonlybyfunctionsthattakeaddressesintheformofnum-
berswithinafixedrange.
43
Operationscanbedividedintoseveraltypesintermsofthissimplemodel.Someopera-
tionsjustchangethecontentsofparticularcells.Wecanlumptogetherthevarioustype-
specificoperationsonthecontentcells,andconsiderthemassubtypesofagenericchange
valueoperation.Anoperationcanalsochangethepropertiesoftheaddressingfunctionfora
datastructure.Forinstance,asortarrayoperationchangesonlythelocationsofthecells(or
theircontents),essentiallyrearrangingthecontentsofthecomposite.Otheroperationsmay
addnewcellstothestructure,whileothersmayremovecellsfromthestructure.Insertand
deleteoperationsonlistsareperhapsthecanonicalexample.
Onecriticalwayinwhichdatatypeandoperationaldefinitionsinteractisintheareaof
datastructureinvariantsthatmayneedtobeenforcedforadatastructuretobevalid.Any
editingoperationsmaysomehowaffectadatastructure’srequiredinvariants,andthusthe
representationofpermissibleoperations.Asortedlist,forinstance,wouldneednolocation
foraninsertionoperation,andindeed,ifonewasused,conflictswouldbemorelikely,as
separatepositionalinsertionswouldbeveryunlikelytosatisfythesortinginvariant.Itis
evenpossibleforanoperationtoimposeaninvariantonastructure.Thesortlistexample
mentionedpreviouslymightcreateanewinvariantthatwouldautomaticallyaffectthere-
sultsofanyoperationsinahistorythatcontainsit.Itwouldalsohaveapotentialconflict
withothersortingoperationsonthesamestructure.
2.3 Change-completenessandversion-completeness
Oncetheparticularoperationsrequiredforagivendatastructureandupdatepattern
havebeenselected,theissueremainsofhowthosechangesaretointeractandbeorganized
intohistories.Thissectionconsiderssomeofthehigh-levelissuesofchange-changeinterac-
tioninhistories,potentialconflictsanddifferentpossibilitiesforresolution.Theexamples
ofoperationsinthediscussionareconcretelyanchoredintheproblemofrepresentingse-
Previous Page Next Page