An Observational Semantics for Linda

Rocco De Nicola1, Rosario Pugliese2
1 Dipartimento di Sistemi e Informatica, Universita' di Firenze
2 Dipartimento di Scienze dell'Informazione, Universita' di Roma ``La Sapienza''


Linda has just four primitives, all of which are devoted to coordinating the interactions among programs by sharing information maintained in a common data space. To write programs manipulating data, it is necessary to embed Linda in a (functional, imperative, logic, etc.) programming language; this leads to a family of languages based on Linda. We define syntax and semantics for a member of the Linda family, L, that is obtained by embedding Linda in a ``simple'' sequential language. The semantics of this concurrent programming language is formalized by applying techniques developed within the framework of process algebras. A two-level semantics for L is provided: an operational one in Plotkin's style, based on a transition system, and an observational one, based on three behavioural preorders, obtained by applying the testing framework to L.