An Extension to ML to Handle Bound Variables in Data Structures: Preliminary Report

Description

Niveau: Supérieur, Doctorat, Bac+8
An Extension to ML to Handle Bound Variables in Data Structures: Preliminary Report Dale Miller Computer and Information Science University of Pennsylvania Philadelphia, PA 19104–6389 USA Abstract Most conventional programming languages have direct methods for representing first-order terms (say, via concrete datatypes in ML). If it is necessary to represent structures containing bound variables, such as ?-terms, formulas, types, or proofs, these must first be mapped into first-order terms, and then a significant number of auxiliary procedures must be implemented to manage bound variable names, check for free occurrences, do substitution, test for equality modulo alpha- conversion, etc. We shall show how the applicative core of the ML programming language can be enhanced so that ?-terms can be represented more directly and so that the enhanced language, called ML?, provides a more elegant method of manipulating bound variables within data structures. In fact, the names of bound variables will not be accessible to the ML? programmer. This extension to ML involves the following: introduction of the new type constructor 'a => 'b for the type of ?-terms formed by abstracting a parameter of type 'a out of a term of type 'b; a very restricted and simple form of higher-order pattern matching; a method for extending a given data structure with a new constructor; and, a method for extending function definitions to handle such new constructors.

• conventional programming


• bound variable


• higher-order abstract


• required when


• syntax since general


• discharge has


• untyped ?-terms


• language can

Sujets

• Hannan
• Free variables and bound variables

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 30
• Langue: English

Extrait

AnExtensiontoMLtoHandleBoundVariables inDataStructures: PreliminaryReport DaleMiller ComputerandInformationScience UniversityofPennsylvania Philadelphia,PA19104–6389USA [e-mail] Abstract Mostconventionalprogramminglanguageshavedirectmethodsforrepresentingfirst-orderterms (say,viaconcretedatatypesinML).Ifitisnecessarytorepresentstructurescontainingbound variables,suchasλ-terms,formulas,types,orproofs,thesemustfirstbemappedintofirst-order terms,andthenasignificantnumberofauxiliaryproceduresmustbeimplementedtomanage boundvariablenames,checkforfreeoccurrences,dosubstitution,testforequalitymoduloalpha- conversion,etc.WeshallshowhowtheapplicativecoreoftheMLprogramminglanguagecanbe enhancedsothatλ-termscanberepresentedmoredirectlyandsothattheenhancedlanguage,called ML λ ,providesamoreelegantmethodofmanipulatingboundvariableswithindatastructures.In fact,thenamesofboundvariableswillnotbeaccessibletotheML λ programmer.Thisextension toMLinvolvesthefollowing:introductionofthenewtypeconstructor’a=>’bforthetypeof λ-termsformedbyabstractingaparameteroftype’aoutofatermoftype’b;averyrestrictedand simpleformofhigher-orderpatternmatching;amethodforextendingagivendatastructurewitha newconstructor;and,amethodforextendingfunctiondefinitionstohandlesuchnewconstructors. WepresentseveralexamplesofML λ programs. 1Introduction Recentworkinthespecificationofawidevarietyofmeta-programmingsystems—typecheckers andinferrers,theoremprovers,programmanipulationsystems,evaluators,andcompilers—has revealedseveralimportantspecificationtechniques,includingonecalledhigher-orderabstractsyntax [16].Thisspecificationtechniqueusesatypedλ-calculustosuccinctlycapturemanycomplex syntacticnotionspertainingtodatastructurescontainingnotionsofboundvariables,suchasthose offreeandboundoccurrences,scopesofbinders,equalityuptoalphabeticchangeofboundvariable names,andsubstitutions.HuetandLang[9]seemtohavebeenthefirsttorecognizethepotential ofthisapproachtoabstractsyntaxinanactualimplementation.Someoftheirideaswerelater generalizedin[11]toalogicprogrammingsetting.Higher-orderabstractsyntaxisnowcentralto 1 ThisresearchwassupportedinpartbygrantsONRN00014-88-K-0633,NSFCCR-87-05596,andDARPAN00014- 85-K-0018.ThispaperwasfirstpresentedattheLogicalFrameworksBasicResearchActionmeetinginNice,France, 7–12May1990.IamgratefultoJohnHannan,FrankPfenning,andseveralattendeesoftheLogicalFrameworks BRAWorkshopforcommentsonthecontentofthispaper. 1