The active operations approach enables incremental evaluation of OCL-like expressions, and can also be used to implement incremental model transformation. Each active operation corresponds to a basic building block such as select, or collect, and encapsulates both its initial computation algorithm as well as its change propagation algorithms. Complex operations such as groupBy can generally be expressed using simpler operations such as select and collect, but have better performance with an e cient map data structure (e.g., a HashMap) as internal state. However, implementing new algorithms for each new kind of complex active operation is costly and error prone. In this paper, we introduce the Active Map active operation that can be used as a basis to express several complex operations, such as groupBy, without speci c propagation algorithms. Several complex operations are shown to be expressible in terms of the Active Map operation without sacri cing scalability when compared to ad-hoc implementations.
Incremental evaluation of OCL-like expressions, including in the context of model
transformation, has many potential applications. It can for instance be used to
improve the performance of querying or transforming rapidly changing models.
Another usage scenario is to update existing target models in-place to make sure
other connected elements (e.g., diagrammatic views) are updated automatically.
In order to address this need for incremental evaluation, active operations [
The Active Operations Framework (AOF) [
However, when scalability becomes an issue, some speci c operations require
ad-hoc implementations. This was notably observed in [
All such speci c operations cannot be integrated in a framework like AOF, otherwise its complexity would increase, at the risk of becoming unmaintainable. It would therefore be useful to de ne a single active operation using which operations like groupBy, and selectBy can be expressed without sacri cing scalability.
This paper presents such an operation called Active Map. This operation also wraps a HashMap, but provides general-purpose access to multiple changeable views, which makes it possible to express groupBy, and selectBy with it.
The Active Map operation makes it possible to express several other operations, while preserving scalability properties. It thus enables the uni cation of multiple operations relying on HashMaps to ensure scalability, and makes it easier for developers to create new scalable operations.
The remainder of the paper is organized as follows. Section 2 details the tackled problem, and gives a motivating example. The Active Map operation is de ned in Section 3, and its API is presented in Section 4. Section 5 presents several applications of the Active Map operation. Finally, some related work are discussed in Section 6, and Section 7 gives some concluding remarks. 2
This section states the problem in more details by starting with some context on operation reuse (Section 2.1) before explaining why preserving e ciency and scalability is not trivial (Section 2.2). Finally, Section 2.3 presents a motivating example. 2.1
When writing OCL code, developers use the set of operations (including iterator expressions such as collect, and select) provided in the OCL standard library to write their own expressions, or even create their own operations (e.g., using the def keyword). Having such a rich standard library makes the developers' job easier: they do not need to implement the same basic algorithms constantly. However, for OCL implementors, the richer the standard library, the more costly its implementation is. This is even more the case for incremental implementations: in addition to designing and implementing algorithms for speci c computations, algorithms for change propagation are also required for each possible kind of change: adding, removing, replacing, and moving elements. Moreover, these speci c algorithms also need to be tested. Non-incremental implementations must be tested for each corner case of their computation, but incremental implementations must also be tested for each propagation corner case for each possible kind of change. Then there is also maintenance cost.
Fortunately, many OCL operations can actually be expressed in terms of other operations, which is notably done in the OCL speci cation [10, Section 11.9, pp. 177{183] to de ne iterator expressions. For instance, reject is dened in terms of select, while exists and most others are de ned in terms of iterate. But, although not detailed in the speci cation, most non-iterator operations can also be expressed in terms of other operations, and some iterator operations can also be expressed without iterate. We can, for instance, reuse the syntax used in the OCL speci cation to de ne iterator expressions in order to express notEmpty in terms of size, includes, and exists in terms of select, and notEmpty, as well as express count in terms of select and size, as shown in Listing 1.1.
Listing 1.1. notEmpty, includes, exists, and count expressed using other operations 1 source >notEmpty ( ) = source >size ( ) <> 0 2 source >includes ( o ) = source >select ( e j e = o ) >notEmpty ( ) 3 source >exists ( iterator j body ) = 4 source >select ( iterator j body ( iterator ) ) >notEmpty ( ) 5 source >count ( o ) = source >select ( e j e = o ) >size ( )
Note that this syntax, although used in the OCL speci cation, cannot itself
be OCL compliant because OCL has no mechanism to de ne general lambda
expressions. Adding lambdas to OCL has already been discussed [
There are generally several ways to express one operation in terms of others. For instance, exists is de ned using iterate in the OCL speci cation, whereas we de ned it above using select, and notEmpty. Which expression of an operation in terms of others is the most useful depends on the context. 2.2
For incrementality purposes, expressing operations in terms of iterate is not especially useful. Indeed, iterate is hard to make e ciently incremental because it computes its result by successively applying its body to both each element of its source collection as well as the intermediate result it computed for the previous element. Therefore, a change to any element in its source collection requires recomputing the iteration for that element as well as all iterations for the following elements. This typically results in linear change propagation time: a change on any source element can entail retraversing the whole source collection.
There are consequently two main ways to preserve the scalability of all operations: 1. lots of code, and 2. smart rewriting. Writing speci c code for each operation (i.e., solution 1) results in more e cient code, but high development costs as mentioned at the beginning of Section 2.1. The second approach consists in implementing a relatively small number of basic operations, and nding a way to express most others in terms of the basic ones while preserving computational complexity. This second approach has a certain overhead, but as long as computational complexity is kept as low as possible, scalability is not threatened.
Let us, for instance, consider the operations de ned in Listing 1.1: notEmpty, includes, exists, and count. They are all directly or indirectly expressed in terms of size, which has trivial constant time propagation algorithms if it maintains the current size in a variable. This is true even if its source collection is a linked list, for which length computation requires linear time1. The current size variable can be incremented when an element is added to the source collection, or decremented when an element is removed from the source collection. Replacing, or moving elements has no impact on the size. notEmpty also has constant change propagation time when expressed in terms of size because the only other operation involved is comparing a scalar value (i.e., the result of size) to 0.
includes, exists, and count all require linear initial computation time because they need to traverse their source collections at least once. Expressing them in terms of select does not increase complexity since select can also be implemented with a linear initial computation time. Because size and notEmpty both have constant time propagation algorithms, includes, exists, and count can also have constant time propagation algorithms if select has constant time propagation algorithms. As a matter of fact this is the case if select does not need to preserve order, which is true here (only size of result is used): { Adding an element to its source results in adding it to its target if its body evaluates to true for that element. { Removing an element from its source results in removing it from its target if its body evaluates to true for that element. { Replacing an old element by a new one in its source can be treated as removing the old one, then adding the new one. { Moving an element in its source has no in uence on its target, because order does not need to be preserved.
Other expressions of these operations would not necessarily have constant change propagation time but may rather have linear change propagation time. This is notably the case when expressing exists in terms of iterate. 1 This is an example application of the classical time-memory trade-o : it is often possible to get a lower change propagation complexity by storing speci c data.
At this point, several interesting questions can be asked: (1) What is the
best change propagation complexity achievable for each OCL standard library
operation? (2) Is there a minimal set of operations from which all other OCL
standard library operations can be expressed while preserving scalability? (3) If
so, what is this minimal set? (4) What is the time-memory complexity trade-o
for each operation? However, they are all beyond the scope of the present paper.
The problem tackled in this paper is to de ne an operation that can be reused
to express operations that so far only have speci c implementations relying on
HashMaps, such as: groupBy, and selectBy. These operations are not in the
OCL standard but were introduced in [
The previous sections presented the problem of reusing operations while
preserving scalability, and concluded by focusing on the problem of nding a reusable
operation for cases where a HashMap is necessary to achieve scalability. One
such case presented itself (see [
Listing 1.2 gives a de nition of this groupBy operation in terms of collect, asSet, and collect. groupBy is de ned as a custom iterator expression taking a body that returns the keys by which the elements of its source collection must by grouped. The Set of keys is rst computed by collecting the results of calling groupBy's body over its source collection, and then converting it into a Set using the asSet operation. In a second time, a tuple is constructed for each unique key by collecting over this Set of keys. The left part of the tuple is set to the key, while its right part is set to the collection of elements having that key. This right part is computed using a select nested inside the collect. Because of this nesting of \loops", a naive implementation therefore has quadratic computation time. Moreover, even if a version of select with constant propagation time is used, there is one call to select per key. This results in linear propagation time when an element is added to or removed from the source collection, as well as when the key of an element changes. Depending upon its implementation, the asSet operation may also have linear propagation time.
Listing 1.2. Possible implementation of GroupBy in OCL 1 source >groupBy ( iter ator j body ) = 2 l e t keys : Set ( OclAny ) = 3 source >collect ( iter ator j body ( iter ator ) ) >asSet ( ) in 4 keys >collect ( key j
The implemented solution proposed in [
The previous section has motivated the need for a reusable operation able to wrap a HashMap in such a way that other operations requiring HashMaps to ensure their scalability can be expressed using it. This section de nes such an operation, which we call Active Map. Section 3.1 de nes the Active Map operation in terms of the views it keeps synchronized, and Section 3.2 extends this de nition to support multiple values per key. 3.1
The Active Map operation is inspired by the Map (or associative array) data type found in many programming languages, notably Java in which AOF is implemented. In Java, a Map (as de ned in interface java.util.Map) provides three collection views2: a set of keys accessible via the keySet method, a collection of values accessible via the values method, as well as a set of key-value mappings accessible via the entries method. When a Java Map is changed, its collection views are also updated. However, they are neither observable nor changeable from without the Map itself. As can be seen on Figure 1, the Active Map operation also provides these views, called after the corresponding Java methods. The central ellipse represents the Active Map operation, while the rectangles denote boxes. The two-ended arrows link the Active Map operation to the boxes it keeps synchronized.
Figure 1 also shows that there are two other boxes in addition to the three collection views. They both also correspond to the Java methods with the same names, but where the Java methods only return plain objects, they are also boxes for the Active Map operation. The reason is that they may be changed externally, or be made to change by the Active Map operation when propagating a change that occurred on one of its other boxes. These additional boxes are: size that contains a single integer whose value is the size of the Active Map, 2 As speci ed in the Javadoc documentation: https://docs.oracle.com/javase/8/ docs/api/java/util/Map.html. and isEmpty that contains a single boolean whose value is true if and only if the Active Map is empty.
Finally, each of the two \3D" boxes shown at the bottom of Figure 1 corresponds to a set of boxes. They correspond to Java methods that take a key as argument: get(key) that contains the single value associated to the key, and containsKey(key) that contains a single boolean indicating whether the Active Map has a mapping for that key. Each set contains one box per possible key.
An Active Map is consistent if all its boxes have the values a non-active Map would have. The purpose of the Active Map operation is to restore consistency upon changes: whenever a change occurs on any of its boxes3, it must update the other boxes so that it is again consistent.
entries keySet values size
isEmpty
Remark: calling the Active Map an operation may seem counter-intuitive to the reader. A Map is generally considered to be a data type, and a HashMap to be a data structure implementing such a data type (among other possible implementations). We could arguably have considered it a map box, or de ned it as a new kind of active data structure. The choice of calling it an operation may be controversial, but is based on the following consideration. Each active operation keeps a set of boxes synchronized. This set often has a xed size of 2, and simply consists of a source and target boxes. This is notably the case for collect, and select, which each have a source collection, and a result collection. An Active Map also keeps a set of boxes synchronized, even if this set does not have a xed size (there may be any number of get and containsKey boxes). This shared characteristic of keeping a set of boxes synchronized is why we call the Active Map an operation. 3 Conceptually, the Active Map operation maintains synchronization upon changes occurring on any of its boxes, and is thus multidirectional. This makes it quite versatile. However, depending on how a given Active Map operation is created, some of its boxes may be read-only, but this is implementation-dependent. Java4, but none is provided in the standard library. It is similar to a Map with collections as values, but is designed to hide its implementation. For instance, it is possible to add new entries without having to write the code that creates collections for new keys. One of the most notable di erences when compared to a Map is that the get(key) method of a Multimap returns a collection view instead of a single plain object. As a matter of fact the Active Map operation as de ned in the previous section already has get(key) boxes. Extending the Active Map operation to handle multiple values per keys is therefore mostly a matter of allowing multiple objects in the get(key) boxes. We therefore chose to extend the Active Map operation instead of de ning a separate Active Multimap.
An Active Map extended to Multimap, which we will simply call an Active Map from now on, is consistent if all its boxes have the values a non-active Multimap would have. The purpose of the extended Active Map operation can be summarized in the the same way as its non-extended version was: whenever a change occurs on any of its boxes, it must update the other boxes so that it is again consistent.
entries groupedEntries keys keySet values size
isEmpty
4 Guava notably provides a Multimap class: https://google.github.io/guava/ releases/23.0/api/docs/com/google/common/collect/Multimap.html, as does Eclipse Collections: https://www.eclipse.org/collections/javadoc/9.2.0/org/ eclipse/collections/api/multimap/Multimap.html.
The two previous sections de ned the Active Map operation in terms of the boxes it keeps synchronized, and in terms of how it should behave. This section presents its API: how its boxes can be retrieved (Section 4.1), and how Active Maps can be created (Section 4.2). 4.1
Note also that getting the box corresponding to a non-existing mapping (i.e., when containsKey(key) is false) is allowed. Such a box will be empty, but may be populated later when changes occur. These empty boxes do not show up in groupedEntries(key), and their existence does not impact any other box until they are populated. This mechanism is useful to be able to use the Active Map operation in more situations. Guava's Multimap behaves similarly. There are multiple ways to create an Active Map depending on which one of its boxes is initially available. The corresponding operations are provided by interface Box, and its specializations BoxOfPairs, and BoxOfMutablePairs. The latter specializes Box to the case where its elements are Pairs with a mutable (and therefore wrapped in a box) right part, as denoted by the E ! P air < K; Box < V >> template binding.
An Active Map can be created from a box of keys. If one wants a simple Map, not a Multimap, one either uses the keysToMap, or keysToMapM operations that both take a lambda expression specifying how to compute a value from a key. keysToMapM allows the key corresponding to a value to change (e.g., because it is a changeable property of a model element), whereas with keysToMap a given value always has the same key. If one wants a Multimap, one uses keysToMultimapM which is similar, but with a lambda that always returns a collection box. Because it always returns a box, their is no \immutable" keysToMultimap operation.
An Active Map may also be created from a box of values, given a lambda to compute the corresponding immutable keys (one per value) or mutable keys (possibly several per value). Operations valuesToMultimap, and valuesToMultimapM perform these roles.
An Active Map can also be created from a box of pairs representing its entries. The entriesToMap, and entriesToMultimap operations perform these roles depending on whether one respectively wants a Map, or a Multimap. In the rst case, there should not be multiple pairs with the same key as left part, otherwise a runtime error will occur.
Finally, an Active Map can also be created from a box of \mutable" pairs, each with an immutable key, and a mutable value. There are two overloaded operations named groupedEntriesToMultimap for this purpose. The second one takes a lambda as argument that computes keys from values. This makes it possible to have a changeable values box.
Remarks: other ways to create Active Maps exist, but we focused on the ones we found useful in practice. Upon creation, an Active Map starts observing the box from which it is created in order to propagate changes to all its views. Which boxes are changeable or not depending on how the Active Map operation is created cannot be discussed here systematically for space reasons. A rule of thumb is: if there is enough information to properly propagate a change occurring on a box to the other boxes, then it is changeable, otherwise changing it results in a runtime error. Active Maps observe all their changeable views. 5
The two previous sections de ned the Active Map operation and its API. This section shows how it can be used to express various other operations, while preserving scalability. Like in Section 2.1, the syntax used in this section is similar to the one used in the OCL speci cation [10, Section 11.9, pp. 177{183] with some extensions. Pair L,R left : L right : R collect<R>(λ<E, R> body) : Box<R> select(λ<E, Boolean> body) : Box<E> . . . zip<R>(right : Box<R>) : BoxOfPairs<E, R> . . . keysToMap<V>(λ<E, V> computeValues) : ActiveMap<E, V> keysToMapM<V>(λ<E, Singleton<V>> computeValues) : ActiveMap<E, V> keysToMultimapM<V>(λ<K, Box<V>> computeValues) : ActiveMap<E, V> valuesToMultimap<K>(λ<E, K> computeKeys) : ActiveMap<K, E> valuesToMultimapM<K>(λ<V, Box<K>> computeKeys) : ActiveMap<K, V> BoxOfPairs
BoxOfPairsWithMutableRight «bind» <E -> Pair<K, V>>
K, V «bind» <E -> Pair<K, Box<V>>>
K, V entriesToMap() : ActiveMap<K, V> entriesToMultimap() : ActiveMap<K, V> groupedEntriesToMultimap() : ActiveMap<K, V> groupedEntriesToMultimap(λ<V, K> computeKeys) : ActiveMap<K, V> The rst operation we consider is the one given as motivating example in Section 2.3. The initial expression of groupBy given in Listing 1.2 used collect, asSet, and select. It had quadratic computation time, and linear propagation time. The new expression of groupBy in terms of the Active Map operation is given below for an immutable body (i.e., always the same grouping key for a given value): 1 source >g r o u p B y ( i t e r a t o r j body ) = 2 source >v a l u e s T o M u l t i m a p ( i t e r a t o r j body ( i t e r a t o r ) ) . g r o u p e d E n t r i e s ( ) Supporting a mutable body (i.e., a body expression returning a mutable value) is simply a matter of switching from valuesToMultimap to valuesToMultimapM: 1 source >g r o u p B y M ( i t e r a t o r j body ) = 2 source >v a l u e s T o M u l t i m a p M ( i t e r a t o r j body ( i t e r a t o r ) ) . g r o u p e d E n t r i e s ( ) Both versions de ne a Multimap with the source collection as values, and the groupBy body as key computation lambda argument. The grouped entries of the Multimap are then returned, resulting in a collection of pairs with each one's left part equal to a key, and its right part equal to a collection box of all associated values. There is a slight typing di erence between these expressions of groupBy and the one given earlier in Listing 1.2: we had tuples, and we now have Pairs. However, this is mostly a cosmetic issue due to the fact that we decided to add an explicit Pair interface to the API class diagram in Figure 3. There is no fundamental di erence, and a concrete implementation can be made to return the same kind of tuples in all cases. Remark: the mutable version also supports grouping a given value with multiple keys if its body returns a collection box instead of a singleton box. 5.2
selectBy
The second operation we consider is selectBy, de ned in [
Note that selectBy requires two arguments: the key to search (searchedKey),
and a lambda expression to compute keys from values. No standard OCL
operation has such a signature, but this should not prevent us from de ning one:
it may not even be made available to users if the execution engine
automatically optimizes a standard select used according to the above pattern into a
selectBy. If searchedKey changes, propagation requires retraversing the whole
source collection. Moreover, as noted in [
Another application example consists in nding the previous or next element in an OrderedSet. These can both be expressed using iterate, or zip plus select (expressions not detailed here), but is easier to express, and more scalable using an ActiveMap. We can compute an Active Map for the previous elements using the following expression: 1 source >prevMap ( ) = 2 source >zip ( source >prepend ( null ) ) >e n t r i e s T o M a p ( )
Each element is paired with its previous one by zip thanks to the prepend of null perform on the right box. Given an element a of the source OrderedSet, getting its previous element consists in calling get(a) on the result of prevMap.
Similarly, we can compute an Active Map for the next elements using the following expression: 1 source >nextMap ( ) = 2 source >prepend ( null ) >zip ( source ) >e n t r i e s T o M a p ( )
Remark: both prevMap, and nextMap rely on a zip. For them to work
correctly, the change alignment problem discussed in [
There are two main categories of related work: those related to integrating Maps
into OCL, and those about incremental computations. Regarding the rst
category, QVT [
Regarding the second category of related work about incremental
computations, IncQuery and VIATRA [
This paper has presented a new versatile active operation called Active Map. It keeps multiple boxes synchronized in a scalable way thanks to the HashMap it wraps. Speci c operations such as groupBy can therefore be expressed in terms of it without sacri cing scalability, thus reducing the need for ad-hoc implementations.
Several aspects of the Active Map operation have not been discussed in the present paper for space reasons. Possible extensions of this work therefore include developing these aspects. For instance, this paper is limited to discussing time complexity without proofs. It may be possible to write such proofs, or at least to benchmark various implementations of operations such as groupBy with and without relying on the Active Map operation. Other notable aspects that would bene t from being examined include memory complexity, di erent kinds of Multimaps (depending on the type of get(key) boxes such as Sequence, or Set), order preservation, and further uni cation by expressing more operations 5 https://help.eclipse.org/oxygen/index.jsp?topic=%2Forg.eclipse.ocl.doc% 2Fhelp%2FMap.html in terms of the Active Map operation. Finally, multiple open questions have been asked in Section 2.2. Looking for answers should prove useful.