modelverse/techreport/multi_conformance/2-conformance.tex

\section{Type/Instance Relation}
\label{sec:conformance}
A language consists of four main components: an abstract syntax, concrete syntax, semantic domain, and a semantic mapping.
Of chief interest to this paper, is the abstract syntax, which defines the set of allowed constructs in the language.
Generally, this set is described through the use of a metamodel, defining the allowable types to use, their interconnection, multiplicities, and cardinalities.
The metamodel, however, is limited to structural constraints (\textit{e.g.}, in Petrinets a place can have outgoing links only to transitions), and does not consider semantic constraints (\textit{e.g.}, in Petrinets a place cannot have a negative number of tokens).
A metamodel can therefore often be augmented with constraints, expressed using a constraint language such as the Object Constraint Language (OCL).

\subsection{Bidirectionality}
The type/instance relation consists of two relations, in opposite directions: instantiation (creating a new model from an existing metamodel), and conformance (checking an existing model with an existing metamodel).
Both are complementary to each other: a newly instantiated model should, by construction, conform to the metamodel it was instantiated from (at least structurally).

Going from the metamodel to the model, is called instantiation.
Through instantiation, an instance is created that conforms (structurally) to the provided metamodel.
A general instantiation method cannot be created, as it strongly depends on what the conformance relation checks, and how it expects the model to be physically represented.
For example, if the conformance relation supports subtyping, instantiation should instantiate the own attributes, but also all inherited attributes.

From the model to the metamodel, we have the conformance relation, often called ``verify'' in tools (\textit{e.g.}, metaDepth~\cite{MetaDepth} and AToMPM~\cite{AToMPM}).
A model is said to conform to its metamodel if each element of the model is an instance of (conforms to) an element of the metamodel.
What it means for a single element to conform to another, is much more vague.
For example, if the conformance relation supports subtyping, an element might conform to types other than its own type, if there is an inheritance relation between them.

If one wants to explicitly model the type/instance relation, as is the goal in this paper, one needs to explicitly model both the instantiation and the conformance checking functions.

\subsection{Metamodelling Hierarchy}
The metamodelling hierarchy, as popularized by the OMG in the four-layered architecture, makes explicit use of the relation between types and their instances.
This architecture consists of four layers, as shown in Figure~\ref{fig:four_layered_architecture}: the metametamodel ($M3$), the metamodel ($M2$), the model ($M1$), and the real world ($M0$).
Each of these models is said to conform to the model at the layer above, meaning that the lower level is an instance of the higher level.
As a result, $M1$ conforms to $M2$, which conforms to $M3$.
At the top of the hierarchy, $M3$ is made to conform to itself, which is called meta-circularity.

This four-layered architecture is used by most (meta-)modelling tools, with only two levels accessible to users: the $M2$ and $M1$ level.
$M3$ is fixed, and has a close relation to the internals of the tool, as well as the physical representation of models.
$M0$ cannot be modelled in the tool, as this represents the real world instance.
This leaves only $M2$ and $M1$ for modification.
Users can then use $M2$ to define their own custom language, specific to the domain they are interested in.
$M1$ is used to model the actual model that is to be manipulated.

\begin{figure}
    \centering
    \includegraphics[width=0.3\columnwidth]{figures/four_layered_architecture.pdf}
    \caption{Four-layered architecture, exemplified using Petri nets.}
    \label{fig:four_layered_architecture}
\end{figure}

Having only two levels at your disposition can be limiting for several applications.
Therefore, multi-level modelling has been introduced, where the number of user-accessible layers is unrestricted.
This raises the question on how to restrict elements several layers deep, which can be done through the use of deep characterization (\textit{e.g.}, through potency~\cite{potency,UnifyingApproach}).
These techniques have an influence on instantiation and conformance semantics, and therefore require specialized tools.
For example, potency will prevent the instantiation of elements whose potency value has reached 0.
The exception being potency *, which indicates unrestricted instantiation until specified~\cite{SupportingConstructiveAndExploratoryModesOfModeling}.

\subsection{Hardcoded Type/Instance relations}
From the previous examples, it becomes clear that instantiation and conformance are more complex than graph (or model) homomorphism.
Apart from finding whether the model structurally conforms to the provided metamodel, additional constraints are imposed on the representation.
Several of the instances of the graph even gain special semantics, deviating from their originally structural role.
For example, a \textit{cardinality} attribute will not merely be structural, but will further constrain the set of allowed instances.
Figure~\ref{fig:special_constructs} shows some more examples of additional constraints.

