48 Pages
English

Under consideration for publication in Theory and Practice of Logic Programming

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
Under consideration for publication in Theory and Practice of Logic Programming 1 Logic programming in the context of multiparadigm programming: the Oz experience ? PETER VAN ROY Universite catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium PER BRAND Swedish Institute of Computer Science, S-164 28 Kista, Sweden DENYS DUCHIER Universitat des Saarlandes, D-66123 Saarbrucken, Germany SEIF HARIDI Royal Institute of Technology (KTH), S-164 28 Kista, Sweden MARTIN HENZ National University of Singapore, Singapore 117543 CHRISTIAN SCHULTE Royal Institute of Technology (KTH), S-164 28 Kista, Sweden Abstract Oz is a multiparadigm language that supports logic programming as one of its ma- jor paradigms. A multiparadigm language is designed to support different programming paradigms (logic, functional, constraint, object-oriented, sequential, concurrent, etc.) with equal ease. This article has two goals: to give a tutorial of logic programming in Oz and to show how logic programming fits naturally into the wider context of multiparadigm programming. Our experience shows that there are two classes of problems, which we call algorithmic and search problems, for which logic programming can help formulate practical solutions. Algorithmic problems have known efficient algorithms. Search problems do not have known efficient algorithms but can be solved with search. The Oz support for logic programming targets these two problem classes specifically, using the concepts needed for each.

  • end

  • oz

  • paradigms

  • programs can

  • store

  • programming

  • logic programming

  • logic variables

  • nil

  • variables must


Subjects

Informations

Published by
Published 01 November 1999
Reads 15
Language English

Exrait

