The Inverse Extension Design Pattern

by Shannon Behrens


In object-oriented programming, it is common for a child class's method to
extend the parent class's method. However, inverting this pattern is useful
as well. Although most object-oriented programming languages support the
former, I have never encountered one that supported the latter. Nonetheless,
it is possible to implement this pattern without explicit support from
the programming language, just as it was possible to implement inheritance
in C before C++ was created.

A few interesting features of normal extension should be kept in mind. First,
a child class can call its parent class's method anywhere within its own method.
Hence, the child class is responsible for determining if the parent gets to
go first, last or somewhere in the middle. Secondly, the child class gets to
choose what to pass to the parent class's method and what to do with
whatever, if anything, the parent class's method returns. Naturally, these
properties hold for each step in the entire class hierarchy. When inverting
this pattern, these properties are inverted as well. Hence, the parent class
is responsible for determining if the child gets to go first, last or somewhere
in the middle. Furthermore, the parent class gets to choose what to pass to
the child class's method and what to do with whatever, if anything, the child
class's method returns (see Figure 1).


____________
| A        |        ^                   |
|__________|        |                   |
| method() |        |                   |
|__________|        |                   |
     |              |                   |
    /_\             |                   |
_____|______        |                   |
| B        |        |                   |
|__________|        |                   |
| method() |        |                   |
|__________|        |                   |
     |              |                   |
    /_\             |                   |
_____|______        |                   |
| C        |        |                   |
|__________|        |                   |
| method() |        |                   |
|__________|        |                   v

Class Hierarchy     Normal Extension    Inverse Extension

                              Method Invocation

Figure 1. Compare Extension with Inverse Extension

The fact that the parent class's method "wraps" the child class's method rather than
the other way around is the whole motivation for this pattern. At first glance, it
is natural to suggest using the Template Method pattern: in the parent class A's
method "a", call the child class B's method "b". This indeed implements the
wrapping behavior, but it is not scalable. For instance, if a grandchild class C
is added, if b is to wrap C's method, C must add a method c. Creating a new name
for each step in the hierarchy is nowhere near as elegant as simply
calling "super", which you can do with normal extension. Furthermore, creating
such names is not flexible. Suppose you wish to move C to be a subclass of A.
Aside from changing the C's parent class, you also must rename its c
method b. As your class hierarchies get larger, this irritation becomes worse.

In traditional HTML, that is, in HTML where tables are used for layout, this
pattern is quite helpful. The parent class is called the Layout. It has a
method that lays out the page, deciding where the navigation should go and
where the main content should go. The child class is called the Screen. It
has a method that outputs the main content. Although the Screen inherits
from the Layout, it is the Layout's method that takes control first. The
Layout then passes control to the Screen's method--the opposite of
"super"--when it is time for the Screen's method to do its work. To change
the navigation used on a particular Screen--login pages and help pages usually
look quite different from normal pages--simply change that Screen's parent class.
To have all of the Screens in a section have their own sub-navigations, subclass
the existing Layout with a new Layout and have the Screens subclass the new Layout.
Applicability
Inverse Extension can be used when the behavior of the parent's method should decorate
the behavior of the child's method instead of the other way around, especially
if this is true for more than two layers of the class hierarchy. You
also can use inverse extension when a parent class method needs to control
access to the method of its child class.
Structure, Participants and Collaborations
The structure of the class hierarchy is the same as it is for normal
extension. One participant is the Parent (Layout), whose method wraps the
child class's method. The other participant is the Child (Screen), whose
method does the main task at hand, without having to worry about many of
the details that the parent class's method handles for it.

The Parent class's method decides when and if to forward the flow of
control to the Child class's method. It optionally may perform additional
operations before and after forwarding the flow of control. It may pass
any argument it wants to the Child class's method and do anything it wants
with whatever, if anything, the Child class's method returns.
Consequences
The Inverse Extension pattern has the following benefits and liabilities:

  • Changing the child class's parent class easily changes all of the code that
    wraps the child class's method. In the example above, changing a normal
    Screen's look-and-feel to match that of a help page involves simply
    changing the Screen's parent (a Layout). No code within the Screen itself
    needs to be changed.
  • The hierarchy is necessarily fixed. This pattern is not appropriate if you
    need to change the decorator dynamically. The Decorator pattern is more
    appropriate in that case.
  • It is hard to implement. If this pattern is not implemented by the
    programming language, it may be challenging to implement manually.
    Specifically, it requires a bit of meta-programming--navigating the
    inheritance hierarchy and dynamically looking up methods, through
    reflection.

