Hanne Riis Nielson
ABSTRACT
Concurrent ML (CML) is an extension of the functional language Standard ML(SML) with primitives for the dynamic creation of processes and channels and for the communication of values over channels. Because of the powerful abstraction mechanisms the communication topology of a given program may be very complex and therefore an efficient implementation may be facilitated by knowledge of the topology.
This paper presents an analysis for determining when a bounded number of processes and channels will be generated. The analysis proceeds in two stages. First we extend a polymorphic type system for SML to deduce not only the type of CML programs but also their communication behaviour expressed as terms in a new process algebra. Next we develop an analysis that given the communication behaviour predicts the number of processes and channels required during the execution of the CML program. The correctness of the analysis is proved using a subject reduction property for the type system.
- 1.D. Berry, R. Milner, D.N. Turner: A semantics for ML concurrency primitives. Proceedings of POPL'92, ACM Press, 1992. Google Scholar
Digital Library
- 2.A. Giacalone, P. Mishra, S. Prasad: Operational and Algebraic Semantics for Facile: A Syrmnetric Integration of Concurrent and Functional Programming. Proceedings of ICALP '90, SLNCS 443, 1990.Google Scholar
- 3.J.M. Lucassen, D.K. Gifford: Polymorphic Effect Systems. Proceedings of POPL'88, ACM Press, 1988. Google ScholarDigital Library
- 4.R. Milner: Communication and Concurrency. Prentice Hall, 1989. Google ScholarDigital Library
- 5.R. Milner, M. Tofte, R. Harper: The Definition of Standard ML. MIT Press, 1990. Google ScholarDigital Library
- 6.F. Nielson: The Typed Lambda-Calculus with First-Class Processes. Proceedings of PARLE'89, SLNCS 366, 1989. Google ScholarDigital Library
- 7.F. Nielson, H.R. Nielson: From CML to Process Algebras. Proceedings of CONCUR'93, SLNCS 715, 1993. Google ScholarDigital Library
- 8.J.H. Reppy: CML: A Higher-order Concurrent Language. Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, ACM Press, 1991. Google ScholarDigital Library
- 9.J.H. Reppy: Higher-Order Concurrency. Ph.D.- Thesis, Report 92-1285, Department of Computer Science, Cornell University, 1992. Google ScholarDigital Library
- 10.J.-P. Talpin, P. Jouvelot: The Type and Effect Discipline. Proceedings of LICS'92, 1992.Google Scholar
- 11.B. Thomsen: A Calculus of Higher Order Communicating Systems. Proceedings of POPL'89, ACM Press, 1989. Google ScholarDigital Library
- 12.B. Thomsen: Polymorphic sorts and types for concurrent functional programs. Technical report ECRC-93-10, 1993.Google Scholar
Index Terms
- Higher-order concurrent programs with finite communication topology (extended abstract)
Recommendations
Definitional Interpreters for Higher-Order Programming Languages
Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters that are themselves written in a programming language based on the lambda calculus (i.e., an applicative language ...
Comments