I):-----·- . ------- - -----·-- - -- ---On Effective Transformations.\ .•...

ofCommunicating Sequential Processes

A Thesis Submit ted to
the F4eulty of Yamanashi University for
the Master's Deg ree. ~: '·lMKS
Mu sha, Hiroyuki

March 19, 1983

•.·

.\

Contents
1. Introduction

1

2. Preliminaries

3

2.1 Definitions of CSP

3

2 . 1.1 overview ~f CSP

3

2 . 1.2 Formal Description of CSP

4

2.1 . 3 Examples of CSP ProgramsB

2.2 Coroutines

13

2 . 3 Graph Theory

13

3. Overview of Transformation

15·4. T.arg.e .t .o.f T.r.ansfor.mation : A Coroutine Language ASL

18

5.

4 . 1 Auxiliary Variables

18

4 . 2 Commands of ASL

20.

Algorithm for Transformation (1)23

5 . 1 overview of _the First Al9orithm

23

5.2 Description of the First Algorithm

24

6 . Algorithm for Transformation (2)27.7. Algorithm for Transformation (3)29

7.1 Conditions to be Satisfied

29

7.2 Overview of the Third Algorithm. 32

7 . 3 Description of the Third Algorithm

33

B. Comparison with Related Works

36

'·

·.

8.1 comparison with Katayam's Method36'

B. 2 Comparison with Habermann and Nassi 's Method ·.

37

8.3 comparison with Hagino's Method

38

9. Conclusion

49

Acknowledgement

41

References

42

-

i -

!,

1 . . Intrdduction
computingDistributedmodelsarenaturalsystems 'for describing both concurrent andandpowerfulsequential

computingphenome~a ~nd they gain growing interests in connection with VLSI
techno~~gy.

which

The

systemofCommunicating Sequential Processes,

we call CSP in the following of
propos~dthose models
In

simplewithandAlgorithms described in·e ·fficiently

is

one

of

input and output of processes are considered basic

CSP,

us

thesis,by C.A.R. Hoare in [41].

primitives~ · ~ombine~p~ovidethisnondeterminism,

those

primitives

transparent descriptions of algorithms.
CSP, . as

they

are,

however,arenotexecutable under ·conyentional computing environment.

Effective scheduling algorithms of processes are needed.
In this the'sis, methods for transformationofalgorithms

ofdescriptions .

in CSP (CS.P programs for short) into sequentially

executable programs aretargetofpresented~

Coroutines

are

set

be

the

