The Functional Programming Language XSLT - A proof through examples

Numerical integration

In this section we'll provide a solution to the following problem: given a real-valued function f which has one real argument, and two endpoints a and b estimate the area of the shape defined by the graphic of the function, the abscissa axis and the end-points.

The numerical integration algorithm we'd be using can be described in the following steps:

If we think of the curve of the function as a straight line, then the following function computes exactly the area:

easyintegrate f a b = (f a + f b) * (b - a) / 2

In practice, the curve will be much different, so the above will provide a satisfactory approximation of the area only on very small intervals. A list of better and better approximations of the area can be obtained by successively dividing (each) interval into two and computing the sum of all subintervals. This is strictly defined by the following Haskell functions:

integrate :: Fractional a => (a -> a) -> a -> a -> [a]

integrate f a b = integ f a b (f a) (f b)

integ :: Fractional a => (a -> a) -> a -> a -> a -> a -> [a]

integ f a b fa fb = let (m, fm ) = ((a + b)/2, f m) in

(((fa+fb)*(b-a)/2):(map addpair(zip(integ f a m fa fm) (integ f m b fm fb))))

where addpair is the sum of a pair of numbers, and zip produces a list out of two given lists, by making a pair of the n-th elements of each of the two lists the n-th element of the resulting list:

zip :: [a] -> [b] -> [(a,b)]

zip (x:xs) (y:ys) = (x,y) zip xs ys

zip _ _ = []

Because XSLT lacks Haskell's ability of lazy evaluation of infinite lists, we translate the above definition to the following equivalent algorithm:

We build a successive list of one dimensional grids, starting with the interval [a,b], then producing each successive grid from the previous, by including its points and for every two adjacent points a_k, a_k+1a new point a_mid = (a_k + a_k+1) / 2. After performing k iterations, the list will be as follows

grid a b k = [a, a + h, a + 2h, ... a + (2^k -1)*h, b]

where h = (a-b)/2^k

Then we define a slight modification of easyintegrate, which operates on two consecutive elements of a list:

easyintegrate1 f (x:y:ys) = (f x + f y) * (y - x) / 2

Then the partialSum, for a particular grid will be:

partialSum (grid a b k) = foldl (add . (map easyintegrate1)) 0 (grid a b k)

The list partialSums, for a partial sums over successively obtained grids can be now defined:

partialSums = [partialSum (grid a b k) | k <- [1..]]

In order to eliminate the very inefficient multiple re-calculations of f (once for a point in every iteration), in practice we will construct another grid1:

grid1 f a b k = [h, f a, f (a + h), f (a + 2h), ... f (a + (2^k -1)*h), f b]

where h = (a-b)/2^k

And we'll use the easyintegrate2 function

easyintegrate2 h (x:y:ys) = (x + y) * h / 2

and we change partialSum and partialSums accordingly, so that partialSum2 will use easyintegrate2, will pass to it the first element of grid1 and the tail of grid1 as arguments.

partialSum2 (grid1 f a b k) = foldl (add . (map (easyintegrate2 hdgrid)))) 0 tlGrid

where hdgrid = head (grid1 f a b k); tlGrid = tail (grid1 f a b k)

partialSums2 f a b = [partialSum2 (grid1 f a b k) | k <- [1..]]

Finally, we can select an appropriate element of partialSums2 by specifying a tolerance:

roughIntegration f a b eps = 
      within eps  (partialSums2 f a b)

Here's the corresponding XSLT implementation:

