Delta-prolog A distributed logic programming langu

DeltaProlog:aDistributedLogicProgrammingLanguageanditsImplementationonDistributedMemoryMultiprocessorsJoseC.CunhaPedroD.MedeirosManuelB.CarvalhosaLusMonizPereiraABSTRACTDeltaPrologisalogicprogramminglanguageextendingPrologwithconstructsforsequentialandparallelcompositionofgoals,interprocesscommunicationandsynchro-nization,andexternalnon-determinism.Wepresentsequentialandparallelsearchstrategiesforthelanguage,basedonthenotionofderivationsspace.Theyrelyupondistributedbacktracking,amechanismsupportingthecoordinatedexecutionofmul-tiplecommunicatingDeltaPrologprocessesintheirjointsearchforthesolutionstoagivenproblem.ThenwedescribeanexecutionenvironmentforDeltaPrologbasedonanabstractmachineanddiscussimplementationissuesfordistributedmemoryTransputer-basedmultiprocessors.1INTRODUCTIONDeltaProlog(P)isaparallelextensiontoProloginspiredbyMonteiro’sDistributedLogic.ThetheoryofDistributedLogic([Mon83],[Mon86])extendsHornClauseLogic(HCL)withconstructsforthespecicationofdistributedsystems.Asadistinctivefeature,thePmodelreliesontheprogrammertospecifythesequentialityconstraintsandthedesirableparallelismexistingineachproblem,togetherwiththecorrespondingcommunicationschemes([PP84],[PMCA86],[PMCA88],[CFP89b],[CFP89a]).Thepresentationisorganizedasfollows.Insection2,wediscusstheprogrammingmodelandgiveanexample.AdiscussionofthePsequentialandparallelexecutionmodelsismadeinsection3.Then,insection4,wediscussimplementationissuesoftheparallelexecutionmodelsandoutlinetheimplementationonaTransputer-baseddistributedmemorymulti-computer(MeikoComputingSurface).Finally,insection5,wepresentsomeconclusionsandcurrentwork.2THEPROGRAMMINGMODELInthissectionwediscussthePlanguage,focusingontheprogrammingmodel,thelanguagesyntaxandsemantics,andgiveanexample.2.1LanguageconstructsAPprogramisasequenceofclausesoftheform:H:-G1;...;Gn:(n0):HisaProloggoalandeachGimaybeeitheraPrologoraPgoal.Thelatterareeithersplit,event,orchoicegoals,describedbelow.Thecommaisthesequentialcompositionoperator.Declaratively,thetruthofgoalsinPistime-dependant,soHistrueifG1;...;Gnaretrueinsuccession(seesection2.2below).Operationally,tosolvegoalHistosolvesuccessivelygoalsG1;...;Gn.AnimportantaspectisthataPprogramwithoutPgoalsisaPrologprogram,andsoPisatrueextensiontoProlog.2.1.1SplitgoalsSplitgoalsareoftheformS1==S2,where//isarightassociativeparallelcompositionoperatorandS1andS2arearbitraryPgoalexpressions.TosolveS1==S2istosolveS1andS2withinconcurrentprocesses.Declaratively,S1//S2istrueiS1andS2arejointlytrue.Theabstractexecutionmodelsforthelanguagedonotrequirethattheprocessessolvingthesetwogoalssharememory.SoifS1andS2sharelogicalvariables,thevariablesmustbeuniedwheneverbothprocessesterminate.Failuretounifythosevariables,failuretosolveS1orS2,orfailureofasubsequentgoalandbacktrackingintothesplitgoal,triggerdistributedbacktracking.Distributedbacktrackingextendsthebacktrack-basedstrategyofsequentialPrologsystemsasrequiredtodealwithconcurrentprocesses.2.1.2EventgoalsEventgoalsareoftheformX?E:CorX!E:C,whereXisaterm(themessage),?and!areinxbinarypredicatesymbols(thecommunicationmodes),EisboundtoaPrologatom(theeventname),andCisagoalexpression(theeventcondition),whichcannotevaluatePgoals.Twoeventgoals,e.g.X?E:CandX!E:C,arecomplementaryitheyhavethesameeventname,anddierentcommunicationmodes(i.e.oneoftype?andtheotheroftype!).IfCandDaretheatomtrue,wewriteX?EandX!E.ThetwoeventgoalsexecutesuccessfullyiXandYunifyandtheconditionsCandDevaluatetotrue.Aneventistheoutcomeofthesuccessfulresolutionofapairofcomplementaryeventgoals.Aneventgoalcanonlybesaidtobetruewhenithasbeensuccessfullysolvedwithitscomplementarygoal.ThusthedeclarativesemanticsofPstatesthatagoalistrueforsomecombinationsofsequencesofevents.Aneventgoal,likeX?E:C,suspendsuntilacomplementaryeventgoal,likeY!E:D,isavailableinaconcurrentprocess.Whentheyaresimultaneouslyavailable,theirjointresolutionmaybeintrepretedasatwo-wayexchangeofmessagesfollowedbyunicationofXandYandevaluationofconditionsCandD.Thisformofrendezvousmecha-nismisageneralizationofHoare’sandMilner’ssynchronouscommunication([Hoa85],[Mil80])asittakesadvantageoftermunicationforexchangingmessages.Theonlysignicanceofthecommunicationmodes!and?isthattheyarecomplementaryinthesensedescribedabove.Failureofaneventgoal,orbacktrackingintoone,causesdistributedbacktracking.2.1.3ChoicegoalsThechoiceoperator::wasintroducedformodellingexternalorglobalnon-determinism([FHLR79],[Hoa85]).InPtheselectionoftheclausesforresolutionwithaselectedProloggoalislikeinPrologsequentialsystems(i.e.itusesthetextualoccurrenceoftheclausesintheprogram),andisindependentofthestateoftheenvironment.Choicegoalsallowtheprogrammingofapplicationswheremultiplecommunicationalternativesmaybesimultaneouslyavailableandwhoseselectiondepends(non-deterministically)ontheenvironment.ThesegoalshavetheformA1::A2::...::Ai::...::An(n2),where::isthechoiceoperator.EachAi(i:1::n),isanalternativeofthegoaloftheformHe;B,whereHeisaneventgoal(theheadofthealternative),sequentiallyconjunctedwitha,possiblyempty,goalexpress