the transformation and three differen.t algorithsm fortransformation are described; the first algorithm ~scantoappliedtosimpleandgeneral CSP programs but nat efficient, theother two · algorithms can only be applied to restricted classes of(
CSP programs but more effie ient than the first .one. Tho~ealgorithms

must

contribute

to

the

problemofscheduling· ofprocesses.
The rest of this thesis is organized as follows. In the next
chapter, definitions of CSP, coroutines and necessary concepts ingraph theory are given. Chapter 3transformation.

ove~views

the· algorithms

In Chapter 4, syntax and semantics of the targetof transformation, a language. with ·a kind of coroutineisdescribed.

for

Chapter

5,

6

and
-

1 -

7 · showthefacility,algor i tbms for....... 4

transfot:mation.

In

Chaptertransformation

taken

in

8,

this

we

- - - - -. - : - -compare

-

the

· -

· -

. . . .--

methodofthesis with other related works.

Conclusi6n is presented in Chapter 9 .

.,

:.
( .

- 2 -

·- ·- -·- --·- --------2. Preliminaries~orIn this chapter, preliminary concepts
inthefollowing

chapters
anddiscussions

given

are defined , In 2.1 , definitions of

CSP , theirsyntax.semantics,

are . given,definitionsofcorouti nes

are given in 2 . 2 , and 2.3 states definitions of terms

related to graph theory.

2.1 Definitions of CSP
In thisinfoimalsect~on ,definitions of

CSP

are

given.

At

first

introductions are given, then . in the following section., ·we show their syntax and semantics

rigorously,

and

in

Section.2.1.3 , examples of CSP ·programs are shown.
2.1.1 Overview of CSP
In this section, sysntax and semantics

A . CSP: described.

?f CSP are informallyprogram is a collection P of processes, whichshare no common variables at all and are supposed to be

executedcon c u Lrently. Communication between two processes p and q of p isexpressed by the. input and output command s
q?v

and
p!e,
~·

where

e

is

an

expression

and

v

is

a variab l e in which thereceived value of the expression of e is assigned .
thesecommands are synchronous,

ready to output the message at
Constituents
Dijkstra's

guardedofeach

Executionofi.e. p waits . at "q?v" until q is

"p~e"

processand vice versa .
arec ommands

based

on

commands (14,15,25], which can be classified

i n to two types: simple

commands

and

- 3 -

structured

commands.

The------------ ----- --- - -- -·---·--··-- ·-- - ··.. ·- ·-·-···---- ---···- - - --- - --membersofthesimple commands are the assignment command, theinput command, the output command and the null command which does
commands,

alternative

nothing.

Structured

andrepetitivecommands,

are organized by a set of guarded commands and express

selective and repetitive execution.
A guarded command is executed when its guard does notAnalternative

commandspecifies

command

fails
many

as

alternative

constituent

fail.

if all guards fail. A repetitive

iterationsaspossibl·eanditterminates when allcommands,

its

.o f

-guards fail.
An input command can appear in the end of~xecut€d

is

a

guard

and

is

only when a coxresponding output command is executed; itcalled an input guard. The input command fails if the ·process

specifiedis~erminated;theexecutionsuspends

ifthecorresponding process is not ready to output, which can result in'

deadlock.

·In

recent.

papers (1,19,28,Sg] output guards are also

permitted, however, in the rest of this thesis output guardsarenot supposed to appear in guards.

2.1.2 Formal Description of CSP
In 'this section, syntax and semantics of CSP are defined. At
first

the

whole

sysntax is shown in terms of extended BNF, andthen, the meaning of each command is explaind. Examples ofusageof theses commands are in the next section.
The whole syntax of CSP is as follows:<command> ::= <simple command>l <st ructured command><simple command> : := <null command>l<assignment command >!<input cornmand>j<output command><structured command> ::= <alternat ive command>! <repetitive command><null command> ::=skip<command list> ::= {<declaration>;<command>;}<command>- 4 -·- - -- - ·-·--·---- --.. - - ..·-·------·--- - -- ·- - - -- -··---···- .,. _.......

- -- --- ··...

_<parallel command> ::= [<process>{ I !<process>}]<process> ::= <process label><command list><process label> ::= <empty>l<identifier>::l<identifier>(<label subscript>{,<label subscript>})::<label subscript> ::= <integer constant>j<range><integer constant> ::= <numeral>l<bound variable><bound variable> := <identifier><range> ::= <bound variable>:<lower bound> .. <upper bound><lower bound> ::: <integer constant><upper bound> ::= <integer . constant><assignment command> ::= <target va r iable>:=<expression><expression> :: = <simple expression>J<structured expression><structured expression> ::= <constructor>(<expression list>)<constructor> ::= <identifier>J<empty>.
<expres.s ion list> : : == <~mpty .> ·1<expression> {,<express ion>}<target variable> ::= <simple variable>l<structured target><structured target> ::= <constructor>(<target variable list>)<target variable list> ::= <empty>l <target variable>{,<target variab+e>}··<input command> ::= <source >?<target variable><output command> ::= <destination>!<expression><source>. ::= <process name><destination> ::= <process name><proc.ess name> :: = <identifier> I <identifier> (<subscripts>)<subscripts> :: = <integer expression>{,<integer expression>}<repetitive ·command>. :: = *<al texnati ve command><alternative command> ::= [<guarded command>.{0<g.uarded command>})<guarded command> ::= <guard>--><command list>
I (<range>{,<range>}}<guard>--><command list><guard> ::= <guard list>l<guard list>;<input command>j<input command>·.
·<guard list> ::~<guard element>{;<guard element>}<guard ~lement> ::= <boolean expression>l<declaratio~>
A CSP program is a collection of disjoint processes each ·ofwhich is organizedbyaclassified

twotypes:

into

list

of

commands.

structured

commands. The members of simple commands are

Commands

commands
the

and

null

can

be

simplecommand,the assignment command, the input command and the output command.
The

membersofst·ructured comma·nds are the alternative commandand the repetitive command.
A command specifies· the behavior of a device
commandandreturnsone

executing

theof the two values "success" or "fail"

- 5 -

,

.-

__

--·u--··- ·- · -·--·- ·----&.-•• ., -- - :-r-·----..,·- ---·- -- ••-when it is executed. lf
it"success",

•

•

the

commandisexecutedthestatesofthechaoges~nvolved.

processes)•< •I·f the command returns

11

and

process

returns(orthefai 1", the executionof the whole system aBorts.
A null command, ~hich is denoted by "skip", does nothing andnever fails.
Ans~ecifies

commandassignment

evaluation

its

of

.)

expression,a.n d

assignmentofthe denoted value to the target

variable. A simple targ;e't variable inay
simple

or

a

have

assigned

constructor.

~alue.

structured
tp
The

it

a

have

assignedA structured target

structured

value,

toitavari~ble

my

-with

effect of such assignment is to assign to ·eachconsti tue.nt simpler variable of the structured targetthedenoted.

'successful

by

the·

~ssignrnent,

targetvari.able,

if

value

Thus~

of the corresponding component of the structured value.
value

same

the

the

evaluated after ais the same as the value

denotedby

theexpression, as evaluated before the assignment .
.•An

assignment

fails

if

the

value

of

its expression is

undefined, or if that value does not match the target
inthevalue offollowing
its

type.

sense:
A

A

variables,

simple target variable matches any

structured

targetvariablematchesastructured value, provided that:(1) they have the same constructor,(2} thetargetvariable

list is the same l ength as the list ofcomponents of the value, and(3) each target variable of the list
the

value

list.

A

the.

structured

corresponding
with

no

Input and output commands specify communication between

twocomponentofmatchesvalue

components is known as a "signal."

- 6 -

__

:

__ .

- · ··· - · -·· ·· · · · · --· - ·- -~--.•processes. Communicatiotr ~ccurs between two processes when
(1) aninput

command · in one process specifies · as its source theprocess name of the

oth~r

.

process;.

( 2) an output command · iri··
proces~destination the(3) thetargettheotherprocess

specifies

asits_name of the first process; andvariableof the input command mqtches the value

denoted by the expression of theou~putcommand.

'>

On these condition s, the input and output commands
Command s

correspond .

i ··whichcorrespondaresaid .

areexecut·ed

sit~\Ul taneously,

and their .effect i:s to assign the · value

expression

the·

of

to

of

the

output command to the target variable of the

input command.
An input command fails
outputcommand· expres~ion

·if

its

of

synchronization

toofbeco~e

An

input

and

6utputready to communicate

be delayed its execution until the correspond in gcommand in the other process also becomesprocess

terminated.

i.s .unde:fi.ne.d .

commands means that the process which
have

is

fails if its destination is terminated or if its

The requirement

firstsourceterminates.

ready,

or

the

other

It is possible that the delay will neverbeended, that is a deadlock.
A set of guarded commands constitutes an

al ter-'(lciti veorarepetitive command. A guarded command can be executed only if the·~execution of its guard does not fail . Firs~ its guard is executed
and

then

its

commandlist is executed, A guard is executed by
rig~t.

Boolean

if it denotes false, the guard

fails;

execution of its constituent commands from left toexpressions are evaluated:but

an expression that denot es true has no effect.

introduces a fresh variable with a scope that
- 7 -A declaration

extendsfromthe

. ·-· .... --· ...··- ·--· ·-··-. .. ..........

place

of

the

-

__ ____ _____·- - ·--·-·-··- ·"·------· --·· ·- ·
...

...

....

declaration to the end of

th~

-· ·

9uraded command . An

input command at the end .of a guard is executed only if andwhen

a cor responding output command is executed .
An alternative command specifies execution of exactly one ofits

constituent

guardedcommands.

Consequ.ently I

fail, the alternative command fails. Otherwise an

if all guards
arbitraryonewith successfully executable guard is selected and execut.ed.
Arepetitivecommandspecifies

as

many

repetitions

possible of its constituent-alternative command:\ Thus,
guardsfail,with returning
executed

once

the
11

when

as
all

repetitive command t erminates with no effeet,

success." Otherwise, the alternative

commandisand then the whole repetitive command is executed

again. Consider a repetitive command when all -its ·true guard list
end in an input guard. Such a command have to\bedelayeduntil

either{1)

anoutputcommand corresponding to one of the input guards

becomes ready, or{2) all the sources named by the input guards . have terminated.
In case (2), the repetitive command terminates. If neither

event

ever occurs, the process fails in deadlock .

2.1. 3 Examples of CSP Programs
rn

this

section, examples of descriptions of algorithms in

CSP are shown.
(1) Subroutines (Procedures)
The following is an example of subroutines, which receives x
and y from process. X and returns ( x d i v y) and ( x mod y) •

- 8 -

/*

a solution of Knight 1 s Tour in CSP[TRY(i:2 •• NSQ)::
board: (N, N) integer;x, y, u, v, k: integer;*[TRY (i- l ) ?{x,y,board) -- >k*/

: . 1;* [k<=S -->nextplace! (x,y , k);
nextplace?(u,v);[1 <=u;u<=8; l<=v;v<=B; board(u,v)•3 -->board(u , v) :=. i;
TRY ( i + 1) ! ( u, v, board) ;board (u ,v ) := 0;
Ou<l;S<ui v<l;B<v; board(u,v)~ >0 -->
skip
·) ;

k := k+1

1·1

TRY (1) ::board : (N , N) integer;j, k!integer
j :. 1;* [ j<=N -->k:.: 1;*[k<=N --> .
board(j,k)
k : = k+l

:= 9;

]~
j

: = j+1l;j: = 1;* [j <=(N+l)/2 -->k ::a j ; .
*[k <= (N+l)/2 -->board(j ,k} := 1;
TRY ( 2) ! ( j, k, board) ;board(j,k) := 0;k : = k+1
Ji
j : = j+l

- HJ -

!* 8-Queens Problem in CSP */[TRY{i:l..B)::
A: (1. . 8) boolean; B: (2 .. 16) boolean;
C: (-7 •• 7} boolean; X: (1 • • 8) integer;*[TRY(i -l }?(A , B,C,X} -- >j: integer; j:=l;*[j<=B ; A(j); B(i+j); C(i-j) -->X(i} . :=j;A(j): = false;
B{i+j) .:• false;
C{i-j) :• false;
TRY(i+l)! (A,B,C,X);
A(j)· - true;
B(i+j) ::true;C(i- j) :=true;
j := j+l
JJ

1-1

TRY (0')::
A: (1 .. 8} boolean; B: (2; .16) boolean;
C: (-7 •. ·7 ) boolean; X: (1 .• 8) integer;
i:integer;
i:=l; *[i<=8 --> · A(i):=true; i:=i+l];
i : ~2; *(i<~l6 --> B(i) :~true; i:=i+l];
i:•-7;*[i<=7 --> C(i) :=tr ue; i: =i +l];i:=l; *[i<=8 --> ~(i)~=0;
i:=i+l];TRY ( 1) 1 (A, B, C , X)

II

TRY ( 9) : :A : ( 1 . • 8 ) boo 1 e an ; B : ( 2 . . 16 ) boolean;
C: (-7 •• 7) boolean; X: (1 •• 8) integer ;~[TRY(8)?(A,B,C~X)-->

PR!NT!X·](5) Description of a Sorter
Thefollowing

programade sc ribes

array of integers.
·.

r.

- 11 -.

··..:·

sorter which sorts an ·

::·.

of

/* a description
a sorter in CSP */sorter (i: 1. .MAX ):: .
num, ord, next, ~rdnext: integer;
sorter(i-l)?(num,~rd}-->*[sorter(i-l)?{ne~t,ordnext)-->[ num>next ~-> or~ := ord+l
num=next -~ > skip
nurn<next -~> ordnext := ordnext+l];sorter (i+i"> ·1 (next,ordnext)
1;.
source! (nurn,ord)

II sorter (0.) ::<)nurn, ord , next, ordnext: integer;~o~rce?(num,ord)-->*[source(next,o~dnext)-->[ nurn>next -->· ord : .:~ ord+ 1
num=next --> skip
num<next - - >. ordnext := ordnext+l] ;sorter (l)! (next,ordnext)] ;souice! (num,ord)11source ::a: (liJ.:.MAX)integer; i, j, nurn, or:d: :l..nteger;i:= . 0;* [ i <=MAX·;]";j

input? a (i) ·-'->
sorter (0)! (a"(i) ,0);i : = i+l:= 0;

* [·j< i. --)sorter(i)?(num,ord);a ( ord) : = num;
output!a(j);j := j+lJ;( .

- 12 -

2.2 Coroutines
A set of coroutines [11] isthetargetoftransformation

explained · in the following chapters. In this section, definitonsof courintes

andcoroutines,areconcretesemicoroutines
giv~n.

language

The

with

a

(59},

targ~tcoroutineofrestrictedourfacility,

kind

of

transformation, aisdescribedinChapter 4.
Acoroutine

is defined as a routine (subprogram) which has

the following two features:(l) the values of the variables local to the routine are retained
between successive activations of the routine, and(2) when the cont·rol re-ent·e rs the 1:0utine, the execution·a t the point where ·i·t

le·~tresumes

off last time.

A semicoroutine, a restricted kind of coroutines, is defined as arou:tine which satisfies (1) and (2) above and; in ·addition,(3) asemicoroutine

must

be

activated by a caller to which it

returns the control on completion of its task.

2.3 Graph Theory
In

this

understandthesection,terms

discussions

in

graph

theorynecessary

given in the following

chapte~stoaredefined; definitions of the terms are due to [32].
A DIGRAPH D consists of a finite
collection,.

ofordered(u,v} is called an ARC or

pairs

set

V

of

POINTSandaof distinct points. Any such pair

DIRECTED

LINE

and

will

usuallybedenoted by uv. The arc uv goes from u to v and is INCIDENT with uand v. We also say that u

is ADJACENT TO v and v is ADJACENT FROM

u.

of

The

OUTDEGREE

od{v)

a

point v is the number of points

adjacent from it, and the INDEGREE id(v)- 13 -

is thenumberadjacent

to ·it.
A (DIRECTED) WALK in a digraph is an alternating sequence ofpointsand arcs, v0, xl, v l, ... , xN, vN in wnich each arc xi is

vi - 1 vi.

The

occ.urrences

LENGTH
of

of

such

a

walk

N,

is

the

number · ofar cs in it . A CLOSED WALK has the same first andAlast points and a SPANNING WALK contains all the points.
is · a

wa lk

in

which

all

pointsare

distinct;PATH

a CYCLE is a

· ~di stinc~nontri v i al closed walk with . all points(except the fiist

and la.St). If there is a path from u ·to v ·, then v is said
REACHABLE

FROM

u,

to

be

and the DISTANCE, d(u,v), from u to v is thelength of any shortest su c h pa th. A SEMIWALK

isanalternating

sequence v0, xl; vl, ••• , xN, vN of points and arcs, but eac h arc
be either vi-1 v i or vi vi-1. A SEM lPATH , SEMICYCLE, and

XI

may

so

forth,

aredefinedas

expected.

A

digr aph

is

STRONGLY

CONNECTED, or STRONG, if every two points are mutually reacha ble;it

is

UNILATERA~LY

CONNECTED ,or

UNILATERAL,

po i nts at lea st one is reachabl e from the o ther;

if for any two
andit

WEAKLYCONNECTED, or WEAK, if every two points are joined by a semipath.
A

STRONGCOMPONENT

subgraph . Let sl , s2,
di g raphofadigraph... , sN be

the

is

s trongamaximalstrongcompone nts

ofaD. The CONDENSATION D* ·of D has the stron g components ofD ·as its points,· with an arc from sr to sJ whenev·e r there

.is

at

l east one arc in D from a point of.si to a point in ·sJ.
An
0

ACYCLIC digraph co ntains no directed cyc les. A SOURCE in

is a poi nt which can r each all other s; an OUT-TREE is a digraphwith a source having no semicycles.

- 14 -

1L

3. Overview of Transformation
In Chapter 4, the target language of thedescribed

andin · Chapter

5transformationisthrough Chapter 7, three kinds ofalgorithms for transformation of CSP programs into coroutines aredescribed. In this chapter, a general methods which are common to
those three algorithms and also the differences

of

those

three

algorithms are presented.

All the three algorithms in the following chapters transform
CSP programs in the following manner:(1} aprocess

of

a

CSP

programwillbetransformed into a

coroutine,(2) a special routine called scheduler .is

introduced

tomanagethe selection and . the execution of those coroutines,(3} eachcommandofaprocess,

exceptfor

input and output

commands, will be transformed into the same command of the target
coroutine,(4} commands which transfer

thecontroloftheexecutionisintroduced,
variables

arevariables, values of the messages to

be

(5)

globally

messagestoaccessiblebeintroduced;
P.assed,

types

in

those
of

· the

passed, and states of the processes are stbred,and(6) communication among processes are realized through the global
variables: a sender of a message first writes the value
type

of

and

the

the message there, and then the rece iver of the message

reads and assigns the value

into

the

targetvariableofthemessage.
we compare the three algorithms for transformation describedin

Chapter

5,

6

and

7.

The

first difference of those th r ee
15 -

algorithms to be discussed is the range of CSP programs tothosealgorithms

candescribed in Chapter 5,

which

be applied. The first algorithm, which iscanbe · applied

to

any

kind

of

CSP

programs. on the other hand, the second and the third algorithms,
which

are described in Chapter 6 and Chapter 7 respectively, canonly be applied to .CSP p_rograms that satisfy certainThe

conditions.

second algorithm can be applied to CSP programs which do nut

contain any input · guard. The third algorithm canbe . applied . to

CSP . progr ams which satisfies three "Conditions stated
two graphs which

represents

the

form

of

in terms ofcommunication

amongprocesses.
Concerning

about efficiency of the exec ution of transformed

programs, we can say the following. The duty
thespecialofthescheduler,routine that manages the execution, is thehe~viest

in ·the programs transformed according to the first algorithm.
thoseprograms,

every

coroutinescheduler every time it ishas

activated.

Intobe . activated by theInprograms

transformed'·

according · to the second
coroutine,thealgorith~,

executioncanonce the scheduler activates aproceed,without

returning thecontrol to the sch ed uler, as far as the execution reaches the endof th e coroutine. The control flows amongbe)activatedcorouti~es

which

must

for the execution of the first coroutine. Programs

transformed according to the third algorithm are executablemost

efficiently. The only thing the schduler has to do is to activate'•aspecialroutin e

called source which leads theexe~ution.

The

control flows among processes almost in the same manner as in the
programs transformed according to the second algorithms but there
is no need for the sc heduler to activate

otherreceivingsource;thecontrol

again

from
- 16 -

theprocesses

after

the execution

terminates.
For the s ake of convenience, in thethisthesis,c o n stituentsofcoroutines, will also be · called
processes
tar ge t

andcoroutines

thefo ll ow ing

cha ptersoftargetoftransformation,

processes;

we

use

interchangeablly

language.

- 17 -

thewords

when we di sc uss the4. Targ'et of. Transformation: A Coroutine Language ASL
The target language of transformation, which we call ASL, isdefined in this chapter. As stated in Chapter 3,

commands

which

are nof· related to input or output commands are borrowed from CSP
prese~vingtheirsyntaxand semantics. Thus, nondeterminism isalso contained in this language. Commands
processe~

output of..,related

to

input

or

are changed. Moreover, commands which express

transfer of the ·con·trol among routines and global variables to bel,lSed for{ communication of processes are introduced.

In

Section

4.1,

we

describe

auxil.iary

variables

introduced. In Section 4.2, syntax and semantics of

to becommandsof

ASL are formally described.

4.1 Auxiliary VariablesIn.o .rder to. explain the meanings of· the commands of ASL, we

introduce auxiliary variables which do not appear in the text
ASL

programs.

Eachprocess

accessible

variablesotherinaccessible

from

other

(coroutine)
than

local

processes.

has

of

several globallyvariables

which

are

One of those is a variablewhich contains the state of the process and is reffered byp. status,~here

p is the name of a paticuler process~ . ~he variable p.statuscontains one of the follow{ng value:,,(1) ready (denoted by ·RE) -- which indicates that the process
ready to proceed its execution if it is(2)

output waitingisactiv~ted,indicates

that

the

process was suspended when it tried to output . a message

and

can

not

process

proceedits(denoted by OW) -- which

execution

unlessthe · corresponding

reaches the place of the rendezvous and receives the message,- 18 -

(3) input waiting (denoted by IW) -- which
process
not

.•

was

proceedthat

thewhen it tried to input a message and cansuspendedits

indicates

execution

unlessthecorresponding

process

reaches the place of the rendezvous,{4) input waiting in guard (denoted by !WIG) -- whichthat the process
alternativeorissuspended

when

it

tried

indicatesto

executeana repetitive command which contains input guards

but none of the guards suceeded, and ·(5) terminated (denoted . by TE) --whichindicates

that

the

process has already finished its execution.
Other

than

-statusexplained

above,

for each process, weprepare globally accessible variables whose names

andfunctions

are stated in the following:(1) message box (denoted by MSGB)

which

contains the-value ofof the message. to be passed ftom the process,(2) message type (denoted by MSGT) -- which contains the typethemessage

to

be

input

or

outputofat an input or an output

command,(3} partner (denoted by PTNR) -- which contains the namepartnerofthethe communication to be taken place at the time, an~(4). caller -- whichcontains

activated the process

~y

will

in

be

of

explained

the

name

of

a · process· whicha call command or a resume command which
~he

next

sebsection~

We

refer

those

variables as<process name>.<name - of the variable>.
For clear explanations of the mechanisms of the execution of
ASL, we introduce
a

one

more

process

andvariable

executing-proces~,

commonvariable

named

executing-

local va·riable named local-sequence-control. The
which

·.
- 19 -willbedenotedby

EXECP,

contains

the

name

of

the

processtobeexecuted next. The

variable local - sequence-control , which will bepointsthe command of thepro~ess

denotedbyLSC,

to be executed next. We assume

that the processer of ASL prog rams picks the content EXECP before
executing a command if necessa ry, andpointed

by

the

LSC

of

the

then

process.

executesacommandWe also assume that theconten·t of the LSC is ren ewed properly a fter executing the comrnnd
and it is retained between succesive

acctivatio~s.

i.e . processes behave as corDutines . In thewedefineof the pr ocess;following

sections,

the meanings of ·commands of ASL using those variables

defined in this section.

4 . 2 Commands of ASL
semantic~

syntax a ndof commands

of

ASL

is

described

byusing the variables defined in the previous sect ion .
Inorde rtotransfer

thecontrolofthe execution, we

introduce co ntrol commands as foll o ws:<control command>: : = <call ·comma nd><call ' command ><return command ><resume command><status><return command><resume command>: : = call <process name> (<status>)• . = return (<status > ):: = resume <process name> (<status >). . = RE I I w I ·I wIG I ow I TE • .

'A call command

call q(ST)

in a process p, transfers t he control of
namedprocessq,

theexecutionto· sets the status of p to ST (here ST is one of

the following: RE, IW, IWIG, OW, or TE), and assigns the nameth~activating

p~o ces s,· ca l l q (ST)thep, into q. calle r , that is:/* in p */
-

20 -

of

-q.caller := p;p.status := ST;
EXECP:= q .
The following return command
return { ST )inaprocess

p returns the control to the callerof p ano sets

the status of p to ST, that is:/* in preturn · ( ST*/·=P · status := ST;: = p. calle.r .

EXECP

The following resume command
resume q( ST )

in a process p activates the process p · and sets thep. call.
•.

Tha.t

is

not

q.

if

The ·command also sets the status of p to ST .

is:resume q { ST )• .

p.caller/* in q */:=p .status := ST;[p.caller = q --> skip
gp.caller <>q -- > q~caller : = p ];EXECP : = q
Message commands which take charge of message passings

have

the following form:<message command >.. - <r ecei ve command><send command><receive command>· ::=receive (<targetvariable>} from <process name><send command>::=send (<expression>) to <process name>.
A

receive command assigns the value of the message to the target

variable and returns the value success as the result

if

it

can

receive the correponding message . It returns the value fail if it
can

no t

receive the message. A send command writes the value of- 21 -

t

~

....

- -· .. .. ,the expression in MSGB, writes the type of the expression in MSGTand changes the status of the partner of the rendezvous if itsuspendea : and the message corresponds.

-

22 -

is

;;_.

5. Algorithm for Transformation (1)Three algorithms for transformation are described in Chapter
5

through

Chapter

7 . In this chapter the first algorithm which

ca n be applied to any kind of CSP

programs

informalin Section 5.1 and the rigorous

description

is

given

a re

presented.

Itsdescription of this algorithm is given in 5.2.

5.1 Overview of the First ALgorithm
As stated in Chapter 3, every process of atransformed
'/'

'

'

/

A

special

The

is

for

input

and

outputroutine called scheduler is added to thosecoroutines and it always
control the

programinto a coroutine and each command of each process · istransformed i nto the same command except
commands.

CSP

k~eps

the status o f

every

process

andex~cution.

scheduler

repeats thefoll~wingcycle until no process

is executable.
(1) The scheduler

chooses · andactivatesaprocess · whichisexecutable·;(2) The

,.·'

:•

\

/

chosenprocess

executes

its commands as far as it canproceed (the process can not proceed when

it

can

not

send

or

receive a message at an input or an output command, or when it isterm ina ted.) ;(3) The suspended process returns the control to the scheduler.
Themechanismofthemessagepassing

is as follows. In

principle the process which reaches the place of
firstwrites

the

type

of

the

messagethe(and the va lue of themessage if the process is the sender of the message)accessible

rendezvous

inglobally

space , then the other. process which· reaches the input

or the output command checks the c o rrespondence of- 23 -

themessage,lL:::::1 .. Q.
where

BE

BE_k_i q,t?vi --> CL~,andCL stand for Boolean expressions and command list.

respectively.
(4) ELSE in[ '(1 z~l-- £. BEt -- > CLx_
ELSE- -> CL )is defined as ELSE=

I\~ (not BE_z) .

An output command in a process q which has the . form
ple

is transformed into the following commands :send (e) top; return (OW}.
An input command which is not appearing in a guard of a ·· process p
and has the formq?v

is transformed into the following command :[receive (v) from q --> skip
ELSE--> retu~n(IW); receive (v) from q]

An alternative command with input

guardsinaprocesspwhich bas the form

[ D~~\,, tBE~; q;;. ?v.t --:-> CL~

O'fit~tt\.,'MBE~--> CLJ::

is transformed into the following:[Ut:..\,,2,. BE~;receive(v.t)

UTil=-14-t--~BEtfrom q,.t -- > CLA--> CL}\or not receive(v_z) ft:om q~). ;ll~.~R:H,,-mBEj' -- >return (!WIG) ;[(!:q"Q r eceive(v,.\) from q;;_ -- > CL,;.

Q(\1::, (not BE;::A

repetitivecommand with input guards in a process p.which has

the form- 25 -

is transformed into the f ollowing:
flag: boolean; flag := true;
flag i BE-' i r eceive (VA} from q ,k -- > CL ~UU t:..~·H" ""' flag ; BE A --> CL li] flag ;,\~ ( not BE-t or not receive ( v;d from q ~) ;1
A~~ ( not BE~ ) · --> rflag: boolean; rflag := true;*.[flag -->[rflag - -> return (IWIG)
Onot rflag -- > skip]
DO J::::\-.~ BE:k; receive (v~ from q;: --> CL ~UQ-:o:. -2'\\,.-r.BEt.. -- > CL~; rflag := false
ELSE --> flag := false* HJ~...I.. t_u]

At the end · of each process, we insert
return(TE)

to inform its

termin~tion.

'··

26 -

6. Algorithm for Transformation (2)If a CSP program to be transformed has
strategy

no

input

guard,acalled demand driven reduces the duty of the scheduler,

since in those cases the pairofparticipantsofa·paticular

communicatin is always determined uniquely.
Ifaprocessp reaches an input or an output command, theprocess transfer the control to the partner
rheacti vatedprocessoftheproceeds execution, until it reaches theplace of the rendezvous and answer the request of theItispossiblethat

rendezvous.

th~

processes, however, thosecalledcalledactivator.

process also activates otherprocesses

can

not

call

any

processwhichis already waiting for the partner . to resporid the~equest,since this indicates the presence of deadlock. Thus, · ifthere does not arise any deadlock, the control must return to the. firstp~ocess

Inp.

process ' p chosen bycontroltothethis .. way · the execution proceeds until thethe . scheduler

scheduler.

terminates

andreturnThus, the number of the scheduler's

choice of the process to activate

decreases·comaringwithfirst algor·ithm. ·The transformation proceeds in the following manner.

(1) If an input command
q?v

..

the

appears, it is changed to[receive v from q --> return (RE)
UPot (receive v from q) -->call q (IW); receive v form q](2) If an output command
q!e
appears, it is changed to- 27 -

thesend (e) t o q; r es ume q (OW)
(3) At the end of each processreturn(TE)

is inserted to inform its t e rmination.

.. '

.

-

28 -

...
7. Algorithm for Transformation (3}
In

this

chapterthethird algorithm for transformatin ispresented. CSP programs which satisfy certain conditions
efficiently

executable.

can

be

The first section of this chapter shows

the conditions to be satisfied, the second secti on

explain·sthealgorithm informally, and in the last section ., r .igorous rules fortransformation are presented.
7.1 Cqnditions to be

Satis~ied

If a CSP program satisfies certain con.ditions stated in thissection,~rocess

thisthe ro le of the scheduler · is to only activate a special
ca~ ledsourc~

process which

leads

computation ~

the

In

section we fir st state s the conditions to be satisfied, andthen, describe the way of transformation.
Any program in CSP that satisfies
below

in

three

conditions

terms of commu·n ication graph [19) and activation graphcan be executed without arbitrary choice of th~scheduler.

stated

At

first

th e

communication

prticessbythegraph Gc is defined as

foilows:
Definition 1 (communication gra ph Gc).
For a given CSP program, the COMMUNICATION GRA PH Gc isdefinedas follows :(1) each process is a point of Gc, and(2) ifthere is a communication (i. e . tra nsf er of me ssages) froma process p to a prcess q, pq is contained in Gc as an arc.
Let P be the set of processes of the CSP program ,words~

or,

in

other

the set of points of Gc 1 and let Ac be the. set of arcs in

Gc. we write as Gc=(P,Ac). The first condition to be satisfied is- 29 -

as fo llows:
Condition 1.
Gc is acyclic.
By this condition a partia l order <(intothe _set

of

c an

be

natura ll y

inducedP of Gc. We shall define the o rd er ofpointsp ,q E P as
pq~Ac

-

==>

~q.

suppose that an expression in CSP s ·a tisfi es the above

c on di ti on.

The next co ndition we take int o consideration is:
Condition 2.
Thereexistsaproces s

s EP such that f or any -pEP, p:S:s or

satisfies-thes;S p holds.
The proce'Ss whi c hunique.

If

thereexistsmo r e

above
t han

con<H tion

may _ not _ beone process, we selec t anarbitrary .one and fix it from now o n.
Definition 2 (source process s) .
we select a process~hic hsatis fi es Conditio 2 and fix

it .

we

call the pr o cess the SOURCE (PROCESS') .of P, which will be den o t ed
by s.

Another

kind

of

graph

calledactivation

graph

is

now

defined.
Definition 3 (activation graph Ga}.
If Condition 1

and

2

ar e

satisfied,the

ACTIVATION

Ga=(Pa,Aa) o f a CSP pr og r am can be defined a s follows:- 30 -

GRAPH

{1)

Pa=P

(the

set of points is the same as that of Gc ; thus we

use P instead of J?a) , ana(2)

pq~ Aa

<==>

qp~Ac

{if q~ s)pq E.Ac(ifs~ p).

Note that indegree of the graph Ga of the source process s is0.

The following proposition is proved easily.
Proposition l.
. Ga is acyclic.

By

this

proposition,different from (I? ,~ )anewpartialis inCiuced;

order(P,~ )

whichis

it represents the orCier oftheactivation .
The last condition to be satisfied is stated in terms of theactivation graph Ga as follows:
Condition· 3.
Ga is an out-tree .
Remark.
The above condition is equival ent to the following one :Condition 3' .
With

resp~ct

to Ga , the inCiegree of thesourc~

s is G a~a fheinCiegrees of all other processes are 1.

·.
For conve nience, we will define several terms.
Definition 4 (producer and consumer}.
A process p is said to be a PRODUCER (PROCESS)
said to be a CONSUMER(PROCESS}

if s~p .

- 31

if p~s, andisDefinition 5 (parent, son, ancestry and descendant).
For e ach pf: P , we de fi ne the fq llowi ng:(1) if qpE;Aa , q is said to be the parent of p (which is unique l ydefined ),(2) if pq~Aa , q is said to be a son of p ,(3){qG- .Pjq~p} i s said to be ancestry of p , and(4){ q GPj p~q} i s sai d to be des cenda nt o f p.

7. 2 o ve rvi ew of th e Thir d Algorithm·Thoseprogr a ms

wh·i ch satisfy above three. conditions can be

execu t ed in the f ollowing manher.
(1) The shce duler activates t he source pr ocess s.
( 2) The source process makes all the pr·oa·ucer proce·sses be·readyt o send me ssages i ri t he fol lowing way:it

(2 - 1)eachactivatesof its sons that i's a consumer , andthen .

(2 - 2) each of those sons also makes their

sons

be

r eady · tosend me s sage.s by activating them ...
{2-2)

proceeds

u ntil all t h e pr od ucer s are a ctivated a rid be comeready to send messag~s t o the ir parent processes.
( 3) The computat io n pr o ceeds by t he lead ing o f the sourc e proce ss
preserving ·thecondition ·. ~hatalways

be

ready

to

send

(Note

that

the

resultdetermined since all the

of

all

the

producerproces ses

a re ·

messages unless they are terminated.
theinpu tpr~ducers

gua r dsca n

beal waysare ready to send messages . )( 4) When t he sou rc e p rocess ' i s re ached its e nd , it b roadc asts i ts
termination to all ~he consumers in the same manner as (2-2).
{5) Al l . th e

consumer s·ch~ n ge

their status to "terminated ". andreturn the control · to their parents.
-

32 -(6) The source process gets the control aga i n and returns

..

it

to

the· scheduler.
(7) The execution terminates.

7.3 Description of the ~hird Algorithm
be

P

Let

the

set

of

processes

ofa CSP program to be.transformed. We transform a process pEP in the following manner.
(1} Ifp~s,call q\insert the following call commands at the top:(RE);

~ -·~; · callq"" (RE),·where each q.t is a son of p.
(2} A command which is not or

does

not

contain

any

input

or

output command is not changed.
(3) An input command which does not appear in guard is changed asfollows:(3-1)

i£ p~ s, · .an.d input commandq?v

is changed to ·receive (v} from q; call q (RE),and(3-2) ifs~p,

an input commandq?v

is change to
receive {v) from q; return (RE).
'·(4) An output command is changed as follows:~4-1)

if ~s, and output commandq!e

is changed tosend (e) to q; return (OW) ,
and ·
-

33 -

.. . - ··· -·- ·---- ... --·- - - --- ....._, .... -. . . ...

(4-2)

if

sLp·-,. an ou t pu t-

commandq!e
is changed to·to q; call q (OW} .

send (e)(5) An alter n ative command with input guards inB~.[;

lD.t:.l ., e...

q.t?vl\.... -- > CL ,....

-- > CL A..-

BE 1,:

nnt-.:fit .. """is changed t o

p~s

. 1)

[l]-\~ .. ~' BEci· re ceivec a 11 q A ( R~ ) ; CL ;A
Ut!t~.,W\ BE A --> CL;.

(vA'}

from q.A... - ->J•

If s~ , the command
call q(RE)

in the above is replaced byreturn (RE) •(6) An repetitive comma nd with input guards in p~s* lH.I.-$I.. .t

BE~;' q~?vi\:

n'UA::::~-i{ ..~ BE).

- - > CLA-- > CL ;_)is c hanged to*[\l.=-\.. ~BE;:-; receive (v..t) f rom q.\ - - >ca l1. q- (RE); CL,f-=.Gtt.."W.. sEA" --> cL ,.c
J•

nn.;:

If

s~p,

the co mmand

call q(RE)

i n the above is r eplaced byreturn (RE) •(7) Ifp~s,returnthe following command is inserted in the end:(TE) .

(B) If s-<p, the following command is inserted in the end:call qwhere each
The

1
a~
~~-

{ TE);•• • ;call g~ (TE);return (TE},is a son of p.

follow in gisanexample
-

34 -

of

this

algori thmsof

transformation. A CSP program shown in 2 . 1 . 3 of 8-Que ens
istransformed

as fo llows,

whe~e

TRY(9)

is chosen as the so urce

process.
[TRY ( i: 1. . 8) : :A: (1. .8) boolean; B: (2 • • 16)
c: (-7 •• 7) boolean; X: (1 •• 8)call TRY(i-1} (RE);boolean;integer;*[receive( (A,B,C,X) ) from TRY(i-1}
call TRY ( i-1) (RE);j:integer; j:c1;* [ j <=8; A ( j) i B ( i + j) ; C ( i- j )) -- >
X(i)
:= j;
A(j)
:= false;
B(i+j) := :false;C(i-j) ::: false;·send( (A,B,C,X}
to TRY(i+1);
return;A(j):= true;
B(i+j) := true;C(i+j) := trti·e ;]]j := j+l-- >II

TRY(0')::

A: (1. .B) boolean; B: (2 •• 16) boolean;
C: (-7 •. 7)boolean; X: (1 .. 8) i qteger;
i:integer;i : =1; * [ i <·;; ~. ' l;-- > A ( i) :=true; 1:=1+1~:=2; · *li<=l6 -- > B(i}:=true; i:=i+l] ii: =-7;*[i <=7 - ..... >. C(i) :=true; i:=i+l];
i:=i+l];i:=l; *[i<=8 --> X(i) : =0;
send( (A,B,C,X} ) to TRY(l};return (OW)II

TRY ( 9) ~:A: (1..8) boolean; B: (2 •. 16)
C: (-7 .. ·7}· boolean; X: (1 •. 8}call TRY(8) (RE};*[receive( (A,B,C,X) ) fromca 11 TRY ( 8) (RE) ;send{ X ) to PRINT; callboolean;integer;
TRY(8)

-->

PRINT

(OW)

- 35 -

Problema. Comparison with Related Works
In this chapter, we compare
presented

in this thesis

work [44,45) of

w~th

the

methodof . transformation

other related works: T. Katayama'stranslationof

attribute

grammars

[48)

into

procesures,

A.N.

Haber~ann

and

r:R.

Nassi's work [33) of Ad~

r7 a 1

into

procedures

and

T.

Hagino's

tasks

work

[28)

of

transformation of CSP programs into ?equental programs.

Katay~ma's

8.1 Gomparison with

MethodKatayama's method for translation of attribute grammers into
procedure~isdesigned · for

effective

attributes and its outline is as follows
Le~

a

X be

G=(Vn,Vt,P,S),

nonterminal
where

Vn,

symbolVt,evaluationof value Of

[44].

of

·an

attribute

grammarP and S are a set of nonterminal

symb~ls, a set of terminal symbols, · a set of ·production rules andthe start

symbol-r espectively,

and

let

s

be

a

synthesized ·attributeof X. we associate with each pair (X,s) a procedure of

the form

R (Vl,••• t

Vm, T; V) i

where Vl, ... , Vm are parameters corresponding toattributes

theinheritedwhich are necessary to evaluate s, T is an derivation

tree and v is a parameter which corresponds to s. Thus parameters
to the left (right) of ' ; ' are input
procedureR

is(output). parameters.

intended to evaluate the synthsized attribute s

when supplied with the values of attributes which
for

the

evaluation

of

s

of

the

initialsymbolarenecessaryand a derivation tree T. When we are

given the initial derivatin tree T0 and a
s0

This

S,

we

executing the procedure call statement- 36 -

begin

synthesized

attributeevaluationof s0 bycall Rl (T0;V9),•

where V0isavariable· . corresponding

to

s0.

The

execution

proceeds,

recursively caliing the procedures which are necessary

to evaluate sunthesized attributes, until the desired value · V0 is
compu ted.
Attri.bute grammar .systems, as well as CSP , can be considered
useful means of description of algorithms. Thus,
Katayama~smethodandthemotivationsofmethod presented in this thesis arequite similar. Since an attiibute grammar is an augmented form ofa context · free grammar, there are ' st~ong relations among
by

means

of

symbols

production rules of the grammar, and usually thosegrammers contain recursiveness by nature. Thus, it is natural.. evaluate

theyaluesoftheattributes by

Among processes~ctiv·ating

generaltomut~ally

recursiveprocedur~.

however,

no . such relation can be found. Hence, ·the method ·taken

~f

CSP

·programs,by Katayama can not be applied to CSP programs dir.ectly.

8.2 Comparison with Habermann and Nassi's Method
The Habermann-Nassi Method for efficient
Ada

tasks

is

implementationofa method which tran sfo rms the calls of entries bytasks into simple procedure calls.

Itsoutlineisasfollows[7·7-]. 'Intheir method, each task with entries is transformed
into
<·.

a procedure andprocedure.

each

However,

entry

is

embedded

as

a

block

of

the

it is not sufficient to replace .the body ofan entry by the body of a corresponding procedure, since inthatcase demands from other tasks which originally have to,- be delayed
willsucceed

each

entry

at once . To avo id this error, we prepa~e lock s forandcontrol

them

as

-

37 -

if

the

cont~ol· proceedssequentially(coroutine

like

way)

through the task. We show ansimple example which is adopted from [77], where four

semaphores

are introduced to control the execution.
Sl :::: 1;
S2,S3 := @;task body T is
begin
loop
accept ·El do- 1 end E.l ;accept E2 do- 2 end E2;
accept E3 do
-

S(:J

:= 0;

P(SCil);

El: P(Sl);- lV(S2);

return;''E2: P (S2);.- 2 - .
V (.S3) i

return;3 E3:

end E3;end loop;
end T;

P(S3};- 3 V (Sl);return;After Transformation

Before Transformation
The · mechanisms

in

Ada arestrongly .in.f.ltienced by CSP, however, the roles of tasks

involvedinar .endezvous

of

ar.e

rendezvous

is

no

two

tasks

not symmetric; a task calls and the oth_el;

task ~ccepts the request
There

of

wh~n

it reaches

anappropriate

entry.

need to write explicitly tbe name of the task withwhich an entry is concerned. These phenomena
statedabove

effective.

applieddirectly, · sinceenablethemethodAs for CSP, the same method can not be
there

is

no

caller-callee

relation

between any two processes.

8.3 Comparison with Hagino's Method
In[28] ,Haginocompletelychangessequential programs, i.e. there is only#transformation.

The

transfo!mation

routineproceeds

in

GJ (<command list>)- 38 -

programs

one

below, where(<command list>}

CSP

after

into
the

the way shown·.

denotes the result of the transformation.
A CSP program[P:: x:=l; Q!x; Q?x
Q:: P?y; y:=y+2; P!ywill be transformed in the .following way.
(x:=l; Q!x; Q?x) <±) (P?y; y: =y+2; P! y)=1 ; (Q 1·X i Q?x) @ (P?y; y:=y+2; P!y)x:=l; y:=x; (Q?x) ffi (y:=y+2; P!y)x:=l; y:=x; y:=y+l; (Q?x) ® (P!y)
x:=l; y:=x; y_: ~y+l; ..X! ·:c:y .•X:This method of trnsformation is proposedforverificationsof CSP porgrams and the eff i ·c iency of transfo-rmation -is of 1 i ttle
concern.

In

fact,

the

procedures

h~ve

to

be

complicated and the meanings of the result of the .

executedaretransforma.t:lon

is almost impossible to_ understansL On the other hand, the method
takeri in thfs £hesis preserves ·the structure of the processes and
the

rules

of

transformation

executable.

39

are

simpleand · efficiently

9. Conclusion
As a way to solve the probl~mpr o cesses

of

CSP,

three

of

effectivea~goiithms

and

can

be

appliedefficient , the othertwo

restrictedofclassestQoffor transformation of CSP

programs into corouti ne s are presented; The
simplesc hedu ling

generalalgorithms

can

first

.

algorithm

isCSP

programs but not

only

be

appliedto

CSP programs but mo~e efficient than thefirst one .
Comparisonspresented.

The

with

th r-eemethodtaken in this thesis has sim ilarity witheach of those works, but
applieddirectly

to

·t he

other:·

methods

r-ela·tedofproblemprocesses of CSP .

..

- 40 -

those
of

works

works

efficient

are

can

also

not

be

scheduling of.·Acknowledgement
The author wishes. to thank Prof. T. Tokuda for hi s · kindandhelpful

advice and ehcouragements , and al so , · wishes to thank themembersofthe. fac~ltyo~Prof. M. Arisawa,

Mr. M.

Iuchi

Yamanashi

includingand Prof. T. Yoshizawa for theiradvice and encouragements.

·.

-

University

41 -References[1] Apt, K.R_. et al.:Sequential

Proof

"A

Processes,"

Systemfor

Communicating

ACM Trans. on Prog. Lang. and Sys .,Vol. 2, No. 3 (Jul. 1980), pp. 359-385.

(2] Arsac, I. et al. : "Some Techniques for Recursion Removal for
Recursi~e Function~,"

ACM Trans. on Prog.

Lang.

and

Sys.,

Vol. 4, No. · 2 (Apr. 1982), pp.295-322.
['3] ·Ashcroft,

E. A • . et al.:"Lucid, a Nonprocedural Language with

Iteration," .. Comm. ACM,

Vol.

20,

No.

7

(Jul. 1977), pp.

GuardsandNondeterminism

519-5 26 .
[4] Bernstein, A.J.:
Communicating"Output

Sequential

Processes,"198~),

Lang. and Sys., Vol. 2, No. 2 (Apr.
[ 5 J Bezi ~in , J. et al.:"Another

View"NotesRee~,usion

onofTrans. on Prog.
pp. 234-238.

Co.routines,"(May. 1978), pp.

SIGPLAN Notices, Vol. 13,, No.5
[61 Bird, R.S.:

ACM

in

ACM

23-25.

-Elimination," Comm. ACM,

Vol. 20, No. 6 (Jun. 1977), pp. 434-439.
[7]

Birtw~stle,(8}

Clarke, E.M.:
History

G.M. et al.: SIMULA BEGIN, . Lund, 1981.
"Proving

Variables,"Correctness . ofCoroutines

Informatica,

Acta

No. 13

Without(1980), pp.

169-188.
(9] Clint, M.:"Program Proving: Coroutines," Acta

Informatica,

No . 2 ( 19 7 3 ) , pp • 50....: 6 3 •Programming(10] Clocksin, W.F. et al.:inprolog,Springer-Transition

Diagramverl ag , 1981:.
(11] Conway, M.E.:
Compiler, 11"DesignComm . ACM,

. of

a

Vol.

Separable
6·,122 -134.

-

42 -

No.

7

(Jul.

1963),

pp.

..
)
·-

o. J. et al.: Structured Programm ing ,[ 12} Dahl,·.

Academic · Press,

1972 .

[ 13) Di j kstr a, E . w. et al.:11

Goto Statement Cons ide red Harmful,"Comm. ACM, Vol. 11 , No.5 (Mar. 1968), pp. 14.7-148 .
[14)

Di j kstra, E. ~1.: "Guarded Commands, Nondete rmi nacy and· Formal
Derivation of Pr.o grams ," . Corom . ACM, Vol.

1975), pp.

I

8

A Discipline of Pro9 rammi nq, Prentice-Hall.,•.[16] Dijkstra, E.W. et a1. : "Termination Detection for
Computations,"
1

{Aug.

453-4~7.

[15] Dijkstra, E.W.:
19,7 6

No.

18,

Informat ion Processing

Le tter~,

DiffusingVol. 11, No.

(Aug. 1980), pp. 1-4.

[17] Doi, N. : "Pr ocesses and Their Syn c hronization - Rendezvous ,".J2.if, Vol .

14_, No . .,4 - 7 (19.82).

[18] Floyd , R.W.:

N0 • 4

11

Nondetermini stic A1gorithll\S, 11 J. ACM, Vol. 14 ·,( 0 c t . 19 6 7 ) , pp

6 3 6 -6 4 4 ;I(19) Francez, N.: "Distributed Termination," ACM Trans. on

Prog.

Lang. and Sys., Vol . 2, No.1 (Jan. 1980), pp. 42-55.
[20] Furuk awa , K. et al .:"Onof Prol og Coroutine

Veri ficati o n

Interpreter," Proc. of 1st Meeting of WGSF of IPS J , 1992 .

(21] Furuya, T.: "Concurrent Programming by High Level . Language ,"Joh o-sho ri, Vo l. 21, No. 9 (Sep . 1980}, pp.949-958.
[22] Gentleman, W.M .:"A Portable Coroutine Sys tem,"

Information

Processing 71, pp . 419 - 424, North- Holland Publishing Company(1972).
[23]

Gries, D.:" SomeIdeas

Languages,"

Comm. ACM,

on

Vol.

414-420.

-

43 -

Data
20,

Types

No.6

in

(Jun .

High-Level
1977),

pp.

(24} Gri es , D. {Ed . ):A~ticles[25]

G~ies,

Programming

Methodo logy,

A

Col lect ion of

by members of IFIP WG 2 . 3 , Springer-Verlag, 1978 .

D.:

The

ScienceofProgramming,

Springer-Verlag,

1981.
[ 26) Griswold, R. E; et al.:"Genera·tors in Icon," ACM Trans. on

Prog. Lang. and Sys., Vol . ·3, No . 2 (Apr. 1981}, pp. 1[ 27]

Gi.•une·, .D • .: "A View of Co routines," ACM SIGPLAN Not ices 1 Vol .

[ 28] Hag in o , T. :of

"V.erific.a ti on·Communicating

S-equential

Processes , " Proc. of 2nd Meeting of WGSF of IPSJ, 19 82 .
[29) Hansen, P.B .:IEEE

Tran~ .

"The Programming Language Concurrent Pas cal, "on Soft. Eng., Vol . SE- 1,

199-207.
{ 313]

2 (Jun. 1975}, pp.

'.

Hansen, P .B. :Programming~o.

Processes:
Conc ept, 11

Concurrent

A

Comrn. ACM,

Vol .

21,

"The

ProcedureNo.

11 (Nov .

19 7 8 ) I PP • 9 3 4 - 9 41 •[ 31 ] Hansen, D.R. et a1 . :SLSMechanism,"

C'omm. ACM 1 Vol. 21, No . 5 {May. 197 8) , pp. 39 2-4 00.
[32] Harary, F.: Graph Theo ry , Addison -Wes ley, 1969 .
{3 3 ] Harberrnann, A.N . et al.:Tasks.'", Dept. of"Efficient

Implementationof AdaScience,

Carnegie- MeLlon
:

Univ.

Comput_er~.

(1980).
(34] Hebner, E.C.R.:"do

Co nsidered

Programming Calculus ," Actaod:'
A Contribution
to theInformati~a~Vol. 11 (1979), pp.

287-31:J4 .
( 35 ] Henderson , P . :..;.F_u_n_c_t_io_n_a_l_ _P_r_o...:;g_r_a_m_m_l_·n_g~_...;;.A;.o.P....,P_l..;..l;;...c..;.....;.;.
a~t..:;
i....;;
o....;.n.;...__a_n _dImplementation, Pre ntice-Hal l International, 1989.

- 44 -

[36} Hewitt, C.E. et al.:"Towardsa

Programming

Apprentice,"

IEEE trans. on Soft. Eng., Vol. SE-1, No . . 1 ("Mar. 1975), pp.
26-45.
"Inti:oduction[37] Hikita, T. et al.:

to

Ada,"

NikkeitoComputerElectronics, Dec. 21 · "(1981), pp. 130-162.
{38]

11

Hoai:e, C.A.R.:

An

Axiomatic

Approach

Programming," Comm. ACM, Vol. 12,'.No. 10(Oct;.

1969),

pp .

576-5801 583 •11[39} Hoare, C.A.R.:

Proof

of

Cor_rectness

of

Data

Represen-tations," Acta Informatica, Vol. 1 (1972) , pp. 271-281.
[40] Hoare, C.A.R.:
Concept,""Monitor$ : An

Comm. ACM,

·Vol.

Operating

17,"Communicating[411 Hoare, C.A.R.:

No.

System

Structuring(Oct.

1974), pp.

10

Sequential

Processes,"Colnm. ACM, Vol. 21, No.8 (Aug. 1978}, pp. 666-.677.
(42} Jacobsen, T;:"Another

Notices, Vol. 13, No.4·[43} Kahn, G. et al . :

View

of

Co~outines ,"ACM SIGPLAN(Apr. 1978}, pp. 68-75.

"Coroutines

andNetworksof

Pa rallel

Proc~sses, 11 Information Processing 77, North Holland {1977),

pp. 993-998.
"Translati on[44] Katayama, T.:
Procedures 1 "Tech. Rep.

of

CS-K8001

Attribute{198 0) ,Grammar-into:oept.

of

Camp.

and

Functional_Sci., Tokyo Inst. of Tech.
[45] Katayama, T.:

"HFP:

A

Hierarchical

Programming Based on Attribute Grammar," Proc. ·of

5th

Int .

conf. on so ft. Eng., 1981.
[46} Kieburtz, R.B.:"CommentsonCommunicating

Sequential

Processes," ACM Trans. on Prog. Lang. and sys., Vol. 1,2 (Oct. 1979) I pp. 21a-225.
- 45 -

No.

(471 Kimura,I.

et al.:

Theoryof

Expressionsof

Algorithms,

Iwanami, 1982.
[481

Knuth, D.E.: "Semantics of c;ontext
Syst.

Theory,J.2(1968) ,Free

Languag-es,"Math.

pp . 127-145 , Correction, Math.

Syst . Theory, J.S (1971), ppL 95-96.
[49] Knuth, D.E.:

A~t

The

of

Computer - Programmini,

Vol.

1,

Addison Wesley, 1969.
[50] Levin, G.M. et al.:

"A

Pioot

Technique,,for Communicating

Sequential Processes, ·" Acta tnformatica, Vol. 15 {1981), pp .
281-302 .
[51} Lewis, B:"Fu rther Comments on 'A View of Coroutines ' ,"ACM

SIGPLAN Notices, Vol. 13 , No . 7 (Jul. 1978), pp. 31-33.
[52] Lindstrow, G.:. Structured.

"Referencing

Corou~ines,"

andRetention

ACM Trans . on Prog .

Lang ~

in

Block-

and

Sys.,

"

Vol. 3, No. 3 (Jul.
[53] Lindstrow,G~:

Setting,"

ACM

19~_ 1),

pp .

263-292.

"Backtracking

inaGeneralized

Control

Trans. on Prog. Lang. and Sys., Vol. 2, No.

1(Jul. 1979) , pp. 8-26.
[54]

Liskov, B.H. et al.:"Specificati o n

Techniquesfor

Abstractions," IEEE Trans. on Soft. Eng., Vol. SE - 1,
(Mar. 1975), _pp. 7-:19.
·. :[551 Liskov, B.H. et al. :"Abstraction

Mechanisms

in.

Data
No .

1

CLU,"

Comm. ACM, Vol. 20, · No.. 8 (Aug. 1977), pp . 564-576 .
(561

Liskov, B.H. et al.: CLO Reference Manual, Lecture Notes

incomputer Science 114 I ·springer-verlag, 1981 . .
(571

Lynning, E. :"Letter

to editor," AC M SIGPLAN Notices, Vol .

13, No. 2 {Feb. 1978) 1 pp. 12-14.

·.

- 46 -

[58) Marlin, C. D.:
editor) ,""Coroutines·· a nd Return

ACM

Addresses(Letterto

SIGPLAN ·No tices, Vo l. 13 , No . 9 (Sep . 1978),pp. 19 - 20.
(59) Marlin, C.·D.: Coroutines, Lecture Not es in Computer

95,

Springer-verl~g,

computation s inTrans.

on19a~.

"Termination[60] Misra, J . et al.:ScienceCommunicating

Detection
Sequ~ntialofDiffusi ng

Proce'sses,"

Prog. Lang. and Sys. , V9l. 4, No . 1

ACM(Jan. 1982),

p.p. 37 - 43 •. [ 61) Musha, H. et al.:11

Co-ro·uti·ne Ra·tfor - ·Its .I-rnp1:ementati6n andosage, " Proc . of 24th Conf . · of IPSJ, pp . 229 - 230 , 1982.
[62] Nakata, I .:paper

" Prog ramming with Streams of Data, "unpublished(1982) •[63] Noel, J.G.:" Lettertoeditor," ACM SIGPLAN Notices , Vol.

12, No; 12 (Dec ; 197 7} , p . 23 .

[64] Pauli,w. et a1. :

.

'

11

Coroutine Behaviour and..:;:S~o:.::f:..:t::.:w:.;a::..r::..=.e_-.=,
P..-::r~a::.:;c::..;t:::.;l:..'c=e---::a::.:n:;.;.d;:;.._....::;:E.:.:x;.~;p:;.;::e:.or;.;i:.;e:;.p;;,;.c.;;;.;:.
e,

Vo 1 •

Implementation,"10( 19 8 !3 ) ,pp .

189-2"~·[ 6 5 ) Pratt, T.. W. :Programming

Languages:

Designandrmelementation , Prentice- Hall Inc ., 1975.
[66) Ritchie, D~M . et al.:" T.heUNIX

Time-sharing . system, ..

-Conun. ACM, Vol . 17, No. 7 {Jul . 1974), pp. 365 - 375.
{67) Roper, T.J. et al .:Languageand"A

Communicating

Implementation, "Sequential

Process

Software -PracticeandExperience, Vol. 11 (1981), pp . 1215-1234.
(68}

sassa, M. et al .:Implernen tat ion,""Stream
Proc.

Functions

and

Their

of 23 rd Conf. of IPSJ, pp. 17 5-17 6 ,1981.

- 47 -

-··-:·.

(69] sassa,

M.

et al.: "Programming with

Streams,~'-P roc. of

25th

Conf. of IPSJ, pp. 257-258, 1982.•[70] .Sahara, M.

et al.:''ImplementationofStream Functions bycoroutines," .Proc. of 24th .conf. of IPSJ, pp. 227-228, 1982.
·[71] Schneider, F.B.:

ACM

Trans.

on"Synchronization in Distributed
Prog.

Programs,"

and Sys.l Vol, 4, No. 2 (Apr.

Lang.

1982), pp. 125-148.
[72] Shaw, · M. et al.:Defining

and

11

Abstraction and Verification

Specifying

IterationinAlphand:-and . Generators,"

Comm. ACM, Vol. 20, No. 8. (Aug. 1977), pp. 553-564.
[73) Skordalakis, E. et al.: "Coroutines in Fortran," ACM SIGPLAN
Not ices, Vol. 13, No ~ 9 (Sep. 1978) , PP .· 76-84.

[74) Staunstrup, J:
Procedure"Message

Passing

Communication

communication,"

Call

VersusSoftwa.re-Practice -.

andExperience, Vol . ·1 2 (1982), pp. 223-234 •.
[75] Stevens, W.P.:

"How

Data

Fl0\-1Can

I _m prove

Application

Development Productivity, .. IBM Systems Journal, Vol. 21, No.
2( 19 8 2 ) , pp • 16 2-1 7 8 .

( 76] Togawa, H. :"Introduction

to S irnula 1 " .l2i.J;., Vol. ll, No. 8,

pp. 28-34, No. 9, pp. 42-49, No. 10, pp. 92-97 {1979) .
[77] Tokuda, T.:"Noteson

Ada

Implementability

Issues.,"Joho-Shori, Vol. 21, No.3 (Mar. 1980), pp. 226-232 •. [78)

u.s. DoD: Reference

Manualfor

Ada

Programming Language,

19813.

•[79) Vanek, Z.I. et al.:for

"Hierar chicalCoroutines:

A . Mechanism

Imprqved Program Structure, 11 Proc. of 4th Int. Conf. on

Soft. Eng., pp. 274-285, 1979.

[80) wang, A. et al.: "Coroutine Sequence in aBlack

Environment 1 11 BIT, Vol. 11 ( 1971) , pp • . 425-44 9.
- 48 -

Structured

..
[81]

Wa~d,

S.A. et ' al.:"A Syntactic Theory . of Message Passing,"

J. · ACM, Vol. 27, . No. 2•[82] Wirth, N.:

Algorithm

(Ap~.

+

1980), pp. 365-383 •

Data

=

Structures

Programs,--~------------------------------------------~-----

Prentice -Hall, 1976.
[831 Yamamoto, K.:"SIMULA,".J oho-Shori,Vol.

22, No.6(Jun .

1981), pp. 477-482.
[84) Yamano, K. et al.:

11

Applicative Communic·a tion

Functionfor

Parallel Programming," Proc, of 3rd Meeting of WGSF of IPSJ,
1982.
(85) Yonezawa, A.:"A Tutorial on ACTOR Theory , 11 Joho-shori, Vol.

2 ~ , N0 • 7 ( J u 1 • 19 7 9 ) I[86] Yoardon, E. et al.:DisciplineofPP. 58 0- 58 9 •Structured

Computer .

Design:ProgramandFundamentals
systemsof a

Design,Prentice-Hall · Inc., · 1979 .

•[87] Yuasa, T. et al.:"Programming.Environment

Programming," Joho-Shor:i, Vol. 23, No.5
433-441.

- 49 -·(May.

forModular1982),

pp.

-,