Tuesday, March 6, 2007

Design Patterns in Haskell: push and pull

I've had a nagging feeling ever since my post on what's wrong with the for loop.

When for loops (and while loops) are the only tools at your disposal, every iteration construct is just an instance of a loop. When you have higher order functions and closures, then you start seeing different kinds of iteration constructs: maps, folds and filters for example. As an added benefit, the higher order approach also also eliminates the scaffolding that leads to bugs.

The problem is, that's not the entire story.

The difference between the for loop and the higher order functions is the same as the difference between push and pull templates in XSLT1.

Push templates are more natural, and easier to write in XSLT. They work with data, instead of against it:
<xsl:template match="para">
XSLT is really just a Scheme dialect that uses an event based virtual machine and an XML syntax. When the XSLT engine finds an element in the XML source document (an XML open tag, a chunk of text, a comment, whatever), it looks for a template rule to determine how to output that element. The template above matches <para> elements in a source document, and replaces them with <p> elements in the output document. The body of the <p> element on output is handled by the <xsl:apply-templates/> instruction, highlighted above. This instruction tells the XSLT engine to start examining the children of the current <para> element in the source document, and look for templates that describe how they are to be formatted in the output document, and place those outputs within a <p>...</p> block.

This leads me to one of my favorite XSLT techniques -- the null template:
<xsl:template match="double-secret-probation"/>
This template doesn't contain any content. Specifically, it doesn't contain an <xsl:apply-templates/> instruction. Therefore, whenever a <double-secret-probation> element is found in a source document that triggers this template, it and all of its children will be pruned from the output document.

Pull templates are the alternative to push templates. Instead of letting data flow through the stylesheet, they pick data out of the source document, and place it directly into the output document:
<xsl:template match="body">
<xsl:for-each select="para">
<xsl:value-of select="text()"/>
This template actively seeks out <para> elements that are children of a <body>, replaces them with <p> tags (as above), and then hunts down the text contents of each <para> element, shoving it directly into the <p>...</p> blocks. The two constructs above, <xsl:for-each> and <xsl:value-of>, are used to pull content out of the input document and into the output document.

If it sounds complicated, it is. XSLT makes it easy to reformat XML documents by providing an implicit processing model that visits every node of an XML document. Input can be rearranged, replaced, or removed in the output. Pull templates, on the other hand, can usually perform the same transformations, except that it generally takes more work to write (and understand) to do it.

In general, it's much better for XSLT stylesheets to use push templates whenever possible, and save pull templates for those rare situations when they are absolutely necessary.

As an exercise for the reader, write a stylesheet that emits this fragment and preserves all of the formatting, but eliminates the chunks labeled <double-secret-probation>:
The 11<sup>th</sup> Annual Homecoming Parade
will take place Thursday at <time>1100 PST</time>.

<double-secret-probation>Under no circumstances will
Delta House participate.</double-secret-probation>
(Hint: the two push templates above will be key parts of the solution. I don't even want to think about how to write a solution using a pull template....)

A few years ago, I taught on-site XSLT training courses. They went from the basic (this is a stylesheet, this is a template) all the way through advanced techniques (how to add commas between elements in a list, but not after the final element). I found that students whose exposure to XSLT started with "view source" always started with pull templates, and translated algorithms out of a Java program into XSLT syntax. It took a while to explain push templates, and appreciate how they simplified the problem domain. (Having copious examples helped, including a few that were nearly impossible with pull templates, but trivial with push templates.)

This is because loops and similar "pull techniques" are some kind of deep knowledge that many of us learn as beginning programmers. It was the only realistic approach when the only available language was some form of assembly, and it propagated through Fortran and ALGOL into every imperative language still in use today.

We can do better now. Computers are plenty fast to handle whatever meager overhead is necessary to apply functional idioms like map, fold/reduce and filter to transform and reduce aggregate values, whether we use those idioms in imperative languages like Perl, Python or Ruby, or in a purely functional language like Haskell.

The good news is that once you understand how to push data through a computation, trivial operations become, well, trivial. Here's the sum of all the odd numbers from 1 to 100:
sum (filter odd [1..100])
Perhaps this is why imperative programmers hesitate to use functional languages: pull techniques are so ingrained that it is hard to leave them behind and start using the push techniques that really make programming easier and more expressive...

1: For a more detailed discussion on push and pull templates with XSLT, see Bob DuCharme's excellent article on XML.com.

No comments: