An interactive semantics of logic programming

arXiv:cs/0107022v1[cs.LO]17Jul2001UnderconsiderationforpublicationinTheoryandPracticeofLogicProgramming1AnInteractiveSemanticsofLogicProgrammingROBERTOBRUNI,UGOMONTANARIDipartimentodiInformatica,Universit`adiPisa,CorsoItalia40,56125Pisa,Italia.{bruni,ugo}@di.unipi.itFRANCESCAROSSIDipartimentodiMatematica,Universit`adiPadova,ViaBelzoni7,35131Padova,[e-mail]programmingsomerecentlyemergingideasfromthefieldofreduction-basedcommunicatingsystems,withtheaimofgivingevidenceofthehiddeninteractionsandthecoor-dinationmechanismsthatruletheoperationalmachineryofsuchaprogrammingparadigm.Thesemanticframeworkwehavechosenforpresentingourresultsistilelogic,whichhastheadvan-tageofallowingauniformtreatmentofgoalsandobservationsandofapplyingabstractcategoricaltoolsforprovingtheresults.Asmaincontributions,wementionthefinitarypresentationofabstractunification,andaconcurrentandcoordinatedabstractsemanticsconsistentwiththemostcommonsemanticsoflogicprogramming.Moreover,thecompositionalityofthetilesemanticsisguaranteedbystandardresults,asitreducestocheckthatthetilesystemsassociatedtologicprogramsenjoythetiledecompositionproperty.Anextensionoftheapproachforhandlingconstraintsystemsisalsodiscussed.IntroductionLogicprogramming(Lloyd,1987)isafoundationalresearchfieldthathasbeenexten-sivelyinvestigatedthroughoutthelast25years.Itcanbesaidthat,inlogicprogramming,theoryandpracticemeettogethersinceitsverybeginning,aseachinnovationononesidecontributesmanyinsightstotheothersidethankstothebasicprincipleoflogicprogram-ming,whichis‘writingprogramsbyexpressingtheirproperties.’Thissymbiosishasalsofacilitatedthestudyandtheprototypingofinterdisciplinaryapplicationsthateitherextendthe‘kernel’oftheframeworkwithadditionalfeaturesortransferhelpfultechniquesfromalargevarietyofparadigms.Atypicalexampleistheembeddingofconstraintswithinlogicprogramming(Marriott&Stuckey,1998;Jaffar&Maher,1994),whichretainsthedeclarativeandcleansemanticsoflogicprogramming,aswellasitstypicalproblemsolv-ingfeatures,whileextendingitsapplicabilitytomanypracticaldomains;infact,constraintlogicprogramming(CLP)isnowconsideredasamajorprogrammingparadigm.Moreinterestingly,veryoftentheseflowsofideashavebeenprofitablybidirectionalandcontinuous,thusallowingonetoestablishstrongconnectionsbetweendifferentareas(bringingusefulanalogies)andalsotobridgegapsbetweendifferentformalisms.2R.Bruni,U.MontanariandF.RossiInteractionviacontextualizationandinstantiationInthispaper,inspiredbyrecentprogressinthefieldsofcommunicatingsystemsandcal-culiforconcurrency,wewanttofocusonaninteractiveviewoflogicprogramming.Theideaistounderstandlogicalpredicatesas(possiblyopen)interactingagentswhoselo-calevolutionsarecoordinatedbytheunificationengine.Infact,theamountofinteractionarisesfromtheunificationmechanismofresolution,assubgoalscansharevariablesandtherefore‘local’progressofacomponentcaninfluenceothercomponentsbyfurtherin-stantiatingsuchsharedvariables.Onecentralaspectofthisviewistounderstandwhatkindofinformationweshouldobservetocharacterizeinteractionandhowfartheapproachcanbeextendedtodealwithdifferentsemanticinterpretationsoflogicprograms.Forexam-ple,oneinterestingissueiscompositionality.Havingacompositionalsemanticframeworkisindeedveryconvenientforformalreasoningonprogrampropertiesandcanfacilitatethedevelopmentofmodularprograms(Bossietal.,1994a;Brogietal.,1992;Gaifman&Shapiro,1989;Mancarella&Pedreschi,1987).Wesketchherethemainideasconcerningtheroleplayedby‘contexts’inreductionsystems,butforamorepreciseoverviewweinvitetheinterestedreadertojoinusinthelittledetour,fromthelogicprogrammingworldtotheprocessdescriptioncalculiarea,insertedinthelastpartofthisintroductorysection(withlinkstorelatedliterature).Generallyspeaking,theissuewefocusonisthatofequippingareductionsystemwithaninteractivesemantics.Infact,althoughreductionsemanticsareoftenveryconvenientbecauseofafriendlypresentation,theyarenotcompositional‘inprinciple.’Theproblemisthattheyaredesignedhavinginmindaprogressivereductionoftheinitialstatetoasuit-ablenormalform,i.e.,onefocusesonacompletelyspecifiedsystemthatcanbestudiedinisolationfromalltherest.Inlogicprogramming,thiswouldcorrespondtostudyingtherefutationofgroundgoalsonlyandtodevelopanad-hocsystemtothisaim.Then,ifonewantstostudythesemanticsofpartiallyspecifiedcomponentstheframeworkisnolongeradequateandsomeextensionsbecomenecessary.Forexample,inprocessdescriptioncal-culi,apartiallyspecifiedcomponentcanbeaprocessterm(calledopenprocessorcontext)thatcontainssuitableprocessvariablesrepresentinggenericsubprocesses.However,alsoaclosedterm(i.e.,withoutfreeprocessvariables)canbeconsideredanopensystemwhenitevolvesaspartofabroadersystem,byinteractingwiththeenvironment.Inlogicpro-grammingwecandistinguishtwomainkindsofopennessandinteraction.Afirstkindisduetogoalswithvariables(ratherthanground)thatcanobviouslyberegardedaspartiallyspecifiedsystems.Asecondkindconsistsofregardinganatomicgoalaspartofalargerconjoinedgoalwithwhichitmustinteract.Theobviouswaytodealwithpartiallyspecifiedcomponentsistotran