\begin{figure}
    \centering
    \includegraphics[width=0.7\columnwidth]{figures/special_constructs.pdf}
    \caption{Constructs that further restrict the set of instances.}
    \label{fig:special_constructs}
\end{figure}

Their semantics is as follows:
\begin{itemize}
\item \textit{Inheritance}.
    A special kind of link between two elements.
    It cannot be further instantiated.
    The source of the link becomes a subtype of the target during the conformance check.
    In the example, this means that any instance of $C$ will also be considered as an instance of $B$, but not the other way around.
    Additionally, when instantiation an instance of $C$, all attributes of $B$ also need to be added.
\item \textit{Potency}.
    A special attribute which indicates how many levels deep this element can still be instantiated.
    When instantiating an element, the potency value is copied and decremented by one.
    When the value reaches zero, no further instances can be made.
    In the example, this means that both $A$, $B$, and $C$ can only be instantiated once more.
    This places restrictions on both instantiation (\textit{i.e.}, refuse to instantiate) and conformance checks (\textit{i.e.}, always find them to be non-conforming).
\item \textit{Cardinalities}.
    A special attribute of an association which limits the number of instances of this association for a single element at the other side of the association.
    Both a lower and upper bound are possible.
    In the example, this means that each instance of $A$ has either $1$ or $2$ connected instances of $B$ through this association.
    For each $B$, there is exactly one connected instance of $A$.
    Instantiating additional links, when the upper limit is already reached, should be disallowed.
    Conversely, a conformance check should flag a model as non-conforming if the constraint is violated, even though it is structurally fine.
\item \textit{Multiplicities}.
    A special attribute that indicates how many instances of this element can be present at the level immediately below.
    Both a lower and upper bound are possible.
    In the example, this means that there will be exactly $2$ instances of $A$.
    Similarly to cardinalities, both the instantiation and conformance relation should be aware of these restrictions.
\item \textit{Constraints}.
    Previous constructs would limit the structure, whereas this part restricts the instances based on its semantics.
    Arbitrary executable models can be coupled to the metamodel, which are evaluated when determining whether the element conforms or not.
    In the example, this means that the value of the attribute $b$ of $B$ will always be greater than zero.
    The conformance check should, apart from checking the previous constraints, execute this piece of code to determine whether or not the model conforms.
    Instantiation does not need to be aware of this, as there is no way to statically know which operations are allowed to satisfy this function.
\end{itemize}

When these constructs are only present structurally, as is the case in most modelling tools, their semantics is non-obvious.
It might even be non-obvious whether or not the attributes have any semantics (within the modelling tool) at all: why would an attribute with a specific name suddenly become part of the restrictions placed on instances?
Somewhere, semantics needs to be given to these constructs: a component of the tool needs to find the attribute, read it out, determine whether or not the model satisfies this requirement, and provide user feedback.

While we acknowledge that these powerful constructs aid in creating a tightly constrained set of possible instances, their inclusion often creates severe problems in the modelling hierarchy.
Because each of these carries its own semantics, informally described above, there needs to be a mechanism to enforce the semantics.
As described above, this semantics is part of the type/instance relation, which is, in most current tools, implicit and hardcoded.

More concretely, this results in the following problems:
\begin{enumerate}
\item \textit{Semantics}.
    The exact semantics of these constructs is often unclear, and only found out by reading documentation or through experimentation.
    While for some constructs the semantics doesn't vary much between tools, other constructs vary significantly.
    And even if the semantics is clearly communicated between both parties, it remains a problem as to how these semantics are applied by the instantiation and conformance checking operations.
    For example multiplicities: what if a lower bound is not reached?
    Does it become impossible to delete elements, which would cause this lower bound to be violated?
    Or would a deletion be allowed, but subsequent conformance checks do fail in case it is still violated at that point in time?
    And is it possible to save a model which violates these constraints?
    Similarly, is it possible to create additional elements if these would violate the constraints?
    Or is it only possible within some kind of a transaction?

    This is even the case in object-oriented programming languages, where the semantics of subtyping varies.
    For example, C++ offers multiple inheritance, whereas Java only offers single inheritance.
    On the completely opposite side of the spectrum, Haskell uses structural subtyping instead of nominal subtyping~\cite{Typing}.
    While each of these has its advantages and disadvantages, it should be clear to users which semantics are used.