partialSumsList

  
            <xsl:stylesheet version = "1.0" 
    xmlns:msxsl="urn:schemas-microsoft-com:xslt"
    xmlns:pGenerator="pGenerator"
    
            xmlns:pController="pController"
    
            xmlns:IntervalParams="IntervalParams"
    
            xmlns:mapEasyIntegrate="mapEasyIntegrate"
    
            xmlns:easy-integrate="easy-integrate"
    
            exclude-result-prefixes = "xsl msxsl pGenerator pController
                              IntervalParams easy-integrate" 
            >

         <xsl:import href = "buildListWhileMap.xsl" 
            />
         <xsl:import href = "foldl.xsl" 
            />

         <xsl:output indent = "yes" omit-xml-declaration = "yes" 
            />

         <pGenerator:pGenerator/>
         <pController:pController/>
         <mapEasyIntegrate:mapEasyIntegrate/>
         <easy-integrate:easy-integrate/>

         <xsl:template name = "partialSumsList" 
            >
             <xsl:param name = "pFun" select = "/.." 
            />
             <xsl:param name = "pA" 
            />
             <xsl:param name = "pB" 
            />
             <xsl:param name = "pEps" select = "0.001" 
            />

             <xsl:variable name = "vMyGenerator" 
                   
            select 
            = "document('')/*/pGenerator:*[1]" 
            />

             <xsl:variable name = "vMyController" 
                   
            select 
            = "document('')/*/pController:*[1]" 
            />

             <xsl:variable name = "vmyEasyIntegrateMap" 
                   
            select 
            = "document('')/*/mapEasyIntegrate:*[1]" 
            />

             <xsl:variable name = "vrtfvIntervalParams" 
            >
                 <IntervalParams:IntervalParams>
                     <Interval>
                         <el>
                             <xsl:value-of select = "$pA" 
            />
                         </el>
                         <el>
                             <xsl:value-of select = "$pB" 
            />
                         </el>
                     </Interval>
                     <xsl:copy-of select = "$pFun" 
            />
                 </IntervalParams:IntervalParams>
             </xsl:variable>

             <xsl:variable name = "vIntervalParams" 
                   
            select 
            = "msxsl:node-set($vrtfvIntervalParams)/*" 
            />

             <xsl:variable name = "vrtfResultIntervalList" 
            >
                 <xsl:call-template name = "buildListWhileMap" 
            >
                     <xsl:with-param name = "pGenerator" select = "$vMyGenerator" 
            />
                     <xsl:with-param name = "pController" select = "$vMyController" 
            />
                     <xsl:with-param name = "pParam0" select = "$vIntervalParams" 
            />
                     <xsl:with-param name = "pContollerParam" select = "$pEps" 
            />
                     <xsl:with-param name = "pMap" select = "$vmyEasyIntegrateMap" 
            />
                 </xsl:call-template>
             </xsl:variable>

             <xsl:copy-of select = "msxsl:node-set($vrtfResultIntervalList)" 
            />

             <xsl:variable name = "vResultIntervalList" 
                   
            select 
            = "msxsl:node-set($vrtfResultIntervalList)/*[last()]/*" 
            />

         </xsl:template>

         <xsl:template name = "listGenerator" match = "*[namespace-uri()='pGenerator']" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pParams" 
            />

             <xsl:variable name = "pA0" select = "string($pParams/*[1]/*[1])" 
            />

             <xsl:variable name = "pB0" select = "string($pParams/*[1]/*[2])" 
            />

             <xsl:variable name = "pFun" select = "$pParams/*[2]" 
            />

             <xsl:choose>
                 <xsl:when test = "not($pList)" 
            >
                     <xsl:variable name = "vFa">
                         <xsl:apply-templates select = "$pFun" 
            >
                             <xsl:with-param name = "pX" select = "$pA0" 
            />
                         </xsl:apply-templates>
                     </xsl:variable>

                     <xsl:variable name = "vFb" 
            >
                         <xsl:apply-templates select = "$pFun" 
            >
                             <xsl:with-param name = "pX" select = "$pB0" 
            />
                         </xsl:apply-templates>
                     </xsl:variable>

                     <e>
                         <xsl:value-of select = "$pB0 - $pA0" 
            />
                     </e>
                     <e>
                         <xsl:value-of select = "$vFa" 
            />
                     </e>
                     <e>
                         <xsl:value-of select = "$vFb" 
            />
                     </e>
                 </xsl:when>

                 <xsl:otherwise>
                     <xsl:variable name = "vprevH" select = "$pList[last()]/*[1]" 
            />

                     <xsl:variable name = "vH" select = "$vprevH div 2" 
            />

                     <e>
                         <xsl:value-of select = "$vH" 
            />
                     </e>

                     <xsl:for-each select = "$pList[last()]/*[position() > 1 
                                and position() != last()]" 
            >

                         <xsl:variable name = "vA" select = "$pA0 + (position() - 1) * $vprevH" 
            />

                         <xsl:variable name = "vMid" select = "$vA + $vH" 
            />

                         <xsl:variable name = "vF_mid" 
            >
                             <xsl:apply-templates select = "$pFun" 
            >
                                 <xsl:with-param name = "pX" select = "$vMid" 
            />
                             </xsl:apply-templates>
                         </xsl:variable>

                         <xsl:copy-of select = "." 
            />

                         <e>
                             <xsl:value-of select = "$vF_mid" 
            />
                         </e>
                     </xsl:for-each>

                     <xsl:copy-of select = "$pList[last()]/*[last()]" 
            />

                 </xsl:otherwise>
             </xsl:choose>
         </xsl:template>

         <xsl:template name = "listController" 
                  
            match 
            = "*[namespace-uri()='pController']" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pParams" 
            />

             <xsl:choose>
                 <xsl:when test = "count($pList) &lt; 2" 
            >1</xsl:when>
                 <xsl:otherwise>
                     <xsl:variable name = "vLastDiff" 
                      
            select 
            = "$pList[last()] - $pList[last() - 1]" 
            />

                     <xsl:if test = "not($vLastDiff &lt; $pParams 
                        and $vLastDiff > (0 - $pParams))" 
            >1</xsl:if>
                 </xsl:otherwise>
             </xsl:choose>
         </xsl:template>

         <xsl:template name = "mapEasyIntegrate" 
                  
            match 
            = "*[namespace-uri()='mapEasyIntegrate']" 
            >
             <xsl:param name = "pParams" select = "/.." 
            /><!-- pMapParams --> 
             <xsl:param name = "pDynParams" select = "/.." 
            /><!-- NewBaseListElement --> 
             <xsl:param name = "pList" select = "/.." 
            />

             <xsl:variable name = "vResult" 
            >
                 <xsl:call-template name = "multiIntegrate" 
            >
                     <xsl:with-param name = "pList" select = "$pDynParams/*" 
            />
                 </xsl:call-template>
             </xsl:variable>

             <xsl:copy-of select = "msxsl:node-set($vResult)" 
            />

         </xsl:template>

         <xsl:template name = "multiIntegrate" 
            >
             <xsl:param name = "pList" select = "/*/*" 
            />
             <xsl:variable name = "vmyeasyIntegrateFn" 
                   
            select 
            = "document('')/*/easy-integrate:*[1]" 
            />

             <xsl:call-template name = "foldl" 
            >
                 <xsl:with-param name = "pFunc" select = "$vmyeasyIntegrateFn" 
            />
                 <xsl:with-param name = "pList" select = "$pList[position() > 1 
                                                and position() &lt; last()]" 
            />
                 <xsl:with-param name = "pA0" select = "0" 
            />
             </xsl:call-template>

         </xsl:template>

         <xsl:template name = "myEasyIntegrateFn" 
                 match = "*[namespace-uri()='easy-integrate']" 
            >
             <xsl:param name = "arg1" select = "0" 
            /><!-- pA0 --> 
             <xsl:param name = "arg2" select = "0" 
            /><!-- node --> 
             <xsl:value-of select = "$arg1 + 
                             (($arg2 + $arg2/following-sibling::*[1]) div 2 ) 
                             * $arg2/../*[1]" 
            />
         </xsl:template>

     </xsl:stylesheet>

Let's test partialSumsList in a concrete example. We want to produce the list of partial sums for:

  1
∫ x² dx 
0

testPartialSumsList.xsl

     <xsl:stylesheet version = "1.0" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:msxsl="urn:schemas-microsoft-com:xslt"
    
            xmlns:IntegralFunction="IntegralFunction"
    
            exclude-result-prefixes = "xsl IntegralFunction" 
            >

         <xsl:import href = "partialSumsList.xsl" 
            />

         <xsl:output indent = "yes" omit-xml-declaration = "yes" 
            />

         <IntegralFunction:IntegralFunction/>

         <xsl:template match = "/" 
            >
             <xsl:variable name = "vMyFun" 
                   select = "document('')/*/IntegralFunction:*[1]" 
            />

             <xsl:variable name = "vrtfPartialSums" 
            >
                 <xsl:call-template name = "partialSumsList" 
            >
                     <xsl:with-param name = "pFun" select = "$vMyFun" 
            />
                     <xsl:with-param name = "pA" select = "0" 
            />
                     <xsl:with-param name = "pB" select = "1" 
            />
                     <xsl:with-param name = "pEps" select = "0.001" 
            />
                 </xsl:call-template>
             </xsl:variable>

             <xsl:variable name = "vPartialSums" 
                   select = "msxsl:node-set($vrtfPartialSums)/*" 
            />

             <xsl:copy-of select = "$vPartialSums" 
            />
         </xsl:template>

         <xsl:template name = "myIntegralFn" 
                  
            match 
            = "*[namespace-uri()='IntegralFunction']" 
            >
             <xsl:param name = "pX" 
            />
             <xsl:value-of select = "$pX * $pX" 
            />
         </xsl:template>

     </xsl:stylesheet>

