A Realizability Model for a Semantical Value Restriction - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2015

A Realizability Model for a Semantical Value Restriction

Résumé

Reconciling dependent product and classical logic with call-by-value evaluation is a difficult problem. It is the first step toward a classical proof system for an ML-like language. In such a system, the introduction rule for universal quantification and the elimination rule for dependent product need to be restricted: they can only be applied to values. This value restriction is acceptable for universal quantification (ML-like polymorphism) but makes dependent product unusable in practice. In order to circumvent this limitation we introduce new typing rules and prove their consistency by constructing a realizability model in three layers (values, stacks and terms). Such a technique has already been used to account for classical ML-like polymorphism in call-by-value, and we here extend it to handle dependent product. The main idea is to internalize observational equivalence as a new non-computable operation in the calculus. A crucial property of the obtained model is that the biorthogonal of a set of values which is closed under observational equivalence does not contain more values than the original set.
Fichier principal
Vignette du fichier
lics2015.pdf (216.89 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01107429 , version 1 (21-01-2015)
hal-01107429 , version 2 (17-03-2016)
hal-01107429 , version 3 (24-03-2016)

Identifiants

Citer

Rodolphe Lepigre. A Realizability Model for a Semantical Value Restriction. 2015. ⟨hal-01107429v2⟩
96 Consultations
142 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More