%$Id: solution.tex 14757 2008-10-10 15:02:59Z amoghk $
%\sqzsmall
\sqzlarge

\section{Templatized Model Transformations}
\label{sec:soln}
%\sqzsmall
\sqzsmall
% Section~\ref{sec:intro} argued for reusable and flexible model
% transformations so that they can be effectively used in software
% development for application families including product lines.  
We now present MTS (Model-transformation Templatization and
Specialization).  MTS uses the Generic Modeling Environment
(GME)~\cite{GME:01} as the modeling environment. 
GME provides a general-purpose editing engine and a separate
model-view-controller GUI.  GME is metaprogrammable in that the same
environment used to define modeling languages is also used to build
models, which are instances of the metamodels.  

Transformation rules are defined using the Graph Rewriting And
\begin{figure}[htb]
\centering
\vspace{-.1in}
\includegraphics[width=0.75\columnwidth,keepaspectratio]{GReATOverview}
\bfcaption{Steps involved in developing model transformation using GReAT.} 
\label{fig:GReAT}
%\vspace{-.1in}
\end{figure}
Transformation (GReAT)~\cite{GReAT:03} language.  GReAT is developed
using GME and can be used to define model transformation rules using its
visual modeling language.  It uses domain-specific modeling languages
(DSMLs) as its source and target languages.   
Figure~\ref{fig:GReAT} shows the various high-level steps involved in
developing transformation algorithms using the GReAT tool chain. In Step
1, the source and target DSMLs for
the transformation tool chain are defined. In Step 2, transformation
developers use the GReAT transformation language to define various
translation rules in terms of patterns\footnote{Here, pattern refers to
  valid structural composition using model objects in source (target)
  DSML.} of source and target modeling objects.  Finally, in Step 3,
developers execute the GR-engine that translates the source model using
rules specified in Step 2 into the target model.  

The MTS approach shown in Figure~\ref{fig:approach} leverages GReAT,
however, without modifying it.  The remainder of this section delves
into the details of each step of MTS. 
\begin{figure}[htb]
\centering
\includegraphics[width=0.8\columnwidth,keepaspectratio]{approach}
\vspace{-0.15in}
\bfcaption{MTS Approach to Reusable Model Transformations.}
\label{fig:approach}
\vspace{-0.3in}
\end{figure}

\iffalse
% Amogh, I rearranged things a bit to conserve space and hence now we
% don't need these bullets. Let us jump right into the subsections.
%
% Andy, OK this is fine.
\noindent\textbf{1. Identifying the variabilities:} In this step 
transformation developers analyze their application family to 
identify variabilities across the variants.  Step 1 of
Figure~\ref{fig:approach} shows how these variabilities are input to the
model transformation in terms of a simple \emph{constraint notation
  specification} (see Section~\ref{sec:variab}).  This  step decouples 
the transformation algorithm from its variabilities that can change in
instance-specific manner.  This is akin to template
functions~\cite{Vlissides:94} in C++ that outline the pattern of the
function code. 
% Amogh, let us explore if the above is more like the ``template
% method'' pattern from gang of 4 book.
%
% Andy, in a sense - template method pattern abstracts the steps that need
% to go into an algorithm, and also provides one or more concrete steps (while)
% leaving the rest for the subclasses to implement. 
% I have given the citation to the book - is it due to someone else?
% Amogh, This citation is correct.
%
% Andy, OK.

\noindent\textbf{2. Generating variability metamodel:} In this step,
developers use a higher order transformation (\emph{i.e.}, 
those model transformations that work on meta-metamodels to 
translate source metamodel(s) to target metamodel(s)) defined in MTS to
automatically generate the variability metamodel (VMM) for their
application family (see Section~\ref{sec:gen-VMM}). 

\noindent\textbf{3. Synthesizing specialization repository:}  Next,
developers create VMM models, where each VMM model corresponds
to a family member.  Thereafter, the variabilities
identified in Step 1 are instantiated for every family member.  A
collection of all the VMM models is termed as a specialization
repository of that family (see Section~\ref{sec:sprepo}).

\noindent\textbf{4. Specializing the application instances:} Finally, 
as shown in Step 4, developers use another higher order transformation 
defined in MTS to create application variants (see 
Section~\ref{sec:specialize}).  This step is similar to instantiating a
C++ template where the compiler generates type-specific code based on
the type of the argument passed.

% The remainder of this section describes the details of our MTS approach.
\fi