Implementation
As mentioned above, implementing this pattern manually requires a bit of
meta-programming:

  1. You must be able to iterate over the class hierarchy. In languages
    such as Python that support multiple inheritance, I have found it
    helpful to constrain the iteration to the "leftmost", that is, the most
    primary, classes in the hierarchy, assuming that the others
    probably would be mixins.
  2. While iterating over the class hierarchy, you must be able to save a
    reference to a method of a given name. That is, given an instance "obj"
    and a method "m", the goal is to loop over the classes in obj's class
    hierarchy and find all the classes that define m, keeping a list of
    references to those methods.
  3. You must have a way for the parent class's method to call the child
    class's method. Having created the list of methods named m above, the
    parent class's method must be able to call the next m in the
    list.
  4. It may be irritating to have a child class's method signature be
    constrained by a parent class's method signature. Suppose a parent
    class, A, has two child classes, B and C. A is generic, whereas B and C are more specific. Let's apply Inverse Extension to
    the method m. B.m may wish to receive one argument whereas C.m
    wishes to receive two arguments. In normal extension, calling B.m or
    C.m with a differing number of arguments is no problem. To maintain
    this flexibility for Inverse Extension, it is important that B.m and
    C.m be able to have signatures that are different from each other
    and from A.m. To implement this, a "varargs" feature in the language is helpful. It
    often is appropriate for the parent class's method to accept an arbitrary
    number of arguments and simply pass them unmodified to the child class's
    method.
  5. Should the caller know Inverse Extension is happening? A coworker,
    David Veach, noticed that in normal extension, calling obj.m() hides
    whether extension is happening in m. It often makes sense to observe
    this constraint when applying Inverse Extension.

Sample Code
Python's dynamic nature makes implementing Inverse Extension straightforward.
In consideration of the points above, it isn't difficult to loop over an object's
class hierarchy, thanks to the __bases__ attribute. Nor is it hard to look up
a method of a given name in each class, thanks to "getattr".

When calling a parent class's method m, a function named callNext is passed as
the first argument. callNext can be invoked anywhere within the method to
transfer control to the child class. callNext is implemented using a
closure, containing references to the inheritance hierarchy. In Java, an Iterator
offers a similar mechanism. Python also supports a varargs feature, hence the
child class's method need not be constrained by the parent class's method.

In the sample code I have provided, in the interest of simplicity, I have not
tried to hide the Inverse Extension pattern from the caller. Nonetheless,
hiding the implementation of a private method that uses Inverse Extension
behind the API of a public method is a trivial matter.

Listing 1 contains the sample implementation in Python. Anthony Eden helped
me to create a similar Java implementation, InverseExtend.java, which
is shown as Listing 3 at the end of this article.

Listing 1. Sample Code in Python


def inverseExtend(boundMethod, *args, **kargs):

    """Iterate downward through a hierarchy calling a method at each step.

    boundMethod -- This is the bound method of the object you're interested in.
    args, kargs -- The arguments and keyword arguments to pass to the
        top-level method.

    You can call this method via something like this:

        inverseExtend(object.method, myArg, myOtherArg)

    When calling the method at each step, I'll call it like this: 

        Class.method(object, callNext, *args, **kargs)

    However, the lowest level class's method has no callNext parameter,
    since it has no one else to call:

        Class.method(object, *args, **kargs)

    In the method:
    
        callNext(*args, **kargs) 
        
    should be called when it is time to transfer control to the subclass.  This
    may even be in the middle of the method.  Naturally, you don't have to pass
    *args, **kargs, but a common idiom is for the parent class to just receive
    *args and **kargs and pass them on unmodified.

    """

    # Build all the necessary data structures.

    obj = boundMethod.im_self
    methodName = boundMethod.im_func.__name__

    # Figure out the classes in the class hierarchy.  "classes" will
    # contain the most senior classes first.

    Class = obj.__class__
    classes = [Class]
    while Class.__bases__:
        Class = Class.__bases__[0]
        classes.insert(0, Class)

    # Skip classes that don't define the method.  Be careful with getattr
    # since it automatically looks in parent classes.  

    last = None
    methods = []
    for Class in classes:
        if (hasattr(Class, methodName) and 
            getattr(Class, methodName) != last):
            last = getattr(Class, methodName)
            methods.insert(0, last)

    def callNext(*args, **kargs):
        """This closure is like super(), but it calls the subclass's method."""
        method = methods.pop()
        if len(methods):
            return method(obj, callNext, *args, **kargs)
        else:
            return method(obj, *args, **kargs)

    return callNext(*args, **kargs)


