Pipelines and Beyond: Graph Types for ADTs with Futures

Explore a groundbreaking approach to modeling parallel programs through graph types in this 20-minute conference talk from POPL 2024. Delve into the innovative work of researchers from Illinois Institute of Technology, Boston University, and Rochester Institute of Technology as they present a new graph type system that allows for extensive combinations of futures and recursive data types. Learn how this system overcomes limitations in prior work by indexing datatypes with type-level vertex structures, enabling the representation of complex pipelining algorithms. Discover the implications for detecting bugs, visualizing parallel structure, and achieving enhanced performance in parallel programming. Examine the soundness proof of the system in a parallel core calculus and understand how these annotations can be inferred from OCaml-like source code. Gain insights into the potential applications of this research for developing more efficient and robust parallel algorithms.