Sunday, November 07, 2004

"Retroactive Abstraction"?

Update as of 2004/11/10: the examples below have been changed to match the latest generic function API in the PyProtocols CVS. Also, I've removed some text that referred to limitations that no longer exist.

While looking for some info on the Chambers and Chen predicate dispatch algorithm, I stumbled across an interesting Java paper: Half & Half: Multiple Dispatch and Retroactive Abstraction for Java. In the paper, they talk about a concept called "Retroactive Abstraction", which sounded really interesting until I realized that it basically amounted to being able to declare that a class supports an interface, somewhere outside the source code of the class. Naturally, this is trivial to do in a dynamic language like Python. Even without an interface package like PyProtocols, one could always mangle a class' __bases__, if you had to.

More interestingly, the paper provides a nice motivation for using generic functions to replace the Visitor pattern, and then goes on to describe an extension to Java to support these enhancements. Lucky for us in the Python world, implementing a new dispatching paradigm doesn't require a language change, just a library addition, like the new dispatch package I just added to PyProtocols in CVS. It supports single, multiple, and even predicate dispatch, using state-of-the-art algorithms that until now have only been available in academic languages and research compilers. And, when paired with Python 2.4 decorators, it lets you do things like this:
@dispatch.generic()
def drink(actor,target):
"""Generic function: 'actor' drinks 'target'"""

@drink.when("not target.isDrinkable()")
def drink(actor,target):
print "You can't drink that."

@drink.when("target.isDrinkable()")
def drink(actor,target):
print "glug, glug..."
target.consume()

@drink.after("target.isDrinkable() and target.isPoisonous()"
" and not actor.isWearing(amulet_against_poison)")
def drink(actor, target):
print "oops, you're dead!"
actor.die()
Okay, so I haven't actually implemented .after() methods yet, but the rest works. Despite the appearance of the above, the test expressions are not eval()-ed; they're actually analyzed and compiled into an efficient dispatch tree that only tests a subexpression once. So, in the example above, the drink() generic function only calls target.isDrinkable() at most once per invocation of the generic function - just as if you'd hand-coded a series of if-then tests.

But, unlike hand-coded tests, generic functions can be extended by code in different modules, leading to increased extensibility and modularity. For example, if the drink() function above were in a verbs module, a beer module could also contain:
import verbs

@verbs.drink.when("target in Beer")
def drink_beer(actor,target):
dispatch.next_method(actor,target)
print "Mmmm... Beer!"
This extends the existing generic function to print a message after enjoying a beer (assuming that beer.isDrinkable() and not beer.isPoisonous(), of course!).

Anyway, the dispatch package isn't quite finished yet; it doesn't support using generic functions as methods on objects, and the default method combination doesn't actually support next_method() yet (though there's a non-default one that does). But it's definitely robust enough to experiment with, and to flaunt in the general direction of Java and other languages less dynamic than Python. :)