\input{stepI}
\input{stepII}
\input{stepIII}
\input{stepIV}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Previous version.
%In order
%to use MTS for templatization of a set of model transformations (\emph{e.g.},
%platform-specific QoS mapping algorithms), the commonalities and variabilities
%amongst various elements (instances) in the set must be identified.   This is
%crucial for the following reasons: (1) the commonalities constitute the
%\emph{invariants} amongst the transformation instances.  As such these
%commonalities can be directly used to construct common but templatized
%transformation rules; and (2) the variabilities constitute the dissimilarities
%of individual transformation instances.  
%
%Consequently the variabilities must be separated from the templatized
%transformation rules such that both can evolve independently.  Thus,  the
%development of templatized model transformation using MTS goes through the
%following three steps:
%
%\begin{figure}[htb]
%\centering
%\includegraphics[width=\columnwidth,keepaspectratio]{approach}
%\bfcaption{Model Transformation Templatization and Specialization.} 
%\label{fig:approach}
%\end{figure}
%
%\begin{NumList}
%\item \textbf{Identifying variability points.} 
%As the first step in using MTS for developing a templatized
%model transformation, the variability points in the transformation process are
%identified.  MTS allows specification of variability points using a
%non-intrusive notation that can be coded in the transformation project itself. 
%
%\item \textbf{Specifying instance variabilities.} 
%In the next step, transformation instance-specific variabilities are
%specified.  MTS allows intuitive specification  of variabilities using a
%modeling language that is automatically generated from the variability points by
%the MTS generative capabilities within the templatized transformation that have
%been identified in earlier step.  This step is similar to C++ class template
%specializations.
%
%% Amogh, is this the same thing as incorporating the variabilities?
%\item \textbf{Compiling model transformation instances.} In the final step,
%templatized model transformation and variabilities from previous steps are used
%to compile instances of model transformation. 
%\end{NumList}
%
%The details of the design and implementation of MTS, how it is used in each of
%the templatized transformation development steps identified above, and the
%supporting toolsuites used are discussed in the remainder of this section.
%
%\subsection{Overview of Supporting Technologies}
%\label{sec:base}
%%\vspace{-0.1in}
%Existing model transformation tools and
%techniques~\cite{GReAT:03,VIATRA:02,Lara:02,Schurr:96} lack support for
%templatized model transformations, which is critical for writing reusable
%(patterns of) model transformations.  Our approach enhances these technologies.
%We introduce the supporting technologies used to realize the capabilities of
%MTS.  
%
%We use the Generic Modeling Environment (GME)~\cite{GME:01} as the
%meta-programmable modeling environment.  GME provides a general-purpose editing
%engine, a separate view-controller GUI, and a configurable persistence engine.
%GME is meta-programmable, and thus the same environment used to define modeling
%languages is also used to build models, which are instances of the meta-models.
%
%We have used Graph Rewriting And Transformation (GReAT)~\cite{GReAT:03} language
%for defining various general-purpose transformations in our tool.  GReAT is
%developed using GME and can be used to define model-to-model transformation
%rules using its visual modeling language.  It also provides the GReAT Execution
%Engine (GR-Engine) for execution of these transformation rules for generating
%target models. 
%
%% Amogh, I moved these lines here.
%Although our transformation parameterization idea has been realized
%using specific modeling and transformation environments, the concepts we
%introduce in this paper for supporting configuration variabilities in
%transformation rules are generic and can be re-applied to other model
%transformation tool suites.   
%
%
%\subsection{Design of Templatized Model Transformations}
%\label{sec:design}
%In this section, we discuss the three development steps identified earlier in
%greater detail, describe the design principles of our approach to templatized
%transformation and its successive specializations, and how we implemented it
%within existing tools. 
%
%\subsubsection{Step 1: Identifying Variability Points.} 
%\label{sec:identify}
%%\vspace{-0.1in}
%Mappings of source objects to target objects are
%well understood by transformation developers and are 
%encoded in terms of transformation rules.  Separation of
%points of variabilities from the transformation rules is 
%necessary such that templatized model transformation can 
%be developed.  As such, the developers should be able to 
%easily identify  these variability points.  
%
%We have introduced a simple constraint notation using which transformation
%developers identify variability points in their transformations.  The notation
%is given in Listing~\ref{lst:constraint} and consists of three blocks that
%separate the types of variabilities \emph{i.e.},  \texttt{direct},
%\texttt{conditional\_value}, and \texttt{conditional\_creation}.  We explain
%each of these blocks below.
%\begin{Constraints}[numbers=true]
%    \begin{Verbatim}[frame=single,fontsize=\relsize{-2}]
%// Identifies code points where current variability
%// will be incorporated.
%sequencing
%{
%  block_name:preceding_rule_name 
%}
%// Identifies direct value variability points.
%direct
%{
%  y1
%  y2
%  ...  
%}
%// Identifies conditional value mappings.
%conditional_value
%{
%  s:t 
%  ...
%} 
%// Identifies conditional creation mappings.
%conditional_creation
%{
%  s:t 
%  ...
%}
%\end{Verbatim}
%\caption{Constraint Notation Block for Identification of Variability Points}
%%\vspace{-0.15in}
%\label{lst:constraint}
%\end{Constraints}
%%\vspace{-0.20in}
%
%\textbf{Direct Value Assignments:} Since source models are typically
%at a higher level of abstraction compared to target models, developers
%would not necessarily be able to define mappings for all of the target
%model objects.  Instead,  as part of the transformation process,
%developers use their knowledge of the target modeling language
%semantics to directly assign values to target objects that cannot be
%mapped from some source objects.  We call this as the direct value
%assignments. 
%
%\textbf{Conditional Value and Creation Mappings:} We define
%conditional mappings as implication relations between source and
%target objects \emph{i.e.}, association relationships between the
%source objects ($s \in S$) and target objects ($t \in T$).  These
%associations may be one-to-one,  one-to-many, or many-to-one, and apply 
%to both value- and (target) object creation-based relations:
%      
%1. A one-to-one association between a pair $(s,t)$ 
%      of source and target objects respectively is
%      defined as an injective function:
%      $s \in S, t \in T \; \exists \;            
%      f(s)\stackrel{\alpha}{\longmapsto}f(t)\;$ such that
%      $if\; f(s) = f(t)\; then\; s = t. $
%            
%2. A one-to-many association between pairs $(s,t)$
%      of source and target objects respectively is defined
%      as: \\     
%      $s \stackrel{\phi}{\longmapsto} t,$ 
%      where
%      $s \in S$ and 
%      $t = \{P1(t_1, t_2, ..., t_n) \mid t_{i = 1..n} \in T\}$.
%      
%3. A many-to-one association between pairs $(s,t)$
%      of source and target objects respectively is defined
%      as: \\      
%      $s \stackrel{\varphi}{\longmapsto} t,$ 
%      where
%      $t \in T$ and 
%      $s = \{P2(s_1, s_2, ..,  s_m) \mid s_{j = 1..m} \in S\}$.
%
%Here $P1$ and $P2$ define patterns of source and target objects.
%More than one such mappings may be defined per constraint notation
%block and they occur on separate lines.
%Finally, the \texttt{sequencing} block indicates the code points
%\emph{i.e.}, source code or model transformation locations where 
%variabilities would be instantiated in order to generate
%transformation instances.  We will explain the use of \texttt{sequencing}
%block in detail in Section~\ref{sec:accommodate}.
%
%Using our approach, transformation developers insert constraint 
%notation blocks as special comments in the source code of their 
%templatized transformations using the syntax described above. The
%notation itself is added as a special comment in the transformation
%project.  Thus, it is opaque to the GReAT interpretation logic or translation
%engine and does not place any extra computational overhead on the toolchain. 
%
%\subsubsection{Step 2: Specifying Instance Variabilities.}
%\label{sec:modelcv}
%%\vspace{-0.1in}
%It is desirable for transformation 
%developers to specify instance-specific variabilities in 
%the templatized transformation project such that these 
%variabilities can evolve and change independently of the 
%transformation leading to rapid software development.
%%\vspace{-0.10in}
%%\begin{figure}[htb]
%%%\vspace{-0.35in}
%%\centering
%%\includegraphics[width=\columnwidth,keepaspectratio]{specification}
%%%\vspace{-0.2in}
%%\bfcaption{Generation of VarML for Variability Specification.}
%%\label{fig:specification}
%%%\vspace{-0.15in}
%%\end{figure}
%%\vspace{-0.20in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{algorithm}[htb]
%\caption{Generation of VarML from Variability Points}
%\label{algo:varml}
%{
%%\small
%%\footnotesize
%\scriptsize
%\dontprintsemicolon
%\Indm
%\Setnlskip{0.17in}
%\linesnumbered
%\KwIn{source modeling language $S$,
%			target modeling language $T$,
%      set of templatized transformation project rules $R$
%      }
%
%\KwOut{variability modeling language $V$
%		 }
%      
%\Begin{
%  transformation rule $r$;
%  constraint notation block $cnb$;
%  set of constraint notation blocks $CNB$; \;
%  creational mapping $cm$;set of creational mappings $CM$;
%  pattern $p$; modeling object $ob$;
%  modeling object type $type$;\;
%  integer $c$; \;
%   
%   $initializeVarML(V);$\;
%   
%   \ForEach{$r \in R$}{
%   			\uIf{$r.cnb() \neq \emptyset$}{
%   			  $CNB \leftarrow r.cnb()$;\;
%   			}
%   			\ForEach{$cnb \in CNB$}{
%   			  \uIf{$cnb.creationalMappings() \neq \emptyset$}{
%   			    $CM \leftarrow cnb.creationalMappings();$\;
%   			    \ForEach{$cm \in CM$}{
%   			      $p \leftarrow cm.SRC();$\;
%   			      \ForEach{$ob \in p$}{
%   			      $parseLanguage(S,ob,type);$
%   			      $createSRCObject(V,ob,type);$\;
%   			    }   			      
%   			      $p \leftarrow cm.TRGT();$ \;
%   			      \ForEach{$ob \in p$}{
%   			      $parseLanguage(T,ob,type);$
%   			      $createTRGTObject(V,ob,type);$\;
%   			    }
%   			    $composeVariabilityAssociation(V)$\;   			       			    	  
%   			}
%   		}
%   	}
%  }
%}      
%}
%\normalsize
%\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%We have developed a model transformation 
%that auto-generates a variability modeling language (VarML).
%Algorithm~\ref{algo:varml}  gives some of the translation rules of this model
%transformation.  VarML is generated from (1) the templatized transformation
%project, and (2) source and target modeling lanaguages.  The auxilliary function
%$initializeVarML(V)$ creates VarML $V$ and initializes its attributes required
%in order to define a new language in GME.  
%
%% Amogh, I think we need to provide more intuition on why this is done the way
%% it is in the algorithm. For me looking at so many nested loops made me frown. 
%As shown in Algorithm~\ref{algo:varml}, for all the creational mappings in the
%transformation, the source and target patterns are read in Lines 13 and 17.
%Next the types of each modeling objects, for both source and target patterns is
%found by parsing the respective modeling languages as shown in Lines 15 and
%19.  The type information is used to create appropriate modeling objects
%corresponding to the specified source and target patterns.  Finally, a similar
%approach is taken in creating modeling objects in VarML for value mappings and
%direct value mappings in  constraints notation blocks (not shown in the
%Algorithm). 
%%\vspace{-0.10in}
%%\begin{figure}[htb]
%%%\vspace{-0.1in}
%%\centering
%%\includegraphics[width=\columnwidth,keepaspectratio]{varml}
%%%\vspace{-0.6in}
%%\bfcaption{Associations in VarML.}
%%\label{fig:VarML}
%%%\vspace{-0.10in}
%%\end{figure}
%%\vspace{-0.10in}
%
%Transformation developers use VarML as the modeling language for specifying 
%instance variabilities in their project. Using our approach, various
%types of variabilities in source and target languages
%are automatically modularized and are now exposed to the developer 
%as VarML modeling abstractions (as opposed to being tightly coupled with 
%the transformation itself). Models of VarML can now vary independently of 
%the transformation project being developed. 
%
%\subsubsection{Step 3: Compiling Model Transformation Instances.}
%\label{sec:accommodate}
%Individual VarML models capture instance
%variability information.  Note however that the transformation 
%project under development still has general, instance-independent 
%mappings from source to target model objects.  Thus, as a final step,
%in order to compile transformation instances, the variability
%information in VarML models needs to be incorporated in the templatized 
%transformation project. It is desirable for transformation developers 
%that this step be automated. 
%% Amogh, if not automated, what can go wrong?
%
%We have defined a model transformation that creates a new
%model transformation instance from the templatized transformation project 
%being developed and VarML model for that instance.  It also
%inserts rules that create and populate temporary data structures from 
%the VarML model.  Recall from Section~\ref{sec:identify} that the
%\texttt{sequencing} block specifies the code points where instance variabilities
%would be incorporated.  From the constraint notation blocks in the templatized
%transformation project, we insert the instance-specific variabilities by
%creating additional rule(s) in instance model  transformation. %Note that the
%%exact values of source and target objects  
%%are contained in VarML models, thus
%%additional rules are necessary that read these values to be used
%%further in the transformation process.
