Communicating Sequential Processes

1. Introduction

	Problems Input/output operations are not well understood Lack of agreement on the comprehensive structuring methods: repetitive, alternative, sequential are well understood, but subroutine, monitor, coroutine, entries, etc. Multiple processor architecture to speed up, but is still disguised as a deterministic and sequential machine to programmers Multiprocessor should be used at the programming level -> Communication and synchronization methods should be defined
	Attempts to find Guarded command as sequential control structure to control non-determinism Parallel command: executing multiple sequential commands at the same time and synchronize Input/output command which can be used for communication between processes Rendezvous as a main synchronization mechanism Input command as a guard the command is executed only when the other party is ready to execute output command: rendezvous! when multiple parties are ready to output, one is selected arbitrarily Repetitive command with guards do the loop until all guards terminate Pattern matching feature to screen out input messages not in the required pattern
	Main points Input/output is a basic primitive of programming Parallel composition of communicating sequential processes is a fundamental program structuring method

2. Concepts and Notations

Grammar <command> = <simple_command> | <structured_command> <simple_command> = <assignment> | <input> | <output> <structured_command> = <alternative> | <repetitive> | <parallel> <command_list> = <command>; <declaration>; <command>; <command>; <declaration>; ... <command> Denotes sequential execution of component commands

2.1 Parallel Commands

	Grammar <parallel> = <process> (|| <process>)* <process> = <process_label> <command_list> <process_label> = <id>:: | <id>(<label subscript>, <label subscript>, <lable subscript> ...):: <label subscript> = <integer constant> | <range> <integer constant> = <numeral> | <bounded variable> <range> = <bounded variable>:<lower bound> .. <upper bound>
	EX Proc-1::do-11;do-12;do-13 || Proc-B::do-B1; do-B2 || ...

2.2 Assignment Commands

Grammar <assignment command> = <target variable> := <expression> Simple target: a generic variable which can hold any type of object Structured target: an object variable which can hold only object of the same type

2.3 Input and Output Commands

	Grammar <input_command> = <source process> ? <target_variable> read from <source process> and assign it (them) to <target_variable> <output_command> = <destination process> ! <expr> send <expr> to <destination process>
	Communication occurs when a process issues input command another process issues output command signatures of target variables of input and output commands match each other
	Synchronization: Rendezvous Whichever of reader or writer comes first should wait until the other comes
	Read/Write fails when the peer process terminates

2.4 Alternative and Repetitive Commands

	Grammar <repetitive command> = * <alternative command> <alternative command> = <guarded command> ([] <guarded command>)* <guarded command> = <guard> -> <command list> | <range>, <range>, ... <guard> -> <command list> <guard> = <guard list> (; <input command>)* | <input command>
	Guarded command Execute command list sequentially only when the execution of guard succeed
	Alternative command Exactly one element of alternative command is executed Which element should be executed when multiple guards are true is undefined Alternative command fails when all the guards failed
	Repetitive command Execute the element alternative command as long as it succeed How to handle break?
	Example: select (rdfds, wrfds, exfds, timeout) can't be simulated * [ readStream ? rdfds -> process data read [] writeStream ! wrfds -> prepare the next data to write [] excepStream ? exfds -> process error; terminate [] elapsed() > timeout -> break; ] "writeStream ! wrfds ->" is not a valid guard

3. Coroutines

In parallel programming, coroutine is more fundamental program structure than subroutine Subroutine is just a special case of coroutine

Lots of functions (coroutines) can be implemented by using the primitives suggested in this paper: COPY: copy characters from proc west to east COPY:: * [c:character; west?c -> east!c] SQUASH: squash two consecutive '*' to up arrow SQUASH:: * [c:character; west?c -> [c != '*' -> east!c [] c == '*' -> [west?c; c == '*' -> east!up_arrow [] east!'*'; east!c]]] DISASSEMBLE ASSEMBLE Reformat Conway's Problem

4. Subroutines and Data Representations

	Subroutine can be simulated by a parallel command: [subr::SUB || X::USER] X: SUB!input_arguments; SUB?return_value; ...; exit; subr: * [ X?input_args -> compute return value from input_args; X!return_val ]
	Note: X and subr are independent processes running parallel subr will run until X is running
	Recursive function can be partly simulated using multiple processes computing each level
	Problems and algorithm Function: Division With Remainder Recursion: Factorial Data Representation: Small Set of Integers Object Oriented: in this case process is the combination of data and method handling them Scanning a Set Recursive Data Representation: Small Set of Integers Actually not a recursive data representation, but a chain of objects of the same type Multiple Exits: Remove the Least Member

5. Monitors and Scheduling

	This paper suggests I/O and messaging as a fundamental synchronization primitives. Hence synchroniztion between processes is essentially not necessary
	Monitor can be simply implemented as a process: * [ pre-conditions to enter monitor; X(i) where i = 0..n ? value -> monitor body; X(i)!result ]

5.1 Bounded Buffer

	Problem: implement a buffer process X between producer and consumer
	Producer to buffer: buffer ! data
	Consumer to buffer: buffer ! more; buffer ? data Note: guard does not allow to have <write command>
	Buffer implementation * [ not_full; producer ? data -> insert the data [] not_empty; consumer ? more -> consumer ! data ]
	Multiple producers and/or consumers are possible. New producer and/or consumer joining to the buffer should be handled appropriately

5.2 Integer Semaphore

	Semaphore process shared by multiple processes
	We don't need to make semaphore operation atomic. But they should be very fast
	Joining and leaving processes are headache too

5.3 Dining Philosophers

	Each philosopher as an process; each fork as an process
	Philosopher -> fork: pickup or pushdown
	No deadlock prevention in the algorithm of the paper

6. Miscellaneous

6.1 Prime Numbers: The Sieve of Eratosthenes

6.2 An Iterative Array: Matrix Multiplication

7. Discussion

7.1 Notations

7.2 Explicit Naming

7.3 Port Names

7.4 Automatic Buffering

7.5 Unbounded Process Activation

7.6 Fairness

7.7 Functional Coroutines

7.8 Output Guards

7.9 Restriction: Repetitive Command With Input Guard

Evaluation

	Message passing for the communication between processes is uniformly used to solve various problems
	As rendezvous is used as the only synchronization mechanism, performance could be poor
	Processes are very dynamic in nature. They are created or destroyed and join or leave some closed group. Hence the language introduced in this paper should have had dynamic nature rather than static one as they claimed. This is why they couldn't fully implement recursions, monitor, semaphore, etc. And the language would have become a lot complex if they had made it dynamic.