Results of testPartialSumsList.xsl

  1
∫ x² dx 
0

0.5 0.375 0.34375 0.3359375 0.333984375

As we can see, the last partial sum is an approximation of the true value of the integral (1/3) with the desired accuracy.

A final thought about the above sequence -- it is produced with successive halving of h. Therefore, we can improve it, using the same mechanism as we used in implementing numerical differentiation. The improvedIntegration template bellow is almost identical to the improvedDiff function from section 4.2. We are producing a list of successively improved lists of partial sums and taking every second element of these lists, until our tolerance criterion has been satisfied.

It is instructive to see how much we are re-using the powerful generic functionality that was already built. Such reuse would simply be impossible without having implemented higher-order functions in XSLT.

improvedIntegration

  
            <xsl:stylesheet version = "1.0" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:msxsl="urn:schemas-microsoft-com:xslt"
    
            xmlns:myImproveGenerator="myImproveGenerator"
    
            xmlns:myImproveController="myImproveController" 
    
            exclude-result-prefixes = "xsl msxsl myImproveGenerator
                               myImproveController" 
            >

         <xsl:import href = "improve.xsl" 
            />
         <xsl:import href = "take.xsl" 
            />
         <xsl:import href = "takeWhile.xsl" 
            />
         <xsl:import href = "PartialSumsList.xsl" 
            />

         <myImproveGenerator:myImproveGenerator/>
         <myImproveController:myImproveController/>

         <xsl:output indent = "yes" omit-xml-declaration = "yes" 
            />

         <xsl:template name = "improvedIntegration" 
            >
             <xsl:param name = "pFun" select = "/.." 
            />
             <xsl:param name = "pA" 
            />
             <xsl:param name = "pB" 
            />
             <xsl:param name = "pEpsRough" select = "0.0001" 
            />
             <xsl:param name = "pEpsImproved" select = "0.0000001" 
            />

             <xsl:variable name = "vMyImproveGenerator" 
                   select = "document('')/*/myImproveGenerator:*[1]" 
            />

             <xsl:variable name = "vMyImproveController" 
                   
            select 
            = "document('')/*/myImproveController:*[1]" 
            />

             <xsl:variable name = "vrtfRoughResults" 
            >
                 <xsl:call-template name = "partialSumsList" 
            >
                     <xsl:with-param name = "pFun" select = "$pFun" 
            />
                     <xsl:with-param name = "pA" select = "$pA" 
            />
                     <xsl:with-param name = "pB" select = "$pB" 
            />
                     <xsl:with-param name = "pEps" select = "$pEpsRough" 
            />
                 </xsl:call-template>
             </xsl:variable>

             <xsl:variable name = "vrtfResults" 
            >
                 <xsl:call-template name = "takeWhile" 
            >
                     <xsl:with-param name = "pGenerator" 
                        
            select 
            = "$vMyImproveGenerator" 
            />
                     <xsl:with-param name = "pParam0" 
                        
            select 
            = "msxsl:node-set($vrtfRoughResults)/*" 
            />
                     <xsl:with-param name = "pController" 
                        
            select 
            = "$vMyImproveController" 
            />
                     <xsl:with-param name = "pContollerParam" 
                        
            select 
            = "$pEpsImproved" 
            />
                 </xsl:call-template>
             </xsl:variable>

             <xsl:variable name = "vResults" 
                   
            select 
            = "msxsl:node-set($vrtfResults)/*" 
            />

             <xsl:value-of select = "$vResults[last()]/*[2]" 
            />
         </xsl:template>

         <xsl:template name = "myImproveGenerator" 
                  
            match 
            = "*[namespace-uri()='myImproveGenerator']" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pParams" select = "/.." 
            />

             <xsl:choose>
                 <xsl:when test = "not($pList)" 
            >
                     <xsl:call-template name = "improve" 
            >
                         <xsl:with-param name = "pList" select = "$pParams" 
            />
                     </xsl:call-template>
                 </xsl:when>
                 <xsl:otherwise>
                     <xsl:call-template name = "improve" 
            >
                         <xsl:with-param name = "pList" select = "$pList[last()]/*" 
            />
                     </xsl:call-template>
                 </xsl:otherwise>
             </xsl:choose>
         </xsl:template>

         <xsl:template name = "MyImproveController" 
                  
            match 
            = "*[namespace-uri()='myImproveController']" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pParams" select = "0.01" 
            />

             <xsl:choose>
                 <xsl:when test = "count($pList) &lt; 2" 
            >1</xsl:when>
                 <xsl:otherwise>
                     <xsl:variable name = "vDiff" 
                      
            select 
            = "$pList[last()]/*[2] - $pList[last() - 1]/*[2]" 
            />

                     <xsl:if test = "not($vDiff &lt; $pParams and $vDiff > (0 - $pParams))
           and count($pList) &lt;= 5 " 
            >1</xsl:if>
                 </xsl:otherwise>
             </xsl:choose>
         </xsl:template>

     </xsl:stylesheet>

