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

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 experie...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of ACM on programming languages 2024-10, Vol.8 (OOPSLA2), p.1787-1813, Article 334
Main Authors: Schenck, Robert, Hinnerskov, Nikolaj Hey, Henriksen, Troels, Madsen, Magnus, Elsman, Martin
Format: Article
Language:English
Subjects:
Functional languages
Parallel programming languages
Software and its engineering
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2475-1421
2475-1421
DOI:10.1145/3689774