×

An open logical framework. (English) Zbl 1352.68061

Summary: The \(\mathsf{LF}_{\mathcal{P}}\) Framework is an extension of the Harper-Honsell-Plotkin’s Edinburgh Logical Framework \(\mathsf{LF}\) with external predicates, hence the name Open Logical Framework. This is accomplished by defining lock type constructors, which are a sort of \(\diamond\)-modality constructors, releasing their argument under the condition that a possibly external predicate is satisfied on an appropriate typed judgement. Lock types are defined using the standard pattern of constructive type theory, i.e. via introduction, elimination and equality rules. Using \(\mathsf{LF}_{\mathcal{P}}\), one can factor out the complexity of encoding specific features of logical systems, which would otherwise be awkwardly encoded in LF, e.g. side-conditions in the application of rules in Modal Logics, and sub-structural rules, as in non-commutative Linear Logic. The idea of \(\mathsf{LF}_{\mathcal{P}}\) is that these conditions need only to be specified, while their verification can be delegated to an external proof engine, in the style of the Poincaré Principle or Deduction Modulo. Indeed such paradigms can be adequately formalized in \(\mathsf{LF}_{\mathcal{P}}\). We investigate and characterize the meta-theoretical properties of the calculus underpinning \(\mathsf{LF}_{\mathcal{P}}\): strong normalization, confluence and subject reduction. This latter property holds under the assumption that the predicates are well-behaved, i.e. closed under weakening, permutation, substitution and reduction in the arguments. Moreover, we provide a canonical presentation of \(\mathsf{LF}_{\mathcal{P}}\), based on a suitable extension of the notion of \(\beta\eta\)-long normal form, allowing for smooth formulations of adequacy statements.

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
03B70 Logic in computer science
68N18 Functional programming and lambda calculus