File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: The Duality of Subtyping

TitleThe Duality of Subtyping
Authors
KeywordsDuoTyping
OOP
Duality
Subtyping
Supertyping
Issue Date2020
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. The Journal's web site is located at hhttp://www.dagstuhl.de/publikationen/lipics/
Citation
The 34th European Conference on Object-Oriented Programming (ECOOP 2020), Virtual Conference, Berlin, Germany, 15-17 November 2020. In Hirschfeld, R & Pape, T (Eds.). LIPICS - Leibniz International Proceedings in Informatics, 2020, v. 166, article no. 29, p. 29:1-29:29 How to Cite?
AbstractSubtyping is a concept frequently encountered in many programming languages and calculi. Various forms of subtyping exist for different type system features, including intersection types, union types or bounded quantification. Normally these features are designed independently of each other, without exploiting obvious similarities (or dualities) between features. This paper proposes a novel methodology for designing subtyping relations that exploits duality between features. At the core of our methodology is a generalization of subtyping relations, which we call Duotyping. Duotyping is parameterized by the mode of the relation. One of these modes is the usual subtyping, while another mode is supertyping (the dual of subtyping). Using the mode it is possible to generalize the usual rules of subtyping to account not only for the intended behaviour of one particular language construct, but also of its dual. Duotyping brings multiple benefits, including: shorter specifications and implementations, dual features that come essentially for free, as well as new proof techniques for various properties of subtyping. To evaluate a design based on Duotyping against traditional designs, we formalized various calculi with common OOP features (including union types, intersection types and bounded quantification) in Coq in both styles. Our results show that the metatheory when using Duotyping does not come at a significant cost: the metatheory with Duotyping has similar complexity and size compared to the metatheory for traditional designs. However, we discover new features as duals to well-known features. Furthermore, we also show that Duotyping can significantly simplify transitivity proofs for many of the calculi studied by us.
Persistent Identifierhttp://hdl.handle.net/10722/301310
ISSN
2020 SCImago Journal Rankings: 0.540

 

DC FieldValueLanguage
dc.contributor.authorDos Santos Oliveira, BC-
dc.contributor.authorCui, S-
dc.contributor.authorRehman, B-
dc.date.accessioned2021-07-27T08:09:14Z-
dc.date.available2021-07-27T08:09:14Z-
dc.date.issued2020-
dc.identifier.citationThe 34th European Conference on Object-Oriented Programming (ECOOP 2020), Virtual Conference, Berlin, Germany, 15-17 November 2020. In Hirschfeld, R & Pape, T (Eds.). LIPICS - Leibniz International Proceedings in Informatics, 2020, v. 166, article no. 29, p. 29:1-29:29-
dc.identifier.issn1868-8969-
dc.identifier.urihttp://hdl.handle.net/10722/301310-
dc.description.abstractSubtyping is a concept frequently encountered in many programming languages and calculi. Various forms of subtyping exist for different type system features, including intersection types, union types or bounded quantification. Normally these features are designed independently of each other, without exploiting obvious similarities (or dualities) between features. This paper proposes a novel methodology for designing subtyping relations that exploits duality between features. At the core of our methodology is a generalization of subtyping relations, which we call Duotyping. Duotyping is parameterized by the mode of the relation. One of these modes is the usual subtyping, while another mode is supertyping (the dual of subtyping). Using the mode it is possible to generalize the usual rules of subtyping to account not only for the intended behaviour of one particular language construct, but also of its dual. Duotyping brings multiple benefits, including: shorter specifications and implementations, dual features that come essentially for free, as well as new proof techniques for various properties of subtyping. To evaluate a design based on Duotyping against traditional designs, we formalized various calculi with common OOP features (including union types, intersection types and bounded quantification) in Coq in both styles. Our results show that the metatheory when using Duotyping does not come at a significant cost: the metatheory with Duotyping has similar complexity and size compared to the metatheory for traditional designs. However, we discover new features as duals to well-known features. Furthermore, we also show that Duotyping can significantly simplify transitivity proofs for many of the calculi studied by us.-
dc.languageeng-
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. The Journal's web site is located at hhttp://www.dagstuhl.de/publikationen/lipics/-
dc.relation.ispartofLIPICS - Leibniz International Proceedings in Informatics-
dc.relation.ispartofThe 34th European Conference on Object-Oriented Programming (ECOOP 2020-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectDuoTyping-
dc.subjectOOP-
dc.subjectDuality-
dc.subjectSubtyping-
dc.subjectSupertyping-
dc.titleThe Duality of Subtyping-
dc.typeConference_Paper-
dc.identifier.emailDos Santos Oliveira, BC: bruno@cs.hku.hk-
dc.identifier.authorityDos Santos Oliveira, BC=rp01786-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.4230/LIPIcs.ECOOP.2020.29-
dc.identifier.hkuros323737-
dc.identifier.volume166-
dc.identifier.spage29:1-
dc.identifier.epage29:29-
dc.publisher.placeGermany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats