Structural operational semantic specifications come in different styles: small-step and big-step. A problem with the big-step style is that specifying divergence and abrupt termination gives rise to annoying duplication. We present a novel approach to representing divergence and abrupt termination in big-step semantics using status flags. This avoids the duplication problem, and uses fewer rules and premises for representing divergence than previous approaches in the literature.
Moggi @cite_31 suggested monads as a means to obtain modularity in denotational semantics @cite_6 . In a similar vein, Modular SOS @cite_23 provides a means to obtain modularity in operational semantics. The flag-based approach to divergence presented here is a variant of the abrupt termination technique used in @cite_23 . That article represents abrupt termination as emitted signals. In a small-step semantics, this enables the encoding of abrupt termination by introducing a top-level handler that matches on emitted signals: if the handler observes an emitted signal, the program abruptly terminates. Exceptions as emitted signals could also be used for expressing abrupt termination in big-step semantics. However, this would entail wrapping each premise in a handler, thereby cluttering rules. Subsequent work @cite_27 observed that encoding abrupt termination as a stateful flag instead scales better to big-step rules by avoiding such explicit handlers. Flag-based divergence was used in @cite_42 for giving a semantics for the untyped @math -calculus. The first author's thesis [Cpt. 4 and 5] BachPoulsen2016xtss describes a rule format for which small-step and pretty-big-step rules are provably equivalent using flag-based abrupt termination and divergence.
@cite_42 @cite_6 @cite_27 @cite_23 @cite_31
2022019286 1568435125 2169488840 2016799432 1997143185
Dealing with polymorphism in the presence of imperative features is a long-standing open problem for Hindley-Milner type systems. A widely adopted approach is the value restriction, which inhibits polymorphic generalisation and unfairly rejects various programs that cannot go wrong. We consider abstract interpretation as a tool for constructing safe and precise type systems, and investigate how to derive store-based types by abstract interpretation. We propose store-based types as a type discipline that holds potential for interesting and flexible alternatives to the value restriction. Big-step semantics for languages with abrupt termination and or divergence suffer from a serious duplication problem, addressed by the novel 'pretty-big-step' style presented by Chargueraud at ESOP'13. Such rules are less concise than corresponding small-step rules, but they have the same advantages as big-step rules for program correctness proofs. Here, we show how to automatically derive pretty-big-step rules directly from small-step rules by 'refocusing'. This gives the best of both worlds: we only need to write the relatively concise small-step specifications, but our reasoning can be big-step as well as small-step. The use of strictness annotations to derive small-step congruence rules gives further conciseness. Abstract Modular SOS (MSOS) is a variant of conventional Structural Operational Semantics (SOS). Using MSOS, the transition rules for each construct of a programming language can be given incrementally, once and for all, and do not need reformulation when further constructs are added to the language. MSOS thus provides an exceptionally high degree of modularity in language descriptions, removing a shortcoming of the original SOS framework. After sketching the background and reviewing the main features of SOS, the paper explains the crucial differences between SOS and MSOS, and illustrates how MSOS descriptions are written. It also discusses standard notions of semantic equivalence based on MSOS. Appendix A shows how the illustrative MSOS rules given in the paper would be formulated in conventional SOS. Abstract The λ-calculus is considered a useful mathematical tool in the study of programming languages, since programs can be identified with λ-terms. However, if one goes further and uses βη-conversion to prove equivalence of programs, then a gross simplification is introduced (programs are identified with total functions from values to values ) that may jeopardise the applicability of theoretical results. In this paper we introduce calculi, based on a categorical semantics for computations , that provide a correct basis for proving equivalence of programs for a wide range of notions of computation .