sign in
english version rss feed

inria-00582570, version 3

On the Power of Coercion Abstraction

Julien Cretin () 1, Didier Rémy () 1

N° RR-7587 (2011)

Abstract: Erasable coercions in System F-eta, also known as retyping functions, are well-typed eta-expansions of the identity. They may change the type of terms without changing their behavior and can thus be erased before reduction. Coercions in F-eta can model subtyping of known types and some displacement of quantifiers, but not subtyping assumptions nor certain forms of delayed type instantiation. We generalize F-eta by allowing abstraction over retyping functions. We follow a general approach where computing with coercions can be seen as computing in the lambda-calculus but keeping track of which parts of terms are coercions. We obtain a language where coercions do not contribute to the reduction but may block it and are thus not erasable. We recover erasable coercions by choosing a weak reduction strategy and restricting coercion abstraction to value-forms or by restricting abstraction to coercions that are polymorphic in their domain or codomain. The latter variant subsumes F-eta, F-sub, and MLF in a unified framework.

  • Domain : Computer Science/Programming Languages
  • Keywords : Types – Système F – Polymorphisme – Coercion – Conversion – Fonction de retypage – Type containment – Sous-typage – Bounded Polymorphism
  • Internal note : RR-7587
  • Available versions :  v1 (2011-04-04) v2 (2011-07-15) v3 (2011-12-12)
 
  • inria-00582570, version 3
  • oai:hal.inria.fr:inria-00582570
  • From: 
  • Submitted on: Monday, 12 December 2011 14:14:37
  • Updated on: Monday, 12 December 2011 15:46:52
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...