From Concurrent Logic Programming to Concurrent Co

FromConcurrentLogicProgrammingtoConcurrentConstraintProgrammingFrankS.deBoerDepartmentofMathematicsandComputerScienceFreeUniversitydeBoelelaan1081,1081HVAmsterdam,[e-mail]artimentodiInformaticaeScienzedell’Informazione(DISI)UniversitadiGenovaviaBenedettoXV3,16132,Genova,[e-mail]xtendlogicprogrammingtoalanguagesuitableforconcurrentsystemshasstimulatedinthelastdecadeanintensiveresearch,resultinginalargevarietyofproposals.Acommonfea-tureofthevariousapproachesistheattempttodenemechanismsforconcurrencywithinthelogicalparadigm,thedrivingidealbeingthebalancebetweenexpressivenessanddeclarativereading.Inthissurveywepresentthemotivations,theprincipallinesalongwhichtheeldhasdeveloped,thevariousparadigmswhichhavebeenpro-posed,andthemainapproachestothesemanticfoundations.1IntroductionAmongthevariousreasonswhichhavecontributedtothepopularityoflogicprogramming,oneistheopinionthatitisaninherentlyparallellan-guage,thereforesuitableforparallelanddistributedarchitectures.Thepurelanguagecanalreadyberegardedasamodelforparallelcomputa-tion:intheso-calledprocessinterpretation(vanEmdenanddeLucena1982;Shapiro1983),thegoalisseenasasystemofparallelprocesses.Thesingleprocessevolvesviaresolutionsteps;dierentclausaldenitionsforthesamepredicateprovidenondeterminismandthesharedvariablesamongprocessesrepresentcommunicationchannels.12ConcurrentLogicandConcurrentConstraintProgrammingHowever,inaconcurrentsystemprocessesinteractwitheachother1,henceaconcurrentlanguageshouldembodysomesynchronizationmecha-nismsandconstructstospecifythedependencyofchoicesupontheenvi-ronment.Furthermoreonceacertainchoiceisselected,theprocesscannotbacktrack.Thisprincipleisincontrastwiththekindofnondeterminismoflogicprogramming,accordingtowhichallpossiblesolutionsarepursued(don’tknownondeterminism).Sincemorethanadecadetherehasbeenanactivelineofresearchaimedatextendinglogicprogrammingwithmechanismsforconcurrency.1.1Don’tknowversusdon’tcarenondeterminismInconcurrentsystemsaprocesscannot‘undo’achoice,evenifitrevealstobewrong(forinstancebecausetheprocessgetsstuck).Thereasonisthatachoice,andtheactionsdoneafterwards,havealreadyinuencedtheenvironment:tomaintainconsistencythewholesystemshouldbacktrack,butthisistooinecient.Itisratherpreferabletoprovidethelanguagewithmechanismstocontrolthechoices,sotoavoidasfaraspossiblethatwrongdecisionsaretaken.Themostcommonsuchmechanismistheguard:aconditionassociatedwitheachalternativewhichistestedbeforeselectingthatalternative.Almostalltheconcurrentlogiclanguagesandconcurrentconstraintlanguagesadoptdon’tcarenondeterminism:clausesareprovidedwithaguardpartandaprocesschooses(commitsto)onlyoneclause,provideditsguardpartissatised.Thefewlanguageswhichmaintaindon’tknownondeterminism,thuspreservingthecharacteristicsoflogicprogrammingtocomputeallsolu-tions,areDistributedLogic(Monteiro1981,1982),thelanguageofGener-alizedHornClauses(Falaschietal.1984),DeltaProlog(PereiraandNasr1984)andthelanguagecc(#;!;))(Saraswat1986,1989).AndorraPro-log(HaridiandBrand1988;Haridi1990;HaridiandJanson1990,1991;Haridietal.1992)combinesdon’tcareanddon’tknownondeterminism.1.2SynchronizationandcommunicationmechanismsRoughly,asynchronizationmechanismspecieswhenaprocesscanbeactivated.Inmanyconcurrentparadigmssynchronizationisinsymbio-siswithcommunication.Thisisthecasealsoinmostconcurrentlogiclanguages.Someoftherstconcurrentlogiclanguages,theRelationalLanguage(ClarkandGregory1981),ConcurrentProlog(Shapiro1983,1986,1988),thelanguageofGuardedHornClauses(Ueda1987,1988)andPARLOG(ClarkandGregory1986;Gregory1987),enforcedsynchroniza-1Thedichotomysequentialprogramming/concurrentprogrammingiscloselyrelatedtothedistinctionbetweentransformationalsystemsandinteractive(orreactive)sys-tems,see(HarelandPnueli1985).FrankS.deBoerandCatusciaPalamidessi3tionbyintroducingadirectionalityonthecommunicationchannels.Inthisway,someprocessesareseenasproducers(ofbindings)onacertainvariable,othersasconsumers.Theadvantageofsuchasolutionisthattheresultinglanguageisquite‘faithful’tothe(parallel)executionmodeloflogicprogramming:onlytheunicationmechanismneedstobemodied.Thekindofcommunicationmechanismdescribedaboveisasynchronous2,inthesensethattheprocessproducingabindingandtheprocesscon-suming(or,moreprecisely,testing)thebinding,performtheiractionsatdierenttimes.Asoppositetothisprinciple,synchronouscommuni-cationrequiresthepartnerstoexchangetheinformationsimultaneously.ThislattermechanismhasbeenadoptedinDistributedLogic,GeneralizedHornClauses,DeltaPrologandthelanguageofCommunicatingClauses(JacquetandMonteiro1990,1991,1992).AratherdierentapproachtosynchronizationhasbeenproposedinP-Prolog(Yang1986;YangandAiso1986).Theideaistosuspendaprocessuntilenoughbindingsareproducedsothatthenumberofconsistentalternativesforthenextstepreducestoone.Thissolutionissemanticallyclean,inthesensethatitdoesnotmodifythedeclarativereadingofthelanguage.Ofcourse,thedisadvantageisthatonlydeterministicprocessescanbespeciedinthisway.Suchamechanism