Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Rendez-vous with metric semantics

  • Regular Papers
  • Published:
New Generation Computing Aims and scope Submit manuscript

Abstract

A comparative semantic study is made of an element of the family of concurrent object-oriented programming languages. Particular attention is paid to two notions: (i) dynamically evolving process structures, including a mechanism to name and refer to processes and a means to create new processes, and (ii) rendez-vous between processes involving the sending and answering of messages and the induced execution of method calls. The methodology of metric semantics is applied in the design of operational and denotational semantics, as well as in the proof of their equivalence. Both semantics employ domains which are determined as fixed points of a contracting functor in the category of complete metric spaces. Moreover, fruitful use is made of the technique of defining semantic meaning functions as fixed points of contracting higher-order mappings. Finally. syntactic and semantic continuations play a pervasive role.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. America, P. and de Bakker, J. W., “Designing Equivalent Semantic Models for Process Creation,”Theoretical Computer Science, 60, pp. 109–176, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  2. America, P., de Bakker, J. W., Kok, J. N. and Rutten, J. J. M. M., “Operational Semantics of a Parallel Object-Oriented Language,” inProc. POPL’86, St. Petersburg, Florida, pp. 194–208, 1986.

  3. America, P., de Bakker, J. W., Kok, J. N. and Rutten, J. J. M. M., “Denotational Semantics of a Parallel Object-Oriented Language,”Information and Computation, 83, pp. 152–205, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  4. America, P., “Issues in the Design of a Parallel Object-Oriented Language,”Formal Aspects of Computing, 1, pp. 366–411, 1989.

    Article  Google Scholar 

  5. America, P. and Rutten, J. J. M. M., «A Parallel Object-Oriented Language: Design and Semantic Foundations,” inLanguages for Parallel Architectures: Design, Semantics, Implementation Models (J. W. de Bakker, ed.), Wiley Series in Parallel Computing, Wiley, pp. 1–49, 1989.

  6. America, P. and Rutten, J. J. M. M., “Solving Reflexive Domain Equations in a Category of Complete Metric Spaces,”Journal of Computer and System Sciences, 39, pp. 343–375, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  7. America, P. and Rutten, J. J. M. M., “A Layered Semantics for a Parallel Object-Oriented Language,”Formal Aspects of Computing, 4, pp. 376–408, 1992.

    Article  MATH  Google Scholar 

  8. de Bakker, J. W.,Mathematical Theory of Program Correctness, Prentice Hall International, 1980.

  9. de Bakker, J. W., Bergstra, J. A., Klop, J. W. and Meyer, J.-J. Ch., “Linear Time and Branching Time Semantics for Recursion with Merge,”Theoretical Computer Science, 34, pp. 135–156, 1984.

    Article  MATH  MathSciNet  Google Scholar 

  10. de Bakker, J. W. and Meyer, J.-J. Ch., “Metric Semantics for Concurrency,”BIT, 28, pp. 504–529, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  11. de Bakker, J. W. and Meyer, J.-J. Ch., Olderog, E.-R. and Zucker, J. I., “Transition Systems, Metric Spaces and Ready Sets in the Semantics of Uniform Concurrency,”Journal of Computer and System Sciences, 36, pp. 158–224, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  12. de Bakker, J. W. and Rutten, J. J. M. M. (eds.),Ten Years of Concurrency Semantics, selected papers of the Amsterdam Concurrency Group, World Scientific, Singapore, 1992.

    Google Scholar 

  13. de Bakker, J. W. and de Vink, E. P., “CCS for OO and LP,” inProc. TAPSOFT’91, Vol. 2 (S. Abramsky and T. S. E. Maibaum, eds.),LNCS, 494, Springer, pp. 1–28, 1991. Corrected version asTechnical Report, CS-R9136, CWI, Amsterdam 1991.

  14. de Bakker, J. W. and Warmerdam, J. H. A., “Metric Pomset Semantics for a Concurrent Language with Recursion,” inSemantics of Systems of Concurrent Processes (I. Guessarian, ed.),LNCS, 469, Springer, pp. 21–49, 1990.

  15. de Bakker, J. W. and Zucker, J. I., “Processes and the Denotational Semantics of Concurrency,”Information and Control, 54, pp. 70–120, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  16. de Boer, F. S., Kok, J. N., Palamidessi, C. and Rutten, J. J. M. M., “On Blocks: Locality and Asynchronous Communication,”Preprint, CWI, Amsterdam, 1992.

    Google Scholar 

  17. Dugundji, J.,Topology, Allyn and Bacon, 1966.

  18. Eliëns, A.,DLP —A Language for Distributed Logic Programming, Wiley Series in Parallel Computing, Wiley, 1992.

  19. Engelking, R.,General Topology, Volume 6 of Sigma Series in Pure Mathematics, Heldermann, revised and completed edition, 1989.

  20. Gunter, C. A. and Scott, D. S., “Semantic Domains,” inHandbook of Theoretical Computer Science, Volume B (J. van Leeuwen, ed.), North-Holland, pp. 633–674, 1990.

  21. Horita, E., de Bakker, J. W. and Rutten, J. J. M. M., “Fully Abstract Denotational Semantics for Nonuniform Concurrent Languages,”Technical Report, CS-R9027, CWI, Amsterdam, 1990. To appear inInformation and Computation.

    Google Scholar 

  22. Kok, J. N. and Rutten, J. J. M. M., “Contractions in Comparing Concurrency Semantics,”Theoretical Computer Science, 76, pp. 180–222, 1990.

    Article  MathSciNet  Google Scholar 

  23. Kuratowski, K., “Sur une méthode de métrisation complète des certains espaces d’ensembles compacts,”Fundamenta Mathematicae, 42, pp. 114–138, 1956.

    MathSciNet  Google Scholar 

  24. MacLane, S.,Categories for the Working Mathematician, volume 5 of Graduate texts in mathematics, Springer, 1971.

  25. Rutten, J. J. M. M., “Correctness and Full Abstraction of Metric Semantics for Concurrency,” inLinear Time, Branching Time and Partial Order in Logics and Models for Concurrency (J. W. de Bakker, W. P. de Roever, and G. Rozenberg, eds.),LNCS, 354, Springer, pp. 628–659, 1989.

  26. Rutten, J. J. M. M., “Deriving Metric Models for Bisimulation from Transition System Specifications,” inProc. IFIP TC2 Working Conference on Programming Concepts and Methods (M. Broy and C. B. Jones, eds.), North-Holland, pp. 155–177, 1990.

  27. Rutten, J. J. M. M., “Semantic Correctness for a Parallel Objoct-Oriented Language,”SIAM Journal on Computing, 19, pp. 341–383, 1990.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CWI, Postbus 4079, NL-1009 AB, Amsterdam, Netherlands

    J. W. de Bakker

  2. Department of Mathematics and Computer Science, Vrije Universiteit, De Boelelaan 1081a, NL-1081 HV, Amsterdam, Netherlands

    J. W. de Bakker & E. P. de Vink

