Active Operations are a set of operations that can be composed to build incremental bidirectional OCL-like expressions on collections. Each operation is capable of updating its result (resp. source) when a change occurs on its source (resp. result). The current implementation of active operations relies on the Observer design pattern to propagate changes from each operation to its successors. These relations form an implicit directed acyclic propagation graph. Previous work showed that this approach is limited and alignment issues appear in some situations. Several workarounds were proposed to mitigate these issues. In this work we present a new relational notation to describe propagation graphs. Along with this notation, we also present a new static analysis method of the propagation graph based on process algebra. This new method enables optimizations of the propagation graph not achievable with previous approaches, such as detection of parallelizable sections of the propagation graph or cache optimizations in speci c situations.
In Model-Driven Engineering (MDE) [
The incremental evaluation of transformations has many advantages since it reduces the amount of computation required to obtain a new target model, after a developer has updated a source model, or even the reverse case. The main purpose is then to devise more responsive systems for the model designer. Another purpose is to avoid creating new target elements, but rather to update existing ones, which may be connected to other kinds of objects (e.g., view objects). Creating new elements would break such connections. For instance, an incremental execution can be used to update target models in-place and to update the target model's visual representation automatically.
Active operations [
In [
The paper is organized as follows. section 2 describes the problems due to implicit propagation and previously presented approaches. section 3 de nes the main concepts used in our approach. section 4 presents the method used to build a process algebra formula from a given propagation graph. Then, section 5 presents several possible outcomes of our analysis method. We discuss about other interesting properties of the approach in section 6 and section 7 provides some concluding remarks. 2 2.1
Active Operations consist of a set of OCL-like operations operating on collections (e.g., collect, select but also zip and zipWith4). After initialization, each operation maintains synchronization between its source and its result. If the 3 Called propagation graph in the rest of the paper. 4 Borrowed from functional languages like Haskell. source is modi ed, the operation incrementally computes how the result should be changed to maintain synchronization. By composing these simple operations in a functional way it is possible to build complex incremental expressions. Active Operations can operate in both unidirectional and bidirectional mode. In this work we focus on unidirectional transformations but similar concepts could be applied to reverse change propagation.
The current implementation of Active Operations relies on the well-known Observer design pattern. Each value is boxed so that it can be observed. Operations observe changes on their sources and react whenever an update occurs. An operation then computes the corresponding target updates and noti es its successors (i.e., next operations). This process is called Observer-based propagation. Source boxes are boxes that are not computed by operations and thus that correspond to entry-points of the transformations (i.e., properties of source model elements). 2.2
Problem statement illustrated on motivating examples We use a graph to represent the propagation process. Nodes correspond to operations and boxes5. Small black dots correspond to inputs and outputs of operations, which can have several inputs and outputs. Arrows connect outputs of upstream operations to inputs of downstream operations.
For instance, the graph in Figure 1 corresponds to the following expression,
which is the motivating example from [
A more complex example with multiple source boxes is presented in Figure 2, which corresponds to the following expression: def : g ( a , b ) = l e t v1 = a >A ( ) in l e t v2 = a >B ( b ) in l e t v3 = v1 >C (v2 ) in l e t v4 = v2 >D ( ) in l e t c = v3 >E (v4 ) in c Note that in this example we used dummy operation names (as our approach only cares about the shape of the graph) and removed intermediate boxes from the graph representation.
In [
These problems occur when there are several paths between a given source
box and operation. For instance, with a depth- rst traversal of the propagation
graph, the expression depicted in Figure 1 would notify the zip operation twice,
which would also notify d twice. In [
Another possible approach, presented in [
In this paper, we present a new approach also based on an explicit propagation graph but that uses the process algebra formalism to de ne valid propagation ordering.
Active Operations are operations (such as bind, collect, select, union or zip) over collections (e.g., singletons, sets or ordered sets). After an initialization phase, which ensures that the inputs and outputs are in a coherent state, changes on the inputs are transformed into changes on the outputs so that both stay coherent. When combined, these operations constitute complex expressions.
For instance, let a = [1; 2; 3] (using the Haskell notation for lists), then the
following expression multiplies each value of a by 2 and then selects the multiples
of 3, h(a) = [
2) >f i l t e r ( e j ( e mod 3) = 0) in
Based on these expressions we derive the following relational notation. Let us consider the following sets: { O is a set of (active) operations (e.g. collect or lter in h) { is a set of ports that represent inputs and outputs of operations
, a transformation is de ned by the following relations : { in O describes the inputs ports of an operation { out O describes the outputs ports of an operation { L represents the links between the ports that describe the di erent interactions between operations in order to achieve the transformation.
{ 8(p; p0) 2 L; (9o 2 O; (o; p) 2 out) ^ (9o0 2 O; (o0; p0) 2 in) (elements of L are used to link outputs of an operation with the input of another operation.) A transformation is a tuple T rans = (O; in; out; L). However this tuple alone cannot ensure the transformation is correct. Hence a speci cation of existing operations is needed. 3.2
Operation speci cation Let us consider = f 1; 2; g a set of sorts and a set P = fp1; p2; g of port variables. Given an operation o 2 O we consider the two following functions : { Pin : O ! 2(P { Pout : O ! 2(P ) ) such that Pin(o) (resp. Pout(o)) de ne the set of sorted input (resp. output) ports of o.
Back to our zip example, we would have Pin(zip) = fleft : l; right : rg and Pout(zip) = fout : (l; r)g. Let us remark that (1) we denote pairs (p; s) of the Cartesian product (P ) as p : s and (2) that such a zip operation should be formally de ned for all relevant sorts s 2 .
An operation speci cation is thus a tuple Spec = (O; Pin; Pout; ).
We can list other operations such as: { collect: Pin(collect) = fin : ig, Pout(collect) = fout : og { select: Pin(select) = fin : ig, Pout(select) = fout : ig { concat: Pin(concat) = fin1 : s; in2 : sg, Pout(concat) = fout : sg
This list is not complete but we can generalize operations based on their arity. Let o1 be an operations with arity 1, it is de ned as Pin(o1) = fin : ig, Pout(out : o). For o2 a binary operation we have, Pin(o2) = fin1 : i1; in2 : i2g, Pout(out : o), and so on for arities greater than 2.
Some special operations may have ports named di erently for semantic reasons such as zip. 3.3
Validation of a transformation with respect to a speci cation Given an operation speci cation Spec = (O; Pin; Pout; ), and a transformation T rans = (O; in; out; L), we need to check if T rans is a valid instance with respect to Spec.
A transformation mapping from T rans to Spec consists in de ning the following mappings : { ports : in [ out ! Pin [ Pout { sorts : in [ out !
A transformation mapping T rans;Spec is thus a pair ( ports; sorts).
A transformation mapping is valid if the following conditions are satis ed : { 8o 2 O; 8p 2 { 8o 2 O; 8p 2 ; (O; p) 2 in ) ; (O; p) 2 out ) ports(p) : sorts(p) 2 Pin(o)
ports(p) : sorts(p) 2 Pout(o)
These conditions just ensure that the input/output speci cations of the operations are satis ed. 3.4
Graphical view of relational notation To ease the visualization of propagation in these expressions we introduce a graphical notation. It consists of a directed graph, nodes represent operations and arcs are links betweens them. An incoming (resp. outgoing) arc is an input (resp. output) parameter of an operation. If an operation has multiple inputs or outputs, each distinct input/output corresponds to a distinct black dot outside the operation. Arguments can be named to remove any ambiguity for operations with multiple inputs or outputs. An operation can have multiple inputs but only one incoming arrow for each of its input. An operation may have multiple arrows going out from a single output.
Figure 3 corresponds to the expression shown in subsection 3.1. b
The previous formalism allows us to represent an instance of a transformation that should be clearly related to a set of given speci ed operations, which have a speci c pro le (signature). For instance, a zip operation is represented by the graph shown in Figure 4. It should be noted that both inputs can have di erent types, which induce the type of the result.
left right zip
out
The foundations of process algebra have been developed by Milner [
We recall here the basic material related to process algebra that will be useful
in our context (we refer the reader to [
{ Actions: we consider processes that are composed of atomic actions a; b; c; or steps. Let A = a; b; c; be the set of atomic actions. { Operations on actions: atomic actions can be combined by means of operators in order to de ne more complex processes. The sequential composition, is denoted : (i.e., a dot, which can be omitted when there is no ambiguity). The alternative composition is denoted +. For instance, a:(b + c) is a process that executes the action a, then executes b or c and then stops. These two operators are the building blocks for complex processes. { Deadlock: we de ne the special action , called the deadlock. represents failure: once is reached, the process is blocked. In the previous example, a(b + c), once the process has executed a then b or c it gracefully nishes. If we consider a:b: , once a and b have been executed, the process fails since it cannot escape from the deadlock state. { Parallel execution: processes can be executed in parallel thanks to parallel composition operators. We note xky the process that starts with x or y and then executes the remaining of x and y in parallel. We introduce an auxiliary operator T such that xTy behaves like xky but forces to start with x. Therefore we have xky = xTy + yTx.
While k is su cient to describe basic parallelization, it does not allow us to describe situations where two processes have to communicate.
To model communications we de ne a partial binary function : A A ! A, where (a; b) represents the result of the communication between a and b. If (a; b) is not de ned then it means that a and b do not communicate. We use this function to de ne a new parallel composition operator j, such that ajb = if (a; b) is not de ned and ajb = (a; b) when it is de ned. Using this new operator we get xky = xTy + yTx + xjy.
Finally, we add the encapsulation operator @H , H A. This operator replaces every action in H by . For instance @H (a + b), with H = fa; c; dg, is equivalent to ( + b).This operator is useful to force communication between two processes. The axioms corresponding to the resulting algebra, de ned by A and the previously described operators and functions, are de ned below: A1 x + y = y + x A2 (x + y) + z = x + (y + z) A3 x + x = x A4 (s + y)z = xz + yz A5 (xy)z = x(yz) A6 x + = x A7 x = CM1 xky = xTy +yTx+xjy CM2 aTx = ax CM3 axTy = a(xky)
CM4 (x+y)Tz = xTz +yTz CM5 axjb = (ajb)x CM6 ajbx = (ajb)x CM7 axjby = (ajb)(xky) CM8 (x + y)jz = xjz + yjz CM9 xj(y + z) = xjy + xjz C1 ajb = bja C2 (ajb)jc = aj(bjc) C3 ja = HA xjyjz = 4
In order to generate an ACP formula corresponding to the propagation graph, we rst need to enrich the relational representation with intermediary operations.
First, we de ne Start = fo 2 OjPin(o) = ;g, the set of starting operations, these operations are the entry-points of the transformations.
To generate an ACP formula that is equivalent to the transformation, we need to split the transformation for each of its entry-points. To this aim, we need to de ne the notion of path between two operations.
There is a path from operation a to operation b, noted P ath(a; b) if any is veri ed: { 9(p; p0) 2 L; (9(a; p) 2 out) ^ (9(b; p0) 2 in) { 9o 2 O; P ath(a; o) ^ P ath(o; b)
The sub-propagation graph of a transformation t = fO; in; out; Lg for a given entry-point s, P T rans(t; s) = fO0; i0n; o0ut; L0g, is derived from t with : { O0 = fsg [ fo 2 OjP ath(s; o)g { i0n = f(o; p) 2 injo 2 O0g { o0ut = f(o; p) 2 outjo 2 O0g { L0 = f(p; p0) 2 Lj(p 2 i0n) ^ (p0 2
o0ut)g
The sub-propagation graph of an entry-point keeps only the operations, ports and arcs that depends on the entry-point. This sub-propagation graph of an entry-point corresponds to the part of the propagation graph involved in the propagation resulting from a change on that entry-point.
We need to add special synchronization operations in the transformations. They are required when an operation can be reached from an entry-point by more than one path. An operation o needs synchronization if 9o0 2 O; 9o00 2 O; o0 6= o00; P ath(s; o0) ^ P ath(o0; o) ^ P ath(s; o00) ^ P ath(o00; o).
Adding a synchronization operation is achieved by adding an operation and modifying the operation o that needs synchronization.
A synchronization operation, Syno, that takes all the inputs of the former operation o, Pin(Syno) = Pin(o) and has one output, is created. o is modi ed so that it takes only one input. Then a link is added between Syno and o. Figures 5a and 5b illustrate this step. Remark: because this transformation is only for static analysis, there is no need to consider how the actual data that ows from the inputs is merged into a single output, but one can imagine that the synchronization operation performs some kind of pairing.
Considering now propagation graphs with only one input and synchronization operations when they are needed, we can divide each synchronization operation that has been added in the previous step.
Each synchronization operation is split into multiple ones, based on its inputs. Let s be a synchronization operation. For each i 2 Pin(s), we create an operation si with Pin(si) = i and Pout(si) = ;. One of the newly created operations, s0 is selected to receive the output pin of s, Pout(s0) = Pout(s) and nally s is removed. We de ne Split(s) as the set of all the new operations intruded while splitting a synchronization node s, Split(s) = fsij8i 2 Pout(s)g. in2
C out
SynC out in
C out (a) Before adding synchronization (b) After adding synchronization in1 in2
SynCin1 SynCin2 out in
C
out (c) After splitting synchronization operation
Since the propagation graph has now been processed, it can easily be converted to an ACP formula. We de ne the function N ext : O ! O that returns all the operations directly connected to an output port of an operation. Let o be an operation. N ext(o) is de ned as:
N ext(o) = fo0 2 Oj8p 2 Pout(o) ^ 9p0 2 Pin(o0) ^ (p; p0) 2 Lg
Finally, we de ne R2ACP (o), a function that takes an operation and transcribes it to an ACP formula.
8 >N ext(o) = ;; > R2ACP (o) = <N ext(o) = o0; o o : R2ACP (o0) >>:N ext(o) = fo1; :::; ong; o : R2ACP (o1) k ::: k R2ACP (on)
This function returns an ACP formula for any given operation: the complete formula can be created by using the alternative composition between the formula of each entry-points of the transformation. We also need to add encapsulation to force a synchronization operation to wait for its counterpart.
X o2Start
This method can be seen as a tree traversal with sequential composition of operations when going down the tree and parallel composition between the children of an operation.
A complete example is shown in Figure 6. Labels on the ports were removed to make the reading easier. The graph in Figure 6a has only one entry-point, so we can skip the isolation of the sub-propagations graphs. In Figure 6b synchronization operation SyncC is added before C because it can be reached from B and D. Then, in Figure 6c the synchronization operation SyncC is split into two new synchronization operations SyncCB and SyncCD and the rst one is chosen to keep the output of SyncC . Finally, in Figure 6d a corresponding formula is given. Below the formula all allowed communications are listed (only SynCB jSynCD in this example). 5
Once the propagation graph has been transformed into a tree and after a corresponding ACP formula has been generated, the formula can be used to infer several interesting facts about the transformation.
The generated formula de nes all valid operations orderings. Thus it can be used to check if existing approaches generate correct orderings. It can also be used to generate new propagation orderings.
During the graph transformation, synchronization operations are added when needed. Adding these synchronization operations generates situations where synchronization is needed explicitly unlike the classical approach that consists in ignoring the rst noti cation. Therefore, it does not require a deep understanding of the propagation. Moreover, adding this operation also means that the zip and zipWith operations do not need to use a speci c algorithm to deal with alignments problems.
As observed in section 4, propagation graphs are split into sub-propagation graphs and a formula is created for each of these graphs. This means that only relevant operations are considered during propagation. This results in a specialized formula for each of the entry-points of the transformation.
Unlike topological sorting that can be used in breadth- rst propagation (as
proposed in [
A A
B D B
D (a) Propagation graph (b) Adding synchronization nodes
SynC
E SynCB SynCD
E
C C (c) Splitting the synchronization nodes
B : SynCB : C k D : (SynCD k E)
SynCB jSynCD = S (d) Corresponding ACP formula and communication function
Exploiting these parallel sections would not be di cult with a central algorithm
responsible for dispatching operation execution as proposed in [
Finally, with an explicit graph transformation and a corresponding formula, it is possible to detect patterns in the transformation. These patterns could be used to infer parts of the transformation where operations do not need to keep a cache. For instance, with a zip operation, it is usually convenient to keep a cache of its inputs in case a change arrives only on one of these inputs. In the current implementation it is not possible to detect situations where it can be proven that noti cations will always arrive in pair (e.g., Figure 1). Noti cations are said to arrive in pair if a change in a source box leads to two changes in the sources of a zip or zipWith operation, and if both changes of the pair always have the same index (e.g., both add an element at index 3). In this case, the operation does not need to keep a cache of its inputs because all information needed to compute the resulting output change is known to be available after both inputs have been noti ed. 6
In the previous section we presented several possible analyses o ered by the process algebra formula generated by our approach. In this section we discuss about other usages of the formula not directly related to propagation optimization.
In Section 3.5 we presented a small subset of process algebra. This subset
is su cient to express formulas corresponding to current propagation graphs.
However, there are many extensions and features that could be used to describe
currently forbidden propagation graphs, such as propagation graphs
containing cycles. In the current implementation, propagation graphs containing cycles
are not allowed. With a depth- rst propagation, such graphs can lead to in
nite propagation. Nevertheless, process algebra does support recursive formula.
Process algebra could thus provide an appropriate representation for such
propagation graphs. However this does not solve the termination problem of such
propagation. In order to solve this issue, it would be necessary to add a
mechanism to detect when the propagation should be ended (such as reaching a xed
point). This mechanism may be usable to represent transformations combining
classical transformations with constraints solving [
Another interesting point we did not investigate is the relationship between the source propagation graph and the generated formulas. During processing of the sub-propagation graph, after a synchronization operation is split, the rest of the propagation is attached to only one of the newly created synchronization operations. Each choice leads to a di erent formula. We believe that these possible formulas are equivalent and result in similar execution orders. This might be provable by showing that all possible formulas are bisimilar.
Moreover, due to the transformation process of the propagation graph, we believe that there is a possibility to rebuild a propagation graph from a given ACP formula. This would enable rewriting of the formula to be forwarded back to the propagation graph. The optimizations applied on the formula could be visualized on the propagation graph. 7
This paper is a follow-up to [
On top of correct ordering, process algebra comes with many interesting properties for propagation. One of them is the possibility to safely parallelize sections of the propagation.
Work partially founded by Angers Loire Metrople and RFI Atlanstic 2020.