David Silverlight

Subscribe to David Silverlight: eMailAlertsEmail Alerts
Get David Silverlight: homepageHomepage mobileMobile rssRSS facebookFacebook twitterTwitter linkedinLinkedIn


Related Topics: XML Magazine

XML: Article

Shedding a Little Light on XML

Shedding a Little Light on XML

To understand recursion you must first understand recursion. Okay, so maybe it's the oldest recursion joke in the book, but fortunately I don't have to make my livelihood as a comedian. This month's column is dedicated to questions on recursion, in both the XML DOM and XSLT.

re·cur·sion \ri-'k r-zh n\ n [mathematics] 1 : see recursion...

I don't often get questions that specifically ask, "How do I use recursion to...? But I do get questions in which recursion plays a key role in the solution. The questions in this month's column are prime examples. If I were to guess why people avoid recursion, I'd say it could be because it appears to be the harder road to take. But IMHO it isn't. And at times it may be the only road.

After you see a few questions and demos, including a game of XSLT Tic-Tac-Toe (you vs XSLT recursion), I hope to change the way you view the subject. Many of the answers in this month's column can be truly appreciated only after you download and examine the source code. Here's to shedding some light on recursion...

Q: Why does XSLT require recursion for what seem to be simple tasks? After all, many other languages can solve the same problems without using recursion.

A: The prevalent use of recursion is a characteristic of functional languages - languages that don't have side effects like global variables. If you have a language with global variables, you don't need recursion as you can iterate through anything with a changing pointer. If you don't have global variables, you have to reintroduce a stack frame with a new set of localized variables with the iterated values and sets (be they sets of nodes or sets of characters).

Functionally (no pun intended), XSLT works the same magic as other functional languages. Essentially, this is because the "call-template" construct opens up a new stack frame with a new set of locally scoped variables that can be bound with values different from the previous stack frame's locally scoped variables. This allows working with a particular item of a set and then recursively calling the same code with either a subset of the string or a different index into the set.

A forefather of XSLT, DSSSL (Document Style Semantics and Specification Language), is also a functional language and many algorithms need to be implemented recursively. XSLT is a templating language but is, in computing theory, Turing-complete, and the "call-template" construct is no different from a function call (except in its verbose syntax, which can make it awkward to write and review). If you understand the use of recursion, it's only the syntax that gets in the way, making it more difficult than the syntax of imperative languages.

Q: How do I iterate through a string of characters in XSL?

A: You don't (well, not exactly). For this problem the desired result is to place an HTML line break (<br/>) before each uppercase character that's processed. The purpose of this algorithm is to iterate through a string of characters and insert an HTML line break ("<BR/>") before each uppercase character. To tackle this type of problem step by step, the first part of the solution is to create a template that will recursively process the string character by character. In fact, the bulk of the solution is contained within this template, called "ProcessString". Listing 1 shows ProcessString.xsl, the inner workings of our string processing template. Once it's coded, all that remains is to call the template, passing to it the string that needs parsing. The following breakdown explains how to pass the string to the template and, more important, what happens within the template.

Solution
Initially, the template is called, passing each string to be parsed. In this implementation a simple "xsl:for-each" is used to feed strings contained within the "SingleString" element to the template. (Full details on ShowProcessString.xsl, the XSLT string processing template, are given in Listing 2.)

<xsl:template match="AllStrings">
<xsl:for-each select="SingleString">

<xsl:value-of select="'Original
String: '"/>
<xsl:value-of select="." />

<xsl:value-of select="'Converted
String: '"/>

<!-- Call the template that will
loop through each character of a
string -->

<xsl:call-template name="Iterate">
<xsl:with-param name="strInput"
select="."/>
</xsl:call-template>
<br/>

</xsl:for-each>
</xsl:template>

Once the "SingleString" element is passed to the template, the remaining processing is performed within the "ProcessString" template. Listing 3, ShowProcessString.xml, provides the XML document containing the strings that will be processed. The template will process the entire string, character by character, placing a "<BR>" before the character if it tests true as uppercase. Within each iteration the template calls itself with a new string that is one character shorter until all the characters are exhausted.

Q: What is recursion useful for?

