XSLorenz

Welcome

The Lorenz Attractor, rendered in Safari by the XSLT code below.

Welcome to XSLorenz. This site demonstrates my attempts — and reasonable successes — at getting various web browsers to render a Lorenz Attractor fractal figure using only an XML document styled by an attached XSLT stylesheet, processed entirely by the browser's XSL engine.

Note that this is not a particularly sensible thing to do. It’s a proof-of-concept. Mostly I did it because I made a flippant suggestion on a mailing list one morning, and was then bored at lunchtime. And then sufficiently interested to hammer away at it for a few more evenings after that. It’s possible I need professional help.

Generating SVG in XSL

The first thing that I decided was that SVG, Scalable Vector Graphics would be a good choice for output. It’s rendered by (some) browsers, and it’s XML, so particularly suited to being generated by XSLT.

The Source Document

I’d played with the Lorenz Attractor during my school days (my friend Paul gave me my first lesson in C programming by drawing a rotating 3D view of it.) However, twenty years later and the maths was gone. Therefore I just grabbed what info I could from the Wikipedia article, and also stole the rendering approach/algorithm from this VGA renderer source code that Mike Andrews was kind enough to leave lying around on the net.

<?xml version="1.0" encoding="utf-8"?>
<?xml-stylesheet encoding="UTF-8" type="text/xsl"
  href="lorenz_1_firefox.xsl" version="1.0"?>
<lorenz>
  <theory>
    <beta>2.66666666666</beta>
    <rho>28</rho>
    <sigma>10</sigma>
  </theory>
  <practice>
    <initialvalues>
      <x>1</x>
      <y>0.001</y>
      <z>0.001</z>
      <t>0</t>
    </initialvalues>
    <iterations>10000</iterations>
    <dt>0.01</dt>
    <view>
      <rotate>
        <x>0.0</x>
        <y>0.0</y>
        <z>0.0</z>
      </rotate>
      <zoom>1.0</zoom>
    </view>
  </practice>
</lorenz>

The source document is split into <theory> and <practice> elements. The <theory> defines the mathematical parameters for the attractor, the beta, rho and sigma values. The <practice> defines how the renderer will work, giving the initial values for the x, y and z co-ordinates, an initial time, and a time delta. (The <practice> also includes a <view> section where you could set a rotation and a zoom factor for the display, but I’ve not implemented any code for those yet, just hardcoded a particular view, so you can safely ignore those.)

The one value from this file that’s important in the later discussion is the <iterations> value. In this source code, it’s set to 10,000, i.e. the renderer should iterate 10,000 times, applying the transform each time to produce the next point of the attractor, and drawing a line from the previous point to that point.

The Transformation

So, time to write the transformation, as specified in the source document's xml-stylesheet instruction:

<?xml-stylesheet encoding="UTF-8" type="text/xsl" 
  href="lorenz_1_firefox.xsl" version="1.0"?>

What I needed to do was take those parameters, and generate SVG output in the shape of a Lorenz attractor from them. After some experiments, and not a little cursing, this is what I came up with. (I’ve broken the code up into sections here for easy reading, but the live XSLT file is here: lorenz_1_firefox.xsl.)

First, the header. This sets us up for outputting an SVG document, including outputting the top-level <svg> element and an SVG group (<g>) to contain the drawing.

<?xml version="1.0" encoding="utf-8"?>
<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
  <xsl:output method="xml" encoding="UTF-8" media-type="image/svg+xml" />
  <xsl:template match="/">
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1000 1000">
      <!-- Centre the SVG drawing at 500,500 in our 1000x1000 viewing box -->
      <g transform="translate(500,500)">
        <xsl:apply-templates />
      </g>
    </svg>
  </xsl:template>

Then it applies templates. Well, specifically, it applies this template, which just reads the values from the source document and kicks off our drawing by calling the main “actually do something” template, which is called “recurse”.

<xsl:template match="lorenz">
  <!-- Kick off recursive drawing using our Lorenz definition from the XML file -->
  <xsl:call-template name="recurse">
    <xsl:with-param name="i">
      <xsl:value-of select="practice/iterations" />
    </xsl:with-param>

    <xsl:with-param name="beta">
      <xsl:value-of select="theory/beta" />
    </xsl:with-param>

    <xsl:with-param name="rho">
      <xsl:value-of select="theory/rho" />
    </xsl:with-param>

    <xsl:with-param name="sigma">
      <xsl:value-of select="theory/sigma" />
    </xsl:with-param>

    <xsl:with-param name="x">
      <xsl:value-of select="practice/initialvalues/x" />
    </xsl:with-param>

    <xsl:with-param name="y">
      <xsl:value-of select="practice/initialvalues/y" />
    </xsl:with-param>

    <xsl:with-param name="z">
      <xsl:value-of select="practice/initialvalues/z" />
    </xsl:with-param>

    <xsl:with-param name="t">
      <xsl:value-of select="practice/initialvalues/t" />
    </xsl:with-param>

    <xsl:with-param name="dt">
      <xsl:value-of select="practice/dt" />
    </xsl:with-param>

  </xsl:call-template>
