Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gelernter D. Generative Communication in Linda. ACM Transactions on Programming Languages and Systems 1985; 7 (1): 80–112
Carriero N, Gelernter D. Linda in Context. Communications of the ACM 1989; 32 (4): 444–458
Shapiro E. Concurrent Prolog: Collected Papers. The MIT Press, 1987
Chandy KM, Misra J. Parallel Program Design: a Foundation. Addison Wesley, Massachusetts, 1988
Brogi A, Ciancarini P. The concurrent language Shared Prolog. ACM Transactions on Programming Languages and Systems 1991; 13 (1): 99–123
Gelernter D, Carriero N, Chandran S, et al. Parallel Programming in Linda. In: proc. of the Internatinal Conference on Parallel Programming (St. Charles, I11., Aug. ). IEEE, 1985, pp 255–263
Carriero N, Gelernter D, Leichter J. Distributed Data Structures in Linda. In: proc. of the ACM Symposium on Principles of Programming Languages (St. Petersburg, Fla., Jan.13-15). ACM, New York, 1986, pp 236–242
Ciancarini P, Yanchelevich D. Inside Linda. Technical Report, Yale University, Department of Computer Science, 1990
Butcher P. A behavioural semantics for Linda-2. Software Engineering Journal 1991; 6 (4): 196–204
Jensen KK. A Formal Linda Definition. Draft, February 1991
Ciancarini P, Jensen KK, Yankelevich D. The Semantics of a Parallel Language based on a Shared Data Space. Technical Report: TR-26/92, Dipartimento di Informatica, Università di Pisa, 1992
Plotkin GD. A Structural Approach to Operational Semantics. Technical Report DAIMI FN-19, Aarhus University, Dep. of Computer Science, Denmark, 1981
Bergstra J, Klop JW. Process Algebra for Synchronous Communication. Infor-mation and Control 1984; 60: 109–137
Hennessy M. Algebraic Theory of Processes. The MIT Press, 1988
Hoare CAR. Communicating Sequential Processes. Prentice-Hall Int., 1985
Milner R. Communication and Concurrency. Prentice Hall International, 1989
De Nicola R, Pugliese R. Testing Linda: an Observational Semantics for an Asynchronous Language. Research Report: SI/RR - 94/06, Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, 1994
Baeten JCM, Vandrager FM. An Algebra for Process Creation. Acta Informatica 1992; 29 (4): 303–334
De Nicola R, Hennessy MCB. Testing Equivalence for Processes. Theoretical Computers Science 1984; 34: 83–133
de Boer FS, Kok JN, Palamidessi C, et al. The Failure of Failures in a Paradigm for Asynchronous Communication. In: proc. of Concur ’91. Springer-Verlag, 1991, pp 111–126 (Lecture Notes in Computer Science no.527)
Goossens KGW. Reasoning about VHDL Using Operational and Observational Semantics. Research Report: SI/RR - 95/06, Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, 1995
The Institute of Electrical and Electronics Engineers. IEEE Standard VHDL Language Reference Manual. IEEE std 1076–1993 edition, 1993
Ladner RE, Fisher MJ. Parallel Prefix Computation. Journal of the ACM 1980; 27 (4): 831–838
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 British Computer Society
About this paper
Cite this paper
De Nicola, R., Pugliese, R. (1995). An Observational Semantics for Linda. In: Desel, J. (eds) Structures in Concurrency Theory. Workshops in Computing. Springer, London. https://doi.org/10.1007/978-1-4471-3078-9_9
Download citation
DOI: https://doi.org/10.1007/978-1-4471-3078-9_9
Publisher Name: Springer, London
Print ISBN: 978-3-540-19982-3
Online ISBN: 978-1-4471-3078-9
eBook Packages: Springer Book Archive