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.