-Calculus Semantics for. the Concurrent Conguration Language Darwin. Department of Computing. Imperial College of Science, Technology and Medicine

Please download to get full document.

View again

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Philosophy

Published:

Views: 0 | Pages: 7

Extension: PDF | Download: 0

Share
Related documents
Description
Calculus Semantics or the Concurrent Conuration Lanuae Darwin Susan Eisenbach Ross Paterson Department o Computin Imperial Collee o Science, Technoloy and Medicine London SW7 2BZ, United Kindom Abstract
Transcript
Calculus Semantics or the Concurrent Conuration Lanuae Darwin Susan Eisenbach Ross Paterson Department o Computin Imperial Collee o Science, Technoloy and Medicine London SW7 2BZ, United Kindom Abstract Darwin is a conuration lanuae or distributed and parallel prorams, providin a hierarchical structure o components with dynamic bindin. In order to speciy precisely the behaviour o Darwin prorams, we sketch a translation o the eatures o the lanuae into the calculus, a ormalism or modellin concurrent processes. The match between underlyin models or Darwin and calculus is ood. Examples done in the calculus are clean abstractions o the same solutions in other concurrent lanuaes. 1 Introduction Without a ormal specication a lanuae is dened by its compiler and even with the best intentions several compilers or a lanuae will lead to several variants. For any concurrent lanuae desined to be implemented on very dierent architectures and the importance o a ormal lanuae specication becomes paramount. A ood specication lanuae is one that enables a clear simple specication to be written. This is most likely i the underlyin model that the specication lanuae supports matches that o the prorammin lanuae. Darwin [4, 7] is a prorammin lanuae or the con uration o prorams across processors; ports can be linked to each other; messaes are explicitly sent and received at ports. Implementations exist or parallel and distributed systems. An important characteristic o Darwin is that it supports mobile processes by makin the addresses o ports rst class objects. This enables systems to be conured dynamically. Darwin is a lanuae[12] that rew out o Conic which has been used in lare scale industrial problems[6]. Several lanuaes such as CSP and CCS that have been devised to speciy communicatin computational To appear in Hawaii International Conerence on System Sciences, Koloa, Hawaii, January systems. These lanuaes should be suitable or speciyin concurrent prorammin lanuaes[9]. However, the modellin o mobile processes is not straihtorward usin these lanuaes. Milner's recent system the calculus [11, 10] is desined to model concurrent computation consistin o processes which interact and whose conuration is chanin. It does this by viewin a system as a collection o independent processes which may share communication links with other processes. Links have names. These names (or addresses) are the undamental buildin blocks o the calculus. Darwin's port addresses are like these names, helpin to make the calculus a ood system or describin Darwin. To date thouh both the examples undertaken in the calculus and the lanuaes specied in it have not been substantial[14]. So bein able to dene Darwin in calculus is also a demonstration that the calculus has the expressive power required or solvin real problems. In this paper brie descriptions o Darwin and the calculus are iven. An example to demonstrate each lanuae is developed. This is ollowed by a ormal semantics o Darwin in the calculus. The paper concludes with a discussion o the value o speciyin a concurrent conuration lanuae and what miht be deducible about the behaviour o Darwin prorams. 2 Darwin The Darwin lanuae[4, 8, 7] is intended or the description o both static and dynamic conurations o processes. Components may be written in any lanuae, or in Darwin itsel; the existin implementation supports C, C++, Modula2 and MPP (a messae passin Pascal[5]). A rammar o Darwin is iven in ure 1. The basic unit o Darwin is a process. The interace o a process with its environment is a vector o names that are provided by the process, and another vec proram = component component = component id(parameters) : instancetype body body = decl action j primitivecomponent type = instancetype j componenttype j array [num 1 ::num 2 ] o type j primitivetype instancetype = [ require decl ; provide decl ] componenttype = component (parameters) instancetype decl = id : type action = inst instanceid := componentid(aruments) j bind servicename 1 servicename 2 j when expr action j orall id : expr 1.. expr 2 action servicename = id j instanceid:id Fiure 1: A rammar or Darwin tor o names that are required by the process. These names may be o any type, dependin on the underlyin lanuae, but in the examples used here they will reer to communication ports. Both kinds o name may be reerred to in the proram denin the process. In a primitive process, written in the underlyin lanuae, the provided names are supplied with values, while required names are unresolved reerences. Any reerence to an undened name by a process will cause the process to block until a value is assined. To illustrate the lanuae, consider a model o a roup practice o doctors[8]. There are three kinds o primitive process, coded in some implementation lanuae, namely doctors, a receptionist, and patients. The receptionist provides communication channels to talk to doctors and patients, each o which require correspondin channels. The interace types o these primitive components are thereore as ollows: Recept = [provide doc : port (A ), pat : port (B )] Doctor = [require next : port (A )] Patient = [require talk : port (B )] Primitive components o these types may be declared as ollows: component receptionist : Recept ; component doctor (did : name ): Doctor ; component patient (pid : name ): Patient ; Processes may also be written in Darwin. Such a process may create instances o other processes, whether written in Darwin or the underlyin lanuae. The core statement o Darwin is bind id 1.requirement id 2.provision which assins the provided value o one instance to the required name o another. The bind statement may also reer to the provisions and requirements o the process bein dened. The ollowin combinations are permitted: bind provision instance.provision bind instance.requirement requirement bind provision requirement However, no variable may be bound twice. In Darwin, all actions may be perormed concurrently. Thus the name on the riht side may not have a value when the bind statement is perormed. The semantics must be dened in such a way that the order in which the bindins are perormed is immaterial. Continuin with our roup practice example, we can rst dene a component to enerate the patients, and another to set up the doctors' surery: Practice Surery Patients doc 1 dnext talk d t doc recep. t pat t door do doc n??? d next J JJ J d talk pat n Fiure 2: Darwin example: a roup medical practice component patients (npat : int ): [require o : port (B )] i : int ; pat : array[1..npat] o Patient ; orall i : 1..npat inst pat [i ]: patient (i ); bind pat [i ].talk o ; component surery (ndoc : int ): [provide door : port (A )] i : int r : Recept ; doc : array[1..ndoc ] o Doctor ; inst r := receptionist ; bind door r.pat ; orall i : 1..ndoc inst doc [i ] := doctor (i ); bind doc [i ].next r.doc ; Finally, these subcomponents are connected toether to orm the whole: component practice (ndoc, npat : int ) inst s := surery (ndoc ); inst p := patients (npat ); bind p.o s.door ; 3 The calculus The calculus is an elementary calculus or describin and analysin concurrent systems with evolvin communications structure[11, 14, 10]. A system is a collection o independent processes which may be linked to other processes. Links have names; the name is the most primitive entity in the calculus; names have no structure. There are an innite number o names, represented usin lowercase letters. Processes e.. P; Q; R : : : are built rom names as ollows: the parallel process P j Q will execute both concurrently. The operation is commutative and associative. the replication!p provides any number o copies o P. It satises the equation!p = P j!p Recursion can be recoded as replication and so need not be explicitly included as a separate receptionist(next; talk) = talk(n; ill; reply): next(answer):answer(n; ill; reply): receptionist(next; talk) doctor(next) = ( answer) next(answer):answer(n; ill; reply): reply(dianose(ill)): doctor(next) patient(n; talk) = ( reply) talk(n; rand(); reply): reply(prescription):0 Fiure 3: The roup practice processes in the calculus method or buildin processes. Recursion will be used when it makes examples clearer. ( y)p introduces a new name y with scope P. As usual, all ree occurrences o y in P are bound by the quantier, and can be uniormly renamed to any new name without chanin the value o the process. The quantier also satises the axioms ( x)( y)p = ( y)( x)p provided x and y are distinct names, and (( x)p ) j Q = ( x)(p j Q) provided x does not occur ree in Q. A communicatin process C. Communicatin processes C are o the ollowin kinds: the sum C 1 + C 2 will execute either C 1 or C 2. The operation is commutative and associative. x(y 1 ; : : : ; y n ):P means output the names y 1 ; : : : ; y n alon the link x and then execute P. x(z 1 ; : : : ; z n ):P receives names y 1 ; : : : ; y n alon x and then executes P with y i substituted or each ree occurrence o z i in P. 0 stops. It is an identity or both j and +. As well as bein able to dene processes the calculus denes a reduction relation between relations, written P! P 0, or process expressions P and P 0. There is only one reduction axiom, called comm: ( + x(y 1 ; : : :; y n ):P ) j ( + x(z 1 ; : : : ; z n ):Q )! P z 1 =y 1 ; : : : ; z n =y n j Q Subprocesses under j and, but not replication or communication, may also be reduced in this way. For example, we can express the processes o our roup practice example in this calculus, as in ure 3. The intended semantics is as ollows. Patients arrive at the practice and talk to the receptionist. They tell her their name and their illness. Doctors who are capable o receivin patients inorm the receptionist o their availability. The receptionist inorms the available doctors o the names and illness o their perspective patients. The patient is iven a prescription by the doctor. Ater a prescription is iven, the patient leaves and the doctor becomes capable o seein another patient. Note that the example proram assumes builtin unctions dianose and rand. 4 Translatin Darwin into the calculus In order to model Darwin, we shall need to add eatures to the calculus. However, this will will not make the lanuae any more powerul, since the eatures can be dened in the calculus itsel, and are thus mere abbreviations. 4.1 Asynchronous communication The rst eature is not required by Darwin itsel, but will be used by many o the concurrent lanuaes on which it is superimposed, namely asynchronous communication channels, in which messaes are queued. x 0 P x=x 0 x out n p v 1 n p v 2 n p v 3? in Fiure 4: A queue containin three elements The calculus uses synchronous communication, but can easily simulate queued streams. We dene ( Q x)p = ( x)( x 0 )(queue(x; x 0 ) j P x=x 0 ) A queued channel x is modelled by a pair o synchronous channels, with a queue process between them. The queue process contains an arbitrary number o element processes, each o which receives, holds and transmits a sinle value. At each stae, the queue consists o a number o active elements connected by channels as shown in ure 4. The rst element holds the output channel. When requested by the process P, it yields its value alon output channel, and then passes the output channel to the next element o the queue. The last element o the queue waits to receive a value rom the input channel. When that happens, it passes the input channel (and a connexion to itsel) to a new queue element, and waits until it receives the output channel, at which time it will be the head o the queue. Thus a queue element is dened as: element(q) = q(in; p):in(v):( n)q(in; n): p(out):out(v):n(out):0 Besides an indenite number o element processes, the queue process includes a small process to start the rst element: queue(x; x 0 ) 4.2 Data structures = ( q)(( n)q(x; n):n(x 0 ):0 j!element(q)) We shall also need to dene some data types in the calculus: Booleans, numbers and lists. The constructions are standard [10]. The values o these data types will be represented by port names. For example, Booleans are ports which expect a pair o ports and reply on one o them, thus permittin the implementation o conditionals. I a process P wishes to reer to the values true and alse, we wrap it as ollows: ( true)( alse)(p j!(true(x; y):x():0) j!(alse(x; y):y():0)) Now suppose b is a name bound to either true or alse. We dene i b then Q else R = ( t)( e)b(t; e): (t():q + e():r) Darwin's when construct is a special case. Natural numbers are iven a unary encodin, usin a similar scheme. For any number, one wants to know i it is zero or positive, and i the latter, what the precedin number is. Thus a number will be a port that expects to be passed two ports. I it is zero, it will respond on the rst port, just like true above. I it is positive, it will output its predecessor on the second port. That is, the successor o a number n is a port n 0 connected to a process!(n 0 (x; y):y(n):0) Finally, we need a port succ to supply such a port or each port n. The complete wrappin or P is ( zero)( succ) (P j!(zero(x; y):x():0) j!(succ(n; r):( n 0 )(r(n 0 ):0 j!(n 0 (x; y):y(n):0)))) Inside P, we can introduce a new value (port) n 0, to be the successor o n, with the sequence ( x)succ(n; x):x(n 0 ): As this construction shows, a unction is modelled in the calculus by passin a new port, down which the result will be sent. All the usual arithmetic unctions may be dened in the standard (but rather inecient) way 1. Darwin's orall construct may now be represented usin recursion and the conditional dened above. An instance can be represented by a tuple containin o the provide and require ports o the subcomponent. A tuple is represented by a port which outputs all the values at once. Lists are dened in the same way as numbers. A list is either empty, in which case there is nothin more to be said o it, or not, in which case it contains a head element and a tail list. Thus an empty list is just like true or zero above, and a nonempty list with head h and tail t is a port l connected to a process!(l(x; y):y(h; t):0) Thus the wrappin or P to provide lists is ( empty)( cons) (P j!(empty(x; y):x():0) j!(cons(h; t; r):( l)(r(l):0 j!(l(x; y):y(h; t):0)))) Arrays can be represented by lists. 4.3 Bindin We can simpliy the restrictions on bindin by roupin the externally visible names o a Darwin component into a special interace instance, in which the provisions o the component appear as requirements, and vice versa. Thus all bindins will be o the orm bind id 1.requirement id 2.provision A provision in a primitive process will contain a value v, and is represented by a port p connected to a process Provide(p; v) =!(p(a):a(v):0) This process receives addresses, represented in the calculus as ports that are to be read exactly once, and 1 Note that two successive applications o a unction like succ to the same arument n will ive two dierent ports, but we cannot compare them or equality; we can only compare their behaviours, and these are identical. sends them its value. The process is replicated since a value may be used several times. A requirement in a primitive process will contain an address a, and is represented by a port r connected to a process Require(r; a) = r(x):x(a):0 This process receives a provision port and sends its address to it. Since the requirement may only be bound once, the process is not replicated. The Darwin statement bind x y will be represented as x(y): Suppose we bind such a primitive requirement and provision: Provide(p; v) j Require(r; a) j r(p):0! Provide(p; v) j p(a):0! Provide(p; v) j a(v):0 So that the value v is sent to the address a. An unassined variable in a Darwin component has a pair o ports, r or receivin a sinle provision, and p or receivin any number o addresses. One o these will be visible outside the component, and the other in the special interace instance, dependin on whether the variable is provided or required. The ports are served by the ollowin process Variable(p; r) = r(x):!(p(a):x(a):0) I we bind such a variable to a requirement, we have Variable(p; r) j Require(r 0 ; a) j r 0 (p):0! Variable(p; r) j p(a):0 Ater several such assinments, an unassined variable carries a collection o addresses requirin values: Variable(p; r) j p(a 1 ):0 j j p(a n ):0 I such a variable is bound to a similar variable, its set o addresses is passed on: Variable(p; r) j p(a 1 ):0 j j p(a n ):0 j Variable(p 0 ; r 0 ) j p 0 (a 0 1):0 j j p 0 (a 0 n):0 j r 0 (p):0! Variable(p; r) j p(a 1 ):0 j j p(a n ):0 j!(p 0 (a):p(a):0) j p 0 (a 0 1 ):0 j j p0 (a 0 n):0! Variable(p; r) j p(a 1 ):0 j j p(a n ):0 j!(p 0 (a):p(a):0) j p(a 0 1):0 j j p(a 0 n):0 The residual process!(p 0 (a):p(a):0) passes on any subsequent bindins to the variable. I such a variable is bound to a provision, the value will be sent to each address: Variable(p; r) j p(a 1 ):0 j j p(a n ):0 j Provide(p 0 ; v) j r(p 0 ):!!(p(a):p 0 (a):0) j p(a 1 ):0 j j p(a n ):0 j Provide(p 0 ; v)!!(p(a):p 0 (a):0) j p 0 (a 1 ):0 j j p 0 (a n ):0 j Provide(p 0 ; v)!!(p(a):p 0 (a):0) j a 1 (v):0 j j a n (v):0 j Provide(p 0 ; v) The residual process!(p(a):p 0 (a):0) j Provide(p 0 ; v) has the same communication behaviour as Provide(p; v) j Provide(p 0 ; v) That is, any address sent to either p or p 0 will be send the value v. 5 Conclusions This paper has presented a ormal semantics in the calculus or the conuration lanuae Darwin. The calculus is a new ormalism. It is simple and eleant. There were no major problems that had to be worked around in order to write the Darwin denition. The least natural part was the denition o basic data types[10]. As these are not an interestin part o a conuration lanuae this is not a serious ect. This demonstrates that the calculus is as powerul as a practical lanuae or solvin parallel or distributed conuration problems. The semantics provided by the calculus denition should be compared with existin semantics or Darwinlike lanuaes such as those in [3, 13]. The underlin model o the calculus, where communication is primarily about exchanin names which then may be used or urther communication, is very similar to the Darwin notion o a service. This leads to a substantially shorted denition then others have produced. More importantly, it makes the calculus an ideal lanuae or speciyin Darwin prorams. This should help Darwin prorammers to ain a reater understandin o what behaviour their prorams will exhibit. Reerences [1] D. Andrews. The Vienna development method. In D. Ince and D. Andrews, editors, The Sotware Lie Cycle, paes 221{259. Butterworths, [2] D. Andrews and W. Henhapl. Pascal. In D. Bjorner and C. Jones, editors, Formal Specication and Sotware Development, paes 175{252. Prentice Hall, [3] S. C. Cheun. Darwin in Z. Technical Report REXWP5ICST040V1.0, REX, March [4] N. Dulay. The Darwin conuration lanuae. Imperial Collee Department o Computin Internal Report, March [5] N. Dulay and J. Maee. MPP: Messae passin Pascal. Imperial Collee Department o Computin Internal Report, April [6] J. Kramer J. Maee and M. Sloman. Constructin distributed prorams in CONIC. IEEE Transactions on Sotware Enineerin, 15:663{375, [7] J. Kramer, J. Maee, M.S. Sloman, and N. Dulay. Conurin object based distributed prorams in REX. IEEE Sotware Enineerin Journal, March [8] J. Maee, N. Dulay, and J. Kramer. Structurin parallel and distributed prorams. In Proceedins o the IEEE International Workshop on Conurin Distributed Systems, March [9] R. Milner. Communication and Concurrency. Prentice Hall, [10] R. Milner. The polyadic calculus: A tutorial. Technical Report ECSLFCS 91180, University o Edinburh, October [11] R. Milner, J. Parrow, and D. Walker. A calculus o mobile processes. Technical Report ECSLFCS 91, University o Edinburh, [12] M. Peltu. Out o the scullery. Computin, May [13] M.D. Rice and S.B. Seidman. A ormal model or module interconnection lanuaes. Auburn University Internal Report, [14] D. Walker. calculus semantics o objectoriented prorammin lanuaes.
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks