The tail-recursion modulo \textit{cons} transformation can rewrite functions that are
not quite tail-recursive into a tail-recursive form that can be executed
efficiently. In this article we generalize tail recursion modulo \textit{cons} (TRMc)
to modulo \textit{contexts} (TRMC), and calculate a general TRMC algorithm from its
specification. We can instantiate our general algorithm by providing an
implementation of application and composition on abstract contexts, and showing
that our \textit{context} laws_ hold. We provide some known instantiations of TRMC,
namely modulo \textit{evaluation contexts} (CPS), and \textit{associative operations}, and further
instantiantions not so commonly associated with TRMC, such as
\textit{defunctionalized} evaluation contexts, \textit{monoids}, \textit{semirings},
\textit{exponents}, and \textit{cons products}. We study the modulo \textit{cons} instantiation in particular and prove
that an instantiation using Minamide's hole calculus is sound. We also
calculate a second instantiation in terms of the Perceus heap semantics to
precisely reason about the soundness of in-place update. While all previous
approaches to TRMc fail in the presence of non-linear control (for example
induced by call/cc, shift/reset or algebraic effect handlers), we can elegantly
extend the heap semantics to a hybrid approach which dynamically adapts to
non-linear control flow. We have a full implementation of hybrid TRMc in the
Koka language and our benchmark shows the TRMc transformed functions are always
as fast or faster than using manual alternatives.