We adapt Kahn-style (\big-step") natural semantics to take on desirable aspects of small-step and denotational semantics forms, more precisely: (i) the ability to express divergent computations; (ii) the ability to reason about the (length of a) computation of a derivation; and (iii) the ability to compute upon and reason about higher-order values. To accomplish these results, we extend the classical, inductive interpretation of natural semantics with coinduction mechanisms and use \negative" rules to express divergence. A simple reformatting of the syntax of derivations allows a simple description of the \length" of a derivation. Finally, the recoding of closure values into denotationalsemantics-like functions lets one embed derivations within closures that embed within derivations; in this sense, the semantics becomes \higher order." Examples are given to support the de nitional developments. Kahn-style (\big-step") natural semantics 9] captures a program's entire computation within a single derivation. This representation is more compact than what one obtains from state-transition, \small-step," and denotational de nitions; in addition, natural semantics provides several additional attractions: When the natural semantics is de ned in \environment form," that is, the semantics' propositions are ternary relations of the form, `e + v, where 2 Environment, e 2 Expression, and v 2 Value, the resulting derivations are (almost always) semicompositional. That is, when one draws a physical derivation tree starting from an initial source program e 0 and initial (empty) environment 0 , then every node within the tree has the form 0`e0 + v 0 , where e 0 is a subphrase of e 0 . See Figure 1
The only related research attempting to widen the interpretations of natural semantics is described in REF .
Adapting Big-Step Semantics to Small-Step Style: Coinductive Interpretations and "Higher-Order" Derivations
In Second Workshop on Higher-Order Techniques in Operational Semantics (HOOTS2
Computer Science