A Decidable Subtyping Logic for Intersection and Union Types
Abstract
Using Curry-Howard isomorphism, we extend the typed lambda-calculus with intersection and union types, and its corresponding proof-functional logic, previously defined by the authors, with subtyping and explicit coercions.We show the extension of the lambda-calculus to be isomorphic to the Barbanera-Dezani-de’Liguoro type assignment system and we provide a sound interpretation of the proof-functional logic with the
$\mathsf {NJ}(\beta )$ logic, using Mints’ realizers.We finally present a sound and complete algorithm for subtyping in presence of intersection and union types. The algorithm is conceived to work for the (sub)type theory
$\varXi $
.
Domains
Computer Science [cs]Origin | Files produced by the author(s) |
---|
Loading...