First-class synchronous operations | SpringerLink
Skip to main content
Springer Nature Link
Log in

First-class synchronous operations

  • Invited Talk 5
  • Conference paper
  • First Online:
Theory and Practice of Parallel Programming (TPPP 1994)

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

Included in the following conference series:

  • 167 Accesses

Abstract

The idea of making synchronous operations into first-class values is an important one for supporting abstraction and modularity in concurrent programs. This design principle has been used with great success in the concurrent language CML, but what are the limitations of this approach? This paper explains the rationale for first-class synchronous operations, and discusses their use in CML. It also presents some recent and fundamental results about the expressiveness of rendezvous primitives, which define the limitations of synchronous abstractions.

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.

References

  1. Abramsky, S. and R. Bornat. Pascal-m: A language for loosely coupled distributed systems. In Y. Paker and J.-P. Verjus (eds.), Distributed Computing Systems, pp. 163–189. Academic Press, New York, N.Y., 1986.

    Google Scholar 

  2. Appel, A. W. and D. B. MacQueen. Standard ML of New Jersey. In Programming Language Implementation and Logic Programming, vol. 528 of Lecture Notes in Computer Science, New York, N.Y., August 1991. Springer-Verlag, pp. 1–26.

    Google Scholar 

  3. Arvind, R. S. Nikhil, and K. K. Pingali. I-structures: Data structures for parallel computing. ACM Transactions on Programming Languages and Systems, 11(4), October 1989, pp. 598–632.

    Article  Google Scholar 

  4. Bjornson, R., N. Carriero, D. Gelernter, and J. Leichter. Linda, the portable parallel. Technical Report YALEU/DCS/TR-520, Department of Computer Science, Yale University, February 1987.

    Google Scholar 

  5. Berthomieu, B. Programming with behaviors in an ML framework — the syntax and semantics of LCS. Technical Report 93133, LASS/CNRS, April 1993.

    Google Scholar 

  6. Biagiono, E., R. Harper, P. Lee, and B. G. Milnes. Signatures for a network protocol stack: A systems application of Standard ML. In Conference record of the 1994 ACM Conference on Lisp and Functional Programming, June 1994, pp. 55–64.

    Google Scholar 

  7. Barth, P., R. S. Nikhil, and Arvind. M-structures: Extending a parallel, non-strict, functional language with state. In Functional Programming Languages and Computer Architecture, vol. 523 of Lecture Notes in Computer Science, New York, N.Y., August 1991. Springer-Verlag, pp. 538–568.

    Google Scholar 

  8. Bornat, R. A protocol for generalized occam. Software — Practice and Experience, 16(9), September 1986, pp. 783–799.

    Google Scholar 

  9. Burns, A. Programming in occam 2. Addison-Wesley, Reading, Mass., 1988.

    Google Scholar 

  10. Cardelli, L. Amber. In Combinators and Functional Programming Languages, vol. 242 of Lecture Notes in Computer Science, New York, N.Y., July 1986. Springer-Verlag, pp. 21–47.

    Google Scholar 

  11. Carriero, N. and D. Gelernter. How to Write Parallel Programs: A First Course. The MIT Press, Cambridge, Mass., 1990.

    Google Scholar 

  12. Cardelli, L. and R. Pike. Squeak: A language for communicating with mice. In SIGGRAPH '85, July 1985, pp. 199–204.

    Google Scholar 

  13. Reference Manual for the Ada Programming Language, January 1983.

    Google Scholar 

  14. Gelernter, D. and A. J. Bernstein. Distributed communication via global buffer. In ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1982, pp. 10–18.

    Google Scholar 

  15. Gelernter, D. Generative communication in Linda. ACM Transactions on Programming Languages and Systems, 7(1), January 1985, pp. 80–112.

    Article  Google Scholar 

  16. Griffin, T. and R. Moten. Tactic trees in eXene. Included in the eXene distribution, 1992.

    Google Scholar 

  17. Giacalone, A., P. Mishra, and S. Prasad. Facile: A symemetric integration of concurrent and functional programming. In TAPSOFT'89 (vol. 2), vol. 352 of Lecture Notes in Computer Science, New York, N.Y., March 1989. Springer-Verlag, pp. 184–209.

    Google Scholar 

  18. Gansner, E. R. and J. H. Reppy. A foundation for user interface construction, In B. A. Myers (ed.), Languages for Developing User Interfaces, pp. 239–260. Jones & Bartlett, Boston, Mass., 1992.

    Google Scholar 

  19. Gansner, E. R. and J. H. Reppy. A Multi-threaded Higher-order User Interface Toolkit, vol. 1 of Software Trends, pp. 61–80. John Wiley&Sons, 1993.

    Google Scholar 

  20. Haahr, D. Montage: Breaking windows into small pieces. In USENIX Summer Conference, June 1990, pp. 289–297.

    Google Scholar 

  21. Halpem, J. Y. and Y. Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3), July 1990, pp. 549–587. An earlier version appeared in the Proceedings of the 3rd ACM Conference on Principles of Distributed Computing.

    Article  Google Scholar 

  22. Krumvieda, C. D. Distributed ML: Abstractions for Efficient and Fault-Tolerant Programming. Ph.D. dissertation, Department of Computer Science, Cornell University, Ithaca, NY, August 1993. Available as Technical Report TR 93-1376.

    Google Scholar 

  23. Kawaguchi, N., T. Sakabe, and Y. Inagaki. TERSE: Term rewriting support environment. In Proceedings of the 1994 ACM SIGPLAN Workshop on ML and its Applications, June 1994, pp. 91–100.

    Google Scholar 

  24. Lin, H. PAM: A process algebra manipulator. In Proceedings of the Third Workshop on Computer Aided Verification, July 1991.

    Google Scholar 

  25. Milner, R., M. Tofte, and R. Harper. The Definition of Standard ML. The MIT Press, Cambridge, Mass, 1990.

    Google Scholar 

  26. Paulson, L. C. ML for the Working Programmer. Cambridge University Press, New York, N.Y., 1991.

    Google Scholar 

  27. Pike, R. A concurrent window system. Computing Systems, 2(2), 1989, pp. 133–153.

    Google Scholar 

  28. Pike, R. Newsqueak: A language for communicating with mice. Technical Report 143, AT&T Bell Laboratories, April 1989.

    Google Scholar 

  29. Panangaden, P. and J. H. Reppy. On the relative expressiveness of rendezvous primitives, unpublished draft, 1994.

    Google Scholar 

  30. Panangaden, P. and K. Taylor. Concurrent common knowledge: Defining agreement for asynchronous systems. Distributed Computing, 1992, pp. 73–93.

    Google Scholar 

  31. Reppy, J. H. Synchronous operations as first-class values. In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation, June 1988, pp. 250–259.

    Google Scholar 

  32. Reppy, J. H. CML: A higher-order concurrent language. In Proceedings of the SIGPLAN'91 Conference on Programming Language Design and Implementation, June 1991, pp. 293–305.

    Google Scholar 

  33. Reppy, J. H. Higher-order concurrency. Ph.D. dissertation, Department of Computer Science, Cornell University, Ithaca, NY, January 1992. Available as Technical Report TR 92-1285.

    Google Scholar 

  34. Reppy, J. H. Concurrent Programming in ML. Cambridge University Press, 1995. (forthcoming).

    Google Scholar 

  35. Reppy, J. H. and E. R. Gansner. A foundation for programming environments. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, December 1986, pp. 218–227.

    Google Scholar 

  36. Siegel, E. H. and E. C. Cooper. Implementing distributed Linda in Standard ML. Technical Report CMU-CS-91-151, cmu-cs, October 1991.

    Google Scholar 

  37. Slind, K. An implementation of higher order logic. Master's dissertation, University of Calgary, Department of Computer Science, December 1990.

    Google Scholar 

  38. Tofte, M. Type inference for polymorphic references. Information and Computation, 89, 1990, pp. 1–34.

    Article  MathSciNet  Google Scholar 

  39. Ullman, J. D. Elements of ML Programming. Prentice Hall, Englewood Cliffs, NJ, 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AT&T Bell Laboratories, USA

    John H. Reppy

Authors
  1. John H. Reppy
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Takayasu Ito Akinori Yonezawa

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Reppy, J.H. (1995). First-class synchronous operations. In: Ito, T., Yonezawa, A. (eds) Theory and Practice of Parallel Programming. TPPP 1994. Lecture Notes in Computer Science, vol 907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026573

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-59172-6

  • Online ISBN: 978-3-540-49218-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation