Volume 39, Number 1, 1-47, DOI: 10.1007/s10817-006-9061-y

Reasoning about Object-based Calculi in (Co)Inductive Type Theory and the Theory of Contexts

Alberto Ciaffaglione, Luigi Liquori and Marino Miculan

View Related Documents

Abstract

We illustrate a methodology for formalizing and reasoning about Abadi and Cardelli’s object-based calculi, in (co)inductive type theory, such as the Calculus of (Co)Inductive Constructions, by taking advantage of natural deduction semantics and coinduction in combination with weak higher-order abstract syntax and the Theory of Contexts. Our methodology allows us to implement smoothly the calculi in the target metalanguage; moreover, it suggests novel presentations of the calculi themselves. In detail, we present a compact formalization of the syntax and semantics for the functional and the imperative variants of the ς-calculus. Our approach simplifies the proof of subject deduction theorems, which are proved formally in the proof assistant Coq with a relatively small overhead.

Keywords  Functional and imperative object-calculi - Logical foundations of programming - Coinductive type theories - Logical frameworks - Interactive theorem proving

Supported by UE project IST-CA-510996 Types and French grant CNRS ACI Modulogic.

Fulltext Preview

Image of the first page of the fulltext document