# Test out the code.
if __name__ == "__main__":

    from cStringIO import StringIO

    class A:
        def f(self, callNext, count):
            buf.write('<A count="%s">\n' % count)
            callNext(count + 1)
            buf.write('</A>')

    class B(A):
        # I don't have an f method, so you can skip me.
        pass

    class C(B):
        def f(self, callNext, count):
            buf.write('  <C count="%s">\n' % count)
            callNext(count + 1)
            buf.write('  </C>\n')

    class D(C):
        def f(self, count):
            buf.write('    <D count="%s" />\n' % count)

    expected = """\
<A count="0">
  <C count="1">
    <D count="2" />
  </C>
</A>"""

    buf = StringIO()
    d = D()
    inverseExtend(d.f, 0)
    assert buf.getvalue() == expected
    buf.close()

Sidebar: Implementing the Pattern Using Python's New Generators
For fans of functional programming, serious Python hackers and other
hardcore engineers who think the callNext parameter is inelegant, I
offer an alternate Python implementation of this pattern using Python's new
generators. Listing 2 uses generators for non-local flow of control. No
callNext parameter is needed. Each parent class method does a
yield *args, **kargs when it is time to call the child class's method. In fact,
this implementation flattens the recursion down to a loop, despite the fact
that the code is not tail recursive. In this way, it is similar to a
continuation. The one drawback of this implementation is it is not
possible to maintain the return value semantics of the earlier
implementation. That is, it is not possible for each child class method to return a value to its
parent class method because of the nature of generators. Nonetheless, I
offer Listing 2 as an intriguing use of generators.

Listing 2. Generator Code for Non-Local Flow of
Control


import types


def inverseExtend(boundMethod, *args, **kargs):

    """Iterate downward through a hierarchy calling a method at each step.

    boundMethod -- This is the bound method of the object you're interested in.
    args, kargs -- The arguments and keyword arguments to pass to the
        top-level method.

    You can call this method via something like this:

        inverseExtend(object.method, myArg, myOtherArg)

    When calling the method at each step, I'll call it like this: 

        Class.method(object, *args, **kargs)

    Each parent class method *must* be a generator with exactly one yield
    statement (even if the yield statement never actually gets called), but the
    lowest level class method must *not* be a generator.  In the parent class:
    
        yield args, kargs

    should be called when it is time to transfer control to the subclass.  This
    may be in the middle of the method or not at all if the parent class does
    not wish for the child class's method to get a chance to run.  

    """

    # Build all the necessary data structures.

    obj = boundMethod.im_self
    methodName = boundMethod.im_func.__name__

    # Figure out the classes in the class hierarchy.  "classes" will
    # contain the most senior classes first.

    Class = obj.__class__
    classes = [Class]
    while Class.__bases__:
        Class = Class.__bases__[0]
        classes.insert(0, Class)

    # Skip classes that don't define the method.  Be careful with getattr
    # since it automatically looks in parent classes.  

    last = None
    methods = []
    for Class in classes:
        if (hasattr(Class, methodName) and 
            getattr(Class, methodName) != last):
            last = getattr(Class, methodName)
            methods.append(last)

    # Traverse down the class hierarchy.  Watch out for StopIteration's which
    # signify that the parent does not wish to call the child class's method.
    # generatorMethods maps generators to methods which we'll need for nice
    # error messages.

    generators = []
    generatorMethods = {}
    for method in methods[:-1]:
        generator = method(obj, *args, **kargs)
        assert isinstance(generator, types.GeneratorType), \
            "%s must be a generator" % `method`
        try:
            (args, kargs) = generator.next()
        except StopIteration:
            break
        generators.insert(0, generator)
        generatorMethods[generator] = method

    # If we didn't have to break, then the lowest level class's method gets to
    # run.

    else:
        method = methods[-1]
        ret = method(obj, *args, **kargs)
        assert not isinstance(ret, types.GeneratorType), \
            "%s must not be a generator" % method

    # Traverse back up the class hierarchy.  We should get StopIteration's at
    # every step.

    for generator in generators:
        try:
            generator.next()
            raise AssertionError("%s has more than one yield statement" %
                                 `generatorMethods[generator]`)
        except StopIteration:
            pass


