Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

Coercive type isomorphism

Authors: Satish R. Thatte;

Coercive type isomorphism

Abstract

There is a variety of situations in programming in which it is useful to think of two distinct types as representations of the same abstract structure. However, language features which allow such relations to be effectively expressed at an abstract level are lacking. We propose a generalization of ML-style type inference to deal effectively with this problem. Under the generalization, the (normally free) algebra of type expressions is subjected to an equational theory generated by a finite set of user-specified equations that express interconvertibility relations between objects of “equivalent” types. Each type equation is accompanied by a pair of conversion functions that are (at least partial) inverses. We show that so long as the equational theory satisfies a reasonably permissive syntactic constraint, the resulting type system admits a complete type inference algorithm that produces unique principal types. The main innovation required in type inference is the replacement of ordinary free unification by unification in the userspecified equational theory. The syntactic constraint ensures that the latter is unitary, i.e., yields unique most general unifiers. The proposed constraint is of independent interest as the first known syntactic characterization for a class of unitary theories. Some of the applications of the system are similar to those of Wadler's views [Wad87]. However, our system is considerably more general, and more orthogonal to the underlying language.

Related Organizations
  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    2
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
2
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!