17
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

Looking at the operational semantics course at my University gives the following three:

Ohad.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.