Let's now test improvedIntegration with a concrete example. We want to calculate the following four integrals:

1
∫ x² dx ,
0

1
∫ x³ dx ,
0

1
∫ 4/(1 + x²) dx , and
0

2
∫ 1/x dx
1

These should return accordingly:

1/3, 1/4, 3.1415926... (Pi), 0.69314718... (ln 2)

testImprovedIntegration.xsl

     <xsl:stylesheet version = "1.0" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:IntegralFunction="IntegralFunction"
    
            xmlns:IntegralFunction2="IntegralFunction2"
    
            xmlns:IntegralFunction3="IntegralFunction3"
    
            xmlns:IntegralFunction4="IntegralFunction4"
    
            exclude-result-prefixes = "xsl IntegralFunction IntegralFunction2 
                               IntegralFunction3 IntegralFunction4" 
            >

         <xsl:import href = "improvedIntegration.xsl" 
            />

         <xsl:output method = "html" encoding = "UTF-8" 
            />

         <IntegralFunction:IntegralFunction/>
         <IntegralFunction2:IntegralFunction2/>
         <IntegralFunction3:IntegralFunction3/>
         <IntegralFunction4:IntegralFunction4/>

         <xsl:template match = "/" 
            >
             <br/> 1 
             <br/>
             <font size = "5" 
            >&#x222B;</font> x&#x00B2; = 
             <xsl:variable name = "vMyFun" 
                   
            select 
            = "document('')/*/IntegralFunction:*[1]" 
            />

             <xsl:call-template name = "improvedIntegration" 
            >
                 <xsl:with-param name = "pFun" select = "$vMyFun" 
            />
                 <xsl:with-param name = "pA" select = "0" 
            />
                 <xsl:with-param name = "pB" select = "1" 
            />
                 <xsl:with-param name = "pEpsRough" select = "0.001" 
            />
                 <xsl:with-param name = "pEpsImproved" select = "0.0001" 
            />
             </xsl:call-template>
             <br/>0 
             <br/>
             <br/>&#xA0;1 
             <br/>
             <font size = "5" 
            >&#x222B;</font> x&#x00B2; = 
             <xsl:variable name = "vMyFun2" 
                   
            select 
            = "document('')/*/IntegralFunction2:*[1]" 
            />

             <xsl:call-template name = "improvedIntegration" 
            >
                 <xsl:with-param name = "pFun" select = "$vMyFun2" 
            />
                 <xsl:with-param name = "pA" select = "0" 
            />
                 <xsl:with-param name = "pB" select = "1" 
            />
                 <xsl:with-param name = "pEpsRough" select = "0.001" 
            />
                 <xsl:with-param name = "pEpsImproved" select = "0.0001" 
            />
             </xsl:call-template>
             <br/>0 
             <br/>
             <br/>&#xA0;1 
             <br/>
             <font size = "5" 
            >&#x222B;</font> 4/(1 + x&#x00B2;) = 
             <xsl:variable name = "vMyFun3" 
                   
            select 
            = "document('')/*/IntegralFunction3:*[1]" 
            />

             <xsl:call-template name = "improvedIntegration" 
            >
                 <xsl:with-param name = "pFun" select = "$vMyFun3" 
            />
                 <xsl:with-param name = "pA" select = "0" 
            />
                 <xsl:with-param name = "pB" select = "1" 
            />
                 <xsl:with-param name = "pEpsRough" select = "0.00001" 
            />
                 <xsl:with-param name = "pEpsImproved" select = "0.0000000000001" 
            />
             </xsl:call-template>
             <br/>0 
             <br/>
             <br/>&#xA0;2 
             <br/>
             <font size = "5" 
            >&#x222B;</font> 1/x = 
             <xsl:variable name = "vMyFun4" 
                   
            select 
            = "document('')/*/IntegralFunction4:*[1]" 
            />

             <xsl:call-template name = "improvedIntegration" 
            >
                 <xsl:with-param name = "pFun" select = "$vMyFun4" 
            />
                 <xsl:with-param name = "pA" select = "1" 
            />
                 <xsl:with-param name = "pB" select = "2" 
            />
                 <xsl:with-param name = "pEpsRough" select = "0.00001" 
            />
                 <xsl:with-param name = "pEpsImproved" select = "0.000000001" 
            />
             </xsl:call-template>
             <br/>1 </xsl:template>

         <xsl:template name = "myIntegralFn" 
                 match = "*[namespace-uri()='IntegralFunction']" 
            >
             <xsl:param name = "pX" 
            />
             <xsl:value-of select = "$pX * $pX" 
            />
         </xsl:template>

         <xsl:template name = "myIntegralFn2" 
                 
            match 
            = "*[namespace-uri()='IntegralFunction2']" 
            >
             <xsl:param name = "pX" 
            />
             <xsl:value-of select = "$pX * $pX * $pX" 
            />
         </xsl:template>

         <xsl:template name = "myIntegralFn3" 
                  
            match 
            = "*[namespace-uri()='IntegralFunction3']" 
            >

             <xsl:param name = "pX" 
            />
             <xsl:value-of select = "4 div (1 + $pX * $pX)" 
            />
         </xsl:template>

         <xsl:template name = "myIntegralFn4" 
                  
            match 
            = "*[namespace-uri()='IntegralFunction4']" 
            >

             <xsl:param name = "pX" 
            />
             <xsl:value-of select = "1 div $pX" 
            />
         </xsl:template>

     </xsl:stylesheet>

Results of testImprovedIntegration.xsl

1
∫ x² dx = 0.3333333333333333
0

1
∫ x³ dx = 0.25
0

1
∫ 4/(1 + x²) dx = 3.1415926535897096
0

2
∫ 1/x dx = 0.693147180943227
1