Model driven development approaches help to alleviate the abstraction gap between high-level design and actual implementation, to aid design, development and maintenance of industrial scale software systems. To provide automatic, easily usable tools for stakeholders, model driven development essentially relies on e cient and expressive translations between the program source code and the model. We present a declarative, rule-based approach to deterministically transform Erlang program sources that satisfy a certain syntactical constraint, into valid UML models of state machines. The transformation relies only on static analysis techniques, and the produced model conforms to the state machine metamodel de ned in OMG UML 2.0.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
framework [
The rest of this paper is structured as follows. At rst, Section 2 describes UML and Erlang state machines. Sections 3 and 4 introduce the methodology and the transformation rules to generate UML state machines. In Section 5 we explain the transformation starting from an example Erlang source code. Section 6 presents the evaluation of our work on several open source projects. Finally, Sections 7 and 8 present related work and conclude the paper. 2
One way to represent the execution history of a computer program is to take snapshots of the state of the program
memory. State machines can be used to abstract away this low level representation. With state machines these
memory snapshots are taken upon the occurrence of certain events, and instead of storing the content of the
memory, we just store descriptive labels, called states. Therefore, a state describes a segment of the program
behaviour, while a state transition describes a change in such behaviours, usually triggered by an event [
Among many others, Uni ed Modeling Language (UML) [
Figure 1 depicts the UML state machine language with a metamodel diagram. The root container object is always an instance of the StateMachine class. The root object contains a Region object, which in turn contains Vertex and Transition objects, that can be used to denote states and state transitions respectively. Pseudostate vertices can be used to denote initial states and choice states, FinalState vertices to denote stop states, and State vertices to denote ordinary states. The transitions can be assigned events (Trigger), guards (Constraint) and actions (Behavior). 2.2
Erlang [
In our research, we use the RefactorErl static analysis framework [
In this section we rst describe the main entities and their related notations involved in the transformation of Erlang state machines (i.e. Erlang modules implementing the gen fsm behaviour), and then we give the algorithm that realises this transformation. 3.1
The RefactorErl analysis framework stores all information it gathers about Erlang programs via static analysis
in a special data structure, called semantic program graph (SPG ) [
A small Erlang program and a segment of its SPG can be observed in Figure 3 and Figure 4 in Section 5. Apart from the special node called root, all nodes in the SPG correspond to lexical, syntactic, or semantic elements in the Erlang source code. The root node is the only node without incoming edges, and serves as the common ancestor for all nodes of the SPG. Edges of the SPG are ordered.
RefactorErl supplies various tools for discovering and analysing the SPG, such as a user friendly query
language, and several useful library functions that can be used in more complex programmed queries [
In this section we will describe a simple state machine metamodel, depicted by Figure 2, with which we represent
the target state machines of the transformation. We showed in [
The target state machines will basically consist of states (AnyState) and transition (Transition) elements between those states. There are four kinds of states: ordinary states (State), the initial state (InitState), stop states (StopState), and choice states (ChoiceState). Every transition may have exactly one source and one target state. States may have arbitrary number of incoming and outgoing edges, including zero. Transitions may have trigger and guard attributes, depending on whether their source state is an ordinary state or a choice state, respectively. In this paper, triggers and guards will be represented as simple strings constructed from events and guard expressions in the Erlang source code. In order to make the target state machines executable, further research could extend this approach to include a more sophisticated representation for trigger and guard elements. In the following sections the set of all states in a speci c state machine instance will be denoted as VF SMG, while the set of all transitions will be denoted as EF SMG. Let Init be the following set of gen fsm callback functions:
Init d=ef finit/1; handle event/3; handle sync event/4; handle info/3; code change/4g As per the speci cation of the gen fsm behaviour, the functions in Init, when triggered, can put the state machine in any arbitrary state, independently of the actual state. If we only consider the behaviour of an Erlang state machine in terms of states and transitions, but do not consider the memory changes (side e ects) accumulated during the execution, then it can be said that these functions e ectively restart the state machine. Therefore, it makes sense to model these as initial states, i.e. states from which the state machine execution can be started.
To describe the transformation rules we will use a textual notation to denote a mapping from nodes in the
SPG and states in the state machine, and also its inverse, a mapping from states to nodes. Since we previously
distinguished four types of states, we will use a di erent function for every type: each of these maps a node to
a state with the associated state-type. All these functions can be de ned to be invertible.
state 2 VSP G ! VF SMG maps nodes to ordinary states. The nodes mapped to ordinary states will precisely
be the semantic nodes representing transition functions, i.e. the user de ned callback functions of the gen
fsm behaviour, bearing the name of a state. We chose these nodes, since they have a 1:1 correspondence
with the states of the state machine implemented by the analysed Erlang module.
choice 2 VSP G ! VF SMG maps nodes to choice states. The nodes mapped to choice states are either
representing functions with multiple clauses, or they are representing branching expressions. For brevity,
in this paper we only touch upon the latter { and simpler { case: branching expressions. We presented
handling of the former case in [
After applying the transformation, every state in the target state machine will correspond to a node in the SPG, and every transition in the target state machine will correspond to an edge sequence in the SPG. In Section 4 where we describe the transformation rules we will denote this state-node correspondence relation with the function node : VF SMG ! VSP G. The node function is de ned as the inverse of the node-state mapping described earlier. Thus, if we regard the earlier functions as relations, i.e. sets of ordered pairs, then node d=ef (state [ choice [ stop [ init) 1 Since the range of these functions are pairwise disjoint, and all four functions were invertible, node always exists.
In the de nition of the transformation rules, we also use a textual notation to denote the trigger and guard labels of the transitions. As mentioned earlier, we represent these as simple human or machine-readable strings. The set of all strings will be denoted by S.
trigger 2 VSP G ! S maps nodes representing the rst parameter pattern of a transition function to a string. For example, the string may consist entirely of the Erlang term denoting this parameter. guardbranch, guardif , guardtry, guardcatch,guardafter and guardclause 2 VSnP G ! S functions map nodes representing the pattern and guard expressions of the clauses of the various branching expressions can be found in the Erlang programming language. Since it may be necessary to use more patterns and guard expression to uniquely identify a state machine guard, we assume these functions can handle more parameters. The exact value of n depends only on the guard function it describes. 3.3
In this section we present an algorithm, that { with the help of a prede ned set of transformation rules { transforms the semantic program graph of any Erlang state machine adhering to the speci cation of the gen fsm behaviour, to a state machine model described in UML or the simple state machine language we introduced in Section 3. Since most of the application speci c logic (the logic related to the RefactorErl semantic program graph) of the transformation are encoded in the transformation rules, the algorithm itself is relatively simple. Basically it is an extended depth rst search, that selects the neighbouring nodes to discover, based on prede ned rules.
This approach has several advantages. To extend the transformation for currently unhandled cases, we do not have to modify the procedural algorithm, we only have to add more rules to the transformation sets. For example, UML o ers several state machine features (e.g. embedded state machines, variables, e ects) that could be utilised by the transformation, after the rule set were to be appropriately extended to handle these cases. Also, the rule sets encapsulate the RefactorErl speci c logic, which means we could use the same algorithm with other static analysis frameworks too. We just have to swap the RefactorErl speci c rule sets to the rule sets speci c to the other static analysis framework. It is worth noting though that devising a rule set, in general, is not a trivial task. Finally, this approach opens up the possibility to execute rules in parallel, to achieve better runtime performance.
Informally, our transformation algorithm, together with the rules presented in Section 4, will perform the
following tasks:
1. Starting with the transition functions in Init, the algorithm analyses the return point of each transition
function it visits.
2. If during the analysis, it discovers an branching expression or a function with multiple clauses, denoted as b,
the corresponding choice(b) choice state will be added to the state machine. Then the algorithm continues
by analysing the return points of each clause of the b branching expression or function.
3. If during the analysis a t tuple is discovered, it will further analysed t to decide whether it indicates a stop
state, or an ordinary state. In the former case, the corresponding stop(t) stop state will be added to the
state machine, and the algorithm backtracks. In the latter case, it will analyse the appropriate element of
t (see the gen fsm speci cation [
More speci cally, our algorithm will perform these generic tasks in three separate stages: an analysis stage, a transformation stage, and a synthesis stage. In the analysis stage, our goal is to discover precisely those nodes and edges in the SPG that will be mapped to state machine elements in later stages. The result is a ltered SPG, called the analysed SPG, consisting only these nodes and edges. The edges are relabelled with semantic information about their role in the future state machine. The transformation stage eliminates nodes and edges from this analysed SPG, so as to obtain a reduced SPG that can be mapped to a state machine instance with relative ease. The synthesis stage will map the reduced SPG to a state machine instance, producing the nal result of the transformation.
The general algorithm with the three stages is denoted on Figure 1. All three stages will start a depth rst algorithm from the function nodes in the Init set or, in the case of the synthesis stage, init(Init), the set of the initial states corresponding to the nodes in Init. For certain edges we will not continue the analysis, i.e. will not extend the target nodes of these edges. The types of these edges are listed in the Exclude1 set.
Later in this paper we will de ne separate rule sets for each of these stages. Rule sets R1 and R2 { corresponding to the analysis and synthesis stage respectively { are side-e ect free. By matching the left hand side of the rules to a graph, their right hand side can be used to construct another graph. Rules in rule set R3 { Algorithm 1 DiscoverF SM G(SP G; R1; R2; R3) 1: Init finit=1; handle event=3; handle inf o=3;
handle sync event=4; code change=4g 2: Exclude1 ftri;gger; co;nd ; fsm;guardg 3: RelationGraph discover(Init; R1; Exclude1; SP G) 4: T RelationGraph transf orm(Init; R2; RelationGraph) 5: F SM G discover(init(Init); R3; ?; T RelationGraph)
corresponding to the transformation stage { are not side-e ect free. By matching their left hand side in a graph, their right hand side can be used to modify this same graph.
The analysis stage and the synthesis stage will make use of the same backtracking algorithm, that tries to pattern match every rule to an environment of the current node, and determines the next neighboring nodes to visit using the matching rules. The transformation stage makes use of a slightly modi ed backtracking algorithm. This one will try to apply a rule to a node as many times as possible, before moving on the next node. After it visited every node, it will proceed to repeat this procedure with the next rule. The stage ends when the last rule was applied as many times as possible to every node in the graph. 4
As mentioned earlier, the transformation is realised by two backtracking algorithms, that are performing pattern
matching on their respective input graphs with the left hand side (LHS) of certain set of rules, and then apply
the right hand side (RHS) of the matching rules to construct an output graph, or { in case of the transformation
stage { to modify the input graph. This section describes the algorithms referenced by Figure 1 and outlines
the rule sets utilised by the analysis, transformation and synthesis stages. The keep the discussion concise, we
only selected a few rules to present here, and these can only be used to transform small, simple state machines,
like the one demonstrated in Section 5. We presented more elaborate rule sets capable of transforming large,
complex state machines, in the appendices of [
First, we introduce a notation that will be used to denote these rules. The LHS of the rules will consist of edge patterns and logical expressions, featuring relations between nodes of the input graph. In these rules, x always denotes the node that the pattern matching must start on, while other variable names are arbitrary. For example, if a rule has the pattern x de!f y 2 SP GE as its LHS, then the rule matches on some x0 node of the input graph if and only if there is an edge, between the nodes x0 and some arbitrary y0, with the label def. We use a shorthand notation for connecting relations: we write x ! y ! z SP GE instead of x ! y 2 SP GE ^ y ! z 2 SP GE . Edges in the semantic program graph are ordered: we denote restrictions on the sequence number of an edge by denoting the number after the edge label. E.g. a rule with x clause=!2 y 2 SP GE in its LHS matches on x0 only if there is an edge with the label clause and the sequence number 2 between x0 and some other node. Unnumbered edges in the patterns may match edges of the input graph with arbitrary sequence numbers. Nodes in the semantic program graph can also possess various properties: we denote restrictions on a property of a node with an equality expression between braces after the node. E.g. x[type = tuple] elem=!1 y 2 SP GE matches on some node x0 only if the pattern x elem=!1 y 2 SP GE matches and the type property of x0 is of the value tuple. Pattern nodes without property restrictions may match nodes with arbitrary values on their properties. 4.1
In the analysis stage we traverse part of the semantic program graph of RefactorErl to identify all the nodes used by the following stages, and to attach transformation-speci c semantic information to the edges by relabelling them. This traversal is done by the backtracking algorithm described in Figure 2, utilising the rules collected in Table 1.
The backtracking algorithm in Figure 2 starts by visiting and expanding the nodes in the Init set. To expand a node x0, it iterates over all the rules in Table 1, and tries to pattern match these rules on x0. For any matching rules, it adds the RHS of the matching rule to the node in the output graph, corresponding to x0, and puts the Algorithm 2 discover(Init; Rules; Exclude; G) 1: V Init 2: E ? 3: V isited ? 4: S stack(Init) 5: while S 6= ? do 6: v S:pop() 7: if v 62 V isited then 8: V isited:add(v) 9: N Edges ? 10: for r 2 Rules do 11: N Edges:add(r:match(G; v)) 12: end for 13: for e 2 N Edges do 14: E:add(e) 15: V:add(endpoint(e)) 16: if e:edgetype() 62 Exclude then 17: S:add(endpoint(e)) 18: end if 19: end for 20: end if 21: end while 22: return (V; E) endpoint, denoted in the rules by y, in the stack to expand later. If the type of the edge in the RHS of the matching rule is featured in Exclude, then the y endpoint will not be expanded. As both the input graph and the rule sets are nite, the backtracking algorithm is guaranteed to terminate, and operates in polynomial time.
Apart from identifying the neighbouring nodes to be visited by the backtracking algorithm, the rules in Table 1 describe how certain edge sequences encountered in the semantic program graph will be labelled in the analysed semantic program graph. These labels indicate the semantic roles of the endpoints of their respective edges, and these roles will determine how each node will be treated in the subsequent stages. Labels ;s0 and ; denote a s transition function node at their source, nam;eof connects an atom with a function with the same name as the value of that atom, and the edges with tri;gger and co;nd labels point to nodes that will be used to construct trigger and guard labels in the nal state machine. The fs;m0 label is a special label that needs to substituted to other labels as speci ed by Table 2. This substitution only serves to make our de nition more compact: it can be eliminated in design time by adding new rules by combining the conditions of the rules in Table 1 and Table 2. Because of this, the substitution step does not need to appear in the algorithm either. As for the labels appearing in Table 2, ;c denotes a branching expression at its source, ;a0 and ;a denote ordinary functions, ;e points to a tuple that will be mapped to a stop state, and ;t points to a tuple which contains the name of a state in the state machine. The label ;0 does not convey any speci c semantic meaning, it is only used to specify the next nodes to be visited by the backtracking algorithm.
In later stages, transition functions will be mapped to states, and each function clause will correspond to a state transition leading out of that state, with a trigger label constructed from the rst parameter (the event) of the clause. Since the gen fsm speci cation allows for multiple clauses to have the same event, this mapping could results in non-deterministic state machines. To avoid this, we introduce a choice state for every group of clauses with the same event. This way there will be only one transition for each event between the original state and the choice state, and we will use guard labels on the transitions leading out from the choice states to distinguish between clauses in the same group. Ordinary functions with multiple clauses, similar to branching expressions, will be mapped to choice states, while those with single clauses do not have to be denoted in the resulting state machine.
In Table 2, the predicate multiclause(x) is true i the node x is a node in the semantic program graph, representing a function with multiple clauses. Let s denote a relation between function clauses, and let c1 s c2 be true for c1; c2 of a function i their rst parameter patterns are identical. As s is an equivalence relation, it partitions the clauses of a function into equivalence classes. In Table 1 the predicate multiclausegroup(x) is true i the node x represents a transition function with multiple clauses and there is at least one class of s with at least two elements, i.e. the function has at least two clauses with identical rst parameter patterns. If x is an atom, f ind(x) denotes the set of all functions with the same name as the value of x.
LHS x de!f y 2 SPGE ^ : multiclausegroup(y) x de!f y fclause=!i cl pattern=!1 patt SPGE x[type=atom] 2 SPGV ^ y 2 find(x) x[type=funcjfun expr] fclause=!i clause cre!t y SPGE type(x) 2 fif exprjcase exprjtry exprjreceive exprg ^
x (exprcljcatchcljaftercl)=!i cl cre!t y 2 SPGE type(x) 2 fcase exprjtry exprjreceive exprg ^
x exprcl=!i cl pattern=!1 patt SPGE x[type=case exprjtry expr] exprc!l cl1 2 SPGE ^
x headcl=!i cl2 cre!t y SPGE x trig;ger=i patt x nam;eof y x fsm;0=i y x condb;ranch=i patt x cond;head=i y
x fs;m0 y
Condition (x; y) type(y) = if exprjcase exprjtry exprjreceive expr type(y) = f uncjf un expr ^ : multiclause(y) type(y) = f uncjf un expr ^ multiclause(y) type(y) = atom
type(y) = tuple ^ y elem=!1 z 2 SP GE ^ In the transformation state we reduce the analysed semantic program graph to acquire a graph that can be easily mapped to a state machine. For this stage we slightly modi ed the backtracking algorithm. This algorithm iterates over all the rules in a predetermined order, and in each iteration it visits the nodes of the analysed semantic program graph to apply the actual rule as many times as possible. Since the matching rules speci ed in Table 3 always eliminate some of the edges from their LHS, the algorithm is guaranteed to terminate. Since eliminated nodes will not be visited again, this algorithm also operates in polynomial time. Algorithm 3 transf orm(Init; Rules; G) Require: Rules is ordered according to the transformation rule set 1: for r 2 Rules do 2: V isited Init 3: S stack(Init) 4: while S 6= ? do 5: v S:pop() 6: if v 62 V isited then 7: V isited:add(v) 8: do 9: success r:execute(G; v) 10: while success 11: S:add(G:children(v)) 12: end if 13: end while 14: end for
We used a procedural approach to describe the rules for this stage: the RHS of these rules contains simple
statements that are inserting or removing edges to or from the input graph. If the LHS of a rule matches, the
modi cations speci ed in the RHS are performed on the input graph. As mentioned previously, we only included
in this paper those rules that are necessary to demonstrate the transformation of a small example state machine,
and a more elaborate extended rule set capable of transforming any Erlang state machines is presented in the
appendices of [
) 9i1; :::; in (n
1) :
R 2 ft; 0g ^ S 2 fa; c; e; sg ^
x R;=i y ;S z x14 x15 x16 x11 x12 x13 8k 2 fi1; :::; ing (insert(x e;=k z)) ; 8k 2 fi1; :::; ing (
remove(x e;=k yk nam;eof z) 8k 2 fi1; :::; ing ( insert(x S;=k zk) ; remove(y S;=k zk) ) ; remove(x ;s0 y) insert(x S;=i z) ; remove(x R;=i y ;S z) 4.3
In the last stage we map the reduced analysed semantic program graph to a state machine. The purpose of the previous transformation stage was to make the rules in the synthesis stage simpler. As shown in Figure 1, this stage reuses the backtracking algorithm in Figure 2 with the rules speci ed in Table 4. This time the algorithm expands states instead of program graph nodes. In the analysis stage, the LHS of the rules were pattern matched to the input semantic program graph, and the news edges identi ed by the RHS were added to the output analysed program graph. In the synthesis state, the input graph is the reduced analysed program graph and output graph is a state machine, thus the LHS pattern matching is performed on the reduced analysed graph, while the new edges in the RHS are transitions, which are added to the state machine. Similar to the fs;m0 label of the rst stage, the la!b labels in the RHS of the rules in Table 4 can be substituted according to Table 5. Again, this label substitution is only required to keep the description concise, and it can be accomplished during design time by adding new rules that combine the corresponding conditions and rules of the two tables.
LHS node(v) ;e y[type6=tuple] node(v) ;e y[type=tuple] node(v) ;c branch v la!b stop(y) v la!b choice(branch) node(v) fsm;0=i node(u) ^
condb;ranch=i patt1 ^ node(v) con;dhead hd
trigger(patt) guardbranch(hd; patt1) 5
In this section we demonstrate the transformation method previously introduced, by presenting the intermediate results of the transformation of a small Erlang state machine. Although we intentionally selected a simple state machine for this example, an implementation of the transformation was also successfully tested on large state machines selected from open source Erlang applications. The code of the example state machine shown in Figure 3 describes the language of identi ers: words starting with letters and proceeding with letters, numbers or underscores. We omitted from the source code some of the callbacks required by the gen fsm speci cation, and also those functions that can be used to interact with the state machines to initialise the state machine, and to send events to it. In this example events could be letters read from some input word. The state machine accepts identi ers ending with the line ending character ($nn), and rejects every other words. The initial state of this state machine is pos1, where it transitions to a rejecting state upon receiving a non-letter character, and transitions to posOther state upon receiving a letter. In posOther, it transitions to an accepting state upon receiving a line ending character, stays in posOther upon receiving alphanumeric characters or underscores, and transitions to a rejecting state upon receiving any other event. E r o t c a f e
The rst stage of the transformation applies the algorithm in Figure 2 to the semantic program graph. The result of this analysis stage is shown in Figure 5. This stage identi es all the nodes used by the following stages and attaches transformation-speci c semantic information to the edges by relabelling them.
The rst node to analyse is the init/1 function node, since init/1 is element of the Init set. This function has only one clause, thus the rst rules that match are x2 and x3. At this point the resulting graph consists of the edges ;s0 and trig;ger=1, and their nodes. Since trig;ger=1 is a member of Exclude1, we will not expand the target node of this edge. The next node to expand, as speci ed by x2, is the form node. The rule x5 matches, thus we add an fs;m0 edge to the result graph. We may choose to do the substitution of fs;m0 right now, based on Table 2, swapping it to ;t. The left hand side of x9 matches the tuple node, thus after substituting fs;m0, we add an ;e edge to the result. Finally x4 matches on the atom node, thus we add to results a nam;eof edge, pointing to the semantic node of the pos1/3 function. At this point the analysis of the init/1 function concludes, since we found the name of the rst state, and the next function to analyse.
On the pos1/3 function node we can match x2 and x3 again, since all the clauses of pos1/3 have di erent events. Now, we can match x5 on two branches, one for each clause. The rst tuple represents a stop state, thus we have to substitute fs;m0 by ;e. There are no rules matching on this branch, thus the algorithm backtracks to the other branch. In the other branch fs;m0 is substituted to ;c. We can match x6, x7, and x8 on the case expr node and its clauses. Again, con;dhead, and cond;branch are in Exlcude1, thus their target nodes { used in later stages to construct guards for the state machine { will not be expanded. In the left branch that matched x6, we substitute fs;m0 by ;t, and then continue the analysis of this branch by matching x10 on the tuple, and swap fs;m0 with ;e. Finally, we nd the posOther/3 function node by matching x4. The analysis of posOther/3 is almost identical, except that the last matching of x4 will result in a nam;eof edge pointing back to the posOther/3 itself. With this the analysis stage concludes.
In the transformation stage we start with the analysed program graph, resulting from the analysis stage, shown in Figure 5, and reduce it to graph, that can be mapped to a state machine model relatively easily. The result of the transformation stage is depicted by Figure 6.
Since in this example the state machine we transform is small, we only have to use a few reductions. To reduce
the analysed semantic program graph of larger state machines may require more kinds of reduction rules, which
are described in the appendix of [
In this stage we map the reduced analysed program graph, shown in Figure 6, unto a state machine model,
depicted by Figure 7. First, we add init(init=1) (the initial state created from the function node of init/1)
to the state machine, since init/1 is the only element of Init in this example. The rule x14 matches the node
corresponding this state (i.e. init/1) with the function node of pos1/3, thus we add state(pos1=3), and a
transition to the state machine. We may choose to do the substitution of la!b right now based on Table 5,
swapping it to trigger label constructed from the joker pattern pointed by the trig;ger=1 edge. Next, we can match
both x15 and x16 on the pos1/3 node. The former results in adding a stop state to the state machine, while
the latter results in adding a choice state. To substitute la!b for a trigger, as speci ed by the substitution rule,
we have utilise the edge numbering to select the pattern nodes corresponding to each transitions: the pattern
pointed by trig;ger=1 will be used to label the transition of the stop state corresponding to the tuple node pointed
by e;=1, and trig;ger=2 for the choice state corresponding to the branching expression pointed by e;=2. Next, x14
and x15 matches on the node of the choice state. This time, la!b is substituted to a guard, constructed with
the appropriate expressions pointed by the con;dhead and cond;branch edges. With the match of x14, we added
state(posOther=3) to the state machine. The corresponding posOther/3 node can be analysed similarly to
pos1/3. Finally, we get the result of the transformation, a complete state machine, as shown in Figure 7.
To test and measure the previously presented transformation method during actual physical execution, we also
created a reference implementation in Erlang. Instead of creating an application that communicates with a
RefactorErl instance via some remote communication protocol, we realised the implementation by extending
the source code of the open source RefactorErl framework to eliminate the need of creating a bridge, and to
minimise the number of dependencies. To implement the matching rules, we were able to make use of the function
clause pattern matching in the Erlang language, and used memoisation technique to avoid repetitive evaluation
of functions called from multiple places in the source code. We also implemented a few small extension not
mentioned in this paper. For example, initialising special states to stand in place of undiscoverable states, or the
recognition of a state machine based on the functions calls that start that state machine. We also used Erlang
to generate the XMI les storing the resulting UML state machines, and used txtUML [
We executed the implemented algorithm on Erlang state machines found in large, popular, open source Erlang
applications. Our sample state machines are from the sources of the Ejabberd communication server [
Our results are summarised in Table 6, containing, for each Erlang state machine module the number of lines of code in the module, the number of discovered states and transitions in the resulting state machine, and the runtime of the transformation (minimum, maximum, average, median runtimes in microseconds). To measure runtime, we repeated every measurement 500 times for each le, thus creating a 500 element sample for each Erlang state machine. The runtime data does not include the time needed to load the respective Erlang applications in the RefactorErl databases, since this operation only has to be performed once for every software application, and in general, the size of the complete application source code is expected to be independent from the size of the individual Erlang state machines the application contains. Since the resulting state machines usually contain choice states, the measured number of states and edges are expected to be higher than the (ordinary) states explicitly de ned by the Erlang state machines.
File name ejabberd c2s ejabberd http bind ejabberd http ws ejabberd odbc ejabberd s2s in ejabberd s2s out ejabberd service
eldap mod irc connection
mod muc room mod proxy65 stream mod sip proxy riak kv 2i aae riak kv get fsm riak kv put fsm riak kv mrc sink ssh connection handler tls connection
Taking our use case into account, fast runtimes are not of critical importance to the success of the transformation. However, even the slowest execution time, measured with tls connection module in Erlang OTP, is quite small with 3 seconds. We have to remind the reader though, that we used memoisation in the implementation to optimise the runtime: without the elimination of repetitive SPG branch evaluations, the algorithm would be noticeably slower.
According to Figure 8 (after eliminating the outlier tls connection), the number of lines positively correlates with time needed to execute the transformation. This phenomenon can be explained by the fact, that the algorithm needs more time to analyse deeper function return points, and the depth of these return points are likely correlated with the length of the source code of the module. Although not shown here, the same connection can be observed between the states in the resulting state machines and the transformation execution time. Since we mapped branching expressions to choice states, and deeper function return points are more likely to contain such branching expressions, it is also more likely that we will create more choice states for those state machines with deeper return points and longer transformation execution times. Figure 9 also shows a positive, although less de nite correlation between the number of lines and the number of states. Using the same reasoning, we conjecture that deeper function return points will have more lines, and are also more likely to contain branching expressions. Conversely, Erlang state machines with more states, and therefore more transition function de nitions, are also more likely to contain more lines of code. Still, because of the low number of state machine modules in the samples, these assertions probably require more thorough research with a bigger sample size, and perhaps with the use of more advanced metrics. 7
While most CASE tools support source code generation from UML models, the inverse operation, generation of
UML models from source code (code-model transformation) is less prevalent. This is probably explained by that
code-model transformation requires complex static and/or dynamic analysis tools. For the most popular
objectoriented languages, industrial tools suitable for this task usually support the discovery of UML class diagrams
and sequence diagrams from the program sources. Such tool are for example ObjectAid [
Model transformations, a recent, but well researched area can also be of interest concerning state machine
transformations. While this methodology is mostly used to specify and execute transformations between models,
it can be extended to also handle entities not usually considered to be models, such as syntax trees. Closely
related to the topic of our current paper, we presented a procedure to map a subgraph of the SPG of RefactorErl
to an SPG model by utilising triple graph grammars [
Similarly to the tool introduced in the present paper, Erlesy [
There is also a mature methodology for discovering deterministic nite state machines using dynamic code
analysis, called state machine induction and behavioural inference. Procedures applying this methodology
execute the analysed program based on speci c use case scenarios (e.g. a sequence of function calls), and collect
information to generate a state machine model. This task requires the elimination of non-deterministic
transitions, and transitions featuring recurring execution traces. Such state machine reducing methods are the k-tail
algorithm, and the QSM algorithm. QSM o ers the user various valid reductions, and proceeds to perform the
reductions chosen by the user. Later methods can eliminate the need for these user dialogues by utilising static
source code analysis to nd good answers automatically and with high precision [
While the dynamic approach to state machine discovery enjoys bene ts from the well de ned methodology,
the requirement for use case scenarios hinders its usability for large systems. With static analysis, it is possible
to discover the complete state machine, relying only on the source code. One of the di culties arising from
using static analysis is identifying the relation between the implementation level programming patterns and high
level state machine concepts. And even if we solve this problem, in some special cases it is still impossible for
pure static analysis to lter out components (e.g. states, transitions) that can be never reached during program
executing (e.g. because of conditions that can only be evaluated to false). Thus, it can be stated that both
the dynamic and static analysis approaches have their advantages and disadvantages, therefore the choice is
dependent upon the goals and requirements of the task at hand. Our approach strongly relies on static analysis,
since the requirements of the gen fsm behaviour [
In this paper, we introduced a method to transform Erlang state machines, implementing the gen fsm behaviour, to state machines described by UML, or similar state machine languages. To analyse Erlang programs, we used the RefactorErl static analysis framework. We also de ned an UML-compatible state machine representation to denote the target state machines of the transformations. The presented method consists of three stages: an analysis stage, a transformation stage, and a synthesis stage. In each stage, a backtracking algorithm is executed on the output of the last stage (or, in the case of the rst stage, the RefactorErl Semantic Program Graph), and each stage utilises a separate set of transformation rules by means of pattern matching. The algorithms themself are general enough not to depend on any static analysis framework, only the presented transformation rules depend on the structural details of the RefactorErl Semantic Program Graph. By separating the algorithm and the rules, we made it more easier to the extend of the transformation: one just has to add more rules to the rule sets. By specifying the bulk of the transformation logic by rules, we also made it possible to parallelise the algorithm to optimise it for environments with multiple processing units. We demonstrated the execution and the results of each stage by a small example. We were able to realise a relatively fast implementation of the algorithm. After testing our implementation on state machines selected from the source code of large, popular, open source Erlang applications, we concluded that the time needed to perform the transformation on an Erlang state machine is positively correlated with the number of lines of code in the program code of the state machine. We also found similar correlation between the transformation execution time and the states created by the transformation. We explained both phenomenon by conjecturing that deeper return point expressions need more time to be analysed, probably have more lines of code, and contain more branching expressions.
The evaluation of our implementation evidences that the method presented in this paper can be used to construct UML state machine models, even from large and complex Erlang state machines. Still, several opportunity remains for improvement, for example by extending the analysis with more elaborate RefactorErl queries to discover even more state machine elements, or by targeting an even larger subset of all the features provided by the UML state machine language, or even by preparing the method to generate executable state machines.