# Test out the code.
if __name__ == "__main__":

    from cStringIO import StringIO

    class A:
        def f(self, count):
            buf.write('<A count="%s">\n' % count)
            yield (count + 1,), {}
            buf.write('</A>')

    class B(A):
        # I don't have an f method, so you can skip me.
        pass

    class C(B):
        def f(self, count):
            buf.write('  <C count="%s">\n' % count)
            yield (count + 1,), {}
            buf.write('  </C>\n')

    class D(C):
        def f(self, count):
            buf.write('    <D count="%s" />\n' % count)

    expected = """\
<A count="0">
  <C count="1">
    <D count="2" />
  </C>
</A>"""

    buf = StringIO()
    d = D()
    inverseExtend(d.f, 0)
    assert buf.getvalue() == expected
    buf.close()

Known Uses
Perl Mason uses the Inverse Extension
pattern as a key component of its templating capabilities. A parent template
can provide a common look-and-feel for each of its child templates. Naturally,
a child template has no idea what part of the layout it belongs in, so it is
necessary for the parent template to call the child template with the call
$m->callnext when it is time to produce its output. Perl Mason was the inspiration
for the same feature in my Python Web application framework
Aquarium, as well
as for this article.
Related Patterns
The Template Method pattern is similar to the Inverse Extension pattern
when there are only two levels in the class hierarchy. Each involves a
parent class method calling a child class method. However, as mentioned
above, the Inverse Extension pattern is more appropriate when the Template
Method pattern needs to be applied recursively--when there is an
arbitrary and varying number of classes in the class hierarchy. If the
class hierarchy is deep and volatile, creating a new method name at each
step, which is required by the Template Method pattern, is not scalable.

The Decorator pattern is similar to the Inverse Extension pattern, because
the decorating class's method calls the decorated class's method. However,
the Decorator pattern is applied at runtime instead of being based on the
class hierarchy. If you need to wait until runtime in order to associate
which objects get to decorate which other objects, use the Decorator
pattern to apply the decorators dynamically. If you want the decorators to
be applied automatically based on the class hierarchy, use the Inverse
Extension pattern.

Listing 3. Sample Code in Java


Listing 3.
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;

/**
 * @author Anthony Eden, Shannon Behrens
 */

/**
 * This class has a static method, <code>inverseExtend</code>, that implements
 * the Inverse Extension design pattern.
 */
public class InverseExtend {

    private Object obj;
    private String methodName;
    private Object arg;
    private List methods;

    /** Just accept the parameters. */
    private InverseExtend(Object obj, String methodName, Object arg) {
        this.obj = obj;
        this.methodName = methodName;
        this.arg = arg;
    }
    
