  Motivated by the increasing shift to multicore computers, recent work has
developed language support for responsive parallel applications that mix
compute-intensive tasks with latency-sensitive, usually interactive, tasks.
These developments include calculi that allow assigning priorities to threads,
type systems that can rule out priority inversions, and accompanying cost
models for predicting responsiveness. These advances share one important
limitation: all of this work assumes purely functional programming. This is a
significant restriction, because many realistic interactive applications, from
games to robots to web servers, use mutable state, e.g., for communication
between threads.
  In this paper, we lift the restriction concerning the use of state. We
present $\lambda_i^4$, a calculus with implicit parallelism in the form of
prioritized futures and mutable state in the form of references. Because both
futures and references are first-class values, $\lambda_i^4$ programs can
exhibit complex dependencies, including interaction between threads and with
the external world (users, network, etc). To reason about the responsiveness of
$\lambda_i^4$ programs, we extend traditional graph-based cost models for
parallelism to account for dependencies created via mutable state, and we
present a type system to outlaw priority inversions that can lead to unbounded
blocking. We show that these techniques are practical by implementing them in
C++ and present an empirical evaluation.
