Constraints for free in concurrent computation | SpringerLink
Skip to main content
Springer Nature Link
Log in

Constraints for free in concurrent computation

  • Concurrency and Networking
  • Conference paper
  • First Online:
Algorithms, Concurrency and Knowledge (ACSC 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1023))

Included in the following conference series:

  • 134 Accesses

Abstract

We investigate concurrency as unifying computational paradigm which integrates functional, constraint, and object-oriented programming. We propose the ρ-calculus as a uniform foundation of concurrent computation and formally relate it to other models: The ρ calculus with equational constraints provides for logic variables and is bisimilar to the γ-calculus. The ρ-calculus without constraints is a proper subset of the π-calculus. We prove its Turing completeness by embedding the eager λ-calculus in continuation passing style. The ρ-calculus over an arbitrary constraint system is an extension of the standard cc-model with procedural abstraction.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Gul Agha. ACTORS: A Model of Concurrent Computation in Distributed Systems. The MIT Press, Cambridge, MA, 1986.

    Google Scholar 

  2. Z. M. Ariola, M. Felleisen, J. Maraist, M. Odersky, and P. Wadler. A call-by-need lambda calculus. In Proc. POPL, pp. 233–246. ACM Press, 1995.

    Google Scholar 

  3. G. Boudol. Asynchrony and the π-calculus (note). Rapport de Recherche 1702, INRIA, Sophia Antipolis, France, May 1992.

    Google Scholar 

  4. S. Brook and G. Ostheimer. Process semantics of graph reduction. In Proc. CONCUR, pp. 238–252, August 1995.

    Google Scholar 

  5. F. S. de Boer and C. Palamidessi. A process algebra of concurrent constraint programming. In Krzysztof Apt, ed., Proc. JICSLP, pp. 463–477, Cambridge, Massachusetts, 1992. The MIT Press.

    Google Scholar 

  6. M. Falaschi, M. Gabbrielli, and C. Palamidessi. Compositional analysis for concurrent constraint programming. In Proc. LICS, pp. 210–220. IEEE Computer Society Press, June 1993.

    Google Scholar 

  7. M. Henz, G. Smolka, and J. Würtz. Object-Oriented Concurrent Constraint Programming in Oz. In V. Saraswat and P. Van Hentenryck, eds., Principles and Practice of Constraint Programming, chapter 2, pp. 27–48. The MIT Press, Cambridge, MA, Cambridge, MA, 1995.

    Google Scholar 

  8. K. Honda and N. Yoshida. On Reduction-Based Semantics. In R. K. Shyamasundar, ed., Proc. FST-TCS, Bombay, India, December 1993.

    Google Scholar 

  9. Sverker Janson. AKL — A Multiparadigm Programming Language. PhD thesis, SICS Swedish Institute of Computer Science, SICS Box 1263, S-164 28 Kista, Sweden, 1994. SICS Dissertation Series 14.

    Google Scholar 

  10. J. W. Klop. Term Rewriting Systems. In S. Abramsky, D. M. Gabbay, and T. S. M. Maibaum, eds., Handbook of Logic in Computer Science, volume 2, chapter 2, pp. 2–116. Oxford University Press, 1992.

    Google Scholar 

  11. M. Mehl, R. Scheidhauer, and C. Schulte. An Abstract Machine for Oz. In Proc. PLILP, LNCS. Utrecht, NL, 9/20-22/95. Springer, Berlin, Germany. To appear.

    Google Scholar 

  12. R. Milner. The polyadic π-calculus: A tutorial. In F. L. Bauer, W. Brauer, and H. Schwichtenberg, eds., Proc. 1991 Marktoberndorf Summer School on Logic and Algebra of Specification. NATO ASI Series, Springer, Berlin, Germany, 1993.

    Google Scholar 

  13. R. Milner. Functions as Processes. Mathematical Structures in Computer Science, 2(2):119–141, 1992.

    Google Scholar 

  14. R. Milner, J. Parrow, and D. Walker. A Calculus of Mobile Processes, I and II. Information and Computation, 100(1):1–40 and 41–77, September 1992.

    Google Scholar 

  15. T. Müller, Konstantin Popow, C. Schulte, and J. Würtz. Constraint programming in Oz. DFKI Oz documentation series, DFKI Saarbrücken, Germany, 1994. Documentation and System: http://ps@www.dfki.uni-sb.de.

    Google Scholar 

  16. J. Niehren. Funktionale Berechnung in einem uniform nebenläufigen Kalkül mit logischen Variablen. Doctoral Dissertation. Universität des Saarlandes, Technische Fakultät, 66041 Saarbrücken, Germany, December 1994. In German.

    Google Scholar 

  17. J. Niehren. Functional computation as concurrent computation, 1995. Submitted, http://ps-www.dfki.uni-sb.de/∼niehren.

    Google Scholar 

  18. Joachim Niehren and Martin Müller. Constraints for Free in Concurrent Computation. Research Report, German Research Center for Artificial Intelligence (DFKI), Stuhlsatzenhausweg 3, D-66123 Saarbrücken, Germany, September 1995.

    Google Scholar 

  19. J. Niehren and G. Smolka. A confluent relational calculus for higher-order programming with constraints. In J.-P. Jouannaud, ed., Proc. CCL, LNCS 845, pp. 89–104, Germany, 1994.

    Google Scholar 

  20. G. D. Plotkin. Call-by-name, Call-by-value and the λ-Calculus. Theoretical Computer Science, 1:125–159, 1975.

    Google Scholar 

  21. V. A. Saraswat, M. Rinard, and P. Panangaden. Semantic foundations of concurrent constraint programming. In Proc. POPL, pp. 333–352. ACM Press, 1991.

    Google Scholar 

  22. G. Smolka. A Calculus for Higher-Order Concurrent Constraint Programming with Deep Guards. Research Report RR-94-03, DFKI, Saarbrücken, Germany, 1994.

    Google Scholar 

  23. G. Smolka. A Foundation for Concurrent Constraint Programming. In J.-P. Jouannaud, ed., Proc. CCL, LNCS 845, pp. 50–72, Germany, 1994.

    Google Scholar 

  24. G. Smolka. An Oz primer. DFKI Oz documentation series, DFKI, Saarbrücken, Germany, 1995. Documentation and System: http://ps-www.dfki.uni-sb.de.

    Google Scholar 

  25. G. Smolka. The Definition of Kernel Oz. In Andreas Podelski, ed., Constraints: Basics and Trends, LNCS 910, pp. 251–292. Springer, Berlin, Germany, 1995.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Programming Systems Lab, German Research Center for Artificial Intelligence (DFKI), Stuhlsatzenhausweg 3, 66123, Saarbrücken, Germany

    Joachim Niehren & Martin Müller

Authors
  1. Joachim Niehren
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Kanchana Kanchanasut Jean-Jacques Lévy

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Niehren, J., Müller, M. (1995). Constraints for free in concurrent computation. In: Kanchanasut, K., Lévy, JJ. (eds) Algorithms, Concurrency and Knowledge. ACSC 1995. Lecture Notes in Computer Science, vol 1023. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60688-2_43

Download citation

  • DOI: https://doi.org/10.1007/3-540-60688-2_43

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60688-8

  • Online ISBN: 978-3-540-49262-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics