Modular Termination for Second-Order Computation Rules and Application to Algebraic Effect Handlers

We present a new modular proof method of termination for second-ordercomputation, and report its implementation SOL. The proof method is useful forproving termination of higher-order foundational calculi. To establish themethod, we use a variation of semantic labelling translation and Blanqui'sGeneral Schema: a syntactic criterion of strong normalisation. As anapplication, we apply this method to show termination of a variant ofcall-by-push-value calculus with algebraic effects and effect handlers. We alsoshow that our tool SOL is effective to solve higher-order termination problems