Wednesday, February 03, 2010

Multidimensional Separation of Concerns, or Matrix Inheritance

I just spotted a paper that I didn't know existed before. Abstract:

Done well, separation of concerns can provide many software engineering benefits, including reduced complexity, improved reusability, and simpler evolution. The choice of boundaries for separate concerns depends on both requirements on the system and on the kind(s) of decomposition and composition a given formalism supports. The predominant methodologies and formalisms available, however, support only orthogonal separations of concerns, along single dimensions of composition and decomposition. These characteristics lead to a number of well-known and difficult problems.

This paper describes a new paradigm for modeling and implementing software artifacts, one that permits separation of overlapping concerns along multiple dimensions of composition and decomposition. This approach addresses numerous problems throughout the software lifecycle in achieving well-engineered, evolvable, flexible software artifacts and traceability across artifacts.

I came up with a remarkably similar concept I called matrix inheritance in a previous job. Here's one description I've written up out there on the web:

[This is a description of a symptom of the problem.] Nested if-then-else can introduce non-essential complexity merely by having dead nested cases which are actually obviated by outer cases; looking at a complex version of this code, it can become quite difficult to see where exactly the code is supposed to flow under what circumstances, as there can seem to be conflicting assumptions in different areas.

Once upon a time I invented a scheme to solve this problem in the best way I thought possible, and called it "matrix inheritance". The problem with inheritance and subclassing is that it only handles a single dimension of customization. Suppose you have two dimensions, genre and type, such as [comedy, drama] and [movie, series]. If you were to try and classify any given thing under a classical type breakdown, you could subclass by one axes or the other, but you would need to duplicate subclassing for the remaining axes. So, you could end up with Programme, Comedy <: Programme, Drama <: Programme, but then you'd need ComedyMovie, ComedySeries, DramaMovie, DramaSeries, duplicating the kind axis in the two different branches.

The matrix inheritance concept basically takes the cartesian product of all option axes, essentially modelling it as an n-dimensional space, and then applies behaviour to sub-spaces of this space. So, you could apply conditions to [drama,*] and [*, series], with these two representing slices of the example 2-dimensional space described above. The advantage of modelling things this way is that it is declarative: you can analyse overlaps and identify un-covered space.

Here's the original post I made on comp.compilers when looking for related work. Here's a brief excerpt:

Object-oriented techniques have been rejected because they constrain me to using a fixed order of dimensions for reuse and overriding. A possible solution presents itself:

1. Creating a notional Cartesian-product of all dimensions of customization.

2. Overriding based on the application of rules whose scope is defined by sets described by a simple language: by example, '{a,b}' represents the set containing a and b, while '*' represents the set containing all the values for that dimension.

4 comments:

Marc said...

I think a good, and not too hard to understand, example of this is handling collisions in the game of asteroids. (There are several types of objects: you, bullets, asteroids and spaceships) and the result of a collision depends on both objects).

This cannot be done with a virtual method (without much code duplication) as it requires some form of double-dispatch which the majority of languages don't support.

Vagn J said...

Isn't this what is typically called multi methods?

Barry Kelly said...

No. Multi-methods resolve the method to call using the run-time type of more than one argument of the method call, whereas virtual methods resolve the method using only the run-time type of the first argument (the receiver).

The matrix inheritance concept is independent of notions of virtual methods, and applies to the behaviour of a notional "method" under certain circumstances or configurations - not necessarily related to any of the arguments. The degree to which it is related to virtual method resolution depends on how you implement configuration or conditional method selection via inheritance.

The problem with inheritance is that you have to choose an ontological hierarchy, but the ontology of the domain doesn't necessarily imply that one category is a superset of another category - rather there can be independent dimensions of behaviour.

Matrix inheritance inverts the problem. Rather than selecting which methods get overridden by who, and have to contort your hierarchy to fit, one annotates the methods such that they should apply in different subspaces of the Cartesian product of configuration, or behaviour, dimensions.

If you look in the paper I link to - though you may need to search for another download link, it doesn't seem to be cached by CiteSeer any more - you can see what they call "hyperslices" in Figure 3 on PDF page 7 (113 in the text). Different aspects of the system, such as the syntax check, semantic check, etc., can be configured independently of the class hierarchy. An entire set of methods across the whole class hierarchy can be "overridden" en masse. You should see that 'check()' is defined in both the syntax and semantic check slices. You can think of them as overrides, but they are rather ways of composing the whole program depending on which aspects you want to include, i.e. depending on circumstances or configuration options.

Patrick said...

Eh Barry, since you obviously don't mind writing lengthy explanations, could you tell how this relates to Aspect Oriented programming? And to partial classes? TIA!