Under consideration for publication in Theory and Practice of Logic Programming

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

Sujets

• Paradigm
• Computer programming
• Logic programming

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 novembre 1999
• Nombre de lectures: 15
• Langue: English

Extrait

UnderconsiderationforpublicationinTheoryandPracticeofLogicProgramming Logicprogramminginthecontextof multiparadigmprogramming: theOzexperience ∗ PETERVANROY Universite´catholiquedeLouvain,B-1348Louvain-la-Neuve,Belgium PERBRAND SwedishInstituteofComputerScience,S-16428Kista,Sweden DENYSDUCHIER Universita¨tdesSaarlandes,D-66123Saarbru¨cken,Germany SEIFHARIDI RoyalInstituteofTechnology(KTH),S-16428Kista,Sweden MARTINHENZ NationalUniversityofSingapore,Singapore117543 CHRISTIANSCHULTE RoyalInstituteofTechnology(KTH),S-16428Kista,Sweden 1 Abstract Ozisamultiparadigmlanguagethatsupportslogicprogrammingasoneofitsma- jorparadigms.Amultiparadigmlanguageisdesignedtosupportdifferentprogramming paradigms(logic,functional,constraint,object-oriented,sequential,concurrent,etc.)with equalease.Thisarticlehastwogoals:togiveatutorialoflogicprogramminginOzand toshowhowlogicprogrammingfitsnaturallyintothewidercontextofmultiparadigm programming.Ourexperienceshowsthattherearetwoclassesofproblems,whichwecall algorithmicandsearchproblems,forwhichlogicprogrammingcanhelpformulatepractical solutions.Algorithmicproblemshaveknownefficientalgorithms.Searchproblemsdonot haveknownefficientalgorithmsbutcanbesolvedwithsearch.TheOzsupportforlogic programmingtargetsthesetwoproblemclassesspecifically,usingtheconceptsneededfor each.ThisisincontrasttothePrologapproach,whichtargetsbothclasseswithoneset ofconcepts,whichresultsinlessthanoptimalsupportforeachclass.Wegiveexamples thatcanberuninteractivelyontheMozartsystem,whichimplementsOz.Toexplainthe essentialdifferencebetweenalgorithmicandsearchprograms,wedefinetheOzexecution model.Thismodelsubsumesbothconcurrentlogicprogramming(committed-choice-style) andsearch-basedlogicprogramming(Prolog-style).Furthermore,asconsequencesofits multiparadigmnature,themodelsupportsnewabilitiessuchasfirst-classtoplevels,deep ∗ Thisarticleisamuch-extendedversionofthetutorialtalk“LogicProgramminginOzwith Mozart”givenattheInternationalConferenceonLogicProgramming,LasCruces,NewMexico, Nov.1999.Someknowledgeoftraditionallogicprogramming(withPrologorconcurrentlogic languages)isassumed.

2P.VanRoyetal. guards,activeobjects,andsophisticatedcontrolofthesearchprocess.InsteadofHorn clausesyntax,Ozhasasimple,fullycompositional,higher-ordersyntaxthataccommo- datestheabilitiesofthelanguage.WegiveabriefhistoryofOzthattracesthedevelopment ofitsmainideasandwesummarizethelessonslearnedfromthiswork.Finally,wegive manyentrypointsintotheOzliterature. 1Introduction Inourexperience,logicprogrammingcanhelpgivepracticalsolutionstomany differentproblems.Wehavefoundthatalltheseproblemscanbedividedintotwo classes,eachofwhichusesatotallydifferentapproach: • Algorithmicproblems .Theseareproblemsforwhichefficientalgorithms areknown.Thisincludesparsing,rule-basedexpertsystems,andtransfor- mationsofcomplexsymbolicdatastructures.Forsuchproblems,alogical specificationofthealgorithmissometimessimplerthananimperativespec- ification.Inthatcase, deterministiclogicprogramming or concurrentlogic programming maybenaturalwaystoexpressit.Logicalspecificationsare notalwayssimpler.Sometimesanimperativespecificationisbetter,e.g.,for problemsinwhichstateupdatingisfrequent.Manygraphalgorithmsareof thelattertype. • Searchproblems .Theseareproblemsforwhichefficientalgorithmsarenot known.Thismaybeeitherbecausesuchalgorithmsarenotpossibleinprin- cipleorbecausesuchalgorithmshavenotbeenmadeexplicit.Wecite,e.g., NP-completeproblems(GareyandJohnson1979)orproblemswithcomplex specificationswhosealgorithmsaredifficultforthisreason.Someexamplesof searchproblemsareoptimizationproblems(planning,scheduling,configura- tion),naturallanguageparsing,andtheoremproving.Thesekindsofproblems canbesolvedbydoingsearch,i.e.,with nondeterministiclogicprogramming . Butsearchisadangeroustool.Ifusednaively,itdoesnotscaleuptoreal applications.Thisisbecausethesizeofthesearchspacegrowsexponentially withtheproblemsize.Forarealapplication,allpossibleeffortmustbemade toreducetheneedforsearch:usestrong(global)constraints,concurrency forcooperativeconstraints,heuristicsforthesearchtree,etc.(Schulteand Smolka1999).Forproblemswithcomplexspecifications,usingsufficiently strongconstraintssometimesresultsinapolynomial-timealgorithm(Koller andNiehren2000). Forthispaper,weconsider logicprogramming asprogrammingwithexecutable specificationswritteninasimplelogicsuchasfirst-orderpredicatecalculus.The Ozsupportforlogicprogrammingistargetedspecificallytowardsthetwoclassesof algorithmicproblemsandsearchproblems.Thefirstpartofthisarticle(Sections2– 6)showshowtowritelogicprogramsinOzfortheseproblems.Section2introduces deterministiclogicprogramming,whichtargetsalgorithmicproblems.Itisthemost simpleanddirectwayofdoinglogicprogramminginOz.Section3showshowto donondeterministiclogicprogramminginthePrologstyle.Thistargetsneither

