Representing and reasoning with operational semantics

Description

Niveau: Supérieur, Doctorat, Bac+8
Representing and reasoning with operational semantics Dale Miller INRIA & LIX, Ecole Polytechnique Abstract. The operational semantics of programming and specification languages is often presented via inference rules and these can generally be mapped into logic programming-like clauses. Such logical encodings of operational semantics can be surprisingly declarative if one uses logics that directly account for term-level bindings and for resources, such as are found in linear logic. Traditional theorem proving techniques, such as unification and backtracking search, can then be applied to animate operational semantic specifications. Of course, one wishes to go a step further than animation: using logic to encode computation should facil- itate formal reasoning directly with semantic specifications. We outline an approach to reasoning about logic specifications that involves view- ing logic specifications as theories in an object-logic and then using a meta-logic to reason about properties of those object-logic theories. We motivate the principal design goals of a particular meta-logic that has been built for that purpose. 1 Roles for logic in the specification of computations There are two broad approaches to using logic to specify computational systems. In the computation-as-model approach, computations are encoded as mathemat- ical structures, containing such items as nodes, transitions, and state. Logic is used in an external sense to make statements about those structures. That is, computations are used as models for logical expressions.

• logic


• rules into


• approach


• cut elimination


• while such


• has provided


• computation


• such


• builds cut-free

Sujets

• École polytechnique
• Approach
• Cut-elimination theorem
• Computation

Informations

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

Extrait

Representingandreasoningwithoperational semantics DaleMiller INRIA&LIX,E ´ colePolytechnique Abstract. Theoperationalsemanticsofprogrammingandspecification languagesisoftenpresentedviainferencerulesandthesecangenerally bemappedintologicprogramming-likeclauses.Suchlogicalencodings ofoperationalsemanticscanbesurprisinglydeclarativeifoneuseslogics thatdirectlyaccountforterm-levelbindingsandforresources,suchas arefoundinlinearlogic.Traditionaltheoremprovingtechniques,such asunificationandbacktrackingsearch,canthenbeappliedtoanimate operationalsemanticspecifications.Ofcourse,onewishestogoastep furtherthananimation:usinglogictoencodecomputationshouldfacil- itateformalreasoningdirectlywithsemanticspecifications.Weoutline anapproachtoreasoningaboutlogicspecificationsthatinvolvesview- inglogicspecificationsastheoriesinanobject-logicandthenusinga meta-logictoreasonaboutpropertiesofthoseobject-logictheories.We motivatetheprincipaldesigngoalsofaparticularmeta-logicthathas beenbuiltforthatpurpose. 1Rolesforlogicinthespecificationofcomputations Therearetwobroadapproachestousinglogictospecifycomputationalsystems. Inthecomputation-as-modelapproach,computationsareencodedasmathemat- icalstructures,containingsuchitemsasnodes,transitions,andstate.Logicis usedinanexternalsensetomakestatements about thosestructures.Thatis, computationsareusedasmodelsforlogicalexpressions.Intensionaloperators, suchasthemodalsoftemporalanddynamiclogicsorthetriplesofHoarelogic, areoftenemployedtoexpresspropositionsaboutthechangeinstate.Thisuse oflogictorepresentandreasonaboutcomputationisprobablytheoldestand mostbroadlysuccessfuluseoflogicforspecifyingcomputation. Thecomputation-as-deductionapproachusespiecesoflogic’ssyntax(formu- las,terms,types,andproofs)directlyaselementsofthespecifiedcomputation. Inthismuchmorerarefiedsetting,therearetworatherdifferentapproachesto howcomputationismodeled.Theproofnormalizationapproachviewsthestate ofacomputationasaprooftermandtheprocessofcomputingasnormalization (viaβ-reductionorcut-elimination).Functionalprogrammingcanbeexplained usingproof-normalizationasitstheoreticalbasis[23].The proofsearch approach viewsthestateofacomputationasasequent(astructuredcollectionofformu- las)andtheprocessofcomputingasthesearchforaproofofasequent:the changesthattakeplaceinsequentscapturethedynamicsofcomputation.Proof