The origins of structural operational semantics
Open accessThe DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Abstract
We review the origins of structural operational semantics. The main publication `A Structural Approach to Operational Semantics,' also known as the `Aarhus Notes,' appeared in 1981 [G.D. Plotkin, A structural approach to operational semantics, DAIMI FN-19, Computer Science Department, Aarhus University, 1981]. The development of the ideas dates back to the early 1970s, involving many people and building on previous work on programming languages and logic. The former included abstract syntax, the SECD machine, and the abstract interpreting machines of the Vienna school; the latter included the λ -calculus and formal systems. The initial development of structural operational semantics was for simple functional languages, more or less variations of the λ -calculus; after that the ideas were gradually extended to include languages with parallel features, such as Milner's CCS. This experience set the ground for a more systematic exposition, the subject of an invited course of lectures at Aarhus University; some of these appeared in print as the 1981 Notes. We discuss the content of these lectures and some related considerations such as `small state' versus `grand state,' structural versus compositional semantics, the influence of the Scott–Strachey approach to denotational semantics, the treatment of recursion and jumps, and static semantics. We next discuss relations with other work and some immediate further development. We conclude with an account of an old, previously unpublished, idea: an alternative, perhaps more readable, graphical presentation of systems of rules for operational semantics.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Calculus of Communicating Systems
(1980) · Lecture Notes in Computer Science · doi:10.1007/3-540-10235-3 · Cited by 4,633
Call-by-name, call-by-value and the λ-calculus
Plotkin, G. D. (1975) · Theoretical Computer Science · doi:10.1016/0304-3975(75)90017-1 · Cited by 1,154
Self-citationLCF considered as a programming language
Plotkin, G. D. (1977) · Theoretical Computer Science · doi:10.1016/0304-3975(77)90044-5 · Cited by 1,083
Self-citationThe Mechanical Evaluation of Expressions
Landin, P. J. (1964) · The Computer Journal · doi:10.1093/comjnl/6.4.308 · Cited by 926
Formal verification of parallel programs
Keller, R. M. (1976) · Communications of the ACM · doi:10.1145/360248.360251 · Cited by 797
Outline of a Mathematical Theory of Computation
Scott, D. (1970) · Medical Entomology and Zoology · Cited by 746
A Basis for a Mathematical Theory of Computation )
(1963) · Studies in Logic and the Foundations of Mathematics · doi:10.1016/s0049-237x(08)72018-4 · Cited by 692
Definitional interpreters for higher-order programming languages
Reynolds, J. C. (1972) · Proceedings of the ACM annual conference on - ACM '72 · doi:10.1145/800194.805852 · Cited by 669
The next 700 programming languages
Landin, P. J. (1966) · Communications of the ACM · doi:10.1145/365230.365257 · Cited by 661
Coroutines and networks of parallel processes
Kahn, G., & MacQueen, D. B. (1976) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 492
Smullyan, R. M. (1962) · Medical Entomology and Zoology · Cited by 422
Proving Properties of Programs by Structural Induction
Burstall, R. M. (1969) · The Computer Journal · doi:10.1093/comjnl/12.1.41 · Cited by 324
A type-theoretical alternative to ISWIM, CUCH, OWHY
Scott, D. S. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90095-b · Cited by 245
Countable nondeterminism and random assignment
Apt, K. R., & Plotkin, G. D. (1986) · Journal of the ACM · doi:10.1145/6490.6494 · Cited by 181
Self-citationProgramming Environments Based on Structured Editors: The MENTOR Experience,
Donzeau-Gouge, V. V., Huet, G., Kahn, G., & Lang, B. (1980) · HAL · Cited by 174
Correct and optimal implementations of recursion in a simple programming language
Vuillemin, J. E. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80048-6 · Cited by 123
Formal Semantics of Programming Languages: VDL
Lucas, P. (1981) · IBM Journal of Research and Development · doi:10.1147/rd.255.0549 · Cited by 86
Recursive definitions of partial functions and their computations
Cadiou, J. M., & Manna, Z. (1972) · ACM SIGACT News · doi:10.1145/942580.807072 · Cited by 77
Advances in Programming and Non-Numerical Computation
(1966) · Elsevier eBooks · doi:10.1016/c2013-0-01911-1 · Cited by 38
A cook's tour of countable nondeterminism
Apt, K. R., & Plotkin, G. D. (1981) · Lecture notes in computer science · doi:10.1007/3-540-10843-2_38 · Cited by 21
Self-citation
Cited by
Bringing the web up to speed with WebAssembly
Haas, A., Rossberg, A., Schuff, D. L., Titzer, B. L., Holman, M., Gohman, D., Wagner, L., Zakai, A., & Bastien, J. (2017) · Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3062341.3062363 · Cited by 537
A brief history of process algebra
Baeten, J. C. M. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.07.036 · Cited by 323
The Nature of Physical Computation
Shagrir, O. (2022) · doi:10.1093/oso/9780197552384.001.0001 · Cited by 70
Metadata
- Authors
- Plotkin, G. D.
- Venue
- The Journal of Logic and Algebraic Programming
- Publisher
- Elsevier BV
- Published
- 2004-07
- Volume
- 60-61
- Pages
- 3-15
- ISSN
- 1567-8326 (ISSN-L)
- OpenAlex
- W2007809070
- Cited by
- 362
- References
- 20
- FWCI
- 14.23
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.