Shoggoth - A Formal Foundation for Strategic Rewriting
summary
Provides a formal denotational semantics for System S and a big-step operational semantics that explicitly models divergence, proves computational soundness and adequacy, and mechanises all proofs in Isabelle/HOL. Introduces a location-based weakest precondition calculus for reasoning about nondeterminism (angelic for errors, demonic for divergence), termination, and composition; shows how sequential composition and repeat can be provably “bad” (empty precondition), and notes real workloads where rewrites take ~50,000 steps.
AI-written summary · about