A Context-based Approach to Proving Termination of Evaluation

AbstractWe present a context-based approach to proving termination of evaluation in reduction semantics (i.e., a form of operational semantics with explicit representation of reduction contexts), using Tait-style reducibility predicates defined on both terms and contexts. We consider the simply typed lambda calculus as well as its extension with abortive control operators for first-class continuations under the call-by-value and the call-by-name evaluation strategies. For each of the proofs we present its computational content that takes the form of an evaluator in continuation-passing style and is an instance of normalization by evaluation