Generating Primes with XSLT

Originally published on: Sat, 20 Jun 2009 01:06:03 +0000

The eXtensible Stylesheet Language (XSL) allows one to write transform rules to alter input XML documents. XSL is considered to be declarative or goal-oriented. However, many XSL transform stylesheets I've seen immediately provide an event trap for the root node reference and take over the XSL processing, using the stylesheet in an imperative manner.

Some of the earliest material I'd read about XSL transforms had indicated that the transform language was Turing-complete. I decided to see for myself by attempting to create an XSL stylesheet whose transform ( regardless of the XML input ) would yield another document containing only a series of prime numbers.

Although one can find numerous command-line XSLT processors, I've chosen to write a short one in C# that I'll use to invoke the transform.

xsl.cs

// xsl.cs - Simple command-line XSL transform utility
//
// License: MIT / X11
// Copyright (c) 2009 by James K. Lawless
// jimbo@radiks.net http://www.radiks.net/~jimbo
// http://www.mailsend-online.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

using System ;
using System.IO ;
using System.Xml ;
using System.Xml.Xsl ;
using System.Xml.XPath ;

namespace XslTransform
{
   public class XslTransform
   {
      public static void Main(string[] args)
      {
         if (args.Length == 2){
            XPathDocument dummyXML = new XPathDocument(args[0]) ;
            XslCompiledTransform myXslTrans = new XslCompiledTransform() ;
            myXslTrans.Load(args[1]) ;
            myXslTrans.Transform(dummyXML,null, Console.Out);

         }else{
            Console.WriteLine("Usage: xsl.exe xml-file xsl-file");
        }
      }
   }
}

The dummy XML input file that I'm using contains only one line: tmp.xml

It could contain as much valid XML as desired; all of it will be ignored as we will take over processing in the XSL stylesheet immediately.

The raw stylesheet that does the transform is as follows:

primes.xsl

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">



  <xsl:template match="/">
     <xsl:call-template name="loop">
        <xsl:with-param name="val" select="2" />
     </xsl:call-template>
  </xsl:template>

  <xsl:template name="loop">
     <xsl:param name="val" select="''" />
     <xsl:if test="$val <= 1000">
        <xsl:call-template name="findPrime">
           <xsl:with-param name="start" select="2" />
           <xsl:with-param name="end" select="$val" />
        </xsl:call-template>
        <xsl:call-template name="loop">
           <xsl:with-param name="val" select="$val+1" />
        </xsl:call-template>
     </xsl:if>
  </xsl:template>

  <xsl:template name="findPrime">
     <xsl:param name="start" select="''" />
     <xsl:param name="end" select="''" />
     <xsl:if test="($start * $start) > $end">
        <xsl:value-of select="concat($end,' is prime ')" />
     </xsl:if>
     <xsl:if test="($start * $start) <= $end">
        <xsl:if test="($end mod $start)!=0">
           <xsl:call-template name="findPrime">
              <xsl:with-param name="start" select="$start + 1" />
              <xsl:with-param name="end" select="$end" />
           </xsl:call-template >
        </xsl:if>
     </xsl:if>
  </xsl:template>
</xsl:stylesheet>

The more commented version of the stylesheet is: primescommented.xsl

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">



     
  <xsl:template match="/">
        
     <xsl:call-template name="loop">
        <xsl:with-param name="val" select="2" />
     </xsl:call-template>
  </xsl:template>

     
  <xsl:template name="loop">
     <xsl:param name="val" select="''" />
        
     <xsl:if test="$val <= 1000">
           
        <xsl:call-template name="findPrime">
           <xsl:with-param name="start" select="2" />
           <xsl:with-param name="end" select="$val" />
        </xsl:call-template>
            
        <xsl:call-template name="loop">
           <xsl:with-param name="val" select="$val+1" />
        </xsl:call-template>
     </xsl:if>
  </xsl:template>

     
  <xsl:template name="findPrime">
     <xsl:param name="start" select="''" />
     <xsl:param name="end" select="''" />
       
     <xsl:if test="($start * $start) > $end">
        <xsl:value-of select="concat($end,' is prime ')" />
     </xsl:if>

        
     <xsl:if test="($start * $start) <= $end">
           
        <xsl:if test="($end mod $start)!=0">
              
           <xsl:call-template name="findPrime">
              <xsl:with-param name="start" select="$start + 1" />
              <xsl:with-param name="end" select="$end" />
           </xsl:call-template >
        </xsl:if>
     </xsl:if>
  </xsl:template>

</xsl:stylesheet>

To invoke the transform using the supplied C# utility, run the following command-line: xsl.exe tmp.xml primes.xsl

After taking over processing with the template that matched the "/" processing event, I took a simple recursive approach to the problem.

Pseudocode for the approach

loop(2)

function loop($val) {
   if($val <= 1000) {
      findPrime(2,$val)
      loop($val+1)
   }
}

function findPrime($start,$end) {
   if( ($start*$start)>$end) {
      print($end " is prime ")
   }
   else {
      if($end mod $start)!=0) {
         findPrime($start+1,$end)
      }
   }
}

The code calls the loop named template which recursively calls itself until the invocation where the $val parameter exceeds 1000. Inside the loop template, a call is made to the named template findPrime which also recursively calls itself to simulate iteration.

If findPrime iterates through the square root of $end, the number is prime. Output is generated stating that $end is prime.

Unless otherwise noted, all code and text entries are Copyright �2009 by James K. Lawless

Save to del.icio.us
Save to StumbleUpon
Digg it
Save to Reddit
Share on Facebook
Share on Twitter
More bookmarks