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

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

3 Downloads (Pure)

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
Number of pages27
DOIs
Publication statusPublished - 2024

Bibliographical note

Publisher Copyright:
© 2024 Owner/Author.

Keywords

  • array programming
  • constraint-based type systems
  • data parallelism

Cite this