Different Ways to Define the Operational Semantics of a Language Based on its Meta-Model

Since meta-modelling became a successful method to define abstract language syntax, many research groups started to define the operational semantics of language also based on a meta-model. A variety of methods have been developed. This article briefly explains three different categories of methods and asks the question of which of the three approaches is the best one.

1. Structural Operational Semantics and Meta-Modelling

What is the abstract structure of operational semantics definitions: Plotkin's [1] classical approach to operational semantics is based on state transition systems. All the possible configurations of a runnable system are defined through states. There are transitions between states; they define which configuration may be followed by which other configuration. A system behaviour is one path leading from a starting configuration, following transitions. A language semantics can then be defined with (1) a set of configurations/states (this includes all possible programs + runtime information like variable assignments, memory, etc.); (2) possible transitions between configurations; and (3) something that selects one (or more [non-determinism]) behaviours, where the initial configuration/state is given by a program or model written in the language.

How can operational semantics be defined based on a meta-model? Meta-modelling allows to define configurations/states. A meta-model is an object-oriented data model that describes a set of models consisting of a finite number of objects, links between object, and attributes of objects. Meta-models can be used to define the abstract syntax of a language (remember that the model or program is one part of a configuration/state) and it can also be used to define data-structures that hold runtime information (like variable assignments, memory, etc.).

2. Three Ways of Defining Transitions and Behaviours Based on a Meta-Model

Even though we know that configurations can be described by meta-models, there are still several ways to define possible transitions and system behaviours. We want to briefly introduce three different approaches.

2.1 Code-Generation

Based on the language concepts given in a meta-model, a code generation can be used to generate executable code from a model. This code can use a mixture of model and programming language variables/states to define a system configuration. The executed code describes state changes by changing the model and/or changing variables within the generated program.

2.2 Action Languages

Meta-modelling defines a set of predefined actions. These actions are things like: create a object, set an attribute, create a link, delete an object, etc. These actions describe very small, atomic changes in a model. Actions can be scheduled from various forms of action languages. Examples are UML activities or most imperative programming languages. Such languages use expressions over models to create decisions and parameters for the actions. Blocks written in those action languages can be linked to the meta-model on two modularisation levels. One possibility is that operations are implemented in an action languages. In this case one operation implementation can call other operations. The whole semantics descriptions feels and behaves like a normal object-oriented program. The other possibility is to provide a behaviour implementation for classes, where each object (class-instance) runs its behaviour once it got created/instantiated.

2.3 Model Transformations

Another approach is model transformation. Using a transformation language, one can define more complicated model transitions. We are here focusing on rule-based transformations, where each rule describes a transition between two models. Such a rule usually selects a part in model that shall be replaced (lhs) and a sub-model (rhs) that is used to replace the lhs. Model transformation allow more complex, user defined transitions between configurations/states.

For rule-based transformations also several ways of scheduling exists. For example, transformations can also be choreographed using action languages, where the execution of a transformation rule becomes an action. Transformation rules can also be grouped with logical operations: one rule can only be applied when another rule could already be applied, or several rules that can be fired are alternatives to each other, where one of the rules is either selected non-deterministically or via rule prioritisation.

3. What is the Best Way of Describing Operational Semantics?

Maybe we should first ask: is there a best way of describing operational semantics? All the methods that we just described, with all their variations that exist out there, have their own advocates, convinced of the advantages of their method. Also do all research groups have their own examples that seem to proof how efficient and elegant their methods are. But how can we really determine what the characteristics of a method really are and for what kind of languages each method is the most suitable?

We plan to take a genuine DSL, that was developed at our institute, and we want to create operational semantics for that languages with the three different approaches. The researched DSL describes stream based data processing. It already has an operational semantics based on scheme-code generation. During our studies on an agile language engineering process we will create an action language-based operational semantics with the method presented here. Furthermore, we will create a transformation-based operational semantics, using a QVT implementation.

We expect to see that different parts of the language will cause troubles when implemented with the three different methods. We hope that we can identify certain language concept characteristics that may favor the one or other method. Furthermore we expect the three solutions to have different qualities when it comes to size of the semantics description, execution performance, scalability, reusability, easyness of combining the language with other or with a concrete system platfrom, and so on and so on.