<p>Structural operational semantics (SOS) is a very general concept. It's essentially just a binary relation on configurations (usually programs plus a context, like state, or available continuations), or, in case of labelled semantics, a ternary relation between configurations, actions (which represent certain minimal contexts) and configurations. The "structural" bit is usually that these relations are defined inductively over the involved syntax (e.g. configurations and actions).</p>

<p>As such, without other requirement, the mathematical entities we consider in SOS are too general to be interesting/tractable in their own right. </p>

<p>SOS becomes interesting and substantial when we look at special cases, e.g. equivalences for timed-calculi, labelled transitions for asynchronous ambient calculus corresponding to reductions, or questions about expressivity of certain (classes of) calculi. </p>

<p>So my recommendation for Mr/Ms Systemsfault is to skip generalities and jump right into specific calculi of interest. General SOS techniques can easily be picked up along the way.</p>

CC BY-SA 2.5
2010-12-09T12:44:38.727Z
2010-12-09T12:44:38.727Z
Martin Berger
<p>I would recommend reading Chapter 2 in this downloadable book:</p>

<p><em>Semantics with Applications: A Formal Introduction,</em> Hanne Riis Nielson and Flemming Nielson, 
Wiley, 1992.
<a href="http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html">http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html</a></p>

CC BY-SA 2.5
2010-12-09T17:08:54.357Z
2010-12-09T17:08:54.357Z
Chan Li
<p>Looking at the <a href="http://www.inf.ed.ac.uk/teaching/courses/lsi/">operational semantics course</a> at my University gives the following three:</p>

<ul>
<li>Andrew Pitts's <a href="http://www.inf.ed.ac.uk/teaching/courses/lsi/sempl.pdf">lecture notes</a></li>
<li>Gordon Plotkin's <a href="http://homepages.inf.ed.ac.uk/gdp/publications/sos_jlap.pdf">Aarhus notes on structural operational semantics</a></li>
<li>Matthew Hennessey's <a href="http://homepages.inf.ed.ac.uk/gdp/publications/sos_jlap.pdf">The Semantics of Programming Languages</a></li>
</ul>

<p>Ohad.</p>

CC BY-SA 2.5
2010-12-09T11:27:09.097Z
2010-12-09T11:27:09.097Z
Ohad Kammar
<p>I'm new to programming languages theory and I'm seeking for a good resource on a resource for formal semantics  of programming languages. Specifically looking  for structural operational semantics. I got some book recommendations. But I'm looking for a resource in a  more introductory level. Especially tutorials, web-site and free book recommendations are  welcomed.</p>

CC BY-SA 2.5
2010-12-09T07:48:55.940Z
See http://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics
Dave Clarke
CC BY-SA 2.5
2010-12-09T08:09:29.407Z
I was going to post the exact same link, but then noticed that the OP already mentioned that they had book recos, and were looking for other references
Suresh Venkat
<reference-request><pl.programming-languages><semantics><formal-systems>
Formal Semantics of Programming Languages
systemsfault
# Formal Semantics of Programming Languages

(Asked by: username_0 on 2010-12-09)

I'm new to programming languages theory and I'm seeking for a good resource on a resource for formal semantics of programming languages. Specifically looking for structural operational semantics. I got some book recommendations. But I'm looking for a resource in a more introductory level. Especially tutorials, web-site and free book recommendations are welcomed.

**Tags:** reference-request, pl.programming-languages, semantics, formal-systems

> **Comments:**
> **username_1**: See http://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics  
> **username_2**: I was going to post the exact same link, but then noticed that the OP already mentioned that they had book recos, and were looking for other references  

---

## 3 answers

### Answer by username_5 on 2010-12-09. Score: 10 | Accepted answer

Looking at the [operational semantics course](http://www.inf.ed.ac.uk/teaching/courses/lsi/) at my University gives the following three:

* Andrew Pitts's [lecture notes](http://www.inf.ed.ac.uk/teaching/courses/lsi/sempl.pdf)
* Gordon Plotkin's [Aarhus notes on structural operational semantics](http://homepages.inf.ed.ac.uk/gdp/publications/sos_jlap.pdf)
* Matthew Hennessey's [The Semantics of Programming Languages](http://homepages.inf.ed.ac.uk/gdp/publications/sos_jlap.pdf)

Ohad.


---

### Answer by username_3 on 2010-12-09. Score: 8

Structural operational semantics (SOS) is a very general concept. It's essentially just a binary relation on configurations (usually programs plus a context, like state, or available continuations), or, in case of labelled semantics, a ternary relation between configurations, actions (which represent certain minimal contexts) and configurations. The "structural" bit is usually that these relations are defined inductively over the involved syntax (e.g. configurations and actions).

As such, without other requirement, the mathematical entities we consider in SOS are too general to be interesting/tractable in their own right.

SOS becomes interesting and substantial when we look at special cases, e.g. equivalences for timed-calculi, labelled transitions for asynchronous ambient calculus corresponding to reductions, or questions about expressivity of certain (classes of) calculi.

So my recommendation for Mr/Ms Systemsfault is to skip generalities and jump right into specific calculi of interest. General SOS techniques can easily be picked up along the way.


---

### Answer by username_4 on 2010-12-09. Score: 7

I would recommend reading Chapter 2 in this downloadable book:

*Semantics with Applications: A Formal Introduction,* Hanne Riis Nielson and Flemming Nielson,
Wiley, 1992.
<http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html>


---