\item \textit{Static}.
    Semantics, even if formally described in the documentation, still remains static.
    While this is not a significant problem in general, as a general concensus exists for these attributes, sometimes a slightly different semantics is desired.
    For example, users might want to make to temporarily violate a multiplicity constraint if the restriction is too strict.

    Similarly, some users might prefer, or even require, different semantics than those implemented.
    For example, Java limits inheritance to single inheritance.
    Users that require multiple inheritance will have to resort to tricks to implement their models which naturally lend themselves to multiple inheritance.
    Should the semantics be modifiable at run-time, users can alter the behaviour to their liking, or just switch implementation.
    Users who prefer to be constrained to single inheritance, can then use the single inheritance semantics, whereas others can decide to opt for multiple inheritance.

\item \textit{Special constructs at the implementation level}.
    Because some constructs gain a special semantics, there needs to be a way of identifying these constructs.
    For some this is easy (\textit{e.g.}, read out an attribute with a pre-defined name, such as \textit{potency}), but for others, this becomes more difficult.
    In particular, the inheritance relation is a special case: it is a link, and one would expect it to be implemented as such.
    Many frameworks~\cite{VMTS,ModelBasedDSLFrameworks,AToMPM}, however, rely on this (or similar relations) to be a special kind of link, unrelated to a normal association.
    And while their underlying model storage hugely mimics existing structures, such as graphs, exceptions need to be made throughout to cope with these constructs.
    Furthermore, this additional type causes further problems in the checking of conformance: how is it typed?
    Resolving these elements should not be done through hardcoded types at the lowest level.
    This prevents the reuse of existing libraries, as a wrapper needs to be written to cope with the special types.

\item \textit{Special constructs at the metamodel level}.
    Even if special constructs at the implementation level are avoided, special constructs at the metamodel level are sometimes still used.
    This hardcodes the identity of some parts of the metamodel in the instantiation and conformance checking functions.
    The metamodel will therefore simply be a normal metamodel, though some associations will gain special importance which are not apparant from the metamodel alone.
    It is only the type/instance relation which adds this additional semantics to the link.

    Apart from the confusion this might cause to users, it prevents users from using a different metamodel, and even prevents multi-level modelling completely.
    This was one of the problems that prevents AToMPM~\cite{AToMPM} from having multi-level metamodelling, or just more than two metametamodels: the inheritance semantics is hardcoded in the core, and only applies to the provided metametamodels.

    Similarly, models cannot simply have attributes if their metamodel does not allow for it.
    While this is not a problem in the traditional four-level architecture, multi-level modelling quickly runs into this problem: users can only specify a potency if their metamodel explicitly calls for it.
    Instead of modifying the metamodel for this, it is possible to encode these \textit{special} constructs as ``explicitly allowed'' in the conformance relation, as was done in the previous (unrelated) version of our tool~\cite{MULTI_modelverse}.
    The instantiation algorithm should also be aware of this, as it should, for whatever model, always add in these attributes by default, and furthermore make them mandatory, such that they cannot be removed.

\item \textit{Inflexible type mapping}.
    Type mappings store the types of elements.
    While they have previously been identified theoretically, most current approaches hide away this important piece of information in the implementation.
    Apart from reading out the type, and possibly altering it through some programming interface, no modifications are possible as they reside in the internal data structures of the tool.

    By making these type mappings explicit, as an ordinary model, it can be modified as any other model, and in particular through the use of model transformations.
    This is one of the limitations of model transformations: the right-hand side cannot create an instances of a metamodel that is only known at run-time.
    This problem is currently solved by using model transformation templates~\cite{GenericModelTransformations}, which is still more constraining than our approach, as it doesn't allow for retyping operations.

\item \textit{Single type}.
    Finally, as the conformance function and typing information is hardcoded, only a single such relation is possible for a given element.
    Sometimes, however, an element can be typed by multiple, possibly unrelated, elements.
    An example has already been given in~\cite{APosterioriTyping}, where a model is created with a single (constructive) type, but additional types can be found during execution.
    This could however also be related to the use of multiple very similar metamodels.
    For example, consider a petri nets metamodel, and a seperate, but identical, petri nets metamodel with inhibitor arcs.
    Every petri net instance without inhibitor arc, also conforms to the petri nets metamodel with inhibitor arcs.
    Similarly, every petri net without inhibitor arcs, even if it was constructed as an instance of the metamodel with inhibitor arcs, will conform to the original metamodel.
    Even though these are unrelated, a model can easily be said to be typed by both of them, depending on the situation in which it is used.
    This can have further repercussions in model evolution, where models frequently need to be retyped to slightly different metamodels.
\end{enumerate}