TY - JOUR
T1 - AUTOMAP
T2 - Inferring Rank-Polymorphic Function Applications with Integer Linear Programming
AU - Schenck, Robert
AU - Hinnerskov, Nikolaj Hey
AU - Henriksen, Troels
AU - Madsen, Magnus
AU - Elsman, Martin
PY - 2024/10/8
Y1 - 2024/10/8
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85206945759&partnerID=8YFLogxK
U2 - 10.1145/3689774
DO - 10.1145/3689774
M3 - Article
SN - 2475-1421
VL - 8
JO - Proceedings of the ACM on Programming Languages
JF - Proceedings of the ACM on Programming Languages
IS - OOPSLA2
M1 - 334
ER -