Modularity in many dimensions

I recently read Doug Janzen and Kris De Volder's paper Programming with Crosscutting Effective Views. I grok a little more clearly now what Gregor Kiczales meant by the word "effective" in the OOPSLA 2007 talk I discussed in my last post. In Janzen and De Volder's terms, a view is effective when it can mediate changes to the underlying model. The problem of making a view effective, sometimes called the problem of bidirectionality, is a tricky one, but won't concern us here. Instead I'm going to talk about what Kiczales and others call fluid AOP, for which effective views are essential.

One program, many faces

Aspect-oriented programming (AOP) is the latest development in our ongoing battle with the problem of modularity. But although AOP, in its standard form, represents a useful step forward, it ultimately succumbs to the very problem it sets out to address: the fact that that some aspects or features of a system cross-cut others. By rearchitecting an OO system into a set of aspect declarations, one often merely inverts the modularity problem, distributing the behaviour of the original classes over the implementation of various aspects. What would previously have been a localised change to the class structure may now involve a change to several aspects.

Fluid AOP addresses this issue by taking a much less static view of programs. The idea is to treat aspects as editable -- "effective" -- views which are generated on demand for particular coding activities. For persistence purposes, one view is nominated as the "primary decomposition". (With a legacy language this may just be the regular source view, but in principle the primary decomposition can be any view that suffices to determine all the others.) Making these views effective is where bidirectionality comes in: each view must define how edits are "put back" as edits to the primary decomposition.

Before we come to fluid AOP, I want to revisit its motivation, and in particular the modularity challenge which is sometimes called The Expression Problem. My claim will be that, although some languages may be able to solve the Expression Problem, the more general modularity problem requires more than just fancy language features. Some kind of "fluidity", it seems, is essential. I'll close by suggesting that fluidity be understood in meta-linguistic terms: views must be seen as syntax, and inspection and manipulation of views as a form of meta-programming, often refactoring. "Effectiveness" (bidirectionality) is a challenge that needs to be tackled within this framework.

But I'm getting ahead of myself. Let's start with modularity. I'll understand modularity to mean, roughly, the extent to which a change to or extension of functionality requires only local changes. I want to make the case that the pursuit of "absolute" modularity is doomed: that we must always ask "modularity with respect to what kind of change?" In effect the question "how modular is my software?" is one that should be qualified by a class of transformation. If you're already familiar with the Expression Problem, you can skip the next section.

Modularity with respect to what?

Imagine we're writing an interpreter in, say, Java, for a simple language for integer arithmetic. We crank out the usual OO class hierarchy:

abstract class SyntaxNode {
    public abstract int eval ();
}

class Add extends SyntaxNode {
    public SyntaxNode left, right;

    public int eval () {
        return left.eval() + right.eval();
    }
}

class IntegerLiteral extends SyntaxNode {
    public int val;

    public int eval () {
        return val;
    }
}

(Don't worry about the fact that the fields are public; that's just me being lazy.)

We can make the observation here that adding a new kind of node involves only local changes: we just add a new node class and implement eval:

class Multiply extends SyntaxNode {
    public SyntaxNode left, right;

    public int eval () {
        return left.eval() * right.eval();
    }
}

What we have identified is a modularity property: modularity with respect to the addition of new node types.

Now let's consider a different kind of change. Instead of a new kind of node, we want to provide a new kind of operation on nodes, say a toString method. One might be tempted to add the following code to the SyntaxNode class:

public final String toString () {
    if (this instanceof IntegerLiteral) {
        IntegerLiteral op = (IntegerLiteral)this;
        return op.val;
    }
    else
    if (this instanceof Add) {
        Add op = (Add)this;
        return op.left.toString() + " + " + op.right.toString();
    }
    else
        throw new AbstractMethodError();
}

The problem with this approach, as we all know from standard OO doctrine, is that our über-method has to know about every kind of syntax node; in particular if we want to add a new kind of syntax node, we need to update this method as well to add a new clause:

    ...
    if (this instanceof Multiply) {
        Multiply op = (Multiply)this;
        return op.left.toString() + " * " + op.right.toString();
    }
    ...

So what we don't like about this approach is that it violates modularity with respect to the addition of new node types.

In a functional language like Haskell this particular kind of modularity failure isn't considered bad; in fact it's normal! Our class hierarchy would correspond to an algebraic data type:

