On Julia's Efficient Algorithm for Subtyping Union Types and Covariant Tuples (Artifact).
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00340375" target="_blank" >RIV/68407700:21240/19:00340375 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.ECOOP.2019.24" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ECOOP.2019.24</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ECOOP.2019.24" target="_blank" >10.4230/LIPIcs.ECOOP.2019.24</a>
Alternative languages
Result language
angličtina
Original language name
On Julia's Efficient Algorithm for Subtyping Union Types and Covariant Tuples (Artifact).
Original language description
The Julia programming language supports multiple dispatch and provides a rich type annotation language to specify method applicability. When multiple methods are applicable for a given call, Julia relies on subtyping between method signatures to pick the correct method to invoke. Julia’s subtyping algorithm is surprisingly complex, and determining whether it is correct remains an open question. In this paper, we focus on one piece of this problem: the interaction between union types and covariant tuples. Previous work normalized unions inside tuples to disjunctive normal form. However, this strategy has two drawbacks: complex type signatures induce space explosion, and interference between normalization and other features of Julia’s type system. In this paper, we describe the algorithm that Julia uses to compute subtyping between tuples and unions – an algorithm that is immune to space explosion and plays well with other features of the language. We prove this algorithm correct and complete against a semantic-subtyping denotational model in Coq
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF15_003%2F0000421" target="_blank" >EF15_003/0000421: Big Code: Scalable Analysis of Massive Code Bases</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
33rd European Conference on Object-Oriented Programming (ECOOP 2019)
ISBN
978-3-95977-111-5
ISSN
1868-8969
e-ISSN
—
Number of pages
24
Pages from-to
1-24
Publisher name
Schloss Dagstuhl - Leibniz Center for Informatics
Place of publication
Wadern
Event location
London
Event date
Jun 15, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—