Finitary Polymorphism for Optimizing Type-Directed Compilation
We develop a type-theoretical method for optimizing type directed compilation of polymorphic languages, implement the method in a full-scale compiler of Standard ML extended with several advanced features that require type-passing operational semantics, and report its effectiveness through performance evaluation. For this purpose, we first define a predicative second-order lambda calculus with finitary polymorphism, where each type abstraction is explicitly constrained to a finite type universe, and establishes the type soundness with respect to a type-passing operational semantics. Different from a calculus with stratified type universes, type universes of the calculus are terms that represent the exact finite set of instance types. We then develop a universe reconstruction algorithm that takes a term of the standard second-order lambda calculus, checks if the term is typable with finitary polymorphism, and, if typable, constructs a term in the calculus of finitary polymorphism. Based on these results, we present a type-based optimization method for polymorphic functions. Since our formalism is based on the second-order lambda calculus, it can be used to optimize various polymorphic languages. We implement the optimization method for natural (tag-free) data representation and record polymorphism, and evaluate its effectiveness through benchmarks. The evaluation shows that 84% of type passing abstractions are eliminated, and achieves the average of 11% speed-up of compiled code.
Tue 25 SepDisplayed time zone: Guadalajara, Mexico City, Monterrey change
10:30 - 12:00 | Compilation and ConcurrencyResearch Papers at Stifel Theatre Chair(s): Heather Miller Carnegie Mellon University | ||
10:30 22mTalk | Competitive Parallelism: Getting Your Priorities Right Research Papers DOI | ||
10:52 22mTalk | Static Interpretation of Higher-Order Modules in Futhark: Functional GPU Programming in the Large Research Papers Martin Elsman University of Copenhagen, Denmark, Troels Henriksen University of Copenhagen, Denmark, Danil Annenkov Department of Computer Science, University of Copenhagen, Cosmin Oancea University of Copenhagen, Denmark Link to publication DOI | ||
11:15 22mTalk | Finitary Polymorphism for Optimizing Type-Directed Compilation Research Papers Atsushi Ohori Tohoku University, Japan, Katsuhiro Ueno Tohoku University, Hisayuki Mima Tohoku University DOI | ||
11:37 22mTalk | Fault Tolerant Functional Reactive Programming (Functional Pearl) Research Papers Ivan Perez National Institute of Aerospace, USA DOI |