Termination analysis based on operational semantics

Abstract

In principle termination analysis is easy: find a well-founded partial order and prove that calls decrease with respect to this order. In practice this often requires an oracle (or a theorem prover) for determining the well-founded order and this oracle may not be easily implementable. Our approach circumvents some of these problems by exploiting the inductive definition of algebraic data types and using pattern matching as in functional languages. We develop a termination analysis for a higher-order functional language; the analysis incorporates and extends polymorphic type inference and axiomatizes a class of well-founded partial orders for multiple-argument functions (as in Standard ML and Miranda). Semantics is given by means of operational (natural-style) semantics and soundness is proved; this involves making extensions to the semantic universe and we relate this to the techniques of denotational semantics. For dealing with the partiality aspects of the soundness proof, it suffices to incorporate approximations to the desired fixed points; for dealing with the totality aspects of the soundness proof, we also have to incorporate functions that are forced to terminate (in a way that might violate the monotonicity of denotational semantics).