    /** 
     * Iterate downward through a hierarchy calling a method at each step.
     *
     * @param obj the object to pass to the method
     * @param methodName the name of the method to call
     * @param arg the argument to pass to the method
     *
     * The method should have a signature something like:
     *
     * <code>public static Object f(InverseExtend inverseExtend, 
     *           Object arg)</code>
     * 
     * (The method must be static because non-static methods are always virtual
     * and it's not possible to call an overriden virtual method.  If you wish
     * to refer to a particular instance, you must pass it using the arg.)
     *
     * Within the method:
     *
     * <code>inverseExtend.next(arg)</code>
     *
     * should be called when it is time to transfer control to the subclass.  
     * This may even be in the middle of the method.  
     */
    public static Object inverseExtend(Object obj, String methodName, 
        Object arg) {

        InverseExtend me = new InverseExtend(obj, methodName, arg);

        // Figure out the classes in the class hierarchy.  "classes" will
        // contain the most senior classes first.
        List classes = new ArrayList();
        Class c = obj.getClass();
        classes.add(c);
        while ((c = c.getSuperclass()) != null) {
            classes.add(0, c);
        }

        // Skip classes that don't define the method.  Be careful--getMethod()
        // will search parent classes for the method.
        me.methods = new ArrayList();
        Method last = null;
        Class[] signature = { me.getClass(), (new Object()).getClass() };
        for (int i = 0; i < classes.size(); i++) {
            c = (Class) classes.get(i);
            try {
                Method m = c.getMethod(me.methodName, signature);
                if (!m.equals(last)) {
                    last = m;
                    me.methods.add(0, last);
                }
            } catch (NoSuchMethodException e) {
                // Don't worry yet.  Someone else might have the method.
            }
        }

        // Now it's time to worry if me.methods is still empty.
        if (me.methods.size() == 0) {
            throw new RuntimeException(
                new NoSuchMethodException(me.methodName));
        }

        return me.next(arg);
    }

    /** 
     * Call the subclass's method.  If there is no subclass or if any other
     * exception is thrown, raise a RuntimeException.
     *
     * @param arg pass this to the subclass's method
     * @return whatever it returns
     */
    public Object next(Object arg) {
        if (methods.size() == 0) {
            throw new RuntimeException("Stack underflow.");
        }
        Method method = (Method) methods.get(methods.size() - 1);
        methods.remove(methods.size() - 1);
        Object args[] = { this, arg };
        try {
            return method.invoke(null, args);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /* 
     * Everything below is used to show the code in action.  Please excuse the
     * sloppiness and redundancy ;)  I'm using static inner classes so that the
     * test cases are near the code being tested.
     */

    public static void main(String[] args) {
        String expected = 
            "<A count=\"0\">\n" +
            "  <C count=\"1\">\n" +
            "    <D count=\"2\" />\n" +
            "  </C>\n" +
            "</A>\n";
        Argument argument = new Argument();
        argument.buf = new StringBuffer();
        argument.count = 0;
        inverseExtend(new D(), "f", argument);
        if (argument.buf.toString().equals(expected)) {
            System.out.println("InverseExtend test passed.");
        } else {
            System.out.println("InverseExtend test failed.");
            System.out.println("Expected:\n" + expected);
            System.out.println("Got:\n" + argument.buf.toString());
        }
    }

    private static class Argument {
        public StringBuffer buf;
        public int count;
    }

    private static class A {
        public static Object f(InverseExtend inverseExtend, Object arg) {
            Argument argument = (Argument) arg;
            argument.buf.append("<A count=\"" + argument.count + "\">\n");
            argument.count++;
            inverseExtend.next(argument);
            argument.buf.append("</A>\n");
            return null;
        }
    }

    private static class B extends A {
        /* I don't have an f method, so you can skip me. */
    }

    private static class C extends B {
        public static Object f(InverseExtend inverseExtend, Object arg) {
            Argument argument = (Argument) arg;
            argument.buf.append("  <C count=\"" + argument.count + "\">\n");
            argument.count++;
            inverseExtend.next(argument);
            argument.buf.append("  </C>\n");
            return null;
        }
    }

    private static class D extends C {
        public static Object f(InverseExtend inverseExtend, Object arg) {
            Argument argument = (Argument) arg;
            argument.buf.append("    <D count=\"" + argument.count + "\" />\n");
            return null;
        }
    }
}

Acknowledgments
Thanks go to Anthony Eden, Brandon L. Golm and Kyle VanderBeek for reviewing
the article and/or source code.
Resources
Gamma, Erich, et. al. Design Patterns: Elements of Reusable Object-Oriented
Software
. Addison-Wesley, ISBN 0-201-63361-2.

Shannon Behrens is a self-professed language lawyer who works for Iron
Port Systems in San Bruno, California. His eventual goal is to implement
a Python-like systems language and then develop a practice kernel in
that language.

Load Disqus comments