[Edited from writeNow (?) style text format -- with some gibberish characters and probably incomplete at the end] Th1.4: The telephone as a Case Study in Animating an LSD Specification The LSD notation was originally developed by Beynon in collaboration with Mark Norris of BTRL. The application of definitive principles to concurrent systems modelling and parallel programming was the theme of Mike Slade's MSc thesis (1989), on which these notes are based. (The LSD specification has been revised to take account of new conventions.) In this section we write an LSD specification to model the behaviour of a simple telephone system. We then consider the issues of synchronisation and interaction between agents which arise from the specification. Using appropriate transformation techniques we convert the LSD specification into a definitive program for the adm. The parameters of the transformation are identified, so that the transformation gives a family of programs. The purpose of this chapter is to illustrate how our method for transforming a model of a system described by an LSD specification into an executable program allows simulaton of the behaviour of the system. Th1.4.1. Telephone specification In Listing 1 we give a specification for a simple telephone system. The telephone specification is based on one given in [Beynon 86]. The use of parameters makes the specification extensible to a multi-user, multi-telephone system. We consider a user U and a source telephone S. The user may attempt to telephone a destination telephone D. Other users may connect to telephone S. When a user picks up the receiver of a telephone which is not ringing a dial() agent is instantiated. If the user dials a number a connect() agent is instantiated by the dial() agent, and the dial() agent is deleted. The connect() agent is extant for the duration of the call. Once the connection is made connected becomes true and the telephone starts ringing. If the line is engaged, the connect() agent is deleted. agent user(U,S) { oracle (int) tone[S], (bool) ringing[S] handle (bool) onhook[S], (int) dialled_number[S] protocol Âonhook[S] ® onhook[S]= true ; dialled_number[S]=@, Âonhook[S] Ù (tone[S] == D) ® dialled_number[S]=N, Âonhook[S] Ù (tone[S] == C) ® , onhook[S] Ù Âringing[S] ® onhook[S] = false ; dial(S), onhook[S] Ù ringing[S] ® onhook[S] = false ; } agent telephone(S) { oracle (bool) onhook[S], connecting[S,*], dialling[S], (int) dialled_number[S], (bool) connected[S,*], engaged[S,*] state (bool) onhook[S] = true, (int) dialled_number[S], (bool) connecting[S,*] = false, (bool) dialling[S] = false, (char) tone[S] derivate (char) tone[S] = D if dialling[S]: E if connecting[S, dialled_number[S]] Ù engaged[S, dialled_number[S]]: R if connecting[S, dialled_number[S]] Ù Âengaged[S, dialled_number[S]]: C if connected[S,?] Ú connected[?,S]: @ otherwise } agent exchange() { oracle (bool) onhook[*], connected[*,*], connecting[*,*], answered[*] state (bool) onhook[*], connected[*,*] = false, answered[*] = false (bool) ringing[*], engaged[S,*] , (time) Tdial , Tcall derivate (bool) ringing[*] = connected[?,*] Ù onhook[*] Ù Âanswered[*], (bool) engaged[S,*] = connecting[S,*] Ù (ringing[*]Ú Âonhook[*]), (time) Tdial = , (time) Tcall = } agent dial(S) { oracle (int) dialled_number[S], (time) Tdial, time, (bool) onhook[S], (bool) connecting[S,*] = false handle (time) tstart state (time) tstart = |time| (bool) valid = derivate (bool) dialling[S] = Âonhook[S] Ù ((time - tstart) < Tdial ), (bool) LIVE = dialling[S] Ù Âconnecting[S, dialled_number[S]] protocol dialling[S] Ù valid ® connect(S, dialled_number[S]) } agent connect(S,D) { oracle (bool) onhook[S], onhook[D], ringing[D], engaged[S,D], (time) Tcall , time handle (time) tcall , (bool) connected[S,D], answered[D] state (time) tcall = |time|, (bool) connected[S,D] = false, (bool) answered[D] = false derivate (bool) connecting[S,D] = Âconnected[S,D], (bool) LIVE = Âonhook[S] Ù ( (connecting[S,D] Ù (time-tcall ) contains no commands in the command list - its purpose is just to invoke a procedural action in the appropriate state to print a message that the telephone is perceived to be ringing. The guard even && (slow[_U,1] > 0) -> slow[_U,1] = |slow[_U,1]| - 1 implements the control mechanism to slow the user entity down when it has dialled a number. When one of the five guards which come from the LSD specification is evaluated as being true the variables selected[_U,1] and level[_U,1] are used to indicate how much of the guarded command has been executed. At each stage an arbitrary delay can be introduce by appending a conjunct of the form "&& (rand(n) == 1)" to the guard. The guard of the command to replace the receiver is even && (selected[_U,1] == 1) && (level[_U,1] == 1) && (rand(3) == 1) print ("replacing the receiver of ",_S) -> onhook[_S]=true ; level[_U,1] = 2 This indicates that there will be some arbitrary, but relatively short, delay between deciding to put the telephone back on the hook and actually doing so. The value chosen for n is 6 before dialling a number, which indicates that there is on average a longer delay between deciding to dial and actually dialling than between deciding to replace and replacing the receiver. Where there is no such conjunct this is because the value chosen for n was 1, and so the conjunct, which is always true, has been omitted. For example: even && (selected[_U,1] == 4) && (level[_U,1] == 2) -> dial(_S,_D) ; level[_U,1] = 0 ; selected[_U,1] = 0 which means that when the receiver has been lifted up the dial() entity is instantiated as soon as possible. The act of speaking into a receiver is indicated in the simulation by a procedural action, but is a null action as far as the execution of the entity is concerned: even && (selected[_U,1] == 3) && (level[_U,1] == 1) && (rand(6) == 1) print ("speaking into ",_S) -> level[_U,1] = 0 ; selected[_U,1] = 0 The change of state when a user speaks is indicated by changing the values of the variables selected[_U,1] and level[_U,1]. A cognitive argument is used to indicate that all variables should be kept as authentic as possible, which leads to the guards: !even -> tone[_S,1] = |tone[_S]|, !even -> ringing[_S,1] = |ringing[_S]|, !even -> onhook[_S,1] = |onhook[_S]|, !even -> dialled_number[_S,1] = |dialled_number[_S]| For example, whenever the tone of the phone changes, it is in general known immediately by the listening user. The user's perception of whether the telephone is on the hook or not is normally accurate. Similar arguments can be applied for all the variables perceived by the user entity. The telephone() entity In this section we comment on the entity which was produced by transforming the telephone() agent in the LSD specification. No unowned variables are initialised by the telephone() agent. Since it does not own the connected or engaged variables, it must update the perceived values of these variables. This means that there will be the guarded commands !even ->connected[_S,_D,2]=|connected[_S,_D]|, !even -> engaged[_S,_D,2] = |engaged[_S,_D]| associated with the telephone() entity, even though there are no guarded commands in the specification of the telephone() agent. The dial() entity In this section we comment on the entity which was produced by transforming the dial() agent in the LSD specification. This entity is instantiated by the user() entity when a call is to be made, and is deleted when the connection has been initiated, the calling telephone has been replaced on the hook, or too long has been taken in dialling. The LIVE derivate variable of the specification has been transformed by testing it whenever even is false !even && !init_flag[_S,3] && !(dialling[_S,3] && !connecting[_S,_D,3]) print ("terminating dialler from ",_S," to ",_D) -> dialling[_S] = false; delete dial(_S,_D) This ensures that updates to variables can only occur when the entity is not about to be deleted (thus avoiding a redefinition and deletion of the owning entity in the same run set). The "dialling[_S] = false" command resets the definition associated with dialling[_S] to that in which the dial() agent was invoked. When it has invoked the connect() entity the operation of the dial() entity is slowed down by using the slow[__S,3] construct: even && (level[_S,3] == 1) print ("starting connection from ",_S," to ",_D) -> connect(_S,_D) ; level[_S,3] = 0 ;slow[_S,3] = 20 This allows time for the connect() entity to perform the initialisations which make connecting true, and for this change to be perceived by the dial() entity. The connect() entity In this section we comment on the entity which was produced by transforming the connect() agent in the LSD specification. The variable tcall[_S] is initialised in the first guarded command because of the problem with initialisations involving evaluation, which is described in the user documentation in Appendix 3. init_flag[_S,4] -> answered[_D] = false ; tcall[_S] = |time| ; connected[_S,_D] = false ; connecting[_S,_D] = !connected[_S,_D] ; init_flag[_S,4] = false Were this not done, it would always have the definition |time|, i.e. the current time. When even is false the value of only_one[_S,_D,4] is set (by the last three guarded commands in the connect() entity) to be the number of whichever of the guards in the LSD specification is true. If no guard is true, then the value of only_one[_S,_D,4] is left unchanged. This means that as soon as the connection can be made, the line is engaged, or the picking up of the ringing receiver is registered, the associated command will be selected for execution. The exchange() and environment() entities In this section we comment on the entities which were produced by transforming the exchange() and environment() agents in the LSD specification. The use of the "*" and "?" constructs in the LSD exchange specification needs to be explicitly enumerated in the exchange() entity, because there are no pattern matching facilities available in am, for example: ringing[7124] = connected[6489,7124] && onhook[7124] && !answered[7124] All such variables must be explicitly declared as owned and stored in the definition store D. In the environment() entity there is no need to use an only_one variable because there is only one guarded command, which becomes: even && (level[6] == 0) -> level[6] = 1, even && (level[6] == 1) -> time = |time| + 1; level[6] = 0 The toggling of the value of even occurs in the environment() entity, because it is always instantiated exactly once: true -> even = !|even| Instantiations at compile time Once entered the definitive program is instantiated as follows: user(10,6489,7124) user(11,7124,6489) telephone(6489,7124) telephone(7124,6489) exchange() environment() This causes the instantiation of two users and their associated telephones, and an exchange and environment entity. The simulation is started by the command: start Telephone animation and testing An LSD specification can be transformed into a family of definitive programs by using different parameters for the transformation process. The following extract is taken from the phone.am program in the ~wmb/public/demo/am directory. It shows how the user() and environment() agents are transformed into entities in such a way that different choices of parameters can be used to simulate different patterns of behaviour. By changing these parameters, you can investigate possible behaviours associated with simulation of the LSD specification. The transformation of the user() agent into an entity involves associating a parameter with each of the 5 user actions thus: R replace receiver D dial number S speak when connected C start a call A answer phone. The values of these will determine the range of values of the variable only_one[_U,1] in the user() entity which will result in the respective guard being the one chosen for evaluation in an execution cycle. (Values of only_one[_U,1] that exceed R+D+S+C+A correspond to "no action on the part of the user" - see below.) In the particular program used for illustration, the relevant parameters are defined Ð by assigning explicit values to variables in the environment() entity ÐÊto the following values: R, D, S, C, A, I = 2, 15,10, 2, 10, 11. It is therefore five times as likely that, once connected, the user will speak rather than terminate the call by replacing the receiver. For this reason we would expect to have reasonable length calls with this simulation. The parameters used for the transformation in the above program are such that it is unlikely that a user will either initiate or terminate a call. The environment() entity in this simulation program has the form: entity environment() { // the 6th entity in the specification, whence level[6] variable definition R = 2, D = 15, S = 10, C = 2, A = 10, // set these parameters for different results // R = replace, D = dial, S = speak, C = call, A = answer - see explanation below time = 0, level[6] = 0, even = 0 action even && (level[6] == 0) -> level[6] = 1, even && (level[6] == 1) -> time = |time| + 1 ; level[6] = 0, true -> even = !|even| } entity user(_U,_S,_D) { // the 1st entity in the specification, whence level[_U,1] etc. definition number_to_dial[_S] = _D, tone[_S,1] = |tone[_S]|, ringing[_S,1] = |ringing[_S]|, onhook[_S,1] = |onhook[_S]|, dialled_number[_S,1] = |dialled_number[_S]|, level[_U,1] = 0, slow[_U,1] = 0, only_one[_U,1] = 1, selected[_U,1] = 0 action even && ringing[_S,1] print (_S," is ringing") -> , even && (slow[_U,1] > 0) -> slow[_U,1] = |slow[_U,1]| - 1, even && !onhook[_S,1] && (level[_U,1] == 0) && (only_one[_U,1] <= R) && (selected[_U,1] == 0) && (slow[_U,1] == 0) -> selected[_U,1] = 1 ; level[_U,1] = 1, even && (selected[_U,1] == 1) && (level[_U,1] == 1) && (rand(3) == 1) print ("replacing the receiver of ",_S) -> onhook[_S]=true ; level[_U,1] = 2, even && (selected[_U,1] == 1) && (level[_U,1] == 2) -> dialled_number[_S]=0 ; level[_U,1] = 0 ; selected[_U,1] = 0, even && !onhook[_S,1] && (tone[_S,1] == 1) && (level[_U,1] == 0) && (only_one[_U,1] > R) && (only_one[_U,1] <= R+D+1) && (selected[_U,1] == 0) && (slow[_U,1] == 0) -> selected[_U,1] = 2 ; level[_U,1] = 1, even && (selected[_U,1] == 2) && (level[_U,1] == 1) && (rand(6) == 1) print ("dialling the number ",_D," on telephone ",_S) -> dialled_number[_S]= number_to_dial[_S] ; level[_U,1] = 0 ; slow[_U,1] = 10 ; selected[_U,1] = 0, even && !onhook[_S,1] && (tone[_S,1] == 4) && (level[_U,1] == 0) && (only_one[_U,1] > R+D) && (only_one[_U,1] <= R+D+S) && (selected[_U,1] == 0) && (slow[_U,1] == 0) -> selected[_U,1] = 3 ; level[_U,1] = 1, even && (selected[_U,1] == 3) && (level[_U,1] == 1) && (rand(6) == 1) print ("speaking into ",_S) -> level[_U,1] = 0 ; selected[_U,1] = 0, even && onhook[_S,1] && !ringing[_S,1] && (level[_U,1] == 0) && (only_one[_U,1] > R+D+S) && (only_one[_U,1] <= R+D+S+C) && (selected[_U,1] == 0) && (slow[_U,1] == 0) -> selected[_U,1] = 4 ; level[_U,1] = 1, even && (selected[_U,1] == 4) && (level[_U,1] == 1) && (rand(3) == 1) print ("lifting up receiver of ",_S," to make call") -> onhook[_S] = false; level[_U,1] = 2, even && (selected[_U,1] == 4) && (level[_U,1] == 2) -> dial(_S,_D) ; level[_U,1] = 0 ; selected[_U,1] = 0, even && onhook[_S,1] && ringing[_S,1] && (level[_U,1] == 0) && (only_one[_U,1] > R+D+S+C) && (only_one[_U,1] <= R+D+S+C+A) && (selected[_U,1] == 0) && (slow[_U,1] == 0) -> selected[_U,1] = 5 ; level[_U,1] = 1, even && (selected[_U,1] == 5) && (level[_U,1] == 1) && (rand(3) == 1) print ("lifting up receiver of ",_S," to answer") -> onhook[_S] = false; level[_U,1] = 2, even && (selected[_U,1] == 5) && (level[_U,1] == 2) && (rand(6) == 1) print ("'hello, ",_S,"'") -> level[_U,1] = 0 ; selected[_U,1] = 0, !even -> tone[_S,1] = |tone[_S]|, !even -> ringing[_S,1] = |ringing[_S]|, !even -> onhook[_S,1] = |onhook[_S]|, !even -> dialled_number[_S,1] = |dialled_number[_S]|, !even && (selected[_U,1] == 0) -> only_one[_U,1] = |rand(50)| // can't use symbolic expression as rand() parameter: ideally should use // only_one[_U,1] = rand(R+D+S+C+A+I), where I is number of cycles user is idle } Devices used in the transformation process To avoid evaluating a variable whilst it is being redefined, we interleave command execution and variable updating. On every even execution cycle we perform agent actions, and on every odd execution cycle we update a subset of the set of perceived variables. The ninth guard in the user entity, has a conjunct && (rand(6) == 1) This means that, once it has been decided to speak, on average only one of the next twelve (since the guard can only be true when even is true) execution cycles will allow speaking to occur. The value for n used in the guarded command !even && (selected[_U,1] == 0) -> only_one[_U,1] = |rand(n)| influences how quickly actions are selected by the user. The higher the value for n, the more execution cycles will on average occur between actions by the user. This is because any value for only_one[_U,1] which is more than R+D+S+C+A (=39) will not allow the selection of any guard from the specification. The higher n is, the more chance there is that only_one[_U,1] will have a value higher than 39. The value of selected[_U,1] is positive when an agent is committed to action, and otherwise 0. The parameter 1 in the variable name selected[_U,1] is for disambiguation only; the user is the 1st agent in the LSD specification, and any other occurrence of the selected[] variable device will incorporate the index of a different entity. A positive value of selected[_U,1] will be in the range 1 to 5, corresponding to the 5 user actions. When execution of an LSD privilege involves a sequence of actions, these are typically separated by intervals of time. The level[_U,1] variable is used to indicate how many steps have been taken in the execution of a sequence of actions. So for instance, after the execution of the first action of a sequence, the value of level[_U,1] is 2. The variable slow[_U,1] is used to delay action execution. n && (slow[_U,1] > 0) -> slow[_U,1] = |slow[_U,1]| - 1, even && !onhook[_S,1] && (level[_U,1] == 0) && (only_one[_U,1] <= R) && (selected[_U,1] == 0) && (slow[_U,1] == 0)