LaboratoiredeM´ethodesInformatiques
ComputationinSpace
&
SpaceinComputation
Jean-LouisGiavitto,OliviertMichel,JulienCohen,AntoineSpicher
email(s):[giavitto,michel,acohen,aspicher]@lami.univ-evry.fr
RapportdeRecherchenoxx-2004
Aoˆut2004
CNRS–Universit´ed’EvryVald’Essonne
523,PlacedesTerrassesdel’agora
F–91000EvryFrance
ComputationinSpaceandSpaceinComputation
Jean-LouisGiavitto,OlivierMichel,JulienCohen,AntoineSpicher
´LaMI∗–CNRS–Universit´ed’Evry–Genopole
(draftpaper)
TheAnalyticalEngineweavesalgebraicpatternsjustastheJacquardloomweavesflowersandleaves.
AdaLovelace
1GoalsandMotivations
Theemergenceoftermslikenaturalcomputing,mimeticcomputing,parallelproblemsolvingfromnature,bio-inspiredcomputing,neurocomputing,evolutionarycomputing,etc.,showstheneverendinginterestofthecomputerscientistsfortheuseof“naturalphenomena”as“problemsolvingdevices”ormoregenerally,asafruitfulsourceofinspirationtodevelopnewprogrammingparadigms.Itisthelattertopicwhichinterestsushere.Theideaofnumericalexperimentcanbereversedand,insteadofusingcomputerstosimulateafragmentoftherealworld,theideaistouse(adigitalsimulationof)therealworldtocompute.Inthisperspective,theprocessesthattakeplaceintherealworldaretheobjectsofanewcalculus:
descriptionoftheworld’slaws
stateoftheworld
parametersofthedescription
simulation
=program
=dataoftheprogram=inputsoftheprogram=thecomputation
Thisapproachcanbesummarizedbythefollowingslogan:“programminginthelanguageofnature”andwaspresentsincetheverybeginningofcomputersciencewithnameslikeW.PittsandW.S.McCulloch(formalneurons,1943),S.C.Kleene(inspiredbythepreviousforthenotionoffinitestateautomata,1951),J.H.Holland(connectionistmodel,1956),J.VonNeumann(cellularautomata,1958),F.Rosenblatt(theperceptron,1958),etc.
Thisapproachoffersmanyadvantagesfromtheteaching,heuristicandtechnicalpointsofview:itiseasiertoexplainconceptsreferringtorealworldprocessesthatareactualexamples;theanalogywiththenatureactsasapowerfulsourceofinspirations;andthestudiesofnaturalphenomenabythevariousscientificdisciplines(physics,biology,chemistry...)haveelaboratedalargebodyofconceptsandtoolsthatcanbeusedtostudycomputations(someconcreteexamplesofthiscrossfertilizationbasedontheconceptofdynamicalsystemaregiveninreferences[6,8,7,49,17]).
Thereisapossiblefallacyinthisperspective:thedescriptionofthenatureisnotuniqueanddiverseconcurentapproacheshavebeendevelopedtoaccountforthesameobjects(e.g.thetwoexamplesgiveninFigure3).Therefore,thereisnotaunique“languageofnature”prescribingauniqueanddefinitiveprogrammingparadigm.However,thereisacommonconcernsharedbythevariousdescriptionsofnatureprovidedbythescientificdisciplines:naturalphenomenatakeplaceintimeandspace1.
´´´umr8042CNRS–Universit´ed’Evry,TourEvry-2,523placedesterrassesdel’agora,91000Evry,France.
Emails:[michel,giavitto,jcohen,aspicher]@lami.univ-evry.fr
1WecannotrefrainustociteKant’sfamoussentencesontheontologicalpreeminenceoftheintuitionofspaceoverallotherobjectperceptions[34,TranscendentalAesthetic,sect.1,A.24,B.39]:Spaceisanecessaryapriorirepresentation,whichunderliesallouterintuitions.Wecanneverrepresenttoourselvestheabsenceofspace,thoughwecanquitewellthinkitasemptyofobjects.Itmustthereforeberegardedastheconditionofthepossibilityofappearances,andnotasa
∗LaMI
1
Inthispaper,weproposetheuseofspatialnotionsasstructuringrelationshipsinaprogramminglanguage.Consideringspaceinacomputationishardlynew:theuseofspatial(andtemporal)notionsisatthebasisofcomputationalcomplexityofaprogram;spatialandtemporalrelationshipsarealsousedintheimplementationofparallellanguages(iftwocomputationsoccuratthesametime,thenthetwocomputationsmustbelocatedattwodifferentplaces,whichisthebasicconstraintthatdrivestheschedulingandthedatadistributionproblemsinparallelprogramming);themethodsforbuildingdomainsindenotationalsemanticshavealsoclearlytopologicalroots,buttheyinvolvethetopologyofthesetofvalues,notthetopologyofavalue.Insummary,spatialnotionshavebeensofarmainlyusedtodescribetherunningofaprogramandnotasmeanstodevelopnewprograms.
Wewanttostressthislastpointofview:wearenotconcernedbytheorganizationoftheresourcesusedbyaprogramrun.Whatwewantistodevelopaspatialpointofviewontheentitiesbuiltbytheprogrammerwhenhedesignshisprograms.Fromthisperspective,aprogrammustbeseenasaspacewherecomputationoccursandacomputationcanbestructuredbyspatialrelationships.Wehopetoprovidesomeevidencesintherestofthispaperthattheconceptofspacecanbeasfertileasmathematicallogicforthedevelopmentofprogramminglanguages.Morespecifically,weadvocatethattheconceptsandtoolsdevelopedforthealgebraicconstructionandcharacterizationofshapes2provideinterestingteaching,heuristicandtechnicalalternativestodevelopnewdatastructuresandnewcontrolstructuresforprogramming.
Therestofthispaperisorganizedasfollows.Section2andsection3provideaninformaldiscussiontoconvincethereaderoftheinterestofintroducingatopologicalpointofviewinprogramming.TheothersectionsaremoretechnicalandfocusontheexperimentalprogramminglanguageMGSusedasavehicletoinvestigateandvalidatethetopologicalapproach.
Section2introducestheideaofseeingadatastructureasaspacewherethecomputationandthevaluesmove.Section3followsthespatialmetaphorandpresentscontrolstructuresaspathspecifications.ThepreviousideasunderlieMGS.Section4sketchesthislanguage.Thepresentationisrestrictedtothenotionsneededtofollowtheexamplesinthenextsections.Section5.1andsection5.2givesomeexamplesinthefieldofdynamicalsystemsimulation.Weintroducethe(DS)2classofdynamicalsystemswhichexhibitadynamicalstructure.Suchakindofsystemsarehardtomodelandsimulatebecausethestatespacemustbecomputedjointlywiththerunningstateofthesystem.Itappearsthatthenotionsdevelopedforthesimulationofdynamicalsystemswithadynamicalstructureenableanewprogrammingstyleandsection6givessomeexamplesoftheexpressiveuseofMGStospecify,inaveryconcisemanner,somefundamentalalgorithmsinvariousareasofcomputerscience.Thepreviousexamplesillustratetheuseofspatialnotionsinthe“programminginthesmall”task[13].Toconcludeinsection7weindicatesomeoftherelatedworkandwementionbrieflysomeperspectivesontheuseofspatialnotionstosupport“programminginthelarge”.
2
DataStructuresasSpaces3
Therelativeaccessibilityfromoneelementtoanotherisakeypointconsideredinadatastructuredefinition:
•Inasimplylinkedlist,theelementsareaccessedlinearly(thesecondafterthefirst,thethirdafterthesecond,etc.).
•Inacircularbuffer,orinadouble-linkedlist,thecomputationgoesfromoneelementtothefollowingortothepreviousone.
determinationdependentuponthem.Itisanapriorirepresentation,whichnecessarilyunderliesouterappearances.Thisstatementjustifiesinsomewaythecurrenttrendtowardsthegeometrizationofphysicssincetheendofthenineteenthcentury[35].
2G.Gaston-Grangerin[29]considersthreeavenuesintheformalizationoftheconceptofspace:shape(thealgebraicconstructionandthetransformationofspaceandspatialconfigurations),texture(thecontinuum)andmeasure(theprocessofcountingandcoordinatization[56]).Inthiswork,werelyonelementaryconceptsdevelopedinthefieldofcombinatorialalgebraictopologyfortheconstructionofspaces[30].
3Theideasexposedinthissectionaredevelopedin[24,19].
2
•Fromanodeinatree,wecanaccessthesons.
•TheneighborsofavertexVinagrapharevisitedafterVwhentravelingthroughthegraph.•Inarecord,thevariousfieldsarelocallyrelatedandthislocalizationcanbenamedbyanidentifier.•Neighborhoodrelationshipsbetweenarrayelementsareleftimplicitinthearraydata-structure.Implementingneighborhoodonarraysreliesonanindexalgebra:indexcomputationsareusedtocodetheaccesstoaneighbor.Thestandardexampleofindexalgebraisintegertupleswithlinearmappingsλx.x±1alongeachdimension(called“VonNeumann”or“Moore”neighborhoods).Thisaccessibilityrelationdefinesalogicalneighborhood.Theconceptoflogicalneighborhoodinadatastructureisnotonlyanabstractionperceivedbytheprogrammerandvanishingattheexecution,butitdoeshaveanactualmeaningforthecomputation.Veryoftenthecomputationindeedcomplieswiththelogicalneighborhoodofthedataelementsanditisfolk’sknowledgethatmostofthealgorithmsarestructuredeitherfollowingthestructureoftheinputdataorthestructureoftheoutputdata.Letusgivesomeexamples.
Insection6.2wepresenttwosortingalgorithms.Thefirstoneisavariationofthewellknownbubble-sort.Inthissortingprocedure,twoadjacentelements(neighbors!)areexchangedifsomeconditionismet.Inthesecondone,tokensmoveverticallyinthecolumnsofanarray.
Therecursivedefinitionofthefoldfunctiononlistspropagatesanactiontobeperformedalongthetraversalofalist.Moregenerally,recursivecomputationsondatastructuresrespectsooftenthelogicalneighborhood,thatstandardhigh-orderfunctions(e.g.primitiverecursion)canbeautomaticallydefinedfromthedatastructureorganization(thinkaboutcatamorphismsandotherpolytypicfunctionsoninductivetypes[40,33]).
Thelistofexamplescanbecontinuedtoconvinceourselvesthatanotionoflogicalneighborhoodisfundamentalinthedefinitionofadatastructure.Sotodefineadataorganization,weadoptatopologicalpointofview:adatastructurecanbeseenasaspace,thesetofpositionsbetweenwhichthecomputationmoves.Eachpositionpossiblyholdsavalue4.Thesetofpositionsiscalledthecontainerandthevalueslabelingthepositionsconstitutethecontent.
Thistopologicalapproachisconstructive:onecandefineadatatypebythesetofmovesallowedinthedatastructure.Anexampleisgivenbythenotionof“GroupBasedFields”orGBFinshort[26,21].Inauniformdatastructure,i.e.inadatastructurewhereanyelementarymovecanbeusedagainstanyposition,thesetofmovespossessesthestructureofamathematicalgroupG.TheneighborhoodrelationshipofthecontainercorrespondstotheCayleygraphofG.Inthispaper,wewilluseonlytwoverysimplegroupsGcorrespondingtothemoves|north>and|east>allowedinatwo-dimensionalgridGrid2andtothemoves|a>,|b>,and|c>allowedinthehexagonallatticeHexafiguredattherightofFig.4.
3ControlStructuresasPaths
Intheprevioussection,wesuggestedlookingatdatastructureasspacesinwhichcomputationmoves.Then,whenthecomputationproceeds,apathinthedatastructureistraversed.Thispathisdrivenbythecontrolstructuresoftheprogram.So,acontrolstructurecanbeseenasapathspecificationinthespaceofadatastructure.Weelaborateonthisideaintotwodirections:concurrentprocessesandmulti-agentsystems.
3.1HomotopyofaProgramRun
ConsidertwosequentialprocessesAandBthatshareasemaphores.ThecurrentstateoftheparallelexecutionP=A||BcanbefiguredasapointintheplaneA×BwhereA(resp.B)isthesequenceofinstructionsofA(resp.B).Thus,therunningofPcorrespondstoapathintheplaneA×B.However,
4A
pointinspaceisaplaceholderawaitingforanargument,L.Wittgenstein,(TractatusLogicoPhilosophicus,2.0131).
3
therearetwoconstraintsonpathsthatrepresenttheexecutionofP.Suchapathmustbe“increasing”becausewesupposethatatleastoneofthetwosubprocessesAorBmustprogress.Thesecondconstraintisthatthetwosubprocessescannotbesimultaneouslyintheregionprotectedbythesemaphores.Thisconstrainthasacleargeometricalinterpretation:theincreasingpathsmustavoidan“obstructionregion”,seeFig.1.Suchrepresentationisknownatleastfromthe1970’sas“progressgraph”[9]andisusedtostudythepossibledeadlocksofasetofconcurrentprocesses.
Homotopy(thecontinuousdeformationofapath)canbeadaptedtotakeintoaccounttheconstraintofincreasingpathsandprovideseffectivetoolstodetectdeadlocksortoclassifythebehaviorofaparallelprogram(forinstanceinthepreviousexample,therearetwoclassesofpathscorrespondingtoexecutionswheretheprocessAorBentersthesemaphorefirst).Referto[28]foranintroductiontothisdomain.
BV(s)P(s)P(s)V(s)BV(s)
V(r)P(r)P(s)
βαP(r)
AV(r)
AP(s)V(s)Figure1:Left:ThepossiblepathtakenbytheprocessA||BisconstrainedbytheobstructionresultingofasemaphoresharedbetweentheprocessesAandB.Right:Thesharingoftwosemaphoresbetweentwoprocessesmayleadtodeadlock(correspondingtothedomainα)ortotheexistenceofa“gardenofEden”(thedomainβthatcannotbeaccessedoutsidefromβanditcanonlybeleaved.)
3.2TheTopologicalStructureofInteractions5
Inamulti-agentsystem(oranobjectbasedoranactorsystem),thecontrolstructuresarelessexplicitandtheemphasisisputonthelocalinteractionbetweentwo(sometimesmore)agents.Inthissection,wewanttoshowthattheinteractionsbetweentheelementsofasystemexhibitanaturaltopology.
Thestartingpointisthedecompositionofasystemintosubsystemsdefinedbytherequirementthattheelementsintothesubsystemsinteracttogetherandaretrulyindependentfromallothersubsystemsparallelevolution.
Inthisview,thedecompositionofasystemSintothesubsystemsS1,S2,...,Snisfunctional:thestatesi(t+1)ofthesubsystemSidependssolelyofthepreviousstatesi(t).However,thedecomposition
ttt
,...,SnforthedecompositionoftheofSintotheSicandependonthetimesteps.SowewriteS1,S2t
tt
systemSattimetandwehave:si(t+1)=hi(si(t))wherethehiarethe“local”evolutionfunctionsof
t
theSi.The“global”states(t)ofthesystemScanberecoveredfromthe“local”statesofthesubsystems:thereisafunctionϕtsuchthats(t)=ϕt(s1(t),...,snt(t))whichinducesarelationbetweenthe“global”
t
evolutionfunctionhandthelocalevolutionfunctions:s(t+1)=h(s(t))=ϕt(ht1(s1(t)),...,hnt(snt(t))).
ttt
ThesuccessivedecompositionS1,S2,...,Sncanbeusedtocapturetheelementarypartsandthet
interactionstructurebetweentheseelementarypartsofS.Cf.Figure2.TwosubsystemsSandSof
tt
SinteractiftherearesomeSjsuchthatS,S∈Sj.TwosubsystemsSandSareseparableifthere
ttt
aresomeSjsuchthatS∈SjandS∈Sjorvice-versa.ThisleadstoconsiderthesetS,calledthe
t
interactionstructureofS,definedbythesmallersetclosedbyintersectionthatcontainstheSj.
ThesetShasatopologicalstructure:Scorrespondstoanabstractsimplicialcomplex.Anabstractsimplicialcomplex[30]isacollectionSoffinitenon-emptysetsuchthatifAisanelementofS,soiseverynonemptysubsetofA.TheelementAofSiscalledasimplexofS;itsdimensionisonelessthatthenumberofitselements.ThedimensionofSisthelargestdimensionofoneofitssimplices.Each
5This
sectionisadaptedfrom[51].
4
nonemptysubsetofAiscalledafaceandthevertexsetV(S),definedbytheunionoftheonepointelementsofS,correspondstotheelementaryfunctionalpartsofthesystemS.Theabstractsimplicialcomplexnotiongeneralizestheideaofgraph:asimplexofdimension1isanedgethatlinkstwovertices,asimplexfofdimension2canbethoughtofasasurfacewhoseboundariesarethesimplicesofdimension1includedinf,etc.
s(0)s(1)
Si1
1S1
s(t)
...
S∈V(S)
S
0S1
Figure2:TheinteractionstructureofasystemSresultingfromthesubsystemsofelementsininteractionatagiventimestep.
4MGSPrinciples
Thetwoprevioussectionsgiveseveralexamplestoconvincethereaderthatatopologicalapproachofthedataandcontrolstructuresofaprogrampresentsomeinterestingperspectivesforlanguagedesign:adatastructurecanbedefinedasaspace(andtherearemanywaystobuildspaces)andacontrolstructureisapathspecification(andtherearemanywaystospecifyapath).
SuchatopologicalapproachisatthecoreoftheMGSproject.Startingfromtheanalysisoftheinteractionstructureintheprevioussection,ourideaistodefinedirectlythesetSwithitstopological
t
structureandtospecifytheevolutionfunctionhbyspecifyingthesetSiandthefunctionshti:
•theinteractionstructureSisdefinedasanewkindofdatastructurescalledtopologicalcollections;
t
•asetoffunctionshtitogetherwiththespecificationoftheSiforagiventarecalledatransformation.
Wewillshowthatthisabstractapproachenablesanhomogeneousanduniformhandlingofseveralcompu-tationalmodelsincludingcellularautomata(CA),latticegasautomata,abstractchemistry,Lindenmayersystems,Paunsystemsandseveralotherabstractreductionsystems.
TheseideasarevalidatedbythedevelopmentofalanguagealsocalledMGS.Thislanguageembedsacomplete,strict,impure,dynamicallyorstaticallytypedfunctionallanguage.Wefocusonthenotionsrequiredtounderstandtherestofthepaper.
4.1Atomicvalues.
Atomicvalues(likeintegers,floats,booleans,strings,symbols...)withtheirusualfunctions,areavailable.SinceMGSisafunctionallanguage,ithasfunctionsasfirst-classvalues.Functionsaredefinedusingtheconstructionfunlikeinfunmax(x,y)=if(x>y)thenxelseyfi.Optionalparameterscanbespecifiedbetweenbrackets:funsucc[inc=1](x)=x+inc.Intheapplicationofthefunction,theseparameterscanbeomittedlikeinsucc(0)whichreturns1orexplicitlyset:succ[inc=3](0)returns3.
4.2TopologicalCollections
ThedistinctivefeatureoftheMGSlanguageisitshandlingofentitiesstructuredbyabstracttopologiesusingtransformations[25].Asetofentitiesorganizedbyanabstracttopologyiscalledatopologicalcollection.Here,topologicalmeansthateachcollectiontypedefinesaneighborhoodrelationinducinganotionofsubcollection.AsubcollectionSofacollectionSisasubsetofconnectedelementsofSandinheritingitsorganizationfromS.Bewarethatby“neighborhoodrelation”wesimplymeanarelationship
5
thatspecifyiftwoelementsareneighbors.Fromthisrelation,acellularcomplexcanbebuiltandtheclassical“neighborhoodstructure”intermsofopenandclosedsetscanberecovered[50].
Atopologicalcollectioncanbethoughtasafunctionwithafinitesupportfromasetofpositions(theelementsofV(S))toasetofvalues(thesupportofafunctionisthesetofelementsonwhichthefunctiontakesawelldefinedvalue).Suchadatastructureiscalledadatafield[18].Thispointofviewisonlyanabstraction:thedatastructureisnotreallyimplementedasafunction.Thisapproachmakesadistinctionbetweenthecontentandthecontainer.Thenotionsofshape[32]andshapetype[15]alsoseparatethesetofpositionsofadatastructurefromthevaluesitcontains.Oftenthereisnoneedtodistinguishbetweenthepositionsandtheirassociatedvalues.Inthiscase,weusetheterm“elementofthecollection”.Letusgiveanexample.AsequencecanbeseenasapartialfunctionN→Value.Thesupportofasequenceoflengthnistheset{0,...,n−1}.ThesetofpositionsNmustbegivenwiththeneighborhoodrelation:iisneighborofjiffj=i+1.
CollectionTypes.Differentpredefinedanduser-definedcollectiontypesareavailableinMGS,in-cludingsets,bags(ormultisets),sequences,CayleygraphsofAbeliangroups(whichincludeseveralunbounded,circularandtwistedgrids),Delaunaytriangulations,arbitrarygraphs,quasi-manifolds[51]andsomeotherarbitrarytopologiesspecifiedbytheprogrammer.Weintroducesomespecificcollectiontypesalongwiththeexamples.
TheMGSinterpreterprovidesadynamicallytypedversionofthelanguage.However,acompilerisunderdevelopmentanditispossibletoenforceastatictypediscipline[10,11].TherearetwoversionsofthetypeinferencesystemsforMGS:thefirstoneisaclassicalextensionoftheHindley-Milnertypeinferencesystemthathandleshomogeneouscollections.Thesecondoneisasofttypesystemabletohandleheterogeneouscollection(e.g.asequencecontainingbothintegersandbooleansisheterogeneous).
Thetypesystemcontainssomeparticulartypesoftheform[τ]ρforthecollectionswhereτisthetypeoftheelementsinsidethecollection,calledthecontenttypeandρisitscontainertypeortopology.Atopologycanbeasymboloftheset{set,bag,seq,...}thatcontainsthepossibletopologiesofacollection,oratopologyvariablethatwewilldenotebytheGreekletterθ.Letusremarkthatatopologyisnotatypeandthatatopologyvariableθcannotbeusedinsteadofatypevariableαandvice-versa.Afunctionfoftype[int]seq→boolisapredicateonsequenceofintegers,[α]seq→boolisapolymorphicpredicatethatactsonanysequenceofelementsandapredicateoftype[α]θisapolytypicpredicatethatactsonanycollection.Theprimitiveemptythatreturnstrueifitsargumentdoesnotcontainanyelementisanexampleofthelatter.
Inordertodealwithheterogeneouscollectionsinoursofttypesystemweusesomeuniontypes,previouslyusedbyotherauthors[1,12,16].Avaluewiththetypeτ1∪τ2haseitherthetypeτ1orthetypeτ2.Knowingthatavaluehasthetypeτ1∪τ2youcannotconcludethatithasthetypeτ1northatithasthetypeτ2.Theinteger1hasthetypeintandhasalsothetypeint∪bool.
BuildingTopologicalCollections.ForanycollectiontypeT,thecorrespondingemptycollectioniswritten():T.ThejoinoftwocollectionsC1andC2(writtenbyacomma:C1,C2)isthemainoperationoncollections.ThecommaoperatorisoverloadedinMGSandcanbeusedtobuildanycollection(thetypeoftheargumentsdisambiguatesthecollectionbuilt).So,theexpression1,1+2,2+1,():setbuildsthesetwiththetwoelements1andd3,whiletheexpression1,1+2,2+1,():bagcomputesabag(asetthatallowsmultipleoccurrencesofthesamevalue)withthethreeelements1,3and3.Asetorabagisprovidedwiththefollowingtopology:inasetorabag,anytwoelementsareneighbors.Tosparethenotations,theemptysequencecanbeomittedinthedefinitionofasequence:1,2,3isequivalentto1,2,3,():seq.
4.3Transformations
TheMGSexperimentalprogramminglanguageimplementstheideaoftransformationsoftopologicalcollectionsintotheframeworkofafunctionallanguage:collectionsarejustnewkindsofvaluesand
6
transformationsarefunctionsactingoncollectionsanddefinedbyaspecificsyntaxusingrules.Trans-formations(likefunctions)arefirst-classvaluesandcanbepassedasargumentsorreturnedastheresultofanapplication.
Theglobaltransformationofatopologicalcollectionsconsistsintheparallelapplicationofasetoflocaltransformations.Alocaltransformationisspecifiedbyarulerthatspecifiesthereplacementofasubcollectionbyanotherone.Theapplicationofarewritingruleσ⇒f(σ,...)toacollections:1.selectsasubcollectionsiofswhoseelementsmatchthepatternσ,2.computesanewcollectionsiasafunctionfofsianditsneighbors,3.andspecifiestheinsertionofsiinplaceofsiintos.
Oneshouldpayattentiontothefactthat,duetotheparallelapplicationstrategyofrules,alldistinctinstancessiofthesubcollectionsmatchedbytheσpatternare“simultaneouslyreplaced”bythef(si).PathPattern.Apatternσinthelefthandsideofarulespecifiesasubcollectionwhereaninteractionoccurs.Asubcollectionofinteractingelementscanhaveanarbitraryshape,makingitverydifficulttospecify.Thus,itismoreconvenient(andnotsorestrictive)toenumeratesequentiallytheelementsofthesubcollection.Suchenumerationwillbecalledapath.
ApathpatternPatisasequenceorarepetitionRepofbasicfilters.AbasicfilterBFmatchesoneelement.Thefollowing(fragmentofthe)grammarofpathpatternsreflectsthisdecomposition:
Pat::=Rep|Rep,Pat
Rep::=BF|BF/exp
BF::=cte|id| wherecteisaliteralvalue,idrangesoverthepatternvariablesandexpisabooleanexpression.Thefollowingexplanationsgiveasystematicinterpretationforthesepatterns: literal:aliteralvaluectematchesanelementwiththesamevalue.Forexample,123matchesanelement withvalue123.emptyelementthesymbol whosepositiondoesnothaveanassociatedvalue.variable:apatternvariableamatchesexactlyoneelementwithawelldefinedvalue.Thevariablea canthenoccurelsewhereintherestofpatternorinther.h.s.oftheruleanddenotesthevalueofthematchedelement.neighbor:b,pisapatternthatmatchesapathwhichbeginsbyanelementmatchedbybandcontinues byapathmatchedbyp,thefirstelementofpbeinganeighborofb.Forsomecollectiontypes,theneighborhoodrelationcanbemademoreprecise.Forexample,inatwo-dimensionalgrid,onemaylookonlyforaneighboralongthe|north>direction.Thisissimplywrittenb|north>p.guard:p/expmatchesapathmatchedbypwhenthebooleanexpressionexpevaluatestotrue.For instance,x,y/y>xmatchestwoneighborelementsxandysuchthatthevalueassociatedtoyisgreaterthanthevalueassociatedtox.Elementsmatchedbybasicfiltersinarulearedistinct.Soamatchedpathiswithoutself-intersection.Theidentifierofapatternvariablecanbeusedonlyonceasabasicfilter.Thatis,thepathpatternx,xisforbidden.However,thispatterncanberewrittenforinstanceas:x,y/y=x. RightHandSideofaRule.Therighthandsideofarulespecifiesacollectionthatreplacesthesubcollectionmatchedbythepatterninthelefthandside.Thereisanalternativepointofview:becausethepatterndefinesasequenceofelements,therighthandsidemaybeanexpressionthatevaluatestoasequenceofelements.Then,thesubstitutionisdoneelement-wise:elementiinthematchedpathisreplacedbytheelementiinther.h.s.Thispointofviewenablesaveryconcisewritingoftherules. Forsomecollectiontypesitispossibletoreplaceasubcollectionbyacollectionwithadifferentshape.Suchcollectionsaretermedasleibnizianandareopposedtonewtoniancollections6.Examples 6This termcomesfromthedifferentvisionsofspaceNewtonandLeibnizhad[19]. 7 ofleibniziancollectionsincludesets,bags,sequences,graphs...Atwo-dimensionalgridisanexampleofanewtoniancollection:onecannotreplaceanarbitrarysubsetofagridbyasubsetwithanothershapewithoutdestroyingthe2Dgridstructure. AVerySimpleTransformation.Themapfunctionwhichappliesafunctiontoeachelementofacollectionisanexampleofasimpletransformation: transmap[f=\\z.z]={ x=>f(x)} Thistransformationismadeofonlyonerule.Thesyntaxmustbeobvious(thedefaultvalueoftheoptionalparameterfistheidentitywrittenusingalambda-notation).Thistransformationimplementsamapsinceeachelementeofthecollectionismatchedbythepatternxandwillbereplacedbyf(e).Thistransformationhastype(α→β)→[α]θ→[β]θandcanbeappliedtoanycollectionirrespectivelytoitstopology.Suchfunctionsaresaidtobepolytypic[33].Polytypismcomes“forfree”whenconsideringdatastructuresinauniformframework. 5Simulation Inthissection,weshowthroughvariousexamplestheabilityofMGStoconciselyandeasilyexpressthestateofadynamicalsystemanditsevolutionfunction.MoreexamplescanbefoundontheMGSwebpage7andinclude:cellularautomata-likeexamples(gameoflife,snowflakeformation,latticegasautomata...),variousresolutionsofpartialdifferentialequations(likethediffusion-reaction`alaTuring),Lindenmayersystems(e.g.themodelingoftheheterocystsdifferentiationduringAnabaenagrowth),themodelingofaspatiallydistributedsignalingpathway,theflockingofbirds,themodelingofatumorgrowth,thegrowthofameristeme,thesimulationofcoloniesofantsforagingforfood,etc. 5.1 5.1.1 ThemodelingofDynamicalSystems HeatDiffusioninaRod. ∂H∂tH =α∂∂x2that 2 WewillsimulatethediffusionofheatHthroughathinrod.TheparabolicPDE describesthediffusionprocesscanbediscretized: H(x,t+∆t)=(1−2c)H(x,t)+c(H(x−1,t)+H(x+1,t)) whereH(x,t)isthetemperatureoftheelementxofthesequenceattimetandtheparametercdependsondiffusioncharacteristicsαoftherod(cislessthan0.5).Someboundaryconditionscanbeaddedtothemodel.WecaneasilywritethecorrespondingMGSprogramthatcomputestheevolutionofthetemperatureintherod: trans xxx} diffuse[c=0.25,Hleft=0,Hright=0]={/(left(x)== ThetwofirstrulesdealwiththeboundaryconditionsgivenbyparametersHleftandHright.Theoperatorsrightandleftgiveaccesstotheneighborsinasequence.Thespecialvalue Inthepreviousmodel,asequenceisusedtodescribethediscretizedrod.Bagscanalsobeusedtorepresentthesamephysicalphenomenabyusingadifferentpointofview.Therodisstilldiscretizedas 7http://mgs.lami.univ-evry.fr 8 Figure3:Resultoftheheatdiffusionwithtwodifferentmodels.Theboundariesoftherodarekeptat0◦C.In theinitialcondition,onlythemiddlethirdhasanonzerotemperature.Inthetwodiagrams,thetimegoesfrombacktofront. asequenceofsmallboxesbutthistimeweadopta“Individual-basedModelling”approach.Eachboxcontainssomeparticlesthatrepresentaquantumofheat.Wecanrepresenteachquantumofheatintheboxxbyanoccurrenceoftheintegerxinthebag.Inthisway,thestateoftherodisabagofintegers.Thecardinalofthebagrepresentsthetotalamountofheatintherod. Thecorrespondingevolutionfunctionissimpletostate:aquantumofheatinaboxxisallowedtojumpinoneoftheneighborboxesortostayinitscurrentbox.ThecorrespondingtransformationistrivialinMGS: transdiffuse={ n=>n+random(-1,0,1) } Twoothersrulescanbeaddedtodealwiththeboundaryconditions.Thefunctionrandomchoosesrandomlyoneofitsargument.Theprobabilityofchoosinganargumentinsteadofanotherisrelatedtotheparametercinthecontinuousformulation.Indeedcistheprobabilityforaparticletochangeitsstate.Asaconsequenceandbecauseeachboxhastwoneighbors,theprobabilitytostayinthesamestateis1−2casitappearsinthecontinuousequation.TherightplotinFig.3presentsthestochasticversionoftheheatdiffusion.Inthissimulation,theyare2500quantaofheatin30boxes.5.1.2 TheDLAEvolutionFunctioninMGS DiffusionLimitedAggregation,orDLA,isafractalgrowthmodelstudiedbyT.A.WittenandL.M.Sander,intheeighties.Theprincipleofthemodelissimple:asetofparticlesdiffusesrandomlyonagivenspatialdomain.Initiallyoneparticle,theseed,isfixed.Whenamobileparticlecollidesafixedone,theysticktogetherandstayfixed.Forthesakeofsimplicity,wesupposethattheysticktogetherforeverandthatthereisnoaggregateformationbetweentwomobileparticles. ThisprocessleadstoasimpleCAwithanasynchronousupdatefunctionoralatticegasautomatawithaslightlymoreelaborateruleset.ThissectionshowsthattheMGSapproachenablesthespecificationofasimplegenerictransformationthatcanactonarbitrarycomplextopologies. ThetransformationdescribingtheDLAbehaviorisreallysimple.Weusetwosymbolicvalues‘freeand‘fixedtorepresentrespectivelyamobileandafixedparticle.Therearetworulesinthetransfor-mation: 1.thefirstrulespecifiesthatifadiffusingparticleistheneighborofafixedseed,thenitbecomesfixed(atthecurrentposition); 9 Figure4:Fromlefttoright:thefinalstateofaDLAprocessonatorus,achesspawn,aKlein’sbottleand anhexagonalmeshes.ThechesspawnishomeomorphictoasphereandtheKlein’sbottledoesnotadmitaconcretizationinEuclideanspace.Thesetwotopologicalcollectionsarevaluesofthequasi-manifoldtype.SuchcollectionarebuildusingG-map,adata-structurewidelyusedingeometricmodeling[38].ThetorusandthehexagonalmeshareGBFs. 2.thesecondonespecifiestherandomdiffusionprocess:ifamobileparticleisneighborofanemptyplace(position),thenitmayleaveitscurrentpositiontooccupytheemptyneighbor(anditscurrentpositionismadeempty).Notethattheorderoftherulesisimportantbecausethefirsthaspriorityoverthesecondone.Thus,wehave: transdla={ ‘free,‘fixed‘free, =>=> ‘fixed,‘fixed Thistransformationispolytypicandcanbeappliedtoanykindofcollection,seeFig.4forafewresults. 5.2ThemodelingofDynamicalSystemswithaDynamicalStructure (DS)2 Thepreviousexamplesareexamplesofcontinuousordiscrete“classicaldynamicalsystems”.Wetermthem“classical”becausetheyexhibitastaticstructure:thestateofthesystemisstaticallydescribedanddoesnotchangewiththetime.Thissituationissimpleandarisesofteninelementaryphysics.Forexample,afallingstoneisstaticallydescribedbyapositionandavelocityandthissetofvariablesdoesnotchange(evenifthevalueofthepositionandthevalueofthevelocitychangeinthecourseoftime).However,insomesystems,itisnotonlythevaluesofstatevariables,butalsothesetofstatevariablesand/ortheevolutionfunction,thatchangesovertime.Wecallthesesystemsdynamicalsystemswithadynamicstructurefollowing[22],or(DS)2inshort.Aspointedoutby[20],manybiologicalsystemsareofthiskind. ToillustratetheuseofMGSinthesimulationof(DS)2,wewanttomodelagrowingsheetofinteractingcells.Wetakeintoaccountthreephenomena:thetensionandpressurebetweencells,thediffusionandreactionoftwochemicalsandthecelldivisionthatisdrivenbytheconcentrationofoneofthechemicals.Theproblemisthat,duetothecellmovementsanddivision,theimmediateneighborsofacellevolvewiththetime.AnillustrationoftheresultisgiveninFig.5. WeuseaDelaunaytriangulationtocomputetheneighborhoodofthecells.TheDelaunaytriangula-tionofasetofpointsisacollectionofedgessatisfyingan”emptycircle”property:foreachedgewecanfindacirclecontainingtheedge’sendpointsbutnotcontaininganyotherpoints.InMGS,westartbydefiningthetypeofthecollectionthatrepresentsacell: recordMecaCell=x,y,z,vx,vy,vz,fx,fy,fz;;recordBioCell=a,b,da,db,c;;recordCell=MecaCell+BioCell;; 10 specifytworecordtypes,thefirsthavingthefieldsx,y,z,etc.,representingthepositionofthecellanditsvelocityandacceleration;thesecondhavingthefieldsa,b,etc.,representingthetwodiffusingchemicalandtheirfirstderivative.TherecordCellcontainsthefieldsofbothMecaCellandBioCell. WethendefineaDelaunaycollectiontype.Thespecification: collectiondelaunay(3)D3= \\e.ifCell(e)then(e.x,e.y,e.z)else?(\"badelementforD3type\")fi;;definesanewDelaunaycollectiontypein3dimensions.Thetype,calledD3,isparameterizedbyauserfunctionthatextractsfromeachelementinthecollection,anabstractcoordinate.Inthisexample,thecoordinatearesimplystoredinthevaluethatrepresentsacellandthefunctionsimplychecksthatthecell’svaluehasacorrecttypeandreturnsitscoordinate(asasequenceof3floats). ThemovementofthecellsresultsfromtheelasticandviscousforcesintheNewton’sequationofdynamics: d2FdFm.2=Felastic+Fviscous=−k(L−L0)−µdtdt Thespringtermhasaconstantk,therestlengthisL0andµisaviscousparameter.Thisequationisintegratedforeachcellbyasimplemethodimplementedbythetransformation: transMeca={ e=>letf=neighborsfold(sum(e),{fx=0,fy=0,fz=0},e) ine+{x=e.x+dt*e.vx, ... vx=e.vx+dt*f.fx,... fx=f.fx,} } Theprimitiveneighborsfolditeratesovertheneighborsofacelle.Itcomputesthesumoftheforceinteractionbetweenacellcandtheneighborcells;thissumisthenusedtoupdatethestateofthecellc.Theoperator+onrecordsisanasymmetricmerge:thefieldsofr=r1+r2arethefieldsofbothr1andr2andr.ahasthevalueofr2.aifaisafieldofr2elsethevalueofr1.a. Thediffusionandreactionofthetwochemicalsismodeledasasimplifiedversion[55]oftheTuring’sdiffusion-reactionmodel[54].Theevolutionofthetwochemicalsisalsoimplementedwithonlyonetransformation,usingalsoaneighborsfoldtocomputetheLaplacianoftheconcentrations. Atlast,whentheconcentrationofbincreasesaboveagivenlevel,thecelldivides,whichisimplementedbythetransformation: Figure5:Fourstepsinthegrowthofasheetofcells.Thecolorofacelliscorrelatedwiththeconcentrationof thechemicalthattriggersthecelldivision(blackcellwilldivide). 11 transDivision={ e/e.b>lsplit=>(e+{a=e.a/3,b=e.b/3}), (e+{a=e.a/3,b=e.b/3,x=noise(e.x),y=noise(e.y),...}) } Thecoefficient3usedtocomputetherepartitionoftheconcentrationinthedaughtercellsisarbitrary;thefunctionnoisedisturbsalittleitsargumentbyaddingaverysmallrandomquantity. 6ProgrammingintheSmall:AlgorithmicExamples ThetwoprevioussectionsshowtheadequationoftheMGSprogrammingstyletomodelandsimulatevariousdynamicalsystems.However,itappearsthattheMGSprogrammingstyleisalsowellfittedfortheimplementationofalgorithmictasks.Inthissection,weshowsomeexamplesthatsupportthisassertion.MoreexamplescanbefoundontheMGSwebpageandinclude:theanalysisoftheNeedham-Schroederpublic-keyprotocol[42],theEratosthene’ssieve,thenormalizationofbooleanformulas,thecomputationofvariousalgorithmsongraphslikethecomputationoftheshortestdistancebetweentwonodesorthemaximalflow,etc. 6.1GammaandtheChemicalComputingMetaphor InMGS,thetopologyofamultisetisthetopologyofacompleteconnectedgraph:eachelementistheneighborofanyotherelement.Withthistopology,transformationscanbeusedtoeasilyemulateaGammatransformations[3,4].TheGammatransformationontheleftissimplytranslatedintotheMGStransformationontheright: M=dotransM={ rpx1,...,xnx1,...,xn =⇒ ifP(x1,...,xn)/P(x1,...,xn)byf1(x1,...,xn),...,fm(x1,...,xn)=>f1(x1,...,xn),...,fm(x1,...,xn)}andtheapplicationM(b)ofaGammatransformationMtoamultisetbisreplacedinMGSbythe computationofthefixpointiterationM[iter=‘fixpoint](b).Theoptionalparameteriterisasys-temparameterthatallowstheprogrammertochooseamongstseveralpredefinedapplicationstrategies:f[iter=‘fixpoint](x0)computesx1=f(x0),x2=f(x1),...,xn=f(xn−1)andreturnsxnsuchthatxn=xn−1. Asaconsequence,theconciseandelegantprogrammingstyleofGammaisenabledinMGS:refertotheGammaliteraturefornumerousexamplesofalgorithms,fromknapsacktothemaximalconvexhullofasetofpoint,throughthecomputationofprimenumbers.SeealsothenumerousapplicationsofmultisetrewritingdeveloppedintheprojectsElan[53]andMaude[52]. OnecanseeMGSas“Gammawithmorestructure”.However,onecannotethatthetopologyofamultisetis“universal”inthefollowingsense:itembedsanyotherneighborhoodrelationship.So,itisalwayspossibletocode(atthepriceofexplicitcodingthetopologicalrelationintosomevalueinspectedatrun-time)anyspecifictopologyontopofthemultisettopology.Weinterpretthedevelopmentof“structuredGamma”[14]inthisperspective. 6.2TwoSortingAlgorithms Akindofbubble-sortisstraightforwardinMGS;itissufficienttospecifytheexchangeoftwonon-orderedadjacentelementsinasequence,seeFig.6.Thecorrespondingtransformationisdefinedas: transBubbleSort={ x,y/x>y⇒y,x } ThetransformationBubbleSortmustbeiterateduntilafixpointisreached.Thisiseasilydoneusingapredefinedoptionalparameteriter:f[iter=‘fixpoint](x0)computesx1=f(x0),x2=f(x1),...,xn=f(xn−1andreturnsxnsuchthatxn=xn−1. 12 Thisisnotreallyabubblesortbecauseswappingofelementshappenatarbitraryplaces;henceanout-of-orderelementdoesnotnecessarilybubbletothetopinthecharacteristicway. Beadsortisanewsortingalgorithm[2].Theideaistorepresentpositiveintegersbyasetofbeads,likethoseusedinanabacus.Beadsareattachedtoverticalrodsandappeartobesuspendedintheairjustbeforeslidingdown(anumberisreadhorizontally,asarow).Aftertheirfalls,therowsofnumbershavebeenrearrangedsuchasthesmallernumbersappearsontopofgreaternumbers,seeFig.6.Thecorrespondingone-lineMGSprogramisgivenbythetransformation: transBeadSort={ empty|north>1⇒1,empty } ThistransformationisappliedonaGrid2.Theconstantemptyisusedtogiveavaluetoanemptyplaceandtheconstant1isusedtorepresentanoccupiedcell.Thel.h.s.oftheonlyruleofthetransformationBeadSortselectsthepathsoflengthtwo,composedbyanoccupiedcellatnorthofanemptycell.Suchapathisreplacedbyapathcomputedinther.h.s.oftherule.Ther.h.s.inthisexamplecomputesapathoflengthtwowiththeoccupiedandtheemptycellswapped. x,y / x>y132434 123 2312 4 12y,x34Figure6:Left:Bubblesort.Right:Beadsort[2]. 6.3HamiltonianPath. AgraphisaMGStopologicalcollection.ItisveryeasytolistalltheHamiltonianpathsinagraphusing thetransformation: transH={ x*/size(x)=size(self)/Print(x)/false=>assert(false)} Thistransformationusesaniteratedpatternx*thatmatchesapath(asequenceofelementsneighbortwobytwo).Thekeywordselfreferstothecollectiononwhichthetransformationisapplied,thatis,theallgraph.Thesizeofagraphreturnsthenumberofitsvertices.So,ifthelengthofthepathxisthesameasthenumberofverticesinthegraph,thenthepathxisanHamiltonianpathbecausematchedpathsaresimple(norepetitionofanelement).ThesecondguardprintstheHamiltonianpathasasideeffectandreturnsitsargumentwhichisnotafalsevalue.Thenthethirdguardischeckedandreturnsfalse,thus,ther.h.s.oftheruleisnevertriggered.Thematchingstrategyensuresamaximalruleapplication.Inotherwords,ifaruleisnottriggered,thenthereisnoinstanceofapossiblepaththatfulfillsthepattern.ThispropertyimpliesthatthepreviousrulesmustbecheckedonallpossibleHamiltonianpathsandH(g)printsalltheHamiltonianpathingbeforereturningg. 7 7.1 Conclusion:ProgrammingintheLarge? CurrentStatusandRelatedWork Thetopologicalapproachwehavesketchedhereispartofalongtermresearcheffort[26]developedforinstancein[18]wherethefocusisonthesubstructure,orin[21]whereageneraltoolforuniform 13 neighborhooddefinitionisdeveloped.Withinthislongtermresearchproject,MGSisanexperimentallanguageusedtoinvestigatetheideaofassociatingcomputationstopathsthroughrules.Theapplicationofsuchrulescanbeseenasakindofrewritingprocessonacollectionofobjectsorganizedbyatopologicalrelationship(theneighborhood).AprivilegedapplicationdomainforMGSisthemodelingandsimulationofdynamicalsystemsthatexhibitadynamicstructure. Multisettransformationisreminiscentofmultiset-rewriting(orrewritingoftermsmoduloAC).ThisisthemaincomputationaldeviceofGamma[3],alanguagebasedonachemicalmetaphor;thedataareconsideredasamultisetMofmoleculesandthecomputationisasuccessionofchemicalreactionsaccordingtoaparticularrule.TheCHemicalAbstractMachine(CHAM)extendstheseideaswithafocusontheexpressionofsemanticofnondeterministicprocesses[5].TheCHAMintroducesamechanismtoisolatesomepartsofthechemicalsolution.ThisideahasbeenseriouslytakenintoaccountinthenotionofPsystems.Psystems[44,45]arearecentdistributedparallelcomputingmodelbasedonthenotionofamembranestructure.Amembranestructureisanestingofcellsrepresented,e.g,byaVenndiagramwithoutintersectionandwithauniquesuperset:theskin.Objectsareplacedintheregionsdefinedbythemembranesandevolvefollowingvarioustransformations:anobjectcanevolveintoanotherobject,canpasstroughamembraneordissolveitsenclosingmembrane.AsforGamma,thecomputationisfinishedwhennoobjectcanfurtherevolve.Byusingnestedmultisets,MGSisabletoemulatemoreorlessthenotionofPsystems.Inaddition,patternsliketheiteration+gobeyondwhatispossibletospecifyinthel.h.s.ofaGammarule. Lindenmayersystems[39]havelongbeenusedinthemodelingof(DS)2(especiallyinthemodelingofplantgrowing).Theylooselycorrespondtotransformationsonsequencesorstringrewriting(theyalsocorrespondtotreerewriting,becausesomestandardfeaturesmakeparticularlysimpletocodearbitrarytrees,cf.theworkofP.Prusinkiewicz[47,46]).Obviously,Lsystemsarededicatedtothehandlingoflinearandtree-likestructures. TherearestronglinksbetweenGBFandcellularautomata(CA),especiallyconsideringtheworkofZ.R´okawhichhasstudiedCAonCayleygraphs[48].However,ourownworkfocusesontheconstructionofCayleygraphsastheshapeofadatastructureandwedevelopanoperatoralgebraandrewritingnotionsonthisnewdatatype.ThisisnotinthelineofZ.R´okawhichfocusesonsynchronizationproblemsandestablishescomplexityresultsintheframeworkofCA. Aunifyingtheoreticalframeworkcanbedeveloped[23,25],basedonthenotionofchaincomplexdevelopedinalgebraiccombinatorialtopology.However,wedonotclaimthatwehaveachievedausefultheoreticalframeworkencompassingthepreviousparadigm.Weadvocatethatfewtopologicalnotionsandasinglesyntaxcanbeconsistentlyusedtoallowthemergingoftheseformalismsforprogrammingpurposes. ThecurrentMGSinterpreterisfreelyavailableattheURLhttp://mgs.lami.univ-evry.fr.Alltheexamplesinthispaperhavebeenprocessedwiththisinterpreter.TheresultshavebeenstoredintoafileusingavarietyofformatsandvisualizedusingeitherMathematicaorImoview(anOpenGLviewerdevelopedwithintheMGSproject). 7.2ProgrammingintheLarge? ThepreviouspresentationshowstheabilityofMGStohandlecomplexmodelsofDSandtoconciselyexpressseveralalgorithms.However,theseexamplesillustrateonlythe“programminginthesmall”taskanddonotaddresstheproblemofthe“programminginthelarge”,thatistheproblemsraisedbythesupportoflargesoftwarearchitecture,theinterconnectionofmodules,thehidingofinformation,thecapitalizationandthereuseofexistingcode,etc.Programminginthelargeiscertainlyoneofthemajorchallengeaprogramminglanguagemustface[13].Wementionverybrieflysomeofthepossiblesupportsprovidedbyatopologicalapproachtothe“programminginthelarge”activity. First,weadvocatethatthepolytypicapproachenablesabettercodereusebecauseitwidenstheapplicabilityofthecode.Thetopologicalapproach,providingaunifiedframeworkforalldatastructure,promotesthedevelopmentofpolytypicandreusablefunctions. Then,theunderlyingideasoftheMGStopologicalapproacharesmoothlyembeddedinafunctionallanguage:atransformationisafunction,atopologicalcollectiontypeactsasanopaquetype,etc.So, 14 allthenotionsdevelopedtohelptheprogramminginthelargewithinfunctionallanguages,arealsoavailable:modulesorpackagesandfunctors[37],mixin[41,31],preprocessingtools,etc. Moredirectly,topologicalnotionscanbeusedtoformalizeinheritancerestructuring[43].Theaimistoinferorrestructuretheinheritancehierarchyofclassesinanobjectorientedlanguagetoachievesmaller,consistentdatastructureandbettercodereuse.However,thecorrespondingtoolsapplyequallywelltomodulesrefactoring.TheproblemofinferringaclasshierarchyfromasetofconcreteobjectscanberephrasedastheinclusionrelationofasimplexinwhichthecriteriausedbyMoore[43]andotherstoconstraintheclasshierarchyaretopologicalconstraintsthathaveasimpleandintuitivemeaning[27]. Thislastworkopensthewaytoatopologicalbasisfora“moduleinterconnectionlanguage”forknittingthosemodulestogetherintoanintegratedwholeandforprovidinganoverviewthatformallyrecordstheintentoftheprogrammersandthatcanbecheckedforconsistencybyacompiler.Theideaistorepresenttheservicesrequiredorprovidedbyaclass,amodule,amixinoranycodefragment,astheboundariesofacellularspace[30].Theboundarycanthenbemergedtoassemblecodefragmentsintoanintegratedwhole.Thiskindofgeometricrepresentationisapromisingperspective,seeforinstancethepreliminaryworkofF.Lamarche[36],wherethefreevariablesinatermcorrespondtothebordersofacomplexandthesubstitutionisrepresentedbythegluingofcomplexesalongtheirsimplices. Acknowledgments TheauthorswouldliketothanksFranckDelaplaceatLaMI,Fr´ed´ericGruauatUniversityofParis-Sud,FlorentJacquemardatLSV-Cachan,C.GodinandP.BarbierdeReuilleatCIRAD-Montpellier,Pierre-´EtienneMoreauatLoria-Nancy,EricGoubaultatCEA-Saclay,P.PrusinkiewiczattheUniversityof ´CalgaryandthemembersoftheEpigenomicgroupatGENOPOLE-Evry,forstimulatingdiscussions, thoughtfulremarksandwarmdiscussions.WegratefullyacknowledgethefinancialsupportoftheCNRS, ´´theGDRALP,IMPBIO,theUniversityofEvryandGENOPOLE-Evry. References [1]A.AikenandE.L.Wimmers.Typeinclusionconstraintsandtypeinference.InProceedingsoftheSeventh ACMConferenceonFunctionalProgrammingLanguagesandComputerArchitecture,pages31–41.ACMPress,June1993.[2]J.Arulanandham,C.Calude,andM.Dinneen.Bead-sort:Anaturalsortingalgorithm.Bulletinofthe EuropeanAssociationforTheoreticalComputerScience,76:153–162,Feb.2002.TechnicalContributions.[3]J.-P.Banatre,A.Coutant,andD.L.Metayer.Aparallelmachineformultisettransformationandits programmingstyle.FutureGenerationComputerSystems,4:133–144,1988.[4]J.-P.Banˆatre,P.Fradet,andD.L.M´etayer.Gammaandthechemicalreactionmodel:Fifteenyearsafter. LectureNotesinComputerScience,2235:17–??,2001.[5]G.BerryandG.Boudol.Thechemicalabstractmachine.InConf.Record17thACMSymp.onPrinciplesof ProgrammmingLanguages,POPL’90,SanFrancisco,CA,USA,17–19Jan.1990,pages81–94.ACMPress,NewYork,1990.[6]R.W.Brockett.Smoothdynamicalsystemswhichrealizearithmeticalandlogicaloperations.InH.Nijmeijer andJ.M.Schumacher,editors,ThreeDecadesofMathematicalSystemsTheory:ACollectionofSurveysattheOccasionofthe50thBirthdayofJ.C.Willems,volume135ofLectureNotesinControlandInformationSciences,pages19–30.Springer-Verlag,1989.[7]R.W.Brockett.Dynamicalsystemsthatsortlists,diagonalizematrices,andsolvelinearprogramming problems.LinearAlgebraanditsApplications,146:79–91,1991.[8]K.M.Chandy.Reasoningaboutcontinuoussystems.ScienceofComputerProgramming,14(2–3):117–132, Oct.1990.[9]E.G.Coffman,M.J.Elphick,andA.Shoshani.Systemdeadlocks.ComputingSurveys,3(2):67–78,1971.[10]J.Cohen.Typingrule-basedtransformationsovertopologicalcollections.InJ.-L.GiavittoandP.-E.Moreau, editors,4thInternationalWorkshoponRule-BasedProgramming(RULE’03),pages50–66,2003. 15 [11]J.Cohen.Typagefortettypagesoupledescollectionstopologiquesetdestransformations.InV.M´enissier-Morain,editor,Journ´eesFrancophonesdesLangagesApplicatifs(JFLA2004),pages37–54.INRIA,2004.[12]F.Damm.Subtypingwithuniontypes,intersectiontypesandrecursivetypes.InSymposiumonTheoretical AspectsofComputerSoftware,volume789ofLectureNotesinComputerScience,pages687–706.Springer-Verlag,1994.[13]F.DeRemerandH.Kron.Programming-in-the-largeversusprogramming-in-the-small.InProceedingsof theinternationalconferenceonReliablesoftware,pages114–121,1975.alsopublishedinACMSIGPLANNoticesVol.10,Issue6(June1975).[14]P.FradetandD.L.M´etayer.StructuredGamma.ScienceofComputerProgramming,31(2–3):263–289,July 1998.[15]P.FradetandD.L.M´etayer.Shapetypes.InProc.ofPrinciplesofProgrammingLanguages,Paris,France, Jan.1997.ACMPress.[16]A.Frisch,G.Castagna,andV.Benzaken.SemanticSubtyping.InProceedingsoftheSeventeenthAnnual IEEESymposiumonLogicinComputerScience,pages137–146.IEEEComputerSocietyPress,2002.[17]F.Geurts.Hierarchyofdiscrete-timedynamicalsystems,asurvey.BulletinoftheEuropeanAssociationfor TheoreticalComputerScience,57:230–251,Oct.1995.SurveysandTutorials.[18]J.-L.Giavitto.Aframeworkfortherecursivedefinitionofdatastructures.InACM-Sigplan2ndInternational ConferenceonPrinciplesandPracticeofDeclarativeProgramming(PPDP’00),pages45–55,Montr´eal,Sept.2000.ACM-press.[19]J.-L.Giavitto.Invitedtalk:Topologicalcollections,transformationsandtheirapplicationtothemodeling andthesimulationofdynamicalsystems.InRewritingTechnicsandApplications(RTA’03),volumeLNCS2706ofLNCS,pages208–233,Valencia,June2003.Springer.[20]J.-L.Giavitto,C.Godin,O.Michel,andP.Prusinkiewicz.ModellingandSimulationofbiologicalprocesses inthecontextofgenomics,chapter“ComputationalModelsforIntegrativeandDevelopmentalBiology”.Hermes,July2002.Alsorepublishedasanhigh-levelcourseintheproceedingsoftheDieppespringschoolon“Modellingandsimumationofbiologicalprocessesinthecontextofgenomics”,12-17may2003,Dieppes,France.[21]J.-L.GiavittoandO.Michel.Declarativedefinitionofgroupindexeddatastructuresandapproximation oftheirdomains.InProceedingsofthe3ndInternationalACMSIGPLANConferenceonPrinciplesandPracticeofDeclarativeProgramming(PPDP-01).ACMPress,Sept.2001.[22]J.-L.GiavittoandO.Michel.Mgs:arule-basedprogramminglanguageforcomplexobjectsandcollections. InM.vandenBrandandR.Verma,editors,ElectronicNotesinTheoreticalComputerScience,volume59.ElsevierSciencePublishers,2001.[23]J.-L.GiavittoandO.Michel.MGS:aprogramminglanguageforthetransformationsoftopologicalcollections. ´TechnicalReport61-2001,LaMI–Universit´ed’EvryVald’Essonne,May2001.[24]J.-L.GiavittoandO.Michel.Datastructureastopologicalspaces.InProceedingsofthe3ndInternational ConferenceonUnconventionalModelsofComputationUMC02,volume2509,pages137–150,Himeji,Japan,Oct.2002.LectureNotesinComputerScience.[25]J.-L.GiavittoandO.Michel.Thetopologicalstructuresofmembranecomputing.FundamentaInformaticae, 49:107–129,2002.[26]J.-L.Giavitto,O.Michel,andJ.-P.Sansonnet.Groupbasedfields.InI.Takayasu,R.H.J.Halstead,and C.Queinnec,editors,ParallelSymbolicLanguagesandSystems(InternationalWorkshopPSLS’95),volume1068ofLNCS,pages209–215,Beaune(France),2–4Oct.1995.Springer-Verlag.[27]J.-L.GiavittoandE.Valencia.DiagrammaticRepresentationandReasoning,chapterATopologicalFrame-workforModelingDiagrammaticReasoningTasks.Springer-Verlag,2001.[28]E.Goubault.Geometryandconcurrency:Auser’sguide.MathematicalStructuresinComputerScience, 10:411–425,2000.[29]G.-G.Granger.Lapens´eedel’espace.OdileJacob,1999. [30]M.Henle.Acombinatorialintroductiontotopology.Doverpublications,New-York,1994. [31]T.HirschowitzandX.Leroy.Mixinmodulesinacall-by-valuesetting.InD.LeM´etayer,editor,Programming LanguagesandSystems,ESOP’2002,volume2305ofLNCS,pages6–20,2002. 16 [32]C.B.Jay.Asemanticsforshape.ScienceofComputerProgramming,25(2–3):251–283,1995. [33]J.JeuringandP.Jansson.Polytypicprogramming.LectureNotesinComputerScience,1129:68–114,1996.[34]I.Kant.CritiqueofPureReason.PalgraveMacmillan,2003.1thedition:1929.2ndRev.edition:2003. TranslationbyNormanKempSmithofthe17872ndedition. [35]H.Kragh.QuantumGenerations:AHistoryofPhysicsintheTwentiethCentury.PrincetonUniversity Press,2002.ISBN:0-691-09552-3.[36]F.Lamarche.Uneth´eorieg´eom´etriquedesobjetssymboliques.FirstmeetingoftheprojectGEOCAL (g´eometrieducalcul),InstitutMath´ematiquedeLuminy(T.Ehrhard),Marseille,Jan.2004.[37]X.Leroy.Amodularmodulesystem.JournalofFunctionalProgramming,10(3):269–303,2000. [38]P.Lienhardt.Topologicalmodelsforboundaryrepresentation:acomparisonwithn-dimensionalgeneralized maps.Computer-AidedDesign,23(1):59–82,1991. [39]A.Lindenmayer.Mathematicalmodelsforcellularinteractionindevelopment,PartsIandII.Journalof TheoreticalBiology,18:280–315,1968. [40]E.Meijer,M.Fokkinga,andR.Paterson.FunctionalProgrammingwithBananas,Lenses,Envelopesand BarbedWire.In5thACMConferenceonFunctionalProgrammingLanguagesandComputerArchitecture,volume523ofLectureNotesinComputerScience,pages124–144,Cambridge,MA,August26–30,1991.Springer,Berlin. [41]O.MichelandJ.-L.Giavitto.Amalgams:Namesandnamecaptureinadeclarativeframework.Technical ´Report32,LaMI–Universit´ed’EvryVald’Essonne,Jan.1998.alsoavalaibleasLRIResearch-Report RR-1159. [42]O.MichelandF.Jacquemard.AnanalysisoftheNeedham-Schroederpublic-keyprotocolwithMGS.In G.Mauri,G.Paun,andC.Zandron,editors,PreproceedingsoftheFifthworkshoponMembraneComputing(WMC5),pages295–315.ECMolConNet-UniversitadiMilano-Bicocca,June2004. [43]I.Moore.Automaticinheritancehierarchyrestructuringandmethodrefactoring.InOOPSLA’96Conference Proceedings:Object-OrientedProgrammingSystems,Languages,andApplications,pages235–250.ACMPress,1996. [44]G.Paun.Computingwithmembranes.TechnicalReportTUCS-TR-208,TUCS-TurkuCentreforComputer Science,Nov.111998. [45]G.Paun.Fromcellstocomputers:Computingwithmembranes(Psystems).Biosystems,59(3):139–158, March2001. [46]P.PrusinkiewiczandJ.Hanan.Lsystems:fromformalismtoprogramminglanguages.InG.Ronzenbergand A.Salomaa,editors,LindenmayerSystems,ImpactsonTheoreticalComputerScience,ComputerGraphicsandDevelopmentalBiology,pages193–211.SpringerVerlag,Feb.1992. [47]P.Prusinkiewicz,A.Lindenmayer,J.S.Hanan,etal.TheAlgorithmicBeautyofPlants.Springer-Verlag, 1990.[48]Z.R´oka.One-waycellularautomataonCayleygraphs.TheoreticalComputerScience,132(1–2):259–290, 26Sept.1994. [49]M.Sintzoff.Invarianceandcontractionbyinfiniteiterationsofrelations.InResearchdirectionsinhigh-levelprogramminglanguages,LNCS,volume574,pages349–373,MontSaint-Michel,France,june1991.Springer-Verlag. [50]R.D.Sorkin.Afinitarysubstituteforcontinuoustopology.Int.J.Theor.Phys.,30:923–948,1991. [51]A.Spicher,O.Michel,andJ.-L.Giavitto.Atopologicalframeworkforthespecificationandthesimulation ofdiscretedynamicalsystems.InSixthInternationalconferenceonCellularAutomataforResearchandIndustry(ACRI’04),LNCS,Amsterdam,October2004.Springer.tobepublished.[52]TheMAUDEproject.Maudehomepage,2002.http://maude.csl.sri.com/. [53]ThePROTHEOproject.Elanhomepage,2002.http://www.loria.fr/equipes/protheo/SOFTWARES/ELAN/.[54]A.M.Turing.Thechemicalbasisofmorphogenesis.Phil.Trans.Roy.Soc.ofLondon,SeriesB:Biological Sciences(237):37–72,1952. [55]G.Turk.Generatingtexturesforarbitrarysurfacesusingreaction-diffusion.InT.W.Sederberg,editor, ComputerGraphics(SIGGRAPH’91Proceedings),volume25,pages289–298,July1991. [56]H.Weyl.TheClassicalGroups(theirinvariantsandrepresentations).PrincetonUniversityPress,1939. Reprintedition(October13,1997).ISBN0691057567. 17 因篇幅问题不能全部显示，请点此查看更多更全内容