Above the Cut: Sequent Calculus as a High-Level Programming Language
For almost a century, the sequent calculus has proven to be an indispensable theoretical tool for studying logic, proofs, and now, computation. More recently, it also provided new insights about practical concerns of compilation and program optimization. But what would it take to actually program with the sequent calculus directly without cutting yourself on low-level concerns? Here, we aim to address questions around designing a practical, high-level language based on the sequent calculus. This involves several solutions to usability issues when writing sequent calculus programs, including the notion of duality between values and contexts, choosing between implicit versus explicit control flow, and weaving between different ways to react to a value or a context. In the end, we provide a higher-level interface surrounding a sequent calculus core that lets the programmer harness its full, uncompromised expressiveness while still rising above the low-level Cuts.