MoDELS ’08: The objects and Arrows of Computational Design

The third keynote, titled ‘The Objects and Arrows of Computational Design’, of the MoDELS ’08 conference was by Don Batory from the University of Texas, US.

Don starts by stating that the future of software design and development is automation. The age of computational design consists of:

• Design: steps to take to create an artifact.
• Synthesis: the evaluation of these steps to produce the actual output / artifact.

Don sees two important complementary notions in this field: Model-Driven Engineering (MDE) and Software Product Lines (SPL). MDE is about using high-level models to specify software and transforming them into low-level artifacts, while SPL is about software families. In SPL we know the problems and the solutions, we just want to automate the construction of these solutions. In short: MDE can be seen as a general paradigm for program synthesis while SPL can be seen as a domain-specific paradigm for program synthesis.

Background

In the old days program generation was relational query optimization (RQO). This has influenced Don’s view on automatic software generation. Software design can be approached in a mathematical way, because it’s all about structure and manipulating structure. The core ideas of Don’s work are inspired by the category theory (theory of mathematical structures).

Definitions

An object is a domain of points, its instances. This holds for all technological spaces, by example: a meta model is a domain of models, an XSD is a domain of XML files, and so on. This perspective on objects can be visualized using cones. In this universe of cones recursion exists (think about the UML meta model structure).

An arrow is a mapping / function / transformation / morphism between objects. Don further formalizes this definition to:

• Arrow: map between objects.
• Transformation: MDE implementation of an arrow.
• Tool: non-MDE implementation of an arrow.

A category is a collection of objects and arrows. A category has the following properties:

• Arrows are composable.
• Composition is associative.
• For each object an identity arrow exist (visualized by an arrow having the same object as input and output).

In literature other names for categories exist, like toolchain diagrams or megamodels.

Multiple arrows can have the same input, meaning that an object is transformed into different other objects. Multiple arrows can also have the same output, meaning that an output is constructed via different transformation from different objects.

If we look at a chain of objects connected with arrows, we can express the output as a multiplication of the transformation functions. So, the output can be described as an expression.

Software Product Lines

As said before an SPL is a set of similar programs (a family), which are defined by features and related by features. Don gives an example of a base program B1 which can be transformed (add code / add a feature) into a second program B2, and so on.

Combined with the previous definitions of objects and arrows, an SPL can be seen as a set of programs related with arrows, each arrow representing a feature. Reasoning along in the same way a program design can be seen as a chain of arrows and thus be described as an expression. We can also deduct that a program can have multiple designs. The last observation is that an SPL is a category.

Model-Driven Software Product Lines

A Model-Driven Software Product Line (MDSPL) is a combination of MDE and SPL. In this combination commuting diagrams arise. Commuting diagrams are the foundational idea of categories. The key property of a commuting diagram is that all paths from one object to another yield equivalent results.

Don adds one extra key concept to the definitions given above: operators. Operators are transformation to transformation mappings, i.e. a mapping from one arrow to another arrow.

Commuting diagrams enable verification and optimization of program design. Program design can be verified by relating different paths to each other using operators. Optimization of program design can be done by choosing different paths.

Conclusions

According to Don the main challenge of these techniques is to find domains were there are different ways to implement the same functionality. If so, commuting diagrams occurs and program design can be verified and/or optimized.

Don’s main advice: do not only focus on models, that’s just a part of the picture. You also have to focus on transformations and operators.

I’m aware of the fact that it is difficult to grasp the idea’s of Don’s keynote without any pictures. For a full understanding of the subject I recommend to read his paper. I like his fundamental view on MDE and I can see how we can benefit from these ideas. However, actually using his ideas in practice will be quite a challenge.