Structural Operational Semantics (SOS) refers systematic approach to giving operational semantics to programming languages. The gist of the method consists of writing down "symbol-pushing" rules that slowly consume the constructs of the programming language, at the same time moving from configuration to configuration.
While this approach may seem completely ordinary today, it was anything but that when it was introduced in the late 1970s. The seminal manuscript on SOS is Gordon Plotkin's famous Aarhus notes. These circulated informally for years before being published by The Journal of Logic and Algebraic Programming [Plotkin 2004]. Note that there were technical deficiencies in the original notes, which have been corrected in the JLAP re-print.
The journal also published an interesting preface in which Plotkin records historical information regarding the formulation of SOS. This draws the line directly from Barendregt's thesis and early formulations of call-by-value semantics for the -calculus, to Milner's CCS and Labelled Transition Systems (LTSs).
Reading the above description an immediate questions come to mind:
The answer seems to be both yes and no. Yes, in the sense that the rules do look like stepping from configuration to configuration of an abstract machine. However, the abstract machine is too abstract: it is allowed to use all sorts of fully mathematical things in its configuration (finite, partial, or infinite maps, etc.). In a sense, the term abstract machine should be reserved for something far closer to implementation than SOS.
Plotkin explains this in his historical preface:
The first idea, already clear from the above ‘preliminary trials,’ was that structural operational semantics was intended as being like an abstract machine but without all the complex machinery in the configurations, just the minimum needed to explain the semantical aspects of the programming language constructs. The extra machinery is avoided by the use of the rules, making the exploration of syntactical structure implicit rather than drearily explicit. Of course, abstract machines are important for the actual implementation of programming languages; indeed it would be good to have a general theory of such machines.
Another question that immediately springs to mind when one first hears of SOS is this:
The salient difference between operational semantics and SOS is that the latter ought to syntax-directed. That is: the rules should follow the "shape" of the term, and mostly depend on the outermost construct. Here is the relevant Plotkin quote:
The second idea was that the rules should be syntax-directed; this is reflected in the title of the Aarhus notes: the operational semantics is structural, not, as some took it, structured. In denotational semantics one follows an ideal of compositionality, where the meaning of a compound phrase is given as a function of the meaning of its parts. In the case of operational semantics one considers the behaviour of a program phrase, which is just the collection of the transitions it can make. This behaviour is, however, not compositional when thought of as a function of program phrases. However the rules do give it structurally, i.e., primitive recursively, in the syntax; the idea of structural recursion is due to Burstall [14].
Informally, one could say that doing SOS over simply operational semantics is simply not being cavalier. We have since developed categorical methods that explain what that means (to be continued elsewhere).
Plotkin, Gordon D. 2004. ‘A Structural Approach to Operational Semantics’. The Journal of Logic and Algebraic Programming 60–61 (July): 17–139. https://doi.org/10.1016/j.jlap.2004.05.001. [preprint pdf]
@article{plotkin_2004,
title = {A structural approach to operational semantics},
volume = {60-61},
issn = {15678326},
url = {https://linkinghub.elsevier.com/retrieve/pii/S1567832604000402},
doi = {10.1016/j.jlap.2004.05.001},
journal = {The Journal of Logic and Algebraic Programming},
author = {Plotkin, Gordon D.},
year = {2004},
pages = {17--139}
}
Plotkin, Gordon D. 2004. ‘The Origins of Structural Operational Semantics’. The Journal of Logic and Algebraic Programming 60–61: 3–15. https://doi.org/10.1016/j.jlap.2004.03.009. [preprint pdf]
@article{plotkin_origins_2004,
title = {The origins of structural operational semantics},
volume = {60-61},
issn = {15678326},
doi = {10.1016/j.jlap.2004.03.009},
journal = {The Journal of Logic and Algebraic Programming},
author = {Plotkin, Gordon D},
year = {2004},
pages = {3--15}
}