</xsl:template>

The “recurse” template is called “recurse” for fairly obvious reasons. Now, the Lorenz algorithm typically calls for iteration, not recursion. However, XSLT doesn’t really do iteration. So, we have to do a bit of hammering and bashing to produce, with recursion, what’s really iteration using a language that doesn’t have the right constructs. More on this later, because it’s the reason this rendering doesn’t work so well in a couple of browsers.

As you can see, the template first checks to see if its “iteration” count, i, has reached zero. If it has, then it does nothing — the drawing is finished. However, if it’s got any iterating left to do, it generates new x, y, z and t values based on the values passed in and the Lorenz formula…

<xsl:template name="recurse">
  <!-- The main event; this recursive function actually does the drawing. This version is projecting
       a planar view of the attractor, drawing simply x and y, looking directly along z. -->
  <xsl:param name="i" />
  <xsl:param name="beta" />
  <xsl:param name="rho" />
  <xsl:param name="sigma" />
  <xsl:param name="x" />
  <xsl:param name="y" />
  <xsl:param name="z" />
  <xsl:param name="t" />
  <xsl:param name="dt" />

  <!-- Hard-coded scale for the SVG output; I adjusted this by looking at the output and 
       changing the value manually. -->
  <xsl:variable name="scale">15</xsl:variable>

  <!-- If we've not yet reached our number of "iterations" on this recursion -->
  <xsl:if test="$i &gt; 0">

    <!-- Move on x, y, z and time -->
    <xsl:variable name="x1">
      <xsl:value-of select="$x + (( -$sigma*$x + $sigma*$y ) * $dt)" />
    </xsl:variable>
    <xsl:variable name="y1">
      <xsl:value-of select="$y + ((( $rho*$x - $x*$z) - $y) * $dt)" />
    </xsl:variable>
    <xsl:variable name="z1">
      <xsl:value-of select="$z + (( ($x)*($y) -($beta)*($z)) * $dt)" />
    </xsl:variable>
    <xsl:variable name="t1">
      <xsl:value-of select="$t+$dt" />
    </xsl:variable>

…and then it draws a line from the previous x, y, z and t values to the new x, y, z and t in SVG. It does this by outputting SVG that will end up looking like this:

<line x1="19.5416639108774" y1="40.7269988481452" 
      x2="21.6601974046042" y2="45.7680541372341" 
      style="stroke:rgb(99,99,99);stroke-width:2" />

…using this XSLT code. Note that I’m actually cheating, and just drawing in the X-Y plane, looking down from Z. At some point I’ll make it cleverer and use the <view> section from the source document, but this is just a proof-of-concept:

<!-- Draw a line from the last x, y position to the newly-calculated x, y
     using the SVG's line element -->
<xsl:element xmlns="http://www.w3.org/2000/svg" name="line">
  <xsl:attribute name="x1"><xsl:value-of select="($x)*($scale)" /></xsl:attribute>
  <xsl:attribute name="y1"><xsl:value-of select="($y)*($scale)" /></xsl:attribute>
  <xsl:attribute name="x2"><xsl:value-of select="($x1)*($scale)" /></xsl:attribute>
  <xsl:attribute name="y2"><xsl:value-of select="($y1)*($scale)" /></xsl:attribute>
  <xsl:attribute name="style">
    <xsl:text>stroke:rgb(99,99,99);stroke-width:2</xsl:text>
  </xsl:attribute>
</xsl:element>
<xsl:text>
</xsl:text>

Finally, the template knocks one off the iteration count that was passed in, and recurses, calling itself with the new x, y, z, t and i values, and the same “theory” values it started with:

