Under consideration for publication in Theory and Practice of Logic Programming
48 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Under consideration for publication in Theory and Practice of Logic Programming

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
48 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Publié le 01 novembre 1999
Nombre de lectures 15
Langue 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).
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents