The Semantics of a Parallel Language based on a Shared Data Space

Linda is possibly the best known parallel language based on a shared data space of consumable tuples (other languages in this class are Associons, Gamma, and Shared Prolog). Although it has been efficiently implemented on a variety of architectures, and in combination with several sequential languages, Linda formal semantics is relatively unexplored. On the other side, a number of different semantic frameworks for modelling concurrency exists, but they are rarely used for language evaluation or compared with respect to their expressive power. In this paper we study the semantics of Linda using a number of different semantic approaches: Plotkin's SOs, Milner's CCS, Petri Nets, and the Berry and Boudol's Chemical Abstract Machine. We compare these semantic specifications, and show how the different semantic models enligthen different language implementations. Our overall goal is—from the point of view of a language designer—to test the expressiveness and clearness of some popular abstract models of concurrency in the specification of the semantics of a parallel programming language.