<!-- And recurse with our newly-calculated values. This should be noticed
     as a tail-recursion in an XSL engine that can recognise that. -->
      <xsl:call-template name="recurse">
        <xsl:with-param name="i"><xsl:value-of select="($i)-1" /></xsl:with-param>
        <xsl:with-param name="beta"><xsl:value-of select="$beta" /></xsl:with-param>
        <xsl:with-param name="rho"><xsl:value-of select="$rho" /></xsl:with-param>
        <xsl:with-param name="sigma"><xsl:value-of select="$sigma" /></xsl:with-param>
        <xsl:with-param name="dt"><xsl:value-of select="$dt" /></xsl:with-param>
        <xsl:with-param name="x"><xsl:value-of select="$x1" /></xsl:with-param>
        <xsl:with-param name="y"><xsl:value-of select="$y1" /></xsl:with-param>
        <xsl:with-param name="z"><xsl:value-of select="$z1" /></xsl:with-param>
        <xsl:with-param name="t"><xsl:value-of select="$t1" /></xsl:with-param>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>
</xsl:transform>

Working in Firefox

Working in Firefox. Click to enlarge.

Anyway. That’s quite enough source for the moment. Want to see the results? First, a preview of the produced SVG code. It’s basically an SVG document with 10,000 lines like these in it:

<line x1="12.110822023525001" y1="11.393263117726468"
      x2="12.039066132945148" y2="14.669411500167069" 
      style="stroke:rgb(99,99,99);stroke-width:2"/>
<line x1="12.039066132945148" y1="14.669411500167069" 
      x2="12.30210066966734" y2="17.891999235299682" 
      style="stroke:rgb(99,99,99);stroke-width:2"/>

…that draw lines from one point to the next point of the figure.

Now, have a look at the real thing. You’ll have to be using Firefox for this to work. View the XML document: lorenz_1_firefox.xml.

...and what you should see there is a Lorenz Attractor, being rendered client-side in your browser, using just the XML source document and XSLT stylesheet you just read through above.

But Not Working Elsewhere

The Opera error.

While that works in Firefox, though, you won’t see much with any other web browser.

Now, I wasn’t surprised that Internet Explorer showed a blank page. It is IE, after all. In this case, though, it’s because Internet Explorer — certainly any version below IE9 — simply doesn’t support SVG.

What I was surprised by was that Safari and Chrome both also showed a completely empty page. No fractal, no code, no error message: nothing. And WebKit, the core of both Safari and Chrome, has excellent SVG support.

My clue came from firing up Opera. I caught a very brief glimpse of a skeletal Lorenz Attractor, and then got unceremoniously presented with an error message on top of my XML source document:

Error: max recursion depth exceeded

I was blowing XSLT’s stack. Which I have a sneaking suspicion is what is also going on with the WebKit browsers.

Algorithmic Mismatch

Before I go on, it’s worth talking about the algorithmic mis-match between iteration and recursion here. Traditionally, Lorenz generators are written in procedural languages, where you’d just use a for loop, or whatever, to perform a few thousand iterations of the algorithm to draw a few thousand little lines on the screen.

However, XSLT, being, by nature, a functional language, doesn’t really do iteration. There are a couple of different ways you can work around this, but they are workarounds: this language simply isn’t best suited for this kind of problem. Which is, frankly, why I wanted to do it!

With my stylesheet, I’m using recursion to simulate iteration. The “recurse” template simply calls itself with a counter, starting — in this case — at 10,000, and decrementing every time it recurses through, until the count reaches zero and everything unfolds back up the tree.

And this is where the main problem with rendering the Lorenz Attractor in browsers kicks in. Because recursion takes up stack space. There's one more level to the call stack with every function call, and with 10,000 “iterations”, that’s a lot of stack space.

Now, you should be able to finesse this using tail-recursion. Fundamentally, in your recursive function, if calling yourself is the very last thing you do, then a smart XSLT engine will be able to spot this as tail-recursion. It should then manage to “flatten out” the recursion, knowing that it doesn’t need to save state across all these calls, and avoid filling up its stack space.

The technique (and others) are described in detail in this very fine IBM developerWorks article, Use recursion effectively in XSL. However, the author notes:

Despite the advantages this technique offers, it requires that the XSL engine doing the transformation recognize the presence of the technique within the XSL code and then change its behavior to accommodate the technique. Unfortunately, most XSL engines do not yet offer such a feature.

Working in WebKit, Opera and Chrome

Working in Opera. Click to enlarge.

So, I did a bit more experimenting. And it turns out the transformation does work in WebKit, including Safari and Chrome, and in Opera. But only if you turn down the number of iterations to a level their XSLT processors can cope with.

Here’s a version of the XML source document with the recursions turned down from 10,000 to 1,000. The XSL transformation document is identical. You should find this displays an (albeit limited) Lorenz Attractor in Safari, Chrome and Opera, and probably in most other web browsers with at least a half-decent XSLT processor and SVG support:

