Skip to main content

Computer Science: Prototypal Match Templates

In object-oriented programming languages, you can subclass an existing class and override a few of its methods. This allows you to take an existing piece of code and tweak it for your own use. However, it's only as granular as the methods that you are overriding. If you want to change one line in a 30 line method, you either have to refactor that 30 line method into several methods (which is the right thing to do if you're in control of the code) or you have to copy the 30 lines and modify that one line (which may be the only thing you can do if you're not in control of the code). Sometimes I actually do both. If I'm using a third-party library that has a 30 line function that I want to change one line of, I copy the whole function into my class, and then refactor it there as if I were refactoring the superclass.

Genshi has a cool mechanism called match templates. I assume XSLT has this too, but since I don't know XSLT, I can't say for certain. Genshi's mechanism let's you write an HTML template and say things like "Every time you see HTML that matches this XPath expression, replace it with this HTML". It turns out that this is a really flexible way of doing templating. It makes it really easy to setup a global look-and-feel and then customize it however you want on a per-template basis. You just write match templates that "tweak" the global look-and-feel. Unlike the template design pattern, the person writing the global look-and-feel doesn't need to do anything to set you up. He doesn't need to create "hook" divs for you to override or anything like that. You can tweak anything you like.

I wonder if the same thing might be useful as a replacement for object-oriented inheritance. Instead of subclassing a class and then overriding some of its methods, you subclass a class and then write match templates that "tweak" the code in the superclass. I think "prototypal match templates" are a good name for this, because you're taking a prototype piece of code and then tweaking it to your needs as if you were doing text substitutions. You would need something like XPath that would make sense for the programming language you're using, but that's not too hard to imagine.

Ok, let me show you what I have in mind. Let's start with how I would do things today:
class Greeter:

"""Let's pretend this is in a third-party module."""

def greet(self, sex):
print 'Howdy,',
if sex == 'female':
print 'good looking!'
print 'stranger.'
Here's my subclass:
class PoliticallyCorrectGreeter(Greeter):

def greet(self, sex):
"""I either have to refactor or I have to duplicate code here."""
print 'Howdy,',
if sex == 'female':
print 'person of the opposite sex.'
print 'stranger.'
If I had prototypal match templates (including some sort of XPath-like syntax for Python syntax), I could write something like:
class PoliticallyCorrectGreeter(Greeter):

match def[name='greet']/if/print[args[0]]:
'person of the opposite sex.'
Ok, I can imagine that many people are going to hate this idea. That's why I'm turning off comments...just joking ;)

One valid complaint is that this breaks encapsulation. I'm overriding a method in a way that requires knowledge of the implementation. That's a fair point. However, I'd like to punt on this issue. When I'm subclassing something, I often need to understand the implementation of the superclass anyway to do what I need to do. I think that if you subclass a class, you're "closer" to that class than if you were just using it. If the superclass's implementation changes, it'll break my code. That's okay. I can look at how it's changed and fix it. That's just a normal part of my life as a modern programmer. Furthermore, I think there are smart ways to use this feature and not-so-smart ways to use this feature. It's a hammer--don't hit yourself over the head with it ;)

Next, I'm sure there's a Lisp programmer out there somewhere saying, "Yeah, been there done that. Haven't you heard of macros?" That's a good point too. Lisp is nice because the syntax tree is just Lisp data. That's one of the nicest things about Lisp syntax. However, an XPath-like syntax for navigating an AST for, say, Python would let Python programmers use some of the same tricks that Lisp programmers use. McCarthy said, "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp," but I sure do like the way that Python makes Lisp-based ideas more readable and accessible to the masses. Back when Lisp was created, doing things like what I'm talking about just didn't make sense. Making the AST normal Lisp data was a brilliant move. These days with strong reflection in scripting languages, it does make sense to play with the AST in your code. You can have your syntax and tweak it too :-D


You definitely came up with one of the best descriptions of the benefits of match templates in Genshi I've seen so far… I personally always have trouble expressing this aspect :P
Ian said…
Generic Functions from pyProtocols come to mind.
> Generic Functions from pyProtocols come to mind.

I can see why. They have a match mechanism. That's not so different than the match mechanism in languages like Haskell. However, I think doing matches on the syntax tree of the code itself rather than on the incoming data is interesting.
Ryan Braley said…
It is surprising that you haven't heard of one of the greatest obscure languages:
It is exactly what you want. It is a purely OOP language. It is a purely functional language. Scala fused them into the same elegant thing. All functions are values, all values are objects. This fusion enabled Scala to do Actor Model concurrency (like erlang or stackless) in a library, without having to fork the compiler or some such nonsense. It supports pattern matching and functional programming like haskell but with all the productivity and reflection of ruby or python, So you can match on the types and blocks of code if you like, for free. The coolest thing is that although it writes like python, it is statically compiled and type-checked and is fully compatible with all Java and .Net libraries and runtime environments. So you have RAD code with more elegant expressive power than python or haskell, but it is enterprise ready. Spread the word and the love.

Thanks for the Scala plug. I've used the words "actor" and "Scala" twice today while talking about concurrency, but I haven't gotten around to learning Scala. Thanks for the tip :)

To be fair, my prototypal match templates still sound very different than Scala.

Best Regards,