Remove Duplicated Expression Evaluations

This is an optimisation pattern.

Summary

Avoid duplicated evaluation of expressions by using mechanisms to retain or cache their values.

Application conditions

This pattern is relevant if the same expression evaluation occurs in multiple places within a transformation rule or specification, and these evaluations will produce the same value at these different locations. It also applies if the same form of complex expression reoccurs with different arguments.

Solution

Remove duplicated evaluations of complex expressions from transformation specifications: duplicated expressions e within a single rule can be factored out by using a

let v = e

construct, which evaluates the expression e once, the value can be subsequently referenced by the identifier v. Duplicates in different rules can be factored out by defining auxiliary data features and storing pre-computed expression values in these features. Alternatively, they can be factored (with or without caching) by defining query operations to compute them. For duplicated expression forms with varying arguments, formal parameters of the query operations are defined.

Benefits

Modularity of the specification is increased, because of the higher factorisation of the specification after the pattern is applied. Efficiency should usually be increased, if duplicated evaluations are removed.

Disadvantages

Efficiency may not be increased in certain cases. If cached values are never used then the overhead of caching may increase memory use and execution time. Likewise, if functions are used to factor out repeated expressions, then there is an additional overhead of function calling.

Applications and examples

The pattern is applicable to all categories of transformation. This optimisation is performed in ATL by moving duplicated expression evaluations to helper operations, whose results are cached. Depending on the structure of the input model, this may reduce execution times. The unique lazy rules of ATL provide another means of avoiding duplicated evaluations, as do cached query operations in UML-RSDS. Languages such as Kermeta and Viatra also have mechanisms for factoring out repeated evaluations.

An example of duplicated expressions within a rule occurs in the class diagram rationalisation case study solution using UML-RSDS (Kolahdouz-Rahimi et al., 2014), in the rule:

a : specialization.specific.ownedAttribute and
v = specialization->select(
specific.ownedAttribute->exists( b | b.name = a.name and b.type = a.type ) ) and v.size > 1 implies
Entity->exists( e | e.name = name + a.name and a : e.ownedAttribute and e.specialization = v and
Generalization->exists( g | g : specialization and g.specific = e and v.specific.ownedAttribute-> select( name = a.name )-> isDeleted() ) )

operating on instances of Entity. Here, a let variable v is used to avoid re-computation of the complex expression

specialization->select(
specific.ownedAttribute->exists( b | b.name = a.name and b.type = a.type ) )

which is used in three places in the constraint.

Related patterns

This is a special case of a general modularisation and optimisation strategy for factoring out repeated sub-expressions from programs or specifications (Lano, 2008). In (Cuadrado et al, 2008) the related pattern finding constant expressions is described to factor out repeatedly evaluated expressions with constant values. Auxiliary Metamodel can be used to cache precomputed expression values in auxiliary metamodel elements. The concept of memoisation of function values (Michie, 1968) is another form of caching of result values to avoid redundant computations.

The same concept of factoring can be applied to common update functionality that is repeated in different rules. However, such factoring only improves the modularity and clarity of the specification, and does not improve efficiency. Implementation of update factoring using explicit rule invocation is described in (Kurtev et al, 2006).

(Cuadrado et al, 2008) J. S. Cuadrado, F. Jouault, J. G. Molina, J. Bezivin, Optimization patterns for OCL-based model transformations, MODELS 2008, vol. 5421 LNCS, Springer-Verlag, pp. 273--284, 2008.

(Kolahdouz-Rahimi et al., 2014) S. Kolahdouz-Rahimi, K. Lano, S. Pillay, J. Troya, P. Van Gorp, Evaluation of model transformation approaches for model refactoring, Science of Computer Programming, 2013, http://dx.doi.org/10.1016/j.scico.2013.07.013.

(Kurtev et al, 2006) I. Kurtev, K. Van den Berg, F. Joualt, Rule-based modularisation in model transformation languages illustrated with ATL, Proceedings 2006 ACM Symposium on Applied Computing (SAC 06), ACM Press, pp. 1202--1209, 2006.

(Lano, 2008) K. Lano, A catalogue of UML model transformations, http://www.dcs.kcl.ac.uk/staff/kcl/tcat.pdf, 2006.

(Michie, 1968) D. Michie, Memo Functions and Machine Learning, Nature, vol. 218, pp. 19--22, 1968.