ATreatmentofHigher-OrderFeaturesinLogiProgrammingGopalanNadathurDepartmentofComputerSieneandEngineeringUniversityofMinnesota4-192EE/CSBuilding,200UnionStreetS.E.Minneapolis,MN55455gopalans.umn.eduAbstratThelogiprogrammingparadigmprovidesthebasisforanewintensionalviewofhigher-ordernotions.Thisviewisrealizedprimarilybyemployingthetermsofatypedlambdaalulusasrepresentationaldeviesandbyusingariherformofuni ationforprobingtheirstrutures.Theseadditionshaveimportantmeta-programmingappliationsbuttheyalsoposenon-trivialimplementationproblems.Oneissueonernsthemahinerepresen-tationoflambdatermssuitabletotheirintendeduse:anadequateenodingmustfailitateomparisonoperationsovertermsinadditiontosupportingtheusualredutionomputa-tion.Anotheraspetrelatestothetreatmentofauni ationoperationthathasabranhingharaterandthatsometimesallsforthedelayingofthesolutionofuni ationproblems.A nalissueonernstheexeutionofgoalswhosestruturesbeomesapparentonlyintheourseofomputation.Thesevariousproblemsareexposedinthispaperandsolutionstothemaredesribed.Asatisfatoryrepresentationforlambdatermsisdevelopedbyexploit-ingthenamelessnotationofdeBruijnaswellasexpliitenodingsofsubstitutions.SpeialmehanismsaremoldedintothestrutureoftraditionalPrologimplementationstosupportbranhinginuni ationandarryingofuni ationproblemsoverotheromputationsteps;apremiumisplaedinthisontextonexploitingdeterminismandonemulatingusual rst-orderbehaviour.Anextendedompilationmodelispresentedthattreatshigher-orderuni ationandalsohandlesdynamiallyemergentgoals.TheideasdesribedherehavebeenemployedintheTeyjusimplementationofthe Prologlanguage,afatthatisusedtoobtainapreliminaryassessmentoftheireÆay.Keywords:lambdaalulus,intensionalhigher-orderprogramming,higher-orderuni a-tion,abstratmahine,ompilation.1IntrodutionCustomaryaquaintanewithhigher-ordernotionsinprogrammingrelatestotheimperativeorfuntionalprogrammingparadigms.Withintheseframeworks,funtionsareequatedwiththemethodsforomputingthatareembodiedinproedures.Higher-ordernessthenonsistsoftheabilitytoobjetifysuhfuntionsand,thereby,toembedthemindataorpassthem1asargumentstootherfuntions.Manyinterestingappliationshavebeenfoundforsuhapabilities.However,allofthesearedependentonauniformextensionalviewoffuntions.Inpartiular,theonlyobservableaspetofsuhobjetsistheirabilitytotransformgivenargumentsintoresultvalues.Logiprogramminghasthepotentialforsupportingadi erentand,insomesenses,moresophistiatedunderstandingofhigher-ordernotions[36℄.Funtionsareusedwithinthisparadigmasameansforonstrutingdesriptionsofobjets.Suhdesriptionsanbeexaminedbymeansofuni ation,anoperationthatisusefulintheanalysisofintensions.Traditionallogiprogramminglanguagesmanifestaweakexploitationofthisapabilitybe-ausetheypermitonlyindividual,non-funtion,objetsasvalues.However,itispossibletosupporttheprobingoffuntionstrutureingenuinelyhigher-orderwaysbyintroduingamehanismsuhasthetermsofalambdaalulusforenodingfuntionobjetsandbyomplementingthiswithrihernotionsofvariablesanduni ation.Theusualformofhigher-orderprogramminganberealizedsimplybyusingtheabilitytorepresentfuntionvaluedobjetsandtheextensionalinterpretationbuiltintologiprogrammingofonekindoffuntion,namely,prediates.Theriherintensionalviewoffuntionso ers,inaddition,manypossibilitiesthathavenotbeensystematiallysupportedbyanypreviousprogram-mingparadigm.Toonsideroneimportantdiretion,theabilitytouselambdatermsasrepresentationaldevieslendsitselfwelltoanabstratviewofsyntaxthattreatsbindingnotionsexpliitly[27,41℄,leadingtherebytomanynovelmetalanguageappliationsforlogiprogramming(e.g.,see[5,15,17,18,40℄).Whilethereisonsiderableappliationpotentialforhigher-orderfeaturesinlogipro-gramming,theadditionofsuhfeaturesalsoraisessigni antimplementationproblems.Oneategoryofproblemsarisesfromtheusethatismadeofthetermsofalambdaalu-lusessentiallyasdatastrutures.Thisisatrulynovelroleforsuhtermsinprogramming,andarepresentationmustbedevelopedforthemthatsupportstheiruseinthisapaity.Asatisfatoryrepresentationshouldpermittheexaminationoftermstrutureandmustfailitatetheomparisonoftermsinasituationwherethepartiularnamesofboundvari-ablesareunimportant,inadditiontoeÆientlysupportingtheusualredutionoperationonterms.Anotherlassofproblemsrelatestothefatthattheuni ationomputationonlambdaterms,knownashigher-orderuni ation[20℄,possessesharaterististhataredistintfromthoseoftheustomary rst-orderuni ation.Inpartiular,performingthisoperationmayinvolveabranhingsearhanditmayalsobeneessarytotemporarily‘suspend’theomputationbeforeauni erisfound.Suitabledynamisupportmustbedesribedforbothfaets.Athirdaspetthatneedsspeialonsiderationisthemixingofintensionalandextensionalviewsofprediateobjets.Thereisadistintionbetweenexaminingthestrutureofanobjetandusingthisstruturetodeterminetheinvoationofode.Asatisfatorymethodmustbeprovidedforrealizingtheswithbetweentheseroles.Finally,anymahinerythatisdesignedforsupportingthenewfeaturesmustbein-terwovenintotherun-timedeviesandapproahestoompilationthatareommonlyusedinlogiprogrammingimplementation.Theproperombinationofallthesemehanismsinonesyst