Generalizing Shape Analysis with Gradual Types
Tensors are multi-dimensional data structures that can represent the data processed by machine learning tasks. Tensor programs tend to be short and readable, and they can leverage libraries and frameworks such as TensorFlow and PyTorch, as well as modern hardware such as GPUs and TPUs. However, tensor programs also tend to obscure shape information, which can cause shape errors that are difficult to find. Such shape errors can be avoided by a combination of shape annotations and shape analysis, but such annotations are burdensome to come up with manually.
In this paper, we use gradual typing to reduce the barrier of entry. Gradual typing offers a way to incrementally introduce type annotations into programs. From there, we focus on tool support for type migration, which is a concept that closely models code-annotation tasks and allows us to do shape reasoning and utilize it for different purposes. We develop a comprehensive gradual typing theory to reason about tensor shapes. We then ask three fundamental questions about a gradually typed tensor program. (1) Does the program have a static migration? (2) Given a program and some arithmetic constraints on shapes, can we migrate the program according to the constraints? (3) Can we eliminate branches that depend on shapes? We develop novel tools to address the three problems. For the third problem, there are currently two PyTorch tools that aim to eliminate branches. They do so by eliminating them for just a single input. Our tool is the first to eliminate branches for an infinite class of inputs, using static shape information. Our tools help prevent bugs, alleviate the burden on the programmer of annotating the program, and improves the process of program transformation.
Tue 17 SepDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
15:30 - 17:00 | |||
15:30 15mTalk | InferType: A Compiler Toolkit for Implementing Efficient Constraint-Based Type Inference Technical Papers Senxi Li The University of Tokyo, Tetsuro Yamazaki University of Tokyo, Shigeru Chiba University of Tokyo | ||
15:45 15mTalk | A Sound Type System for Secure Currency Flow Technical Papers Luca Aceto Reykjavik University, Daniele Gorla Department of Computer Science, Sapienza University of Rome, Stian Lybech Reykjavik University | ||
16:00 15mTalk | Type Tailoring Technical Papers Ashton Wiersdorf University of Utah, Stephen Chang University of Massachusetts Boston, Matthias Felleisen Northeastern University, Ben Greenman University of Utah | ||
16:15 15mTalk | Learning Gradual Typing Performance Technical Papers Mohammad Wahiduzzaman Khan UL Lafayette, Sheng Chen University of Louisiana at Lafayette, Yi He Old Dominion University | ||
16:30 15mTalk | Generalizing Shape Analysis with Gradual Types Technical Papers Zeina Migeed University of California, Los Angeles, James Reed Fireworks AI, Jason Ansel Meta, Jens Palsberg University of California, Los Angeles (UCLA) | ||
16:45 15mTalk | Refinements for Multiparty Message-Passing Protocols: Specification-agnostic theory and implementation Technical Papers |