Formal semantics

participate to all the possible join in correspondence with that fork, so as to en-sure that a single control state of M results from the join. Moreover, a box bx called by a fork either participates with an exit transition in all the join corre-sponding to that fork, or it never exists.

For eample, the machine in Figure 4.5 is well formed. The transitions are all well-formed and, in addition, the fork and join pseudonodes are in corre-spondence: the asynchronous fork transition t41 corresponds to the internal join transition t43 and and the entering by default transition t42 is in correspondence with the exiting by default transition t44.

• Σ is a non-empty alphabet of labels;

• ∆ is a transition relation, i.e., a subset of S× Σ × S;

• S0⊆ S is a set of initial states.

With reference to a DSTM D (see Definition 1), s ∈ S represents the current state of D including: (a) the current control locations, (b) the values of variables, (c) the content of channels, (d) the set of events produced by actions. Thus, the LTS in each step is always organized with a root node that represent the current node of the main machine, intermediate nodes which can be: (i) the name of a box, (ii) the name of a machine instantiated by the box addressed in its parent node, or (iii) the name of a vertex which represents the current node of a currently executing machine, addressed in its parent node. According to this organization, the leafs of the LTS can be the nodes of the currently executing machines.

The formal definition of the semantics is not the main focus of this thesis work. However, its definition is at the basis of the mapping process described in the Chapter5. This section provide the necessary background to support the discussion of the above mentioned chapter and to better state the constraints defined for DSTM.

According to this, there are some relevant aspects, of the DSTM formal se-mantics, that can be summarized as follows:

DSTM Machine evolution The evolution context of a DSTM machine is a se-quence of steps. A step is a maximal set of transitions which are triggered by the current set of available events, with some constraints:

• a node or a box cannot be entered and exited simultaneously in the same step (this is instead possible for pseudo nodes);

• events generated by the firing of a transition cannot trigger other transi-tions in the same step but only in the next one.

Parametric instantiation DSTM allows for dynamic instantiation of paramet-ric machines. This means that parameters are instantiated at execution time, when call transition are performed. Thus, parameters, do not hold values dur-ing the execution, but serve only as place holders for the actual values that are dynamically substituted when a call operation is performed. To allow such be-haviour a substitution function, associated with the corresponding call transi-tion has been defined. As a consequence, in order to define the semantics of a DSTM, the concept of ground machine has been introduced. A ground machine is

a machine where terms occurring in actions, triggers and guards do not contain parameters. Ground machines are obtained from parametric ones by applying the appropriate parameter substitutions.

Message exchange with the environment As stated above, the events gener-ated by the firing of a transition cannot trigger other transitions in the same step but only in the next one. This means that the messages generated during a step and sent over an external channel cannot trigger other transitions in the same step. This means that sequential firings of transitions are not allowed within a step and only transitions affecting concurrent processes can be performed within the same step.

Transition semantics A specific semantics for the transitions has been defined.

In particular, there are some transitions whose source and/or destination are pseudonodes. When such transitions fire, the machine lead itself in a non-stable state. Thus, in order to avoid the ambiguousness, there is the need to specify system behaviour with the respect to these cases. The transition of the language, that could lead to a non-stable state are:

• transitions exiting from an entering node;

• transitions exiting from the initial node;

• transitions entering in a fork or join.

In particular, the set of transitions crossing a fork can be seen as an hyper transition taking from a source and leading to many targets simultaneously, and, analogously, the set of transitions crossing a join can be seen as an hyper transi-tion taking from many sources simultaneously and leading to a target. To man-age such transitions the concept of Compound transition has been introduced. A Compound transition(CT) is a pair of two sets of transitions: incoming transitions and outgoing transitions; it is used to represent the evolution of the machine in the cases above discussed. According to compound transition, three different cases exist:

• Simple case: when a transition is between two nodes (or boxes), in the related CT both the incoming transition and the outgoing transition sets are made uniquely by the considered transition. The trigger, condition and actions of the CT are give by those of the considered transition.

• Fork case: the transition entering a fork and the corresponding transitions outgoing the same fork are grouped in the CT as follows: the incoming transitions set coincides with the transition entering the fork while the out-going transitions set is give by the set of the transitions exiting the fork.

In this the CT is executed as follows: when the transition belonging to the incoming transition set is executable (trigger and condition are evaluated true) it is taken and possible actions are hence executed; the outgoing set, instead, is executed immediately after the previous one as well as the re-lated actions, that are however executed in interleaving (that means with non-determinism in the execution order).

• Join case: the transitions entering a join and the corresponding transition exiting, are grouped in the CT as follows: the incoming transitions set coin-cides with the transitions entering the join while the outgoing set coincoin-cides with the transition exiting the considered join. The incoming transitions set is executable when all the triggers and the condition of the transitions in it, are evaluated true. When it happens, these transition are taken and the cor-responding actions are executed in interleaving. After that, the transition belonging to the outgoing set is taken and the related actions are executed.

Lets note that the outgoing transitions set is always executable since the transi-tions composing it cannot have trigger and condition (constrained by the syntax).

In the simple case, actions are removed in the incoming transitions set and put in the outgoing one, while, with the respect to the outgoing set trigger and condi-tion are removed. In addicondi-tion lets note that when more than one transicondi-tion enter a fork (respectively exit a join) different CTs are obtained, each one correspond-ing to a scorrespond-ingle of these transitions.