data SyntaxNode =
    Add SyntaxNode SyntaxNode |
    IntegerLiteral Int

All our functions would start with a case analysis, the functional counterpart of a type switch:

eval :: SyntaxNode -> Int
eval x = case x of
    Add a b -> eval a + eval b
    IntegerLiteral n -> n

toString :: SyntaxNode -> String
toString x = case x of
    IntegerLiteral n -> show n
    Add a b -> toString a ++ "+" ++ toString b

and adding a new kind of node would require modifying every function to add the corresponding clause.

But returning to the world of OO, the "right" way to define toString is as follows:

class SyntaxNode {
    ...
    public abstract String toString();
}

class Add {
    ...
    public String toString () {
        return left.toString() + " + " + right.toString();
    }
}

This allows us to maintain modularity with respect to the addition of new node types. As before, we need only define a new class and provide an implementation of the various abstract methods:

class Multiply extends SyntaxNode {
    public SyntaxNode left, right;

    public int eval () {
        return left.eval() * right.eval();
    }

    public String toString () {
        return left.toString() + " * " + right.toString();
    }
}

But clearly this kind of modularity actually came at the expense of modularity of a different kind. To make it easy to add node types, we had to spread our toString implementation across the class hierarchy. In other words adding new operations entails modifying each class; the design thus lacks modularity with respect to the addition of new node operations.

FPers usually inhabit the other corner of the trade-off space: they enjoy modularity with respect to new operations, but not with respect to new node types. Although we could probably achieve a similar inversion of modularity in Haskell:

class SyntaxNode a where
    eval :: a -> Int
    toString :: a -> String

data IntegerLiteral = IntegerLiteral Int
instance SyntaxNode IntegerLiteral where
    eval (IntegerLiteral n) = n
    toString (IntegerLiteral n) = show n

data SyntaxNode a => Add a = Add a a
instance SyntaxNode a => SyntaxNode (Add a) where
    eval (Add a b) = eval a + eval b
    toString (Add a b) = toString a ++ "+" ++ toString b

data SyntaxNode a => Multiply a = Multiply a a
instance SyntaxNode a => SyntaxNode (Multiply a) where
    eval (Multiply a b) = eval a * eval b
    toString (Multiply a b) = toString a ++ "*" ++ toString b

In either paradigm, it seems that we're torn between operations cross-cutting data types, and data types cross-cutting operations (although OO prefers the former, and FP the latter). Which of these two alternatives is the "more modular" simply depends on whether it's operations, or data types, that we intend to modify. That's not to say that whether a design is modular is a mere matter of taste or opinion, but just that modularity is relative to what you're trying to do.

The multi-dimensional modularity problem

It's tempting to look for a "linguistic" solution to this problem. Perhaps with the right language feature (or the right design pattern), it would be possible to make a program modular with respect to both kinds of transformation simultaneously. Some time ago Philip Wadler dubbed this challenge the Expression Problem. (Although discussion of the problem itself goes back further: see for example this chapter of SICP. Thanks Noel!) CLOS-style multi-methods are one linguistic approach to this problem; design patterns such as Extensible Visitor are another.

But although there certainly are linguistic approaches to the Expression Problem, there is usually a cost in terms of design-time cohesion. Multi-methods and similar approaches work precisely by making programs more granular (less cohesive), and then relying on a dispatch mechanism to compose the fragments (restore cohesion) at run-time. The point of the granularity is precisely to achieve modularity: behaviour can often be added or modified by just dropping in a new code fragment. But the loss of any unified view of individual features or behaviours means the programmer has to mentally execute the composition rules in order to know what will happen when the program runs. And the cohesion problem only gets worse when you try to generalise these approaches to multiple dimensions of composition.

Standard "static" AOP is not really a response to the Expression Problem but to this more general problem of multi-dimensional composition. It avoids the granularity problem associated with multi-methods and similar approaches by allowing us to specify aspects as cohesive design-time modules. But the very cohesion of these definitions means that they are inevitably cross-cut by other features of the system. These features can now only be understood by reasoning about how the aspects are woven into them. The benefit of increased modularity in some respects has, as with our interpreter example earlier, been bought at the price of reduced modularity in others.