The Lorenz Source XML document, reduced to 1,000 iterations

So, I’m guessing that the XSLT processors in WebKit and Opera have significantly less stack space than the one Firefox uses. However, I’m fairly convinced that not even Firefox is recognising tail-recursion and doing anything clever with it, as if I wind the iteration/recursion count up to 20,000, Firefox tells me:

Error during XSLT transformation: XSLT Stylesheet (possibly) contains a recursion.

So, I guess it runs out of stack space, too, eventually. It’s just that it runs about about 10,000 recursions further down the road than the other browsers.

I’m not really sure I can do much about that. Unless I’m missing something obvious, and there is a way of getting these browser XSLT engines to recognise tail-recursion. My code is successfully detected as tail-recursion by some processors. Saxon, for example, which definitely takes advantage of tail-recursion, will generate me a 50,000-iteration figure without batting an eyelid. Here it is, in SVG (warning: may slow your SVG-enabled browser to a crawl.)

Working in Internet Explorer

Working in IE8/VML. Click to enlarge.

However, that satisfied my immediate objective of squeezing a recognisable Lorenz Attractor out of Firefox, Safari, Chrome and Opera.

Now for what I figured would be the bigger challenge: Internet Explorer.

VML

Now, there are “cheats” you can apply to Internet Explorer in order to make it display SVG, but they’re all a bit kludgy. Adobe make an SVG Viewer plugin, for example, or I guess Chrome Frame might do the job. There’s probably some cool JavaScript solution too.

But that would involve more complexity than I wanted, or for the user to have to install something extra.

Instead, I figured the best thing to do would be to use VML. VML, the Vector Markup Language, is the closest thing to SVG supported by pre-IE9 versions of Internet Explorer.

And it turned out to be very easy to add into my solution.

To render SVG in IE, it seems like you need an actual web page, i.e. an HTML page with VML embedded1. But that’s actually quite handy, as it turns out.

In order to get VML out, I mangled my existing stylesheet to produce an HTML page with the correct VML stuff in the header. (And may I say how utterly annoying it was to get that working in Internet Explorer while using a document with a valid DOCTYPE? I may? Thanks. Finally, after tracking down this discussion about the right magic for making things work in IE8 I found that it needed a different format from the one I’d used before, and a position: workaround for the stuff to actually show up. Nice.)

I ended up with this stylesheet, which transforms the XML Lorenz definition into an XHTML page. The XHTML page has both the original SVG document I was outputting embedded into it (in what’s probably an illegal way when it comes to XHTML; I’ve not validated the output) and also the Microsoft VML.

Here’s the document being output by the new XSLT:

<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:v="urn:schemas-microsoft-com:vml" version="1.0">
  <xsl:output method="xml" doctype-system="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd" doctype-public="-//W3C//DTD XHTML 1.0 Transitional//EN" indent="yes"/>
  <xsl:template match="/">
    <html>
      <head>
        <title>XSLorenz</title>
        <!--    For VML. IE8 will barf on the older star notation for 
                   VML style, but all IE versions work okay with the 
                   import instruction, it seems. -->
        <xsl:processing-instruction name="import">
          namespace="v" 
          implementation="#default#VML"
        </xsl:processing-instruction>
        <style> v\:shape { display:inline-block } </style>
      </head>
      <body>
        <h2>XSLorenz</h2>
        <div>
          <xsl:apply-templates />
        </div>
      </body>
    </html>
  </xsl:template>

The VML generation itself is just tagged into the original “recurse” template alongside the SVG:

<xsl:choose>
  <xsl:when test="$style='svg'" >
    <xsl:element xmlns="http://www.w3.org/2000/svg" name="svg:line">
      <xsl:attribute name="x1"><xsl:value-of select="($x)*($scale)" /></xsl:attribute>
      <xsl:attribute name="y1"><xsl:value-of select="($y)*($scale)" /></xsl:attribute>
      <xsl:attribute name="x2"><xsl:value-of select="($x1)*($scale)" /></xsl:attribute>
      <xsl:attribute name="y2"><xsl:value-of select="($y1)*($scale)" /></xsl:attribute>
      <xsl:attribute name="style">
        <xsl:text>
          stroke:rgb(99,99,99);stroke-width:2
        </xsl:text>
      </xsl:attribute>
    </xsl:element>
  </xsl:when>
  <xsl:when test="$style='vml'" >
    <xsl:element xmlns="urn:schemas-microsoft-com:vml" name="v:line" >
      <xsl:attribute name="style">position: absolute;</xsl:attribute>
      <xsl:attribute name="strokecolor">rgb(99,99,99)</xsl:attribute>
      <xsl:attribute name="strokeweight">1pt</xsl:attribute>
      <xsl:attribute name="from">
        <xsl:value-of select="($x)*($scale)" />,<xsl:value-of select="($y)*($scale)" />
      </xsl:attribute>
      <xsl:attribute name="to">
        <xsl:value-of select="($x1)*($scale)" />,<xsl:value-of select="($y1)*($scale)" />
       </xsl:attribute>
    </xsl:element>
  </xsl:when>
