Programming in Prolog

TheJournalofFunctionalandLogicProgrammingTheMITPressVolume2000,Article431March2000ISSN1080{5230.MITPressJournals,FiveCambridgeCenter,Cambridge,MA02142-1493,USA;[phone];[e-mail],[e-mail]erarticlessee:flp/gopher.mit.edu[phone];[e-mail]dLogicProgrammingisapeer-reviewedandelectronicallypublishedscholarlyjournalthatcoversabroadscopeoftopicsfromfunctionalandlogicprogramming.Inparticular,itfocusesontheintegrationofthefunctionalandthelogicparadigmsaswellastheircommonfoundations.Editor-in-Chief:G.LeviEditorialBoard:H.A¨t-KaciL.AugustssonCh.BrzoskaJ.DarlingtonY.GuoM.HagiyaM.HanusT.IdaJ.JaarB.JayaramanM.K¨ohlerA.KrallH.KuchenJ.LaunchburyJ.LloydA.MiddeldorpD.MillerJ.J.Moreno-NavarroL.NaishM.J.O'DonnellP.PadawitzC.PalamidessiF.PfenningD.PlaistedR.PlasmeijerU.ReddyM.Rodrguez-ArtalejoF.SilbermannP.VanHentenryckD.S.WarrenAreaEditorExecutiveBoard:M.M.T.ChakravartyA.HallmannH.C.R.LockR.LoogenA.M¨uckElectronicMail:jfl[e-mail][e-mail]@cs.mu.oz.au31March2000AbstractThispaperpresentstwoviewsofstepwiseenhancement,oneapragmaticsyntax-basedapproachandtheotherasemanticapproachbasedonhigher-orderfunctionsandrelatingtoshapeandpolytyp-ism.Theapproachesareoutlined,andtheperhapssurprisinglycloserelationshipbetweenthetwodescribed.Bycombiningtheadvantagesofbothapproaches,itisshownhowmorecodeinbothfunctionalandlogicprogramminglanguagescanbeconstructedinasystematicway.Wedescribeaprototypesystemthatallowshigher-orderpred-icatedenitionstobeproducedautomaticallyfromtypedenitionsorHornclauseskeletonsandrelatesomeexperiencesinusinghigher-orderprogramminginProlog.1MotivationInthelastfewyears,interestinsystematicmethodsfortheconstructionofPrologprogramshassignicantlyincreased.See,forexample,Gegg-Harrison[GH95];PowerandSterling[PS90];Kirschenbaum,Michaylov,andSterling[KMS96];SterlingandYalcinalp[SY96];andVasconcelosandFuchs[VF95].Thesepapershavebuiltonprevious,less-systematicapproachestoPrologprogramming,implicitintextbooksandsharedcode.TheprogressionofapproacheswasdiscussedinNaishandSterling[NS98].Twoaudiencescanbenetfromsystematicapproaches:noviceprogram-merswhoneedguidancetocreatecodeofreasonablequalityandexperienced1programmerswhowanttoincreasetheirproductivity.Theneedsofthesetwogroupsarequitedierent.Novicescanlearnmoreeasilyfromconcreteexam-plesanddonothavetheexperiencetorecognisepatternsandabstractions.Experiencedprogrammerscanbenetfromusinghigherlevelsofabstractioninpowerfultools.Weclaimthatbothaudiencescanbeaddressedthroughthemethodofstepwiseenhancement.Thismethodcanbeexplaineddirectlyintermsofprogrammingtechniquesappliedtosimpleprogramsandcanbegivenamoretheoreticalbasisintermsofhigher-orderfunctions.Inthispaperwereviewstepwiseenhancement,sketchhowtocaptureanenhancementasahigher-orderfunctionadaptedfromfoldr,andthensketchhowindividualenhancementsarespecialisationsoftheparticularfoldrpredicate.Weshowhowthisiscloselyrelatedtothenewideasonshapeandpolytypismbeingdiscussedinthefunctionalprogrammingcommunity(seeJayandCockett[JC94];Jay[Jay95];Belle,Jay,andMoggi[BJM96];JeuringandJansson[JJ96];JanssonandJeuring[JJ97]).Wegoontogeneralisethisworkinseveralways,utilisingkeyfeaturesoflogicprogramming,suchasnondeter-minismandflexiblemodes,andweshowhowfoldlcanalsobeadapted.ThisleadstoaproposalforasetofsoftwaretoolstoautomaticallyproducePrologproceduresfromtypedenitions.Wedescribeaprototypeimple-mentationandrelateourinitialexperiencesusingthesetoolsandusingthehigher-orderprogrammingstylewithProlog.Thecurrentworkwassparkedbythechallengetousethehigher-orderapproachtoexplaina\complicatedprogram,theruleinterpreterdescribedinSection17.4ofthesecondeditionofTheArtofProlog(SterlingandShapiro[SS94]).Inexplainingtheprogram,anewmethodwasformulated:Thenalprogramisbuiltaroundanoutputtyperatherthananinputtype.Inthispaperwegiveanotherexampleofthistechnique,usingadierentinterpreter.Whathasemergedisabetterunderstandingofhowtypescandrivepro-gramdevelopment,andhowNaishandSterling'sviewsofsystematicprogramconstructionviastepwiseenhancementarecomplementary.Theworkrelatestorecent,excitingadvancementsinthefunctionalprogrammingcommunityconcerningshape,whichsetsourviewsonprogramdevelopmentinabroadercontext.Theseinsightshavepromptedthedevelopmentofprototypesoft-waretoolsforpartiallyautomatingcodingbasedontypesandskeletons.Thispaperdescribesourexper