A: As part of the source code for this article, a number of other examples demonstrating recursion are included:

  • "Splitting XML Elements into Smaller XML Elements" (from Infoteria's StylesheetCentral)
  • "Transformation of Linefeed Characters to HTML" (from Mike J. Brown at Fourthought, Inc.)
  • "XSLT Template to Perform Substring Replacements" (also from Mike J. Brown)
  • "Trimming the Leading Spaces from a String" (from Infoteria's StylesheetCentral)
  • "Trimming the Trailing Spaces from a String" (from Infoteria's StylesheetCentral)
The approach used in the foregoing resources is similar to that for the previous question.

Q: How can I load a tree view in Visual Basic with XML data?

A: Finally, a chance to use recursion in VB. Displaying the contents of an XML document as a tree control (with VB, XML DOM, and recursion) can be accomplished without a tremendous amount of effort. Due to the hierarchical nature of XML, it's a prime candidate for display as a tree view. It's also a prime candidate for recursive processing. Here's how the three technologies combine into a single solution.

Overview
There are really two parts to loading the tree control from your XML. The algorithm is rather trivial once you see it.

Breakdown
The first part of the algorithm involves setting up the tree view. In this function the DOM is initialized, the TreeView control is reset, and the root node is extracted. In the Visual Basic application the ShowScreenTreeView function performs the environment setup and makes the initial call to the recursive function - PopulateTreeWithChildren - passing it the root note and the TreeView control (see Listing 4).

The second part involves calling PopulateTreeWithChildren, passing the initial root node and a TreeView control as parameters. This function does all of the recursive work in processing the XML DOM object and will continue to call itself recursively while objNode.childNodes.length is greater than 1.

During each iteration, contents of the element will be added as a leaf in the tree if it's the innermost element; otherwise it will be added as a branch of the tree (see Listing 5).

That's about it. Once again, the recursive function in this VB application will call itself until all nodes are added to the tree. The same concepts described in earlier questions apply.

Some XML/XSL tree views worth checking out:

Fancy XML tree view: http://skew.org/xml/stylesheets/treeview/
Crane Softwrights Showtree: http://www.cranesoftwrights.com/resources/showtree/
XML TreeView in SVG: http://www.dpawson.co.uk/xsl/sect4/d301e152
Tree view menu implemented using XML/XSL: http://manudea.duemetri.net/xtree/

Q: What's the difference between tail-end recursion and embedded recursion?

A: For starters, think of recursion in XSLT as a template that calls itself as a template. Questions then arise: At what point does it call itself? At the beginning of the template? Somewhere in the middle? At the end? The point at which it recursively calls itself could have serious implications on the consumption of resources. Tail end, as has been demonstrated in all of the examples thus far, includes the recursive call at the very end (the "tail" end); embedded recursion makes the call to itself anywhere within.

When determining what constitutes the "very end," the rule of thumb is that it shouldn't be the last call written in the code block, but in the flow of logic the call is the last operation of the block. This means that a single block of code may have many recursive calls, all of which can be characterized as tail-end calls because each is at the end of different flows of logic within the module, not at the end of the syntax of the module.

A drawback to recursive algorithms can be the amount of stack consumed and the indeterminate amount of system resources that may be required by the processor. An XSLT processor that implements tail-end recursion will survive recursive-based algorithms far longer than an XSLT processor that does not, because tail recursion recognizes that a stack frame is no longer required during a recursive call and disposes of the old stack frame before using the new one, thus reducing the demand for stack space.

Implementation is also an important consideration when coding recursive algorithms. Saxon supports tail-end recursion while XT does not. Other processors will vary. If the coder of the routine has *any* logic after the recursive call, the implementation is obliged to keep the stack frame around and can quickly run out of stack space...hence the burden on the programmer to code carefully.

Elements of Design
Tic-Tac-Toe Using XSLT Recursion

Let's have some fun with XSLT. This month, as a demonstration of recursion and XSLT, I've written a game of Tic-Tac-Toe. Here's the catch. You'll be using your brain to figure out your moves; the computer will be using pure XSLT recursion. Think of it as a variation on Kasparov vs Deep Blue. Are you up for it? The source code is included in this article.

Are you wondering how I did it? I started with a very common recursion algorithm (http://erwnerve.tripod.com/tictactoe.htm) and created my first proof of concept in VB6. I followed it up with a secondary version using VBScript and HTML. After the smoke cleared, and with many cups of coffee behind me, as well as a few tears...voilá: XSLT Tic-Tac-Toe. Enjoy.

More Stories By David Silverlight

David Silverlight is the chief XML evangelist for Infoteria. He has
been working in the trenches for a number of years as a software
architect and consultant, specializing in database-driven Web
applications. He also maintains www.xmlpitstop.com, a resource for
XML examples, resources, and everything else XML.

Comments (0)

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.