Communicating sequential processes

ABSTRACT

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of Dijkstra's guarded command, these concepts are surprisingly versatile. Their use is illustrated by sample solutions of a variety of familiar programming exercises.

REFERENCES

• 1: Atkinson, R., and 14ewitt, C. Synchronisation in actor systems. Working Paper 83, M.I.T., Cambridge, Mass., Nov. 1976.
• 2: Bfinch Hansen, P. The programming language Concurrent Pascal. IEEE Trans. Software Eng. 1, 2 (June 1975), 199-207.
• 3: Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
• 4: Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
• 5: Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
• 6: Dijkstra, E.W. Cc-operating sequential processes. In Programming Languages, F. Genuys, Ed., Academic press, New York, 1968, pp. 43-112.
• 7: Dijkstra, E.W. Notes on strdctured prograraraing. In Structured Programming, Academic Press, New York 1972, pp. 1-82.
• 8: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 9: Dijkstra, E.W. Verbal communication, Marktoberdorf, Aug. 1975.
• 10: Hoare, C.A.R. Towards a theory of parallel programming. In Operating Systems Techniques, Academic Press, New York, 1972. pp. 61-71.
• 11: Hoare, C.A.R. Proof of correctness of data representation. Acta lnformatica 1, 4 (1972), 271-281.
• 12: Kahn, G. The semantics of a simple language for parallel programming. In Proc. IFIP Congress 74, North Holland, 1974.
• 13: Liskov, B.H. A note on CLU. Computation Structures Group Memo. 112, M.I.T., Cambridge, Mass, 1974.
• 14: Mcllroy, M.D. Coroutines. Bell Laboratories, Murray Hill N.J., 1968.
• 15: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 16: Reynolds, J.C. COGENT. ANL-7022, Argonne Nat. Lab., Argonne, Ill., 1965.
• 17: Thompson, K. The UNIX command language. In Structured Programming, Infotech, Nicholson House, Maidenhead. England, 1976. pp. 375-384.
• 18: van Wijngaarden, A. Ed, Report on the algorithmic language ALGOL 68. Numer. Math. 14 (1969), 79-218.
• 19: Wulf, W.A., London, R.L., and Shaw, M. Abstraction and verification in ALPHARD. Dept. of Comptr. Sci., Carnegie- Mellon U., Pittsburgh, Pa., June 1976.
• 20: Wirth, N. The programming language PASCAL. Acta Informatica 1, I (1971), 35-63.

INDEX TERMS

Keywords:
classes, concurrency, conditional critical regions, coroutines, data representations, guarded commands, input, iterative arrays, monitors, multiple entries, multiple exits, nondeterminacy, output, parallel programming, procedures, program structures, programming, programming languages, programming primitives, recursion