LogicprogramminginOz3 algorithmicnorsearchproblems,andisthereforeonlyofpedagogicalinterest.Sec- tion4showshowtodoconcurrentlogicprogrammingintheclassicaltradition.This targetsmorealgorithmicproblems.Section5extendsSection4withstate.Inour experience,stateisessentialforpracticalconcurrentlogicprogramming.Section6 expandsonSection3toshowhowsearchcanbemadepractical. Thesecondpartofthisarticle(Sections7–9)focusesontheessentialdifference betweenthetechniquesusedtosolvealgorithmicandsearchproblems.Thisleads tothewidercontextof multiparadigm programming.Section7introducestheOz executionmodel,whichhasastrictfunctionalcoreandextensionsforconcurrency, lazyevaluation,exceptionhandling,security,state,andsearch.Thesectionexplains howtheseextensionscanbeusedindifferentcombinationstoprovidedifferentpro- grammingparadigms.Inparticular,Section7.4explainstheabstractionofcompu- tationspaces,whichisthemaintoolfordoingsearchinOz.Spacesmakepossible adeepsynthesisofconcurrentandconstraintlogicprogramming.Section8gives anoverviewofotherresearchinmultiparadigmprogrammingandashorthistory ofOz.Finally,Section9summarizesthelessonswehavelearnedintheOzproject onhowtodopracticallogicprogrammingandmultiparadigmprogramming. Thisarticlegivesaninformal(yetprecise)introductiontargetedtowardsProlog programmers.AmorecompletepresentationoflogicprogramminginOzandits relationshiptootherprogrammingconceptsisgiveninthetextbook(VanRoyand Haridi2002). 2Deterministiclogicprogramming Wecall deterministic logicprogrammingthecasewhenthealgorithm’scontrolflow iscompletelyknownandspecifiedbytheprogrammer.Nosearchisneeded.Thisis perfectlyadaptedtosequentialalgorithmicproblems.Forexample,adeterministic naivereversecanbewrittenasfollowsinOz: declare proc{AppendXsYsZs} caseXs ofnilthenZs=Ys []X|XrthenZrin Zs=X|Zr{AppendXrYsZr} dne dne proc{NRevXsYs} caseXs ofnilthenYs=nil []X|XrthenRin {NRevXrR} {AppendR[X]Ys} dne dne ThissyntaxshouldbevaguelyfamiliartopeoplewithsomeknowledgeofProlog andfunctionalprogramming(SterlingandShapiro1986;MaierandWarren1988;

4P.VanRoyetal. Thompson1999;CousineauandMauny1998).Weexplainitbriefly,pointingout whereitdiffersfromProlog.Allcapitalizedidentifiersrefertologicvariablesin aconstraintstore. 1 Append and NRev areprocedureswhoseargumentsarepassed byunification,asinProlog.The declare declaresnewglobalidentifiers, Append and NRev ,whichareboundtothenewly-createdprocedurevalues.Thismeansthat theorderofthedeclarationsdoesnotmatter.Alllocalvariablesmustbedeclared withinascope,e.g.,“ Zrin ”and“ Rin ”declare Zr and R withscopestothenext enclosing end keyword.Alistiseithertheatom nil orapairofanelement X and alist Xr ,written X|Xr .The [] isnotanemptylist,butseparatesclausesina case statement(similartoaguardedcommand,exceptthat case issequential). Weexplainbrieflythesemanticsofthenaivereversetohighlighttherelationship tologicprogramming.Theconstraintstoreconsistsofequalityconstraintsover rationaltrees,similartowhatisprovidedbymanymodernPrologsystems.State- mentsareexecutedsequentially.Therearetwobasicoperationsonthestore,ask andtell(Saraswat1993): •Thetelloperation(e.g., Ys=nil )addsaconstraint;itperformsunification. Thetellisan incrementaltell ;iftheconstraintisinconsistentwiththe storethenonlyaconsistentpartisaddedandanexceptionisraised(see, e.g.,(Smolka1995b)foraformaldefinition). •Theaskoperationisthe case statement(e.g., caseXsofX|Xrthen... else...end ).Itwaitsuntilthestorecontainsenoughinformationtode- cidewhetherthepatternismatched(entailment)orcanneverbematched (disentailment). Theaboveexamplecanbewritteninafunctionalsyntax.Wefindthatafunctional syntaxoftengreatlyimprovesthereadabilityofprograms.Itisespeciallyuseful whenitfollowsthedataflow,i.e.,theinputandoutputarguments.InOz,the definitionof NRev infunctionalsyntaxisasfollows: declare fun{AppendXsYs} caseXsofnilthenYs []X|XrthenX|{AppendXrYs}end dne fun{NRevXs} caseXsofnilthennil []X|Xrthen{Append{NRevXr}[X]}end dne Thisisjustsyntacticsugarfortheproceduraldefinition.InOz,afunctionisjust ashorterwayofwritingaprocedurewheretheprocedure’slastargumentisthe function’soutput.Thestatement Ys={NRevXs} hasidenticalsemanticstothe procedurecall {NRevXsYs} . 1 Including Append and NRev ,whichareboundtoprocedurevalues(lexically-scopedclosures).