Total Outcome Logic: Unified Reasoning for a Taxonomy of Program Logics

Abstract

While there is a long tradition of reasoning about (non)termination in program analysis, specialized logics are typically needed to give different termination criteria. This includes partial correctness, where termination is not guaranteed, and total correctness, where it is guaranteed. We present Total Outcome Logic (TOL), a single logic which can express the full spectrum of termination conditions and program properties offered by the aforementioned logics. TOL extends (non)termination and (in)correctness reasoning across different kinds of branching effects, so that a single metatheory powers this reasoning in different kinds of programs, including nondeterministic and probabilistic. We also show that TOL subsumes several recently created taxonomies of (in)correctness logics, so that many different kinds of properties can be proven with a single unified theory.