Incremental computations are those that process input changes faster than a naive recomputation from scratch. Due to the importance and prevalence of incremental, reactive systems, ad hoc variants of incremental computation are ubiquitous in modern software systems. As an everyday example, spreadsheets such as Excel re-calculate selectively based on user interaction and the dynamic dependencies of formula. Incremental computation is needed in this domain, and many others, for efficiency and responsiveness. As other examples, build systems and integrated development environments re-compile selectively, based on the code dependencies. Hence, build systems strive to use a domain-specific form of incremental computation that is aware of compiler dependencies Erdweg et al. , Szabo et al. . Doing so is necessary to support interactive development, testing and debugging, which should be responsive to code changes. Meanwhile, the interactive behavior of the visual elements in the development tools, and their interaction with external tools, can be modeled with reactive computation. Finally, modern web browsers (such as Chrome, Firefox, Safari, etc.) house incremental computations that respond to mobile code, whose execution leads to re-computing layout and styling information (viz., dynamic variation of CSS attributes incrementally affect the placement and appearance of modern web pages). These scripts, as well as the browser platform in which they run, are incremental, reactive computations [Anderson et al., 2015].
Due to their prevalence in practical systems used every day, notions of incremental computing abound in computer science broadly, and within research on programming languages (PL). In the area of PL, researchers are particularly interested in language-based approaches to incremental computation. In contrast to the algorithms community that often studies each incremental problem in isolation (e.g., incremental convex hull), PL researchers study large classes of incremental programs that are defined by a general language. Their typical goal is to provide a language and associated technique that is general enough to express the behavior of many incremental or reactive programs. For instance, many general-purpose techniques can derive the incremental behavior of two-dimensional convex hull from the expression of a textbook algorithm for the non-incremental algorithm (e.g., quickhull) [Acar et al., 2006, Hammer and Acar, 2008, Acar and Ley-Wild, 2009, Hammer et al., 2015]. More generally, researchers have shown that for certain algorithms, inputs, and classes of input changes, IC delivers large, even asymptotic speed-ups over full reevaluation [Acar et al., 2007, 2008]. IC has been developed in many different language settings [Shankar and Bodik, 2007, Hammer et al., 2007, 2009, Chen et al., 2014], and has even been used to address open problems, e.g., in computational geometry [Acar et al., 2010].
Call for Papers
|Thu 22 Jun 2017 - new|
- No members yet