A treatment of higher-order features in logic prog

ATreatmentofHigher-OrderFeaturesinLogiProgrammingGopalanNadathurDepartmentofComputerSieneandEngineeringUniversityofMinnesota4-192EE/CSBuilding,200UnionStreetS.E.Minneapolis,MN55455gopalans.umn.eduAbstratThelogiprogrammingparadigmprovidesthebasisforanewintensionalviewofhigher-ordernotions.Thisviewisrealizedprimarilybyemployingthetermsofatypedlambdaalulusasrepresentationaldeviesandbyusingariherformofuniationforprobingtheirstrutures.Theseadditionshaveimportantmeta-programmingappliationsbuttheyalsoposenon-trivialimplementationproblems.Oneissueonernsthemahinerepresen-tationoflambdatermssuitabletotheirintendeduse:anadequateenodingmustfailitateomparisonoperationsovertermsinadditiontosupportingtheusualredutionomputa-tion.Anotheraspetrelatestothetreatmentofauniationoperationthathasabranhingharaterandthatsometimesallsforthedelayingofthesolutionofuniationproblems.Analissueonernstheexeutionofgoalswhosestruturesbeomesapparentonlyintheourseofomputation.Thesevariousproblemsareexposedinthispaperandsolutionstothemaredesribed.Asatisfatoryrepresentationforlambdatermsisdevelopedbyexploit-ingthenamelessnotationofdeBruijnaswellasexpliitenodingsofsubstitutions.SpeialmehanismsaremoldedintothestrutureoftraditionalPrologimplementationstosupportbranhinginuniationandarryingofuniationproblemsoverotheromputationsteps;apremiumisplaedinthisontextonexploitingdeterminismandonemulatingusualrst-orderbehaviour.Anextendedompilationmodelispresentedthattreatshigher-orderuniationandalsohandlesdynamiallyemergentgoals.TheideasdesribedherehavebeenemployedintheTeyjusimplementationoftheProloglanguage,afatthatisusedtoobtainapreliminaryassessmentoftheireÆay.Keywords:lambdaalulus,intensionalhigher-orderprogramming,higher-orderunia-tion,abstratmahine,ompilation.1IntrodutionCustomaryaquaintanewithhigher-ordernotionsinprogrammingrelatestotheimperativeorfuntionalprogrammingparadigms.Withintheseframeworks,funtionsareequatedwiththemethodsforomputingthatareembodiedinproedures.Higher-ordernessthenonsistsoftheabilitytoobjetifysuhfuntionsand,thereby,toembedthemindataorpassthem1asargumentstootherfuntions.Manyinterestingappliationshavebeenfoundforsuhapabilities.However,allofthesearedependentonauniformextensionalviewoffuntions.Inpartiular,theonlyobservableaspetofsuhobjetsistheirabilitytotransformgivenargumentsintoresultvalues.Logiprogramminghasthepotentialforsupportingadierentand,insomesenses,moresophistiatedunderstandingofhigher-ordernotions[36℄.Funtionsareusedwithinthisparadigmasameansforonstrutingdesriptionsofobjets.Suhdesriptionsanbeexaminedbymeansofuniation,anoperationthatisusefulintheanalysisofintensions.Traditionallogiprogramminglanguagesmanifestaweakexploitationofthisapabilitybe-ausetheypermitonlyindividual,non-funtion,objetsasvalues.However,itispossibletosupporttheprobingoffuntionstrutureingenuinelyhigher-orderwaysbyintroduingamehanismsuhasthetermsofalambdaalulusforenodingfuntionobjetsandbyomplementingthiswithrihernotionsofvariablesanduniation.Theusualformofhigher-orderprogramminganberealizedsimplybyusingtheabilitytorepresentfuntionvaluedobjetsandtheextensionalinterpretationbuiltintologiprogrammingofonekindoffuntion,namely,prediates.Theriherintensionalviewoffuntionsoers,inaddition,manypossibilitiesthathavenotbeensystematiallysupportedbyanypreviousprogram-mingparadigm.Toonsideroneimportantdiretion,theabilitytouselambdatermsasrepresentationaldevieslendsitselfwelltoanabstratviewofsyntaxthattreatsbindingnotionsexpliitly[27,41℄,leadingtherebytomanynovelmetalanguageappliationsforlogiprogramming(e.g.,see[5,15,17,18,40℄).Whilethereisonsiderableappliationpotentialforhigher-orderfeaturesinlogipro-gramming,theadditionofsuhfeaturesalsoraisessigniantimplementationproblems.Oneategoryofproblemsarisesfromtheusethatismadeofthetermsofalambdaalu-lusessentiallyasdatastrutures.Thisisatrulynovelroleforsuhtermsinprogramming,andarepresentationmustbedevelopedforthemthatsupportstheiruseinthisapaity.Asatisfatoryrepresentationshouldpermittheexaminationoftermstrutureandmustfailitatetheomparisonoftermsinasituationwherethepartiularnamesofboundvari-ablesareunimportant,inadditiontoeÆientlysupportingtheusualredutionoperationonterms.Anotherlassofproblemsrelatestothefatthattheuniationomputationonlambdaterms,knownashigher-orderuniation[20℄,possessesharaterististhataredistintfromthoseoftheustomaryrst-orderuniation.Inpartiular,performingthisoperationmayinvolveabranhingsearhanditmayalsobeneessarytotemporarily‘suspend’theomputationbeforeaunierisfound.Suitabledynamisupportmustbedesribedforbothfaets.Athirdaspetthatneedsspeialonsiderationisthemixingofintensionalandextensionalviewsofprediateobjets.Thereisadistintionbetweenexaminingthestrutureofanobjetandusingthisstruturetodeterminetheinvoationofode.Asatisfatorymethodmustbeprovidedforrealizingtheswithbetweentheseroles.Finally,anymahinerythatisdesignedforsupportingthenewfeaturesmustbein-terwovenintotherun-timedeviesandapproahestoompilationthatareommonlyusedinlogiprogrammingimplementation.Theproperombinationofallthesemehanismsinonesyst