Expressing bidirectional transformations

As part of the preparation for my invited talk at the International Conference on Graph Transformations I have been trying to understand the relationships between triple graph grammars, lenses and QVT. In particular, how does their expressivity compare, and how does it relate to the general notions of computability and coherent transformations? Some useful email from PC chair Reiko Heckel made me realise that I was failing to think carefully enough about basic notions.

A function f : M -> N is called computable if it can be implemented by a Turing machine; it turns out that this is a very robust notion, so that, for example, you can say "it's computable if you can write a program that computes it" and it basically doesn't matter what programming language you're thinking about. In particular, expressivity for actual programming languages is something of a non-question: they are all equi-expressive.

Is the situation equally boring for bidirectional transformations between M and N? We have to decide what M and N are, but that's probably not very important, any more than it's important to know what the type of our ordinary function was. Any of the bidirectional languages we've been thinking about can be looked at as means of specifying three things:

1. the consistency relation, a subset of M x N
2. the forward transformation, a function M x N -> N
3. the backward transformation, a function M x N -> M

Each of these three elements can be considered as an ordinary function, and then we can ask whether the corresponding function is computable or not. If you wanted to write your bidirectional transformation in your favourite ordinary programming language, you could write three programs: the first would take elements of M and N and return true if they were consistent, else false, the second would take elements of M and N and return an element of N, etc. Since your favourite programming language can express all computable functions, and since we can't hope for any more (because if we had a bidirectional transformation language which could express something with an uncomputable component, we could use it as an ordinary programming language by disregarding everything else), this gives us a notion of computable bidirectional transformation, and any standard programming language can express all computable bidirectional transformations. Boring.

Next attempt: the point about bidirectional languages is that you don't write separate programs for those three elements: you write one text, which somehow encodes all three. There's something deeply unsatisfactory about saying "yes, my language can express bidirectional transformations, you just [do something equivalent to writing the three things separately]". Formally, what exactly is unsatisfying? On the face of it, the notion of "one text to express all three things" is not really a formal notion, but a pragmatic one. The point of it is to ease the software engineering process. In order for a bidirectional transformation to be sane (whatever that means) the three elements have to stay consistent. For example, one kind of sanity, discussed last time, is correctness -- after applying a transformation (defined in 2. or 3.) we expect consistency (defined in 1.) to be restored. So, if we change the definition of consistency (1.) we may well have to change the transformations (2. and 3.) to make sure that the whole bidirectional transformation stays correct. Busy software engineers are not very good at remembering that when you do X you also have to do Y. (Let X be "update the code" and Y be "update the documentation" for example...) So the name of the game is to remind the engineer about Y when they do X; or, to be a bit more ambitious, to make it impossible for them to do X without also doing Y. For example, it's better to have a variable called widgetsInStock (and no comment) than to have a variable called x and a comment "x is the number of widgets in stock".

No mention of "same text" yet -- specifying several things in one text is just one possible way to achieve that aim. At the extreme, if we complain to our Java programmer that we don't like the use of Java as a bidirectional programming language, because the three things are specified in different methods, we will not be much happier if the programmer modifies their bidirectional transformation class to have only one method which begins with a switch statement...

What the language of lenses, and to a lesser extent the other languages like TGGs and QVT, do, is in effect to limit the expressivity of the language to only those triples that are well-behaved in some language-dependent sense. In Focal, for example, it's a key part of the language design to ensure that the basic lenses satisfy some lens laws, and that the ways of composing basic lenses into compound lenses preserve those lens laws. The idea is that it is not possible for the lens programmer to write a bidirectional transformation which is insane, for Focal's idea of sanity. Even, maybe, that it isn't possible for the programmer to think about writing an insane program!

That's interesting. Given a language which can express all computable bidirectional transformations -- including the many insane ones -- an obvious question is "is it decidable whether a transformation is sane?" Excuse me while I demonstrate that it's too long since I tutored Computability and Intractability, but it's at least tempting to think that the answer to that is always going to be No, by Rice's Theorem. Here's Rice's Theorem as stated in Papadimitriou's Computational Complexity, p62.

Suppose that C is a proper, non-empty subset of the set of all recursively enumerable languages. Then the following problem is undecidable: Given a Turing machine M, is L(M) in C?

