@article{10.1145/3689774,
author = {Schenck, Robert and Hinnerskov, Nikolaj Hey and Henriksen, Troels and Madsen, Magnus and Elsman, Martin},
title = {AUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming},
year = {2024},
issue_date = {October 2024},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {8},
number = {OOPSLA2},
url = {https://doi.org/10.1145/3689774},
doi = {10.1145/3689774},
abstract = {Dynamically typed array languages such as Python, APL, and Matlab lift scalar operations to arrays and replicate scalars to fit applications. We present a mechanism for automatically inferring map and replicate operations in a statically-typed language in a way that resembles the programming experience of a dynamically-typed language while preserving the static typing guarantees. Our type system---which supports parametric polymorphism, higher-order functions, and top-level let-generalization---makes use of integer linear programming in order to find the minimum number of operations needed to elaborate to a well-typed program. We argue that the inference system provides useful and unsurprising guarantees to the programmer. We demonstrate important theoretical properties of the mechanism and report on the implementation of the mechanism in the statically-typed array programming language Futhark.},
journal = {Proc. ACM Program. Lang.},
month = oct,
articleno = {334},
numpages = {27},
keywords = {array programming, constraint-based type systems, data parallelism}
}