</xsl:choose>

And this is an XML document that will render a decent-size Lorenz Attractor as VML in IE6, 7 and 8. Though it'll take some time to render, and won't work in most other browsers, because of the stack-size issue.

Alternate Content

As you can see, this outputs two different regions of the document, one for SVG and one for VML. This is a nice trick, because if you view this document with a browser that’s not Internet Explorer, it ignores the VML, and if it has SVG support, it displays the SVG inline. And if you view the document in Internet Explorer, it ignores the SVG, and just displays the VML2. Though we'll have to reduce the number of iterations back down from our IE demo to get it working across other browsers.

Result

Here is the final XML document; if you view this document it should display a (small bit of the) Lorenz Attractor just fine in Firefox, Safari, Chrome, Opera, IE6, IE7 and IE8. I've not tested with IE9 because I don't have Windows 7, but it's possible you'll get two Attractors out of it, as it might render both the VML and the SVG.

The Attractor is smaller here because doubling up the output to produce SVG and VML limits the WebKit and Opera XSLT stack space even more, and they fall on their arses with much more than 500 iterations, which is why the Lorenz figure is looking even more diminished now.

On the other hand, I was astounded to discover that Internet Explorer (even IE6!) can cope perfectly happily with a thousand iterations, although it does take a while to generate and render the VML. I guess IE’s XSLT engine is more generous with its stack space than the Opera or WebKit engines. Give it much more than a thousand iterations and it does die, though, failing to render the page, so I guess it doesn’t detect tail recursion, either.

Conclusion

So, a quick summary of what I’ve learned with all this:

It is possible to render a Lorenz Attractor, to some degree, using SVG or VML in all modern mainstream browsers.
It’s not sensible to do this, though. XSLT is a declarative language, and doing 10,000 iterations of anything where there aren’t 10,000 elements in your source document is hard, especially if you’re using a browser XSLT engine.
Deep recursion will bump you into limits in browser XSLT engines, though both Firefox and IE are better than WebKit and Opera in this respect.
If you wanted to do this server-side, you could choose to use an XSLT processor where you could bump up the stack size, or find one that detects tail recursion and therefore doesn’t disappear up its own stack at a certain number of iterations.
VML and SVG can be presented on a single page and different browsers will display the one they’re happy with, though I’m still not sure my documents are legal, even if they are practical.
I have way too much time on my hands.

Next Steps

If I were a complete masochist, I would probably implement some code for those other bits in my Lorenz definition document, where the same stylesheet would show different views of the Attractor — for example in different planes, or at different zoom levels — depending on the values in the source docuement. That would be quite doable.

There may even be a sensible, standards-compliant way of using GET parameters to change the parameters, so you might be able to do something like:

http://xslorenz.gothick.org.uk/lorenz.xml?viewpoint=23,92,104&zoom=50

That will have to wait for another rainy lunchtime at work, though…

Credits

Lorenz Attractor in XSLT brought to you by Matt Gibson. Documented using Scrivener and Multimarkdown. Syntax highlighting by google-code-prettify. Image lightboxing by jQuery ColorBox. Coded using Coda.

Comments

If you’ve got any comments or suggestions on generating the Lorenz Attractor using XSLT — bearing in mind I already know I could do with going outdoors more — please join in below.

blog comments powered by Disqus

Footnotes

I could be wrong; I didn’t spend a lot of time looking into it once I realised it was the best way of getting SVG and VML output on the same page. ↩
As an aside, I have no idea whether the resulting XHTML document is being interpreted as XHTML or HTML by IE. You’re looking at a .xml file when you view it, but the XHTML is generated on the fly, client-side. I don’t know what Content-type it ends up being interpreted as. Any ideas? Comments should be enabled at the bottom of this page. ↩
I haven’t got IE9 here to test with. If Microsoft do finally add SVG support to IE9 as they’ve been rumbling, I imagine that if you view this document in it, either the universe will implode, your machine will bluescreen, or two Lorenz attractors will appear. Personally, I wouldn’t risk it. ↩