Info

Public Audience

English

60 Minutes

Saarbrücken

Application data often changes slowly or incrementally over time.
Since incremental changes to input often result in only small changes
in output, it is often feasible to respond to such changes
asymptotically more efficiently than by re-running the whole
computation. Traditionally, realizing such asymptotic efficiency
improvements requires designing problem-specific algorithms known as
dynamic or incremental algorithms, which are often significantly more
complicated than conventional algorithms to design, analyze,
implement, and use. A long-standing open problem is to develop
techniques that automatically transform conventional programs so that
they correctly and efficiently respond to incremental changes.

In this paper, we describe a significant step towards solving the
problem of automatic incrementalization: a programming language and a
compiler that can, given a few type annotations describing what can
change over time, compile a conventional program that assumes its data
to be static (unchanging over time) to an incremental program. Based
on recent advances in self-adjusting computation, including a
theoretical proposal for translating purely functional programs to
self-adjusting programs, we develop techniques for translating
conventional Standard ML programs to self-adjusting programs. By
extending the Standard ML language, we design a fully featured
programming language with higher-order features, a module system, and
a powerful type system, and implement a compiler for this language.
The resulting programming language, LML, enables translating
conventional programs decorated with simple type annotations into
incremental programs that can respond to changes in their data
correctly and efficiently.

We evaluate the effectiveness of our approach by considering a range
of benchmarks involving lists, vectors, and matrices, as well as a ray
tracer. For these benchmarks, our compiler incrementalizes existing
code with only trivial amounts of annotation. The resulting programs
are often asymptotically more efficient, leading to orders of
magnitude speedups in practice.

--email hidden

passcode not visible

logged in users only