Authors
  1. J. W. de Bakker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. P. de Vink
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The research of J. W. de Bakker was partially supported by ESPRIT Basic Research Action 3020: Integration.

Jaco de Bakker, Ph. D.: He has worked at the CWI. Amsterdam, since 1964, at present as head of its Department of Software Technology. He is also professor of theoretical computer science at the Vrije Universiteit Amsterdam. His research interests are semantics, concurrency and programming logics. He has been involved in several European projects such as ESPRIT 415 (on Parallel Architectures and Languages), ESPRIT INTEGRATION (of FP, LP and OO foundations) and Science MASK (Mathematical Structures in Concurrency Semantics). He is editor of several journals and book series, and member of the Royal Netherlands Academy of Arts and Sciences, and of the Academia Europaea.

Erik de Vink, Ph. D.: He is assistant-professor at the Department of Mathematics and Computer Science, Vrije Universiteit Amsterdam concerned with education and research in theoretical computer science, in particular semantics of programming languages. He received his Master’s degree in Mathematics in 1985 from the University of Amsterdam, and his Ph. D. degree in 1990 from Vrije Universiteit Amsterdam. His Ph. D. thesis concerns the semantics of concurrent and logic programming languages. Currently, his research interest includes the metric approach for denotational semantics, dealing with true concurrency vs. interleaving semantics, and dealing with the communication mechanism for object oriented languages.

About this article

Cite this article

de Bakker, J.W., de Vink, E.P. Rendez-vous with metric semantics. New Gener Comput 12, 53–90 (1993). https://doi.org/10.1007/BF03038272

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF03038272

Keywords

Search

Navigation