Patterns of translating to patterns

My previous introductory blog posts talked about the importance of modeling, the concept of model queries (with OCL and EMF-IncQuery) and model evolution. Last time, I demonstrated the translation of OCL expressions into graph patterns. Now it is time to discuss how the various OCL constructs can be mapped to graph patterns of EMF-IncQuery.

Let's start with the simplest of OCL language elements: navigation.

cl.students

Last time we discussed interpreting OCL expressions as relations. The above OCL expression correspons to a binary relation between the value of "cl" (which can be statically inferred to be of type SchoolClass)  and another variable (let's say "x") created by the relationification (ugh, I made this ugly word up on the spot), which will be assigned to the various students belonging to "cl". Thus the graph pattern equivalent would look like this:

pattern translated(cl: SchoolClass, x: Student) = {
  SchoolClass.students(cl, x);
}

And we're done... for now. Keep in mind that more complex constructs will add additional elements to the pattern body, and possibly maipulate the set of parameters, as seen below.

Note that the same translation method actually goes for attribute access as well:

s1.name

translates to:

pattern translated(s1: Student, y: EString) = {
  Student.name(s1, y);
}

Selection, rejection, collection, (in)equality

Last time the result of navigation was processed further by a selection expression - it is a type of OCL function that can be applied to a collection to filter its contents. Recalling the OCL snippet from last time:

cl.students->select(s2 | s1 <> s2)

we can see that it generalizes to the following form:

some_collection_expression->select(x | boolean_expression_involving_x_and_possibly_other_variables(x,..) )

This can be generally translated as a graph pattern body like this:

pattern translated(...,x) = {
  TRANSLATED<some_collection_expression>(...,x);
  TRANSLATED<boolean_expression_involving_x_and_possibly_other_variables>(x,...);
}

Recalling last months's solution, the above example translates to:

pattern translated(cl: SchoolClass, x: Student, s2: Student) = {
  SchoolClass.students(cl, x);
  x != s2;
}

...where an attentive reader can notice that "x != s2" is the straightforward translation of the inequality check "x <> s2", while e.g. "x = s2" would be translated as "x == s2". Which brings as to an alternative way to specifíing an equivalent OCL expression:

cl.students->reject(s2 | s1 = s2)

And since this involves rejection instead of selection, the corresponding graph pattern must use the negated criterion. The translator is either smart enough to recognize that the negation of equality is simple inequality, thus yielding the translation given above; or else resorting to the negation feature in the graph pattern language:

pattern translated(cl: SchoolClass, x: Student, s2: Student) = {
  SchoolClass.students(cl, x);
  neg find translated_2(x,s2);
}
pattern translated_2(x: Student, y: Student) = {
  x == y;
}

Finally, OCL's collect()  function is very similar to select(), however the given expression does not have to be boolean-valued, and the returned collection will consist of all such computed values (instead of the original elements of collection on which select() is applied on). This means that the graph pattern translation will look pretty much the same.

Boolean operations

Let's see the following expression:

self.students->select(s2 | s2.name = s1.name and s1 <> s2)

According to the previous rule, this translates to:

pattern translated(self:SchoolClass, s1:Student, s2:Student) = {
  SchoolClass.students(self,s2);
  TRANSLATED<s2.name = s1.name and s1 <> s2>(s1,s2);
}

Along the logical connective "and", the latter constraint can be split into two conjunctive constraints:

pattern translated(self:SchoolClass, s1:Student, s2:Student) = {
  SchoolClass.students(self,s2);
  TRANSLATED<s2.name = s1.name>(s1,s2); 
  TRANSLATED<s1 <> s2>(s1,s2);
}

We already now how to transcribe both new constraints. Note that the first one introduces a local variables "y" and "z" that are not among pattern prameters:

pattern translated(self:SchoolClass, s1:Student, s2:Student) = {
  SchoolClass.students(self,s2);
  Student.name(s1,y); 
  Student.name(s2,z); 
  y == z;
  s1 != s2;
}

Other logical connectives include "or", which can be translated to disjunctive pattern bodies ("or" keyword in EMF-IncQuery); "not" which is negation (handled similarly to reject(), as seen above); and "implies" where "a implies b" is equivalent to "not a or b".

Putting it all together

Let's go back to our first ever OCL expression from February:

context SchoolClass def:
  nameConflicts(): Set(TupleType(student1: Student, student2:Student, name:EString)) =
    self.students->collect(s1 | self.students->select(s2 | s2.name = s1.name and s1 <> s2)->
      collect(s2 | Tuple{student1 = s1, student2 = s2, name = s1.name}))

The named OCL expression nameConflicts corresponds to a relation between the SchoolClass "self", Student instances"student1", "student2", and data value "name" of type EString. This determines the pattern parameters, and the rest could be translated according to the patterns of mapping introduced earlier. See the first step, the translation of the collect() function application:

pattern nameConflicts(self: SchoolClass, student1: Student, student2:Student, name:EString) = {
  TRANSLATED<self.students>(self,s1);
  TRANSLATED<self.students->select(s2 | s2.name = s1.name and s1 <> s2)->collect(s2 | Tuple{s1 = s1, s2 = s2, name = s1.name})>(self,students1,students2,name)
}

Applying the translation rule for navigation and collection:

pattern nameConflicts(self: SchoolClass, student1: Student, student2:Student, name:EString) = {
  SchoolClass.students(self,s1);
  TRANSLATED<self.students->select(s2 | s2.name = s1.name and s1 <> s2)>(self,s1,s2);
  TRANSLATED<Tuple{s1 = s1, s2 = s2, name = s1.name})>(self,students1,students2,name);
}

Applying an already familiar transcription:

pattern nameConflicts(self: SchoolClass, student1: Student, student2:Student, name:EString) = {
  SchoolClass.students(self,s1);
  SchoolClass.students(self,s2);
  Student.name(s1,y); 
  Student.name(s2,z); 
  y == z;
  s1 != s2;
  TRANSLATED<Tuple{s1 = s1, s2 = s2, name = s1.name})>(self,students1,students2,name);
}

For the last time, we use the navigation rule to (somewhat redundantly) factor out the attribute access:

pattern nameConflicts(self: SchoolClass, student1: Student, student2:Student, name:EString) = {
  SchoolClass.students(self,s1);
  SchoolClass.students(self,s2);
  Student.name(s1,y); 
  Student.name(s2,z); 
  y == z;
  s1 != s2;
  Student.name(s1,w); 
  TRANSLATED<Tuple{s1 = s1, s2 = s2, name = w})>(self,students1,students2,name);
}

And we're done, we just have to rename internal variables to be consistent with the parameter names:

pattern nameConflicts(self: SchoolClass, student1: Student, student2:Student, name:EString) = {
  SchoolClass.students(self,student1);
  SchoolClass.students(self,student2);
  Student.name(student1,y); 
  Student.name(student2,z); 
  y == z;
  student1 != student2;
  Student.name(student1,name); 
}

Following these simple rules, we have arrived at a complete graph pattern transcription of the original OCL expression. And it's only a bit less concise than its original, manually written equivalent:

pattern nameConflicts(clazz: SchoolClass, student1: Student, student2: Student, name: EString) = {
  SchoolClass.students(clazz, student1);
  SchoolClass.students(clazz, student2);
  student1 != student2;
  Student.name(student1, name);
  Student.name(student2, name);
}

Nice, isn't it?

Acknowledgement: this research was realized in the frames of TÁMOP 4.2.4. A/1-11-1-2012-0001 „National Excellence Program – Elaborating and operating an inland student and researcher personal support system”. The project was subsidized by the European Union and co-financed by the European Social Fund.