Language Support for Efficient Dynamic Computation

While programming language researchers have the techniques and tools to design and develop programming languages that can improve the algorithmic—not just runtime—efficiency of computations, they usually avoid doing so, leaving this problem instead to algorithm designers. This approach results in a clean division of labor: programming language researchers focus on correctness and semantics and the algorithms researchers focus on algorithmic effi- ciency. It can, however, lead to undesirable outcomes such as impractical, overly complicated algorithms, and inefficient programming languages. We feel that integrating concerns of algorithm efficiency into the language design can improve the impact of programming languages research. In this paper, we propose to study a notion of continuity which we call dynamic optimality, for the purpose of improved efficiency of computations operating on dynamically changing data.