Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
We present a simple, practical, and expressive type and effect system based on Boolean constraints. The effect system extends the Hindley-Milner type system, supports parametric polymorphism, and preserves principal types modulo Boolean equivalence. We show how to support type inference by extending Algorithm W with Boolean unification based on the successive variable elimination algorithm. We implement the type and effect system in the Flix programming language. We perform an in-depth evaluation on the impact of Boolean unification on type inference time and end-to-end compilation time. While the computational complexity of Boolean unification is NP-hard, the experimental results demonstrate that it works well in practice. We find that the impact on type inference time is on average a 1.4x slowdown and the overall impact on end-to-end compilation time is a 1.1x slowdown.
Original language | English |
---|---|
Title of host publication | Proceedings of the ACM on Programming Languages |
Number of pages | 29 |
Volume | 4 |
Publisher | Association for Computing Machinery |
Publication year | 13 Nov 2020 |
Edition | OOPSLA |
DOIs | |
Publication status | Published - 13 Nov 2020 |
Series | ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages and Applications |
---|
Publisher Copyright:
© 2020 Owner/Author.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
See relations at Aarhus University Citationformats
ID: 215997179