Content deleted Content added
m →Reduction semantics: corrected broken link to https://mitpress.mit.edu/9780262062756/semantics-engineering-with-plt-redex/ |
m Disambiguating links to Object-orientation (link changed to Object-oriented programming) using DisamAssist. |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 106:
Following Plotkin, showing the usefulness of a calculus derived from a set of reduction rules demands (1) a Church-Rosser lemma for the single-step relation, which induces an evaluation function, and (2) a Curry-Feys standardization lemma for the transitive-reflexive closure of the single-step relation, which replaces the non-deterministic search in the evaluation function with a deterministic left-most/outermost search. Felleisen showed that imperative extensions of this calculus satisfy these theorems. Consequences of these theorems are that the equational theory—the symmetric-transitive-reflexive closure—is a sound reasoning principle for these languages. However, in practice, most applications of reduction semantics dispense with the calculus and use the standard reduction only (and the evaluator that can be derived from it).
Reduction semantics are particularly useful given the ease by which evaluation contexts can model state or unusual control constructs (e.g., [[first-class continuations]]). In addition, reduction semantics have been used to model [[Object-oriented programming|object-oriented]] languages,<ref>{{cite book|title=A Theory of Objects|last1=Abadi|first1=M.|last2=Cardelli|first2=L.|date=8 September 2012|publisher=Springer |isbn=9781441985989|url=https://books.google.com/books?id=AgzSBwAAQBAJ&q=%22operational+semantics%22}}</ref> [[design by contract|contract systems]], exceptions, futures, call-by-need, and many other language features. A thorough, modern treatment of reduction semantics that discusses several such applications at length is given by Matthias Felleisen, Robert Bruce Findler and Matthew Flatt in ''Semantics Engineering with PLT Redex''.<ref>{{cite book|last1=Felleisen|first1=Matthias|last2=Findler|first2=Robert Bruce|last3=Flatt|first3=Matthew|title=Semantics Engineering with PLT Redex|year=2009|publisher=The MIT Press|isbn=978-0-262-06275-6|url=https://mitpress.mit.edu/9780262062756/semantics-engineering-with-plt-redex/}}</ref>
===Big-step semantics===
Line 112:
Big-step structural operational semantics is also known under the names '''natural semantics''', '''relational semantics''' and '''evaluation semantics'''.<ref>[https://web.archive.org/web/20131019133339/https://fsl.cs.illinois.edu/images/6/63/CS422-Spring-2010-BigStep.pdf University of Illinois CS422]</ref> Big-step operational semantics was introduced under the name ''natural semantics'' by [[Gilles Kahn]] when presenting Mini-ML, a pure dialect of [[ML (programming language)|ML]].
One can view big-step definitions as definitions of functions, or more generally of relations, interpreting each language construct in an appropriate ___domain. Its intuitiveness makes it a popular choice for semantics specification in programming languages, but it has some drawbacks that make it inconvenient or impossible to use in many situations, such as languages with control-intensive features or concurrency.<ref>{{cite book|last1=Nipkow|first1=Tobias|last2=Klein|first2=Gerwin|date=2014|title=Concrete Semantics|pages=101–102|doi=10.1007/978-3-319-10542-0|url=http://concrete-semantics.org/concrete-semantics.pdf|access-date=Mar 13, 2024|doi-access=free|isbn=978-3-319-10541-3 }}</ref>
A big-step semantics describes in a divide-and-conquer manner how final evaluation results of language constructs can be obtained by combining the evaluation results of their syntactic counterparts (subexpressions, substatements, etc.).
Line 136:
== Further reading ==
*[[Gilles Kahn]]. "Natural Semantics". ''Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science''. Springer-Verlag. London. 1987.
*<cite id=plotkin81>[[Gordon Plotkin|Gordon D. Plotkin.]] [http://citeseer.ist.psu.edu/673965.html A Structural Approach to Operational Semantics]. (1981) Tech. Rep. DAIMI FN-19, Computer Science Department, Aarhus University, Aarhus, Denmark. (Reprinted with corrections in J. Log. Algebr. Program. 60-61: 17-139 (2004), ([http://homepages.inf.ed.ac.uk/gdp/publications/sos_jlap.pdf preprint]). </cite>
*<cite id=plotkin04>[[Gordon Plotkin|Gordon D. Plotkin.]] The Origins of Structural Operational Semantics. J. Log. Algebr. Program. 60-61:3-15, 2004. ([http://homepages.inf.ed.ac.uk/gdp/publications/Origins_SOS.pdf preprint]). </cite>
*<cite id=scott70>[[Dana Scott|Dana S. Scott.]] Outline of a Mathematical Theory of Computation, Programming Research Group, Technical Monograph PRG–2, Oxford University, 1970.</cite>
*<cite id=algol68> [[Adriaan van Wijngaarden]] et al. Revised Report on the Algorithmic Language [[ALGOL 68]]. IFIP. 1968.
*<cite id=hennessybook>[[Matthew Hennessy]]. Semantics of Programming Languages. Wiley, 1990. [https://www.cs.tcd.ie/matthew.hennessy/splexternal2015/resources/sembookWiley.pdf available online].</cite>
| |||