[TYPES] Terminology in operational semantics

[sanjiva at cse.iitd.ernet.in]

Both Winskel and Nielson-Nielson are right in different senses.
Winskel in the broader sense that both the
(a) Kahn-style "Natural" or "Big-step" semantics; and
(b) Plotkin style "Reduction" or "Small-step" semantics
are structural in that they are syntax oriented, with structural
induction being the main analysis technique.  Except that the
induction is on slightly different things -- in big step it tends to be
solely on the syntax, whereas in small-step it is on the rules (ergo the
distinction made by Nielson-Nielson).  The distinction shows up in little
ways, e.g., the former style is usually formulated as a reflexive
relation, the latter (usually) as an irreflexive one.

You can find on my home page http://www.cse.iit.ac.in/~sanjiva
a pointer to an introductory chapter on Operational semantics,  which
appears in a CRC Press Handbook for Compiler Design.
It also has some stuff about the abstract machine style of operational
semantics...

Cheers,
Sanjiva



> [The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list]
>
> Hi,
>
> I am confused by what I think appears to be different notions of
> operational semantics. Nielson-Nielson seems to distinguish natural
> semantics from structural operational semantics, whereas Winskel
> considers (in a remark) natural semantics one particular notion of
> structural operational semantics. Also we have big step semantics
> versus small step semantics.
> On the other hand, some researchers distinguish  between reduction
> semantics and operational semantics, and I am not clear about how this
> relates to the above notions, if at all.
>
>  From this, I wonder what is the "standard" or "preferred" terminology.
>
> Best Wishes,
> Johan Glimming
>