Fri 30 Oct 2015 13:52 - 14:15 at Grand Station 1 - 11. Programming Language Design Chair(s): Gary T. Leavens

Over the past thirty years, there has been significant progress in developing general-purpose, language-based approaches to incremental computation, which aims to efficiently update the result of a computation when an input is changed. A key design challenge in such approaches is how to provide efficient incremental support for a broad range of programs. In this paper, we argue that first-class names are a critical linguistic feature for efficient incremental computation. Names identify computations to be reused across differing runs of a program, and making them first class gives programmers a high level of control over reuse. We demonstrate the benefits of names by presenting Nominal Adapton, an ML-like language for incremental computation with names. We describe how to use Nominal Adapton to efficiently incrementalize several standard programming patterns—including maps, folds, and unfolds—and show how to build efficient, incremental probabilistic trees and tries. Since Nominal Adapton's implementation is subtle, we formalize it as a core calculus and prove it is from-scratch consistent, meaning it always produces the same answer as simply re-running the computation. Finally, we demonstrate that Nominal Adapton can provide large speedups over both from-scratch computation and Adapton, a previous state-of-the-art incremental computation system.

Fri 30 Oct

Displayed time zone: Eastern Time (US & Canada) change

13:30 - 15:00
11. Programming Language DesignOOPSLA at Grand Station 1
Chair(s): Gary T. Leavens University of Central Florida
13:30
22m
Talk
Remote-Scope Promotion: Clarified, Rectified, and VerifiedOOPSLA Artifact
OOPSLA
John Wickerson Imperial College London, Mark Batty University of Cambridge, Bradford M. Beckmann Advanced Micro Devices, Inc, Alastair F. Donaldson Imperial College London
DOI Media Attached
13:52
22m
Talk
Incremental Computation with NamesOOPSLA Artifact
OOPSLA
Matthew Hammer University of Maryland, College Park, Jana Dunfield University of British Columbia, Canada, Kyle Headley University of Maryland, College Park, Nicholas Labich University of Maryland at College Park, USA, Jeffrey S. Foster University of Maryland at College Park, USA, Michael Hicks University of Maryland at College Park, USA, David Van Horn University of Maryland at College Park, USA
DOI
14:15
22m
Talk
Checks and Balances: Constraint Solving without Surprises in Object-Constraint Programming LanguagesOOPSLA Artifact
OOPSLA
Tim Felgentreff HPI, Germany, Todd Millstein University of California at Los Angeles, USA, Alan Borning University of Washington, USA, Robert Hirschfeld HPI
DOI
14:37
22m
Talk
Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM CollectionsOOPSLA Artifact
OOPSLA
Michael Steindorfer CWI, Netherlands, Jurgen Vinju CWI, Netherlands
Link to publication