Generating statechart designs from scenarios
Contents
1. Cancel can occur in one of two states see Figure 11 Cancel can be generalized however such that it can occur in any state in which cardIn is true and cardHalfway is false This suggests the introduction of hierarchy by partitioning the statechart over the values of cardIn and cardHalfway using the ordering cardIn lt cardHalfway At present such generalizations are given explicitly by the user in the form of expressing an ordering or invoking a transformation but it may be possible to suggest generalizations automatically for example by using machine learning techniques 321 Input A FSM N so V p L 6 S C N an ordering lt over the state vector variables W Output A partitioning P of the FSM W v1 Uk for v E W and v lt vj i lt j P PARTITION S W while OPTIMAL P do W select variable ordering W P PARTITION S W done where PARTITION S W vj first W split on first var in W Ds vj YUO m Ds v l for 1 lt i lt m do Si s S e s j ith Ds v P PARTITION S rest W done P PiP 0 where OPTIMAL P check P according to our design criteria Figure 12 Sketch of algorithm for partitioning over the state vector Example Figure 13 shows the FSM from Figure 11 which has been partitioned according to the ordering cardIn lt cardHalfway and in which the Cancel message has been generalized2. Generating Statechart Designs From Scenarios Jon Whittle Recom NASA Ames Research M S 269 2 Moffett Field CA 94035 USA 650 604 3589 jonathw ptolemy arc nasa gov ABSTRACT This paper presents an algorithm for automatically gen erating UML statecharts from a collection of UML se quence diagrams Computer support for this transi tion between requirements and design is important for a successful application of UML s highly iterative dis tributed software development process There are three main issues which must be addressed when generating statecharts from sequence diagrams Firstly conflicts arising from the merging of independently developed se quence diagrams must be detected and resolved Sec ondly different sequence diagrams often contain identi cal or similar behaviors For a true interleaving of the sequence diagrams these behaviors must be recognized and merged Finally generated statecharts usually are only an approximation of the system and thus must be hand modified and refined by designers As such the generated artifact should be highly structured and read able In terms of statecharts this corresponds to the introduction of hierarchy Our algorithm successfully tackles all three of these aspects and will be illustrated in this paper with a well known ATM example Keywords UML Scenarios Automated Software Engineering 1 INTRODUCTION The Unified Modeling Language UML 17 provides a standardiz
3. archy if the structure is explicitly represented in the scenarios e g concurrent threads expressed in a col laboration diagram lead to a statechart node with two orthogonal subnodes However structure beyond that present in the scenarios must be introduced manually Our work extends this approach by introducing hier archy where the structure is deduced from other UML notations such as a class diagram or from a domain theory where partitioning is made over a state variable Most other approaches assume the correctness of the input scenarios In practice the scenarios will contain ambiguities and inconsistencies Our algorithm detects conflicts which may correspond to such ambiguities and hence can be used as a guide for refining the scenarios To further extend our consistency checks we may be able to leverage off work done in checking the consis tency of SCR requirements specifications 8 or work in the feature interactions community 11 6 CONCLUSIONS We have presented an algorithm for generating UML statecharts from scenarios These scenarios comprise parts of the system requirements and are given as se quence diagrams By adding semantic information in the form of a domain theory we are able to correctly identify similar states and to detect and report incon sistencies By identifying similar states our approach allows the merging of a number of sequence diagrams into a single statechart In order to make such an
4. explicitly by the user as in the previous paragraph to produce the same behavior for the source state of Request password as for the other two states in which it is applicable a Using Class Diagrams It is important to incorporate other design decisions made by the developer into the synthesis process Within the UML framework a natural place for higher level design decisions are class diagrams These describe the types of the objects in the system and the static re lationships among them A hierarchical structure of a generated statechart can easily be obtained from the class diagram the outer most superstate surmounting the entire statechart cor responds to the class node of the corresponding object Aggregation results in a grouping of nodes e g in Fig ure 1 the ATM statechart will have subcharts physical device and dialogs If a class contains several sub classes e g card reader and cash dispenser are sub classes of physical device in Figure 1 the state charts corresponding to the sub classes are sub nodes of the current node Due to space restrictions we do not show the resulting statechart when Figure 1 is struc tured according to the class diagram E SES 2 4 gt 2 Figure 13 Structured statechart for the ATM example The final way of introducing structure is somewhat higher level than the first two Typically the class di agram can be used to obtain a very abstract structure and
5. al gorithm practical the generated statecharts must be readable To enable this we introduce structure and hierarchy into the generated statechart Information and guidance for structuring are taken from the domain theory a UML class diagram and additional preferences the user may select A prototype of this algorithm has been implemented in Java The development of high quality software requires a rig orous enforcement of formal techniques during the entire lifecycle UML covers a wide spectrum of diagrams and notations on various levels of software development and encourages an iterative life cycle For high productivity a transition between the different levels has to be made effectively and fast However current CASE tools only support translations from specification to code e g generation of C code from class diagrams or stat echarts Our approach can be used to close the gap between the requirements and specification phase Since most requirements do not specify the full behav ior of the system the generated SCs are only a skele ton which serve as a basis for manual refinement and modification Therefore our algorithm fully supports iterative model development Careful software design requires that the specification and requirements are al ways kept in a consistent state Manually maintaining consistency is a tedious and error prone task Our algo rithm provides the first step towards an automated tool for carryin
6. bank account account message quest take card Bad account Figure 3 Interaction with an ATM SD1 then the system changes state to Al If the system is in any of the states Al A2 A3 when transition f d b fires then it will change state to C _ By using composite nodes hierarchy or depth can be introduced This not only decreases the number of indi vidual nodes substantially but also enhances readabil ity and maintainability of a statechart For details on statecharts see e g 6 17 for their semantics cf 7 Sequence Diagrams The basis for our approach are scenarios which describe concrete examples of the system s intended behavior Scenarios can be expressed in UML as sequence dia grams A sequence diagram SD shows the interaction between objects of a system over time The SD in Fig ure 3 is an example for interactions between the objects User ATM Consortium and Bank The ver tical lines represent the life line or time line for the given object defining the object s life during the inter action Messages like Insert card are exchanged be tween the objects In this paper we will focus on basic SDs for further details and extensions e g conditional messages or iteration cf 17 3 ADDING SEMANTIC INFORMATION The simplicity of sequence diagrams makes them suit able for expressing requirements as they can be easily understood by customers requir
7. passwd Request take card pre cardHalfway true post l Canceled message pre cardIn true post Figure 5 Domain Knowledge for the ATM class conflict detection Currently our algorithm only ex ploits constraints of the form var value but there may be something to be gained from reasoning about other constraints using an automated theorem prover As well as being used for conflict detection the OCL constraints can be used to identify identical states in different sequence diagrams which allow these diagrams to be merged The constraints also allow an automatic partitioning of the generated statecharts into hierarchi cal super nodes cf Section 4 Figure 5 gives specifications for selected messages in our ATM example The state variables in the form of a state vector are used to characterize states in the gen erated statechart The state vector is a vector of values of the state variables In our example the state vector has the form lt cardiIn cardHalfway passwdGiven card passwd gt where var Dom var U and represents an un known value The notion of state vector is crucial to our algorithm 4 GENERATING STATECHARTS Single Sequence Diagrams We shall first consider how individual SDs can be con verted into statecharts This process starts by detecting 317 conflicts between the SD and the domain theory and hence other SDs Note that there are two kinds of c
8. semantics of conditional messages in UML SDs is unclear We follow that presented in 4 where keywords IF ENDIF CASE ENDCASE are used to partition a SD into conditional branches Input A sequence diagram S containing objects O O and messages m Mp as in 1 Output A FSM Co for each object 1 lt i lt k for i 1 k do i Create a new FSM Co with a single node no i the initial node and current node in Co no i done fori 1 rdo ADD mj ac m Tce ADD m ev m e done i where ADD mess type obj curr current node in Cobj if there is a n No with curr l n 6 and l type mess and s u n then current node in Cop n return fi if there is a n E No with s p n and m is state changing then add new transition curr type mess n current node in Cobj n return fi add a new node n and let u n s add a transition curr type mess n current node in Cobj n return Figure 8 Translating a sequence diagram into FSMs proach taken in 18 Recall however that one of our main aims is to generate readable statecharts which can then be further modified by the user Merely taking the union of the FSMs would result in a chart with many independent branches one for each SD Our approach makes an analysis of which nodes in different FSMs can be identified so that different branches can be merged The result is a statechart with fewer no
9. the first two methods can be used to introduce fur ther structure within each subchart generated using the class diagrams 5 RELATED WORK There have been a number of recent attempts at gen erating specifications from scenarios Our work stresses the importance of obtaining a specification which can be read understood and modified by a designer This is reflected in the following main ways Many approaches make no attempt to interleave differ ent scenarios 18 gives a learning algorithm for gener ating a temporal logic specification from a set of exam ples counterexamples expressed as scenarios Each sce nario gives rise to a temporal logic formula G and sce nario integration is merely J G augmented with rules for identifying longest common prefixes In terms of generating FSMs this corresponds to having separate branches in the FSM one for each scenario However this does not correspond well to what a human designer would do A more effective integration of scenarios necessitates some way of identifying identical states in different sce narios The solution to this in 10 is to ask the user to explicitly name each state in the FSM generated from a scenario Different states are then merged if they have been given the same name This approach requires a good deal of effort from the user however The SCED tool 13 generates FSMs from traces using 322 the Biermann Krishnaswamy algorithm 3 This algo rithm uses b
10. acktracking to identify identical states in such a way that the final output FSM will be determin istic As a result there is no use of semantic information about the states and the algorithm ultimately may pro duce incorrect results by identifying two states that are in fact not the same In addition designers will often introduce non determinism into their designs which will only be resolved at a later implementation stage Hence the insistence on determinism is overly restrictive 12 tackles the problem of integration by requiring that the user gives an explicit diagram a high level Message Sequence Chart showing the transitions from one sce nario to the next This merely shows however how the start and end points of different scenarios relate There is no way to examine the contents of scenarios to for ex ample detect interleavings or loops 5 follows a similar approach essentially using an AND OR tree instead of a high level Message Sequence Chart The work closest to our own is described in 16 where timed automata are generated from scenarios The user must provide message specifications with ADD and DELETE lists which maintain a set of currently valid predicates in a STRIPS like fashion States are then identified if the set of valid predicates is the same The ability to introduce structure and hierarchy into the generated FSM is crucial if user modifications must be made 10 allows the limited introduction of hier
11. and Methodology 5 3 231 261 1996 7 8 9 I Horrocks Constructing the User Interface with Statecharts Addison Wesley 1999 I Khriss M Elkoutbi and R Keller Automat ing the synthesis of UML statechart diagrams from multiple collaboration diagrams In UML98 Be yond the Notation pages 132 147 Springer 1999 10 11 K Kimbler Feature Interactions in Telecommuni cations and Software Systems V IOS Press 1998 S Leue L Mehrmann and M Rezai Synthe sizing software architecture descriptions from Mes sage Sequence Chart specifications In Automated Software Engineering pages 192 195 Honolulu Hawaii 1998 T M nnist T Syst and J Tuomi SCED re port and user manual Report A 1994 5 Dept of Computer Science University of Tampere 1994 12 13 14 Rational Rose Rational Software Corporation Cu pertino CA 1999 15 Rhapsody 1 Logix Inc Andover MA 1999 16 S Som and R Dssouli From scenarios to timed automata building specifications from users re quirements In Asia Pacific Software Engineering Conference pages 48 57 1995 17 Unified Modeling Language Specification Version 1 3 1999 Available from Rational Software Cor poration Cupertino CA A van Lamsweerde Inferring declarative re quirements specifications from operational scenar ios IEEE Transactions on Software Engineering 24 12 1089 1114 1998 K Weidenh
12. aupt K Pohl M Jarke and P Haumer Scenarios in system development Cur rent practice IEEE Software pages 34 45 1998 18 19
13. d into FSMs C C then we create a new FSM C which includes C1 Cp and has e transitions as fol lows 1 Let c be the union of C3 Ck i e No UiNe Lic Uic etc Let C have a new initial node no and create e transitions from no to each of the initial nodes of Cy yaray Cr For each pair of similar nodes n and ns in No create e transitions from n to nz and from nz to ni The algorithm that we use subsequently is a variant of a standard algorithm for transforming a non deterministic finite automaton NFA into a deterministic finite au tomaton DFA 1 Each state in the DFA is a set of NFA states which simulates in parallel all possi ble moves the NFA can make on a given input string In order to leverage off this algorithm we introduce e transitions as above These e transitions are removed by the algorithm resulting in a FSM that has successfully interleaved a number of SDs by placing similar nodes into a single state in the output Note that the output of the algorithm is only determin istic in the sense that there are no e transitions remain ing It still may be the case however that there are two transitions leaving a state labelled with the same events but different actions Hence our algorithm may produce non deterministic statecharts Note that this is a good thing as a designer may wish to leave a design non deterministic initially and refine it later Example Figure 11
14. des correspond ing more closely to the statechart that a designer might produce manually from the SDs The idea is that we recognize similar nodes from dif ferent FSMs and join them with empty e transitions A standard algorithm from 1 can then be used to re move these transitions and simultaneously merge sim ilar nodes A key question then is how to recognize similar nodes The obvious solution is to define similar ity such that two nodes are similar if their state vectors are the same However such a definition would produce an excessive number of similar nodes since some mes sages do not change the state vector The way around this when merging multiple SDs is to base the notion of similarity on both the state vectors and the ordering of 319 messages Definition 1 Two nodes n and nz in a FSM are sim ilar if they have the same state vector u ni p n2 and they have at least one incoming transition with the same label i e there exist transitions t na l n and tz n4 l n2 for some nodes nz na The existence of a common incoming transition means that in both cases an event has occurred which leaves the state variables in an identical assignment Hence the definition takes into account the ordering of the mes sages and the current state We illustrate how e transitions are introduced when con sidering the FSMs generated for an object O Suppose we start with sequence diagrams which are translate
15. ed collection of notations for describing arti facts in a software intensive system It supports modern complex software development whereby requirements are expressed in one notation e g sequence diagrams the design is then described in other notations e g class diagrams and statecharts finally code is produced using the earlier notations as a guide This approach allows different stakeholders to develop models indepen dently and encourages rapid prototyping Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To copy otherwise to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee ICSE 2000 Limerick Ireland Copyright ACM 2000 1 58113 206 9 00 6 5 00 314 Johann Schumann Caelum NASA Ames Research 3 M S 269 2 Moffett Field CA 94035 USA 650 604 0941 schumann ptolemy arc nasa gov _ Each UML notation represents a particular aspect of a software system from a particular viewpoint However there exists a good deal of overlap between many no tations This overlap can be exploited in the form of automatic translations between notations to reduce the time spent in design and to help maintain consistency between the models of differ
16. ements engineers and software developers alike Unfortunately the lack of se mantic content in sequence diagrams makes them am biguous and therefore difficult to interpret For exam ple suppose there exists an additional sequence dia gram SDO identical to SD1 in Figure 3 except that there are two Insert card messages adjacent to each User Re Consortium Bank ATM Display main screen gp uest password Cancel Figure 4 Interaction with an ATM SD2 other There are three possible ways to interpret the conjunction of the two SDs either one or two cards may be inserted exactly one card must be inserted so SDO is incorrect or exactly two cards must be inserted so SD1 is incorrect In current practice ambiguities are often resolved by examining the informal documentation but in some cases ambiguities may go undetected lead ing to costly software errors In the case of computer generation of designs the documentation is usually too informal for the automatic resolution of conflicts There are two extreme ways to overcome this problem First insist that the user provides a complete formal domain theory providing semantic information about the mes sages Second assume no additional semantic informa tion but interpret scenarios based on some heuristic Neither of these is sufficient however The provision of a complete domain theory is overly burdensome and an algorithm w
17. ent developers Currently commercial tools such as iLogix s Rhapsody 15 and Rational s Rose 14 do not adequately bridge the gaps between UML notations The generation of C code is now commonplace but the generation of UML models themselves has not been adequately ad dressed Some model translations can be trivially de fined because the models represent the same information in slightly different ways One such example is convert ing between sequence diagrams and collaboration dia grams However other translations are inherently more involved such as translating between requirements and actual system designs This paper presents an algorithm which supports the design process by generating statechart designs auto matically from scenarios A scenario is a trace of an individual execution of a software artifact 19 Sce narios are widely used as a pre requirements technique since they describe concrete interactions and are there fore easier for customers and domain experts to use than an abstract model In what follows scenarios will be expressed as UML sequence diagrams and the design model will consist of a class diagram and UML state charts Since each scenario is usually written in isolation bring ing many scenarios together will result in inconsistencies which have to be detected and resolved UML sequence diagrams alone do not contain enough semantic informa tion to enable the automatic detection of confl
18. erarchy into the generated FSMs us ing implicit information present in the state vectors in troducing generalizations and using information explic itly given by the user in class diagrams Using the State Vector The set of state variables in our annotated SDs pro vides an excellent means for introducing structure into the generated statechart State variables usually encode that the system is in a specific mode or state e g if the card is inserted or not Thus it is natural to partition the statechart into subcharts containing all nodes be longing to a specific mode of the system More specifically we recursively partition the set of nodes according to the different values of the variables in the state vectors In general however there are many different ways of partitioning a statechart not all of them suited for good readability Thus we introduce additional heuristic constraints on the layout of the stat echart These constraints rule out unreadable partitions and are controlled by user given parameters 1 the maximum depth of hierarchy too many nested levels of compound states limit readability 2 the maximum number of states on a single level 3 the maximum percentage of inter level transitions transitions between different levels of the hierarchy limit modularity but can occasionally be useful a partial ordering lt over the state variables de scribing an order in which partitions should be a
19. g out such a task Future plans will augment our algorithms so that changes made to the generated statechart can be fed back to the sequence diagrams In this way design modifications can be validated on the fly by highlighting scenarios that are no longer valid or suggesting new scenarios that become possible REFERENCES 1 A Aho R Sethi and J Ullman Compilers Prin ciples Techniques and Tools Addison Wesley 1986 2 Argo UML University of California Irvine 1999 http www ics uci edu pub arch uml index html 3 A Biermann and R Krishnaswamy Con structing programs from example computations IEEE Transactions on Software Engineering SE 2 3 141 153 1976 4 T Gehrke and T Firley Generative sequence diagrams with textual annotations In For male Beschreibungstechniken fir verteilte Systeme FBT99 pages 65 72 1999 323 5 M Glinz An integrated formal model of scenarios based on statecharts In 5th European Software En gineering Conference ESEC pages 254 271 Sit ges Spain 1995 6 D Harel Statecharts A visual formalism for com plex systems Science of Computer Programming 8 231 274 1987 D Harel A Pnueli J Schmidt and R Sherman On the formal semantics of statecharts In Proc 2nd LICS pages 54 64 Springer 1987 C Heitmeyer R Jeffords and B Labaw Auto mated consistency checking of requirements spec ifications ACM Transactions on Software Engi neering
20. gives the statechart generated au tomatically from the SDs in Figures 3 4 9 and 10 Our algorithm implemented in Java has actually been ap plied to the full ATM example which consists of eleven Consortium Bank User ATM Display main scree Insert card ed gt Da a message Take card Re Figure 9 Interaction with an ATM SD3 Consortium Bank Re p KEG pa J _Cancred mes Verify account _Figure 10 Interaction with an ATM SD4 Figure 11 Statechart generated from SD1 SD2 SD3 and SD4 SDs Two conflicts were found and a loop was detected which was not intended but which was allowed by the SDs and domain theory In this way the algorithm car ries out some degree of validation of the input SDs w Introducing Hierarchy So far we have shown how to generate FSMs without any hierarchy In practice however statechart designs tend to get very large and so the judicious use of hierar chy and orthogonality is crucial to readability and main tainability of the designs In what follows we consider how hierarchy can be introduced automatically into the FSMs generated by our algorithm There are several issues which comprise a well designed statechart see for example 9 They in clude the consolidation of related behavior the sepa ration of unrelated behavior and the introduction of meaningful abstractions We consider three approaches 320 for introducing hi
21. iagram for our ATM example In an object oriented fashion the main class here ATM toplevel is broken down into sub classes The aggre gation relation shows when one class is part of another one The generalization relation gt shows when one class is an instance of another For further details see 17 315 Figure 1 A Class Diagram for the ATM VAR ERNE See ez c2 a Figure 2 Example of a Statechart Statecharts Statecharts introduced originally by D Harel 6 are finite state machines extended with hierarchy and or thogonality parallelism allowing a complex system to be expressed in a more compact and elegant way Fig ure 2 shows a simple example of a statechart Nodes can either be simple nodes or composite nodes which themselves contain other statecharts The initial node in a statechart is marked by e Transitions between states have labels of the form e c a If event e occurs and guard c holds then the transition may be selected to fire which results in action a being taken and a state change occurring This behavior is extended in a natu ral way to handle composite nodes In Figure 2 if the system is in state B when the transition e c a fires 2 All class diagrams and statecharts in this paper have been drawn using the Argo UML tool 2 Consortium Bank User ATM Display main screen rd Verify account Verify card with ban Bad
22. ication two state vectors S and S i j are considered the same if they are unifiable i e there exists a variable assignment such that S S This amounts to the detection of _ loops within a SD e The frame axiom for each j if s j i gt 0 then let s j s _ j and if s j then let s j s j This assumes of course that there are no hidden side effects between messages These two techniques extend the state vectors by prop agating variable values throughout the SD This allows us to detect conflicts between state vectors a conflict is detected if the state vector immediately following a message and the state vector immediately preceding the next message differ if they are unifiable they will al ready have been unified Any reported conflicts must be resolved by the user and the algorithm is started again Figure 6 shows how these techniques fit together Example Figure 7 shows SD1 from Figure 3 after the state vectors have been extended by unification and the frame axiom Our procedure detects a conflict with Input A SD annotated with state vectors Output A SD with extended annotations for each state vector S do if there is some j and some unifier with 5 S then unify S and S propagate instantiations with frame axiom if there is some k l with s 1 A sk 1 1 then Report Conflict break done Figure 6 Extending the state vector annotati
23. icts but this information can be obtained by allowing the user to express constraints on the diagrams UML provides a convenient notation for giving such constraints the Ob ject Constraint Language 17 OCL which is a side effect free specification language The OCL constraints 1This is similar to the feature interactions problem of the telecommunications industry 11 amount to a very simple domain theory Domain theo ries are under used in software engineering because the effort required to develop a complete and consistent do main theory usually outweighs the gains In our case we do not insist on a complete domain theory but re quire only a theory expressing instantiations of global variables that can easily be provided by a software en gineer In addition our approach allows for revisions of the domain theory based on conflicts discovered during statechart generation This use of a domain theory is a novel one as traditionally domain theories are consid ered absolute The addition of semantic information also allows a jus tified merging of multiple scenarios Different scenarios will often contain identical or similar behaviors and the use of a domain theory allows us to merge these scenar ios in a way such that the behavior intended by the user is preserved Since scenarios only give a partial description of a sys tem we expect the use of this algorithm to be similar to that of a code generator i e the a
24. ith no semantic information ultimately produces incorrect results We make a compromise whereby messages in a sequence diagram may be annotated with a pre post condition style specification expressed in OCL Note that this is only a small additional burden on the user since the amount of information required by our algorithm for a 316 successful merging of SDs is actually very small The specifications should include the declaration of global state variables where a state variable represents some important aspect of the system e g whether or not the user has inserted his card into the ATM Pre and post conditions should then include references to these variables Note that not every message needs to be given a specification although clearly the more semantic in formation that is supplied the better the quality of the cardIn cardHalfway passwdGiven Boolean card Card passwd Sequence Insert card c Card pre cardIn false post cardIn true and card c Enter password p Sequence pre passwdGiven false and p gt forAll p gt includes d gt digit d post passwdGiven true and passwd p Take card pre cardHalfway true post cardHalfway false and cardIn Display main screen pre cardIn false and cardHalfway post Request password pre passwdGiven false post false false Eject card pre cardIn true post cardIn false and cardHalfway and card null and
25. lgorithm pro duces a skeleton design which the user then has to mod ify complete Since the user needs to modify the gen erated statecharts they must be readable This means that the statecharts must include sensible use of hier archy and orthogonality We have devised a number of ways of introducing hierarchy into the generated state charts We believe that the use of hierarchy is crucial to the success of design generation tools Section 2 introduces the relevant parts of the UML along with an example that will be referred to throughout the paper Section 3 shows how scenarios can be annotated with semantic information and Section 4 presents an algorithm that uses this semantic information to gener ate statechart designs Section 5 discusses related ap proaches and we conclude in Section 6 2 UML NOTATION AND EXAMPLE Throughout this paper we will use an ongoing example to illustrate our techniques The well known ATM ex ample see e g 13 is rather small yet complex enough to illustrate the main issues The example describes typ ical scenarios for user interaction with an ATM machine e g inserting or removing a card entering a password and interaction between the ATM a consortium and the bank for account validation Class Diagram A class diagram is a notation for modeling the static structure of a system It describes the classes in a sys tem and the relationships between them Figure 1 shows an example of a class d
26. olved we are ready to gen erate a statechart Our strategy is to generate a number of flat statecharts in fact finite state machines FSMs for each individual SD one for each object in the SD Each FSM describes the behavior of the class to which the corresponding object belongs Messages directed to wards a particular object O are considered events in the FSM for O Messages directed away from O are considered actions A loop is detected if the state vec tor immediately after the current message has been ex ecuted is the same as an existing state vector and if this message is state changing i e s 4 sj Note that 318 Consortium Bank pi ivan ATM lt f f t null nul Insert card lt tftcnull gt Request password lt p ffc null gt 4 lt tffcnull gt lt tffc null gt lt tftep gt Verify card with bagk lt fi p gt lt tfit ep gt lt I beP Bad bank account lt tftcp gt lt t fte p gt lt f t t null null lt tftop gt lt tfitcp gt lt ft tnull null gt lt fttnull nullp lt fttnull null lt fftnull nul lt fftnull nullp lt fft null null gt ren Figure 7 Figure 3 with Extended Annotations some messages may not have been given a specification hence they will not affect the state vector To iden tify states based solely on the state vector will result in incorrect loop detection e g a message with no speci fication will always loop back to its sta
27. on straints on a SD constraints on the state vector given by an OCL specification and constraints on the order ing of messages given by the SD itself Conflicts between these constraints mean that either the scenario does not follow the user s intended semantics or the domain the ory is incorrect The decision as to which holds must be taken by the user and appropriate modifications must be made This enables both the domain theory and the SDs to be refined during statechart generation Let a sequence diagram be represented as follows Mr t 1 where the m are messages between objects and s s4 are the state vectors immediately before and after message m is executed The source and destination objects of message m are denoted by m2 lt e and mest respec tively S will be used as a notational convenience to denote either s or s S j is the jth element of the the vector S vj will denote the name of the variable associated with position j in the state vector m m m so gt sp 851 gt SL Sr gt s The initial state vectors are obtained directly from the message specifications if m has a precondition v y then let s j y and if m has a postcondition v y let si j y Otherwise s j s j Since each message is specified independently the initial state vectors will contain a lot of unknown values Most but not all of these can be given a value in one of two ways e Unif
28. ons the domain theory This arises because state vectors SV1 and SV2 are unified the figure shows the instan tiations of the vectors after unification This corre sponds to the fact that the ATM returns to its initial state after Take card is executed The state vectors tell us that there is a potential loop at this point which will be created when the SD is translated into a stat echart see Figure 8 The effect of this loop is that there exists an execution path such that the variable passwdGiven is set to true when Request password is encountered the value of passwdGiven is the third el ement in the vector However the domain theory tells us that passwdGiven must be false as a pre condition of Request password Hence there is a conflict which represents the fact that the developer did not account for the loop possibility when designing the domain the ory The user must now decide on a resolution of this conflict either he can tell the system that the loop is not possible in which case the unifier that detected the loop is discarded or he modifies the sequence diagram or he modifies the domain theory The action taken in this case is that the domain theory is updated by giving Eject card the additional postcondition passwdGiven false This extra postcondition resets the value of the variable when the ATM user removes his card Translation into Finite State Machines Once conflicts have been res
29. rting state To overcome this loops are only created when the message changes the state l Figure 8 shows how a single SD is translated into a FSM for each object A FSM as generated by Figure 8 is a 6 tuple N so V p L where N is the set of nodes so N is the initial node V is the set of state vectors u N gt V isa labelling of the nodes with state vectors L is the set of transition labels and 6 C Nx Lx N is the transition relation Transition labels are either events denoted ev m or actions denoted ac m where m is a sequence of messages Note that we create a tran sition for each event and each action This produces an overly large number of states but makes analysis eas ier For presentation to the user actions and events can be amalgamated into the same transition in the usual statechart style Our implementation also deals with conditional branches expressed in the sequence diagram which introduce transition guards into the FSM but we omit these here for the sake of clarity The detection of loops is done in the second if statement in the definition of ADD Multiple Sequence Diagrams The previous section dealt with a single sequence dia gram The key ideas were how to identify if a SD con flicts with the domain theory and how to detect loops When merging multiple sequence diagrams one way would be to convert each SD to FSMs and then take the union of those FSMs This is essentially the ap 3The
30. t tempted some state variables may be more im portant than others and thus should be given pri ority The ordering encapsulates important design decisions about the way in which the statechart should be split up The process of structuring a given subset S of the nodes of a generated FSM is shown in Figure 12 Given the set of variables W of the state vector and the ordering lt a sequence W is constructed w r t lt Then the nodes S are partitioned In case the partition does not meet the design criteria 1 3 above a warning will be issued that the given ordering would result in a non optimal hierarchy and a new ordering of the variables is selected This selection is done until the criteria are met The actual splitting is performed recursively according to the variable sequence W Let vj be the top level vari able minimal in W on which to split The partition is made up of m equivalence classes corresponding to each possible value of v given in the SDs For example for the boolean variable cardIn we would collect all nodes where this variable is true or false respectively Then these compound states will be partitioned according to the remaining variables Generalizations Since SDs often represent concrete instances of a more general behavior it is useful to be able to introduce gen eralizations into the generated statechart We present one example of this here The input SDs show that the event
Download Pdf Manuals
Related Search