To apply this, let's suppose we wrap up a given computable bidirectional transformation in a Turing machine which takes as input an indicator of what the machine is supposed to do (check consistency, apply a forward transformation, or apply a backward transformation) together with appropriate arguments for the task. If the machine is to check consistency, the appropriate arguments are a pair of models and a boolean: the machine should accept the input iff the boolean correctly indicates whether or not the models are consistent. If it is to do a forward transformation, the arguments are a triple of models, and the machine accepts iff the third model is the transformation's output on being given the first two; and dually.

Regardless of whether the transformation is sane or not, this is a reasonable definition of a Turing machine, so the language accepted by it is recursively enumerable. Modulo some boring coding, it'll have the form of a set of strings which might be

• (consistent, M, N, true)
• (consistent, M, N, false)
• (forward, M, N, N')
• (backward, M, N, M')

and there will be enough of those strings to specify the whole of the transformation.

Now let C be the subset of that set of recursively enumerable languages which represent sane transformations. The amazing thing about Rice's theorem is that we don't have to decide on a notion of sane: provided we ensure that there is some sane transformation, that's enough: the theorem tells us that it is undecidable whether a given Turing machine's language is in C or not.

Unfortunately, this isn't what we wanted to know. Given a TM, there's no reason to think that it'll be obvious whether or not it even is a wrapped-up bidirectional transformation at all; so it's not very interesting that it's undecidable whether or not it's a wrapped-up sane bidirectional transformation. That said, usually the kind of thing we did there is sorted out by some more boring coding, so I guess that "morally" Rice's thm is going to tell us that no non-trivial notion of sanity will be decidable on any language that can express all computable bidirectional transformations. I guess this with enough confidence that I can't muster the confidence to actually check right now...

Conclusion: that wasn't the right question. Onwards and upwards...

What's still wrong with code generation?

Generating code from models is fine, and can certainly save time compared with actually typing that boilerplate stuff that's obvious from looking at the model. Life gets interesting - and that's sometimes a euphemism - when you start editing the code, while still editing the model too, and you need to keep the two in sync. This is often called "round-trip engineering", but if I remember correctly, that's actually a trademark of Rational. Let's call it model-code synchronisation.

Typically, you'll develop a model in UML or some such, then you'll generate code from the model. The generated code will often have special comments of some kind scattered through it to show the tools which bits of the code are autogenerated, and there will often be a notion of some parts of the code "belonging" to the tool, which is interesting. If you add code, code written by you is distinguished from autogenerated code, and the tool is supposed to leave it alone. If you modify code that was autogenerated, you'll probably have to do something to indicate to the tool that you don't want your changes thrown away; maybe you delete one of its special comments. Now, what happens when you modify the model? If you add new structural elements, it's pretty simple: when you press the button, new code gets generated for them and it doesn't interfere (much) with what was there already. What if you delete a structural element from the model? If you do so before any hand-written code has been added that's "owned" by this element, no problem: the autogenerated code should be deleted too. If you have hand-written code for it, then deleting the element from the model is a slightly surprising thing to do. What should the tool do about this? It could restore consistency to the world by deleting the code corresponding to the deleted model element, and in the end that may be the only sensible thing to do. Maybe, though, the presence of that code indicates that more work needs to be done? Maybe it even indicates that deleting the model element is a mistake? It might be better for the tool to indicate in some way that this was a surprising thing to do.

In this particular case, we can probably cover it by something like:

1. enforce a hard separation between code "owned" by the tool and code that "should not be touched" by the tool;
2. any time the tool needs to change or delete code that "should not be touched", do something special, e.g., require confirmation.

However, it's not hard to go on inventing more and more puzzling cases, so we need a systematic way to think about what's reasonable behaviour and what's not.

Since code can be seen as a special kind of model - after all, it records some information about a software system - this is a special case of bidirectional model transformations, which I've been interested in for a while. In general we can think about a definition of model-code synchronisation as involving (a) a definition of what it is for the code and model to be in sync (b) a pair of recipes for fixing it when they aren't. Let's assume that the person pressing the button has just finished editing either the code or the model, and doesn't want their work changed, so that synchronisation should change either the model, or the code, but not both. (How much it complicates things if we allow both to be changed deserves some thought, but the answer is probably "not much".) What should be true? Well, two things seem fairly uncontroversial:

1. if it happens to be the case that the code and the model are already in sync, then nothing should happen. I called this the transformation being hippocratic - "first, do no harm".
2. after the synchronisation, the code and the model should be in sync. I called this the transformation being correct, since the job of the transformation is to restore consistency.

The first of these deserves a bit of comment: isn't it automatic from the second? Well, not if there can be more than one model that's in sync with the same code, or vice versa. (That is, not if the consistency relation can be non-bijective.) Is that likely? Absolutely. For example, a UML model can include sequence diagrams for any parts of its behaviour, so there's an endless choice of model for the same code there. For an example the other way round, anything that's specified in code but not visible in the model can be changed without altering consistency, too.

Notice that in the process of thinking about that, it becomes obvious that there's a real choice about what "being in sync" means, too. How much model is there expected to be for a given code body? If there's a class diagram but no state diagrams, is that in sync, or should there have to be a state diagram for each (important?) class? Which classes are important, and what kind of state diagram? The right answers should, ideally, depend on the needs of the user: they won't be defined once and for all by the tool vendor.

Unfortunately, correctness and hippocraticness - nor their near ancestors, the basic lens laws of Foster, Pierce et al. - are not enough to ensure sensible behaviour. For example, the transformation that silently deletes the user's handwritten code to restore consistency when an element is deleted from the model can perfectly well be correct and hippocratic. More another time on what else we might require...

Logic and algorithms workshop

This week Edinburgh is hosting an ICMS event called Logic and Algorithms . I didn't register for it, but I've been going into the odd talk (and not eating the lunches, as required). This morning saw a lovely tutorial by Phokion Kolaitis on Foundations and applications of schema mappings. Very useful, since this is something I've realised for a while that I know almost nothing about, despite its obvious connections with model transformation. More anon, maybe.
Well, OK... I didn't promise that this blog was readable, let alone correct. So here goes with some notes; caveat lector.

There are two related concepts.

1. Data integration, aka federation, lets you answer queries over multiple data sources as though they were integrated. The data stays where it is, but a new schema is created, against which the user can write queries; something must explain how to translate the query and its results so that the query is done over the actual data sources with their actual schemas, and the results presented to the user in a consistent way.
2. Data exchange, aka translation, really does move the data. You take some data with its original schema; you take a new schema; you explain how to fit the old data into the new schema.

At the time I thought "ah, 1. is model merging, 2. is model transformation". Well, sort of.

The way this field talks about these problems is using schema mappings. A schema mapping is a triple (S,T,\Sigma) [how do I do Greek in this thing, or maths for that matter?! never mind for now!]. S and T are the source and target schemas - let's be thinking about 2. for now - and Sigma is a set of dependencies. There are two kinds of dependencies: source-to-target dependencies Sigma_ST, which model transformation people might think of as the specification of a consistency relation that forms part of a model transformation, and constraints Sigma_T over the target schema, which we might think of as part of the target metamodel. (We see already an example of the common phenomenon that related problems in different areas often put their concept boundaries in different places: another kind of translation problem...)

Then the data exchange problem is to take this triple, and a model I for S, and create a model J for T which satisfies Sigma. We might say: given a pair of metamodels S (plus some constraints which are not specified because we're about to be given the data as well and it is guaranteed to satisfy whatever it has to: let's write S+) and T plus Sigma_T (let's write T+), and a consistency relation Sigma_ST, and a model I for S+, construct J which is a model for T+ such that (I,J) satisfy the consistency relation.

At this point, the database people observe that solutions may not exist, or if they exist, may not be unique, and they go on to define and study the existence-of-solutions problem which is: for a given M and I, does a solution J always exist? This is initially puzzling from a model transformation point of view, because in our world, we would not expect it to be useful to try to apply a model transformation which is defined only by its consistency relation. It's sort of the whole point that we have to have some way of choosing among solutions: we expect the consistency relation to be only part of the specification of a model transformation; we expect to add a constructive procedure of some kind to explain how to construct a target model, at which point non-existence is "just" a bug in the program. Still, I'd like to be able to say confidently whether or not we can write transformations which are not actually executable (at all, never mind non-determinacy) in (fragments of) our favourite bidirectional transformation languages, so maybe it would be useful to think about this more.

Back in the database world, they observe that there's an important question concerning the language in which the constraints are written. FOL is too strong - the existence of solutions problem is undecidable - so they look at fragments. It turns out that what happens is very sensitive to which fragment they choose.

Time to go to the next talk; maybe even more anon. Do let me know if you're reading this: perhaps I should offer a small prize for the first comment.

First post

Welcome to my blog on software engineering research. I don't make any particular promises for it: it may prosper, or not. My main intention is to use it as a place to write notes that don't amount to papers: somewhere to mention interesting papers, or issues that I or someone else might want to think about some time, or whatever. If I say anything you find interesting, do comment or email me!