UnderconsiderationforpublicationinTheoryandPracticeofLogicProgrammingLogicprogramminginthecontextofmultiparadigmprogramming:theOzexperiencePETERVANROYUniversite´catholiquedeLouvain,B-1348Louvain-la-Neuve,BelgiumPERBRANDSwedishInstituteofComputerScience,S-16428Kista,SwedenDENYSDUCHIERUniversita¨tdesSaarlandes,D-66123Saarbru¨cken,GermanySEIFHARIDIRoyalInstituteofTechnology(KTH),S-16428Kista,SwedenMARTINHENZNationalUniversityofSingapore,Singapore117543CHRISTIANSCHULTERoyalInstituteofTechnology(KTH),S-16428Kista,Sweden1AbstractOzisamultiparadigmlanguagethatsupportslogicprogrammingasoneofitsma-jorparadigms.Amultiparadigmlanguageisdesignedtosupportdifferentprogrammingparadigms(logic,functional,constraint,object-oriented,sequential,concurrent,etc.)withequalease.Thisarticlehastwogoals:togiveatutorialoflogicprogramminginOzandtoshowhowlogicprogrammingfitsnaturallyintothewidercontextofmultiparadigmprogramming.Ourexperienceshowsthattherearetwoclassesofproblems,whichwecallalgorithmicandsearchproblems,forwhichlogicprogrammingcanhelpformulatepracticalsolutions.Algorithmicproblemshaveknownefficientalgorithms.Searchproblemsdonothaveknownefficientalgorithmsbutcanbesolvedwithsearch.TheOzsupportforlogicprogrammingtargetsthesetwoproblemclassesspecifically,usingtheconceptsneededforeach.ThisisincontrasttothePrologapproach,whichtargetsbothclasseswithonesetofconcepts,whichresultsinlessthanoptimalsupportforeachclass.WegiveexamplesthatcanberuninteractivelyontheMozartsystem,whichimplementsOz.Toexplaintheessentialdifferencebetweenalgorithmicandsearchprograms,wedefinetheOzexecutionmodel.Thismodelsubsumesbothconcurrentlogicprogramming(committed-choice-style)andsearch-basedlogicprogramming(Prolog-style).Furthermore,asconsequencesofitsmultiparadigmnature,themodelsupportsnewabilitiessuchasfirst-classtoplevels,deepThisarticleisamuch-extendedversionofthetutorialtalk“LogicProgramminginOzwithMozart”givenattheInternationalConferenceonLogicProgramming,LasCruces,NewMexico,Nov.1999.Someknowledgeoftraditionallogicprogramming(withPrologorconcurrentlogiclanguages)isassumed.
2P.VanRoyetal.guards,activeobjects,andsophisticatedcontrolofthesearchprocess.InsteadofHornclausesyntax,Ozhasasimple,fullycompositional,higher-ordersyntaxthataccommo-datestheabilitiesofthelanguage.WegiveabriefhistoryofOzthattracesthedevelopmentofitsmainideasandwesummarizethelessonslearnedfromthiswork.Finally,wegivemanyentrypointsintotheOzliterature.1IntroductionInourexperience,logicprogrammingcanhelpgivepracticalsolutionstomanydifferentproblems.Wehavefoundthatalltheseproblemscanbedividedintotwoclasses,eachofwhichusesatotallydifferentapproach:Algorithmicproblems.Theseareproblemsforwhichefficientalgorithmsareknown.Thisincludesparsing,rule-basedexpertsystems,andtransfor-mationsofcomplexsymbolicdatastructures.Forsuchproblems,alogicalspecificationofthealgorithmissometimessimplerthananimperativespec-ification.Inthatcase,deterministiclogicprogrammingorconcurrentlogicprogrammingmaybenaturalwaystoexpressit.Logicalspecificationsarenotalwayssimpler.Sometimesanimperativespecificationisbetter,e.g.,forproblemsinwhichstateupdatingisfrequent.Manygraphalgorithmsareofthelattertype.Searchproblems.Theseareproblemsforwhichefficientalgorithmsarenotknown.Thismaybeeitherbecausesuchalgorithmsarenotpossibleinprin-cipleorbecausesuchalgorithmshavenotbeenmadeexplicit.Wecite,e.g.,NP-completeproblems(GareyandJohnson1979)orproblemswithcomplexspecificationswhosealgorithmsaredifficultforthisreason.Someexamplesofsearchproblemsareoptimizationproblems(planning,scheduling,configura-tion),naturallanguageparsing,andtheoremproving.Thesekindsofproblemscanbesolvedbydoingsearch,i.e.,withnondeterministiclogicprogramming.Butsearchisadangeroustool.Ifusednaively,itdoesnotscaleuptorealapplications.Thisisbecausethesizeofthesearchspacegrowsexponentiallywiththeproblemsize.Forarealapplication,allpossibleeffortmustbemadetoreducetheneedforsearch:usestrong(global)constraints,concurrencyforcooperativeconstraints,heuristicsforthesearchtree,etc.(SchulteandSmolka1999).Forproblemswithcomplexspecifications,usingsufficientlystrongconstraintssometimesresultsinapolynomial-timealgorithm(KollerandNiehren2000).Forthispaper,weconsiderlogicprogrammingasprogrammingwithexecutablespecificationswritteninasimplelogicsuchasfirst-orderpredicatecalculus.TheOzsupportforlogicprogrammingistargetedspecificallytowardsthetwoclassesofalgorithmicproblemsandsearchproblems.Thefirstpartofthisarticle(Sections2–6)showshowtowritelogicprogramsinOzfortheseproblems.Section2introducesdeterministiclogicprogramming,whichtargetsalgorithmicproblems.ItisthemostsimpleanddirectwayofdoinglogicprogramminginOz.Section3showshowtodonondeterministiclogicprogramminginthePrologstyle.Thistargetsneither
LogicprogramminginOz3algorithmicnorsearchproblems,andisthereforeonlyofpedagogicalinterest.Sec-tion4showshowtodoconcurrentlogicprogrammingintheclassicaltradition.Thistargetsmorealgorithmicproblems.Section5extendsSection4withstate.Inourexperience,stateisessentialforpracticalconcurrentlogicprogramming.Section6expandsonSection3toshowhowsearchcanbemadepractical.Thesecondpartofthisarticle(Sections7–9)focusesontheessentialdifferencebetweenthetechniquesusedtosolvealgorithmicandsearchproblems.Thisleadstothewidercontextofmultiparadigmprogramming.Section7introducestheOzexecutionmodel,whichhasastrictfunctionalcoreandextensionsforconcurrency,lazyevaluation,exceptionhandling,security,state,andsearch.Thesectionexplainshowtheseextensionscanbeusedindifferentcombinationstoprovidedifferentpro-grammingparadigms.Inparticular,Section7.4explainstheabstractionofcompu-tationspaces,whichisthemaintoolfordoingsearchinOz.Spacesmakepossibleadeepsynthesisofconcurrentandconstraintlogicprogramming.Section8givesanoverviewofotherresearchinmultiparadigmprogrammingandashorthistoryofOz.Finally,Section9summarizesthelessonswehavelearnedintheOzprojectonhowtodopracticallogicprogrammingandmultiparadigmprogramming.Thisarticlegivesaninformal(yetprecise)introductiontargetedtowardsPrologprogrammers.AmorecompletepresentationoflogicprogramminginOzanditsrelationshiptootherprogrammingconceptsisgiveninthetextbook(VanRoyandHaridi2002).2DeterministiclogicprogrammingWecalldeterministiclogicprogrammingthecasewhenthealgorithm’scontrolflowiscompletelyknownandspecifiedbytheprogrammer.Nosearchisneeded.Thisisperfectlyadaptedtosequentialalgorithmicproblems.Forexample,adeterministicnaivereversecanbewrittenasfollowsinOz:declareproc{AppendXsYsZs}caseXsofnilthenZs=Ys[]X|XrthenZrinZs=X|Zr{AppendXrYsZr}dnedneproc{NRevXsYs}caseXsofnilthenYs=nil[]X|XrthenRin{NRevXrR}{AppendR[X]Ys}dnedneThissyntaxshouldbevaguelyfamiliartopeoplewithsomeknowledgeofPrologandfunctionalprogramming(SterlingandShapiro1986;MaierandWarren1988;
4P.VanRoyetal.Thompson1999;CousineauandMauny1998).Weexplainitbriefly,pointingoutwhereitdiffersfromProlog.Allcapitalizedidentifiersrefertologicvariablesinaconstraintstore.1AppendandNRevareprocedureswhoseargumentsarepassedbyunification,asinProlog.Thedeclaredeclaresnewglobalidentifiers,AppendandNRev,whichareboundtothenewly-createdprocedurevalues.Thismeansthattheorderofthedeclarationsdoesnotmatter.Alllocalvariablesmustbedeclaredwithinascope,e.g.,“Zrin”and“Rin”declareZrandRwithscopestothenextenclosingendkeyword.AlistiseithertheatomnilorapairofanelementXandalistXr,writtenX|Xr.The[]isnotanemptylist,butseparatesclausesinacasestatement(similartoaguardedcommand,exceptthatcaseissequential).Weexplainbrieflythesemanticsofthenaivereversetohighlighttherelationshiptologicprogramming.Theconstraintstoreconsistsofequalityconstraintsoverrationaltrees,similartowhatisprovidedbymanymodernPrologsystems.State-mentsareexecutedsequentially.Therearetwobasicoperationsonthestore,askandtell(Saraswat1993):Thetelloperation(e.g.,Ys=nil)addsaconstraint;itperformsunification.Thetellisanincrementaltell;iftheconstraintisinconsistentwiththestorethenonlyaconsistentpartisaddedandanexceptionisraised(see,e.g.,(Smolka1995b)foraformaldefinition).Theaskoperationisthecasestatement(e.g.,caseXsofX|Xrthen...else...end).Itwaitsuntilthestorecontainsenoughinformationtode-cidewhetherthepatternismatched(entailment)orcanneverbematched(disentailment).Theaboveexamplecanbewritteninafunctionalsyntax.Wefindthatafunctionalsyntaxoftengreatlyimprovesthereadabilityofprograms.Itisespeciallyusefulwhenitfollowsthedataflow,i.e.,theinputandoutputarguments.InOz,thedefinitionofNRevinfunctionalsyntaxisasfollows:declarefun{AppendXsYs}caseXsofnilthenYs[]X|XrthenX|{AppendXrYs}enddnefun{NRevXs}caseXsofnilthennil[]X|Xrthen{Append{NRevXr}[X]}enddneThisisjustsyntacticsugarfortheproceduraldefinition.InOz,afunctionisjustashorterwayofwritingaprocedurewheretheprocedure’slastargumentisthefunction’soutput.ThestatementYs={NRevXs}hasidenticalsemanticstotheprocedurecall{NRevXsYs}.1IncludingAppendandNRev,whichareboundtoprocedurevalues(lexically-scopedclosures).