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
<x>y</x>
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">
<!--
Show primes all from 2 to 1000
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.
-->
<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">
<!--
Show primes all from 2 to 1000
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.
-->
<!-- Immediately bend the XSLT processor to our will by
matching "/" -->
<xsl:template match="/">
<!-- call loop with initial parm of 2 -->
<xsl:call-template name="loop">
<xsl:with-param name="val" select="2" />
</xsl:call-template>
</xsl:template>
<!-- "loop" is a named template that will recusively call
itself to iterate from 2 to 1000 inclusive. -->
<xsl:template name="loop">
<xsl:param name="val" select="''" />
<!-- test to see if we're under our limit of 1000 -->
<xsl:if test="$val <= 1000">
<!-- call findPrime(2,$val) -->
<xsl:call-template name="findPrime">
<xsl:with-param name="start" select="2" />
<xsl:with-param name="end" select="$val" />
</xsl:call-template>
<!-- now recursively call ourself;
loop($val+1) to simulate iteration -->
<xsl:call-template name="loop">
<xsl:with-param name="val" select="$val+1" />
</xsl:call-template>
</xsl:if>
</xsl:template>
<!-- recursive named template "findPrime" . Search from $start to
$end. Stop when $start*$start is greater than
$end. ( Once we hit the square root, there won't
be any chance of discovering a prime -->
<xsl:template name="findPrime">
<xsl:param name="start" select="''" />
<xsl:param name="end" select="''" />
<!-- if we make it this far, the number $end is
prime -->
<xsl:if test="($start * $start) > $end">
<xsl:value-of select="concat($end,' is prime ')" />
</xsl:if>
<!-- otherwise ... -->
<xsl:if test="($start * $start) <= $end">
<!-- if $end isn't evenly divisble by $start ... -->
<xsl:if test="($end mod $start)!=0">
<!-- recursively call ourselves bumping $start by 1 -->
<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
Views expressed in this blog are those of the author and do not necessary reflect those of the author's employer. Views expressed in the comments are those of the responding individual.
Save to StumbleUpon
Digg it
Save to Reddit
Share on Facebook
Share on Twitter
More bookmarks
