  Applications such as Google Docs, Office 365, and Dropbox show a growing
trend towards incorporating multi-user live collaboration functionality into
web applications. These collaborative applications share a need to efficiently
express shared state, and a common strategy for doing so is a shared log
abstraction. Extensive research efforts on log abstractions by the database,
programming languages, and distributed systems communities have identified a
variety of optimization techniques based on the algebraic properties of updates
(i.e., pairwise commutativity, subsumption, and idempotence). Although these
techniques have been applied to specific applications and use-cases, to the
best of our knowledge, no attempt has been made to create a general framework
for such optimizations in the context of a non-trivial update language. In this
paper, we introduce mutation languages, a low-level framework for reasoning
about the algebraic properties of state updates, or mutations. We define BarQL,
a general purpose state-update language, and show how mutation languages allow
us to reason about the algebraic properties of updates expressed in BarQ L .
