Fri 30 Oct 2015 13:52 - 14:15 at Grand Station 1 - 11. Programming Language Design Chair(s): Gary 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

oopsla2015
13:30 - 15:00: OOPSLA - 11. Programming Language Design at Grand Station 1
Chair(s): Gary Leavens University of Central Florida
oopsla201513:30 - 13:52
Talk
John WickersonImperial College London, Mark BattyUniversity of Cambridge, Bradford M. BeckmannAdvanced Micro Devices, Inc, Alastair DonaldsonImperial College London
DOI Media Attached
oopsla201513:52 - 14:15
Talk
Matthew HammerUniversity of Maryland, College Park, Joshua DunfieldUniversity of British Columbia, Canada, Kyle HeadleyUniversity of Maryland, College Park, Nicholas LabichUniversity of Maryland at College Park, USA, Jeffrey S. FosterUniversity of Maryland at College Park, USA, Michael HicksUniversity of Maryland at College Park, USA, David Van HornUniversity of Maryland at College Park, USA
DOI
oopsla201514:15 - 14:37
Talk
Tim FelgentreffHPI, Germany, Todd MillsteinUniversity of California at Los Angeles, USA, Alan BorningUniversity of Washington, USA, Robert HirschfeldHPI
DOI
oopsla201514:37 - 15:00
Talk
Michael SteindorferCWI, Netherlands, Jurgen VinjuCWI, Netherlands
Link to publication