The basic problem is that there is no static language feature that can universally resolve the tension between modularity and cohesion. What we really need is greater fluidity. Since no design can anticipate its evolution, the capacity to "remodularise" a program quickly is much more valuable than any particular contingent modularity property. Our programming tools should allow us to eliminate degrees of freedom which we no longer wish to exploit (so they don't distract us from the task at hand), and introduce, in their place, the degrees of freedom required to achieve that task, safely and easily. This is the promise of tool-based approaches such as fluid AOP: "just-in-time cohesion".

Cohesion-on-demand turns weaving and unweaving into a browsing activity. The programmer no longer has to reason about complex composition rules à la multi-methods or static aspects, as she can simply inspect the content of the relevant view.

Where fluid tools become fluid languages

So it seems like fluid AOP is the only plausible approach to the problem of multi-dimensional modularity. It's hugely exciting, but also rather daunting when one thinks about what's involved in making the vision a practical reality. The words "indistinguishable" and "magic" come to mind. I'm well out of time and space resources, so I'll wrap up for now by just sketching what I see as the way forward.

Shortcomings aside, linguistic approaches have one indispensible property: they offer well-defined semantics for multi-dimensional composition. (As an example, see this paper, which extends Hindley-Milner type inference with static advice weaving.) The future of fluid AOP lies I think in harnessing this linguistic precision in an interactive tool.

After all, if we hope to rely on "fluid aspect" views to visualise key features of our software, as well as mediate critical changes to it, then they really are "the source files of the future". How the contents of the various views are combined, how edits are put back, and so forth, will have to be precisely defined. In turn, this will require fluid aspects to have well-defined syntax.

Indeed the difference between fluid aspects and traditional syntax trees is not one of kind, but only of lifecycle: they are built on the fly in response to the user's changing goals, and may co-exist with other effective views that share the same underlying model. But otherwise they are just plain ol' syntax. We see a taste of this in the "virtual source files" of Janzen and De Volder, as well as in the "fluid source code views" of Desmond et al.

(Of course I don't mean that we should necessarily store such syntactic artifacts in text files, or present them to users as flat, uninterpreted text; but in an uncontroversial sense they are "just syntax". This was the point of my post Why syntax won't go away.)

A corollary of this perspective is that we must regard our interactions with these views as a form of meta-programming. Matt Hellige expressed the same idea when he suggested that we think of "programming-time" as a computational stage. To interact is to effect a syntactic transformation. Switching to a new view of a program is really just a refactoring.

A mature AOP, then, is not a static language feature as such, but an interactive meta-programming activity: the process of refactoring a program into a view that provides a single locus of change for the edit you want to apply. Refactoring back to the original view distributes ("puts back") your change into all the relevant places. We could for example implement the toString method we defined earlier as a single type switch, for convenience; expand it over a class hierarchy, in order to add a new node type like Multiply; collapse it back to a single method again, perhaps to modify its signature; expand it again, to add more node types; and so on.

The toggling, in this hypothetical scenario, between two different points in modularity space is little more than the iterated application of the refactoring Inline method and its inverse. For an overriding method, Inline method injects the body of the method to be inlined into a new clause of a type switch in the overridden method. There are really just two syntactic presentations of the "same" system here, and a function that computes one view from the other, that happens to be able to compute backwards as well as forwards. (Ok, ok: maybe there's just an incey, wincey little bit of work to do to distinguish this from magic.)

FInCo 2007

Here is the draft of a FInCo 2007 paper which elaborates (although still entirely informally) the programming model called declarative interaction which I mentioned in my first posting. FInCo is one of the satellite workshops of ETAPS 2007.

The review comments were useful, and reasonably positive. I'm looking forward to some interesting discussions. I conspicuously failed to give even a passing nod to agent-oriented programming; given the likely focus at the workshop, this is something I need to learn about.

Programming languages for interactive computing

Almost all software systems today are interactive, in that they maintain ongoing interactions with their environments, rather than simply producing a result on termination [GSW06]. Indeed, a consistent trend since the beginning of the digital era has been towards increasingly interactive systems. The trend has progressed on at least two fronts: enhancements to end-user interactivity, and increasingly integrated systems. The trend began with the first teletype and textual interfaces and continued through early GUIs and LAN-based operating systems. It continues with today's 3D virtual worlds and applications deployed over the wide-area network.

With the Internet emerging as the "global operating system", the pressure on our software to be interactive is greater than ever before. Consider how the following requirements can be understood in terms of enhanced interactivity:

• Ability to reconfigure or repair applications without taking them offline → interaction with code as well as data
  
• Long-running, continously-available applications → interaction must be robust
  
• Sessions resumable from wherever we happen to be located → persistence of interactions
  
• Transparent recovery from latency problems and intermittent connectivity → interaction should not be semantically sensitive to the network
  
• Mobile code whose behaviour depends on execution context → dynamically scoped interactions
  

A variety of process algebras and other formalisms have been developed for modelling and reasoning about interactive systems. Yet despite the trend towards greater interactivity, we continue to lack a simple and coherent paradigm for building robust interactive systems. The main bugbear that has faced us has been what we might characterise as an "impedance mismatch" between traditional algorithmic programming languages and the way interactive systems abstractly work. Whereas an algorithmic language treats a program as a black box which produces a final value on termination, an interactive system allows other systems to observe and influence its behaviour as it executes, and must adjust its internal state in response to each interaction to maintain the consistency of the computation.

In current desktop systems, the mismatch is usually resolved by representing the state of the system as a set of mutable stores and then employing a notification scheme to maintain the consistency of the state. Rather than the host language being used to execute a single sequential program to termination, it is employed to execute fragments of imperative code as interactions occur. Each executed fragment must produce exactly the side-effects required to synchronise the state of the system correctly.

Unfortunately this near-universal reliance on the imperative to support interaction has come at an enormous cost in complexity. It will be useful here to recall Brooks' distinction between essential and accidental (or inessential) complexity [Bro87]. Complexity inherent in the problem itself (from a user's perspective), or which can be attributed to human factors, is essential; what remains is accidental or inessential. Interactive systems as currently implemented are dominated by inessential complexity, the main culprits being this ad hoc management of state, explicit concern with flow of control, and unnecessary use of non-deterministic concurrency. Imperative languages (ab)used in this way are the "Turing tar-pit in which everything is possible but nothing of interest is easy" [Per82]. Web applications only complicate things further, by adding a variety of ill-defined staging policies and interaction models into the mix.

Ironically, what unifies much of this inessential imperative complexity is that it exists in the service of essentially declarative ends. Indeed, I suggest that the reason the current paradigm works at all is that systems implemented in this way approximate a much simpler, declarative model of interactive computation. Experienced software designers rely tacitly on something like this declarative model in order to make decisions about what counts as reasonable behaviour. Rather than being ill-suited to interaction, as is sometimes assumed, perhaps because of the somewhat arcane feel of techniques such as monads [JW93][Wad99] for modelling effectful computation, the declarative paradigm - with a simple orthogonal extension to support interactivity - fits the abstract behaviour of interactive, stateful systems surprisingly well. But today, because this declarative behaviour is achieved only indirectly, interactive systems are significantly less reliable and understandable than they need to be, despite the widespread use of design patterns such as Observer [GHJV95] to manage some of the inessential complexity. State-related dysfunctions in particular, such as the gradual degradation of a system over time, spurious sensitivities to the order in which two operations take place, deadlocks and race conditions, are common. I propose that the best way to address the impedance mismatch between algorithmic languages and interactive systems is not to wallow in the tar-pit of imperative languages, but to lift declarative languages into a computational model which supports interaction directly.

The aim of this blog is to explore the conceptual foundations of such a programming model, which I shall refer to as the declarative interaction model. Developing a formal semantics will be a topic for later treatment. Like some other declarative approaches to interaction, the declarative interaction model maintains a clean separation of (stateless, deterministic) declarative computation and (stateful, non-deterministic) reactive computation. The model is distinguished by its modal construal of interaction, whereby an interactive system is taken to be a space of canonically represented "possible worlds", each expressing a purely declarative computation, along with an index into that space indicating the "actual world", which represents the system's current state. To interact with such a system is to select a new actual state from this space of possible states. Interactions (effectful operations) are lifted to meta-programs that manipulate values of modal type; crucially, they are unable to interfere with the purely declarative semantics of each possible state, and in any case are only required when they are essential to application logic. Non-determinism arises from concurrent interactions, which are handled transactionally.

The declarative interaction model relates to many active research areas, including modal type systems, incremental computation, meta-programming, declarative concurrency, transactional concurrency, dataflow computing, interactive computing, and wide-area computing. As we shall see, four closely related concepts in particular are central to the model: modality, incrementality , concurrency, and persistence. A key validation of the model will be the development of an interactive programming language which supports the model directly.