AUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming

Robert Schenck, Nikolaj Hey Hinnerskov, Troels Henriksen, Magnus Madsen, Martin Elsman

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Article number334
JournalProceedings of the ACM on Programming Languages
Volume8
Issue numberOOPSLA2
DOIs
Publication statusPublished - 8 Oct 2024
Externally publishedYes

Fingerprint

Dive into the research topics of 'AUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming'. Together they form a unique fingerprint.

Cite this