xsl-list
[Top] [All Lists]

Re: [xsl] How smart are the XSLT processors? Are there any XSLT processors that convert tree-recursive functions into efficient iterative procedures?

2010-04-27 20:40:10
On Tue, Apr 27, 2010 at 4:27 PM, Costello, Roger L. 
<costello(_at_)mitre(_dot_)org> wrote:
Hi Folks,

Below are two implementations of the Fibonacci sequence.

The first version is a direct translation of the definition of the Fibonacci 
sequence into XSLT -- it is declarative code.

The second version is an iterative approach -- it is imperative code.


Iterative  !=  Imperative


The advantage of the first version is that it is easy to specify and 
understand. It's disadvantage is that, if the XSLT processor is not smart, it 
is highly inefficient --  Fib(n) grows exponentially with n.

However, a "smart compiler" could transform tree-recursive functions into 
more efficient iterative procedures that compute the same result -- a smart 
XSLT processor could convert the first version into the second version.

I ran both versions on Fib(100). The second version finished in less than 1 
second. As for the first (declarative) version, after 10 minutes it was still 
executing so I killed the process.

This one (from FXSL) runs significantly faster than your second
version (it implements an O(log(N) algorithm):

 <xsl:function name="f:fibo" as="xs:integer" >
   <xsl:param name="pN" as="xs:integer"/>

   <xsl:sequence select=
    "if ($pN gt 10)
        then
          if($pN mod 2 = 0)
            then
               for $i in $pN idiv 2,
                   $fi in f:fibo($i),
                   $fi-1 in f:fibo($i -1)
                     return $fi*$fi + $fi-1*$fi-1
            else
               for $i in ($pN -1) idiv 2,
                   $fi in f:fibo($i),
                   $fi-1 in f:fibo($i -1)
                     return (2*$fi-1 + $fi) * $fi
            else
              (1,1,2,3,5,8,13,21,34,55,89)[$pN +1]
    "/>
 </xsl:function>


I conclude that, at least for the XSLT processor I used, it does not convert 
the first version into more efficient iterative procedures. This is sad. I 
would prefer writing declarative code, but if XSLT processors do not optimize 
the execution of declarative code then how realistic is declarative 
programming?


As David Carlisle already commented, both versions are declarative,
but they use different definitions of what a Fibonacci number is.

Are there any XSLT processors that convert tree recursive functions into more 
efficient iterative procedures?


Some processors recognize and optimize tail-recursion, some don't.

To avoid the perils of deep recursion and exceptions due to stack
overflow, one can use in most cases DVC (Divide and Conquer) type
recursion, for which the maximum call stack depth is log2(N) vs. N for
simple list recursion. DVC does not require a "smart processor".

As my code above shows, there are cases where a recursive
implementation significantly outperforms an iterative implementation,
simply because the former implements an O(log(N)) algorithm while the
latter implements an O(N) algorithm.

Conclusion: It is incorrect and often wrong to make concusions about
the efficiency of an implementation just based on its being recursive
or iterative.

To finish, the provided O(log(N)) XSLT code calculates F(3000) in just 33ms. :)



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play







/Roger

-------------------------------------------------
    Version #1: Tree Recursion
-------------------------------------------------
   <xsl:function name="ex:fibonacci">
     <xsl:param name="n" />

     <xsl:choose>
         <xsl:when test="$n eq 0">
             <xsl:value-of select="0" />
         </xsl:when>
         <xsl:when test="$n eq 1">
             <xsl:value-of select="1" />
         </xsl:when>
         <xsl:otherwise>
             <xsl:value-of select="ex:fibonacci($n - 1) + ex:fibonacci($n - 
2)" />
         </xsl:otherwise>
     </xsl:choose>

   </xsl:function>

-------------------------------------------------
    Version #2: Tree Iterator
-------------------------------------------------
   <xsl:function name="ex:fibonacci">
     <xsl:param name="n" />

     <xsl:value-of select="ex:fibonacci-iterator(1, 0, $n)" />

   </xsl:function>


   <xsl:function name="ex:fibonacci-iterator">
     <xsl:param name="a" />
     <xsl:param name="b" />
     <xsl:param name="count" />

     <xsl:choose>
         <xsl:when test="$count eq 0">
             <xsl:value-of select="$b" />
         </xsl:when>
         <xsl:otherwise>
             <xsl:value-of select="ex:fibonacci-iterator($a + $b, $a, $count 
- 1)" />
         </xsl:otherwise>
     </xsl:choose>

   </xsl:function>

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: 
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--



--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

<Prev in Thread] Current Thread [Next in Thread>