The Functional Programming Language XSLT - A proof through examples

Lazy evaluation

A very powerful feature of some FP languages (e.g. Haskell ) is having so called non-strict functions and lazy evaluation. A function f is said to be strict if, when applied to a non-terminating expression, it also fails to terminate. For most programming languages all functions are strict. But this is not so in Haskell. In Haskell if a function does not need a value from its argument, it never gets evaluated. Such kind of function evaluation is called lazy evaluation, and non-strict functions are called "lazy functions", and are said to evaluate their arguments "lazily", or "by need" [10]. With lazy evaluation it becomes possible to operate on infinite data structures. For example,

numsFrom n = n : numsFrom (n + 1)

evaluates to the infinite list of successive integers, beginning with n. From it, the infinite list of squares is constructed:

squares = map (^2) (numsFrom 0)

With lazy evaluation implemented, a function can reference an infinite data structure and use only a finite number of its elements like in:

take 10 squares => [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

which takes the first 10 elements from the infinite list squares, or:

takeWhile (< 100) squares => [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

which takes from the infinite list squares the first elements, which are less than 100, etc.

Because XSLT does not support lazy evaluation, we provide implementation of several functions from the Haskell Prelude, which perform (simulated) lazy evaluation of infinite lists:

The function take produces a list of the starting n elements of a given list. Its definition in Haskell is as follows:

take :: Int -> [a] -> [a]

take 0 _ = []

take _ [] = []

take n (x:xs) | n>0 = x : take (n-1) xs

take _ _ = error "Prelude.take: negative argument"

The function takeWhile produces a list consisting of all elements beginning from the start of a given list, which satisfy a given predicate.

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile p [] = []

takeWhile p (x:xs)

| p x = x : takeWhile p xs

| otherwise = []

and we also implement a group of other Haskell functions on lists, but our implementation is restricted only on finite lists:

drop -- takes all the elements of a list with the exception of the first n.

drop :: Int -> [a] -> [a]

drop 0 xs = xs

drop _ [] = []

drop n (_:xs) | n>0 = drop (n-1) xs

drop _ _ = error "Prelude.drop: negative argument"

dropWhile -- produces a list consisting of all the elements of a given list with the exception of the starting group of elements, which satisfy a given predicate.

dropWhile :: (a -> Bool) -> [a] -> [a]

dropWhile p [] = []

dropWhile p xs@(x:xs')

| p x = dropWhile p xs'

| otherwise = xs

splitAt -- produces two lists from a given list when split at the n-th element.

splitAt :: Int -> [a] -> ([a], [a])

splitAt 0 xs = ([],xs)

splitAt _ [] = ([],[])

splitAt n (x:xs) | n>0 = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs

splitAt _ _ = error "Prelude.splitAt: negative argument"

span -- produces two lists from a given list, the first consisting of all starting elements that satisfy a given predicate, and the second, consisting of the rest of the elements of the given list.

span        :: (a -> Bool) -> [a] -> ([a],[a])

span p []   = ([],[])

span p xs@(x:xs')

   | p x       = (x:ys, zs)

   | otherwise = ([],xs)

                where (ys,zs) = span p xs'

partition -- produces two lists: the first consisting of all the elements of a given element, which satisfy a given predicate, and the second consisting of the rest of the elements of the given list.

partition :: (a -> Bool) -> [a] -> ([a],[a])

partition p xs = foldr select ([],[]) xs

where select x (ts,fs) | p x = (x:ts,fs)

| otherwise = (ts,x:fs)

The code of the implemented XSLT functions is presented below:

buildListWhile

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


         <xsl:template name = "buildListWhile" >
             <xsl:param name = "pGenerator" select = "/.." />
             <xsl:param name = "pParamGenerator" select = "/.." />
             <xsl:param name = "pController" select = "/.." />
             <xsl:param name = "pParam0" select = "/.." />
             <xsl:param name = "pContollerParam" select = "/.." />
             <xsl:param name = "pElementName" select = "'el'" />
             <xsl:param name = "pList" select = "/.." />

             <xsl:if test = "not($pController)" >
                 <xsl:message terminate = "yes" >
         [buildListWhile]Error: No pController specified: 
						 
       
  would cause infinite processing.
       
            </xsl:message>
             </xsl:if>

             <xsl:variable name = "vElement" >
                 <xsl:element name = "{$pElementName}" >
                     <xsl:apply-templates select = "$pGenerator" >
                         <xsl:with-param name = "pParams" select = "$pParam0" />
                         <xsl:with-param name = "pParamGenerator" select = "$pParamGenerator" />
                         <xsl:with-param name = "pList" select = "$pList" />
                     </xsl:apply-templates>
                 </xsl:element>
             </xsl:variable>

             <xsl:variable name = "newList" >
                 <xsl:copy-of select = "$pList" 
            />
                 <xsl:copy-of select = "msxsl:node-set($vElement)/*" 
            />
             </xsl:variable>

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

             <xsl:variable name = "vAccept" 
            >
                 <xsl:apply-templates select 
            = "$pController" 
            >
                     <xsl:with-param name = "pList" 
                        select 
            = "$vResultList" 
            />
                     <xsl:with-param name = "pParams" 
                        select 
            = "$pContollerParam" 
            />
                 </xsl:apply-templates>
             </xsl:variable>

             <xsl:choose>
                 <xsl:when test = "not(string($vAccept))" 
            >
                     <xsl:copy-of select = "$pList" 
            />
                 </xsl:when>
                 <xsl:otherwise>
                     <xsl:call-template name = "buildListWhile" 
            >
                         <xsl:with-param name = "pGenerator" 
                          select 
            = "$pGenerator" 
            />
                         <xsl:with-param name = "pParamGenerator" 
                          select 
            = "$pParamGenerator" 
            />
                         <xsl:with-param name = "pController" 
                         select 
            = "$pController" 
            />
                         <xsl:with-param name = "pContollerParam" 
                         select 
            = "$pContollerParam" 
            />
                         <xsl:with-param name = "pParam0" 
                         select 
            = "$pParam0" 
            />
                         <xsl:with-param name = "pElementName" 
                         select 
            = "$pElementName" 
            />
                         <xsl:with-param name = "pList" 
                         select 
            = "$vResultList" 
            />
                     </xsl:call-template>
                 </xsl:otherwise>
             </xsl:choose>
         </xsl:template>

     </xsl:stylesheet>

buildListUntil

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

         <xsl:template name = "buildListUntil" 
            >
             <xsl:param name = "pGenerator" select = "/.." 
            />
             <xsl:param name = "pController" select = "/.." 
            />
             <xsl:param name = "pParam0" select = "/.." 
            />
             <xsl:param name = "pParamGenerator" select = "/.." 
            />
             <xsl:param name = "pElementName" select = "'el'" 
            />
             <xsl:param name = "pList" select = "/.." 
            />

             <xsl:if test = "not($pController)" 
            >
                 <xsl:message terminate = "yes" 
            >
         
[buildListUntil]Error:
         
No pController specified: would cause infinite processing.
       
            </xsl:message>
             </xsl:if>


             <xsl:variable name = "vElement" 
            >
                 <xsl:element name = "{$pElementName}" 
            >
                     <xsl:apply-templates select 
            = "$pGenerator" 
            >
                         <xsl:with-param name = "pParams" select = "$pParam0" 
            />
                         <xsl:with-param name = "pList" select = "$pList" 
            />
                     </xsl:apply-templates>
                 </xsl:element>
             </xsl:variable>

             <xsl:variable name = "newList" 
            >
                 <xsl:copy-of select = "$pList" 
            />
                 <xsl:copy-of select = "msxsl:node-set($vElement)/*" 
            />
             </xsl:variable>

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

             <xsl:variable name = "vShouldStop" 
            >
                 <xsl:apply-templates select 
            = "$pController" 
            >
                     <xsl:with-param name = "pList" select = "$vResultList" 
            />
                     <xsl:with-param name = "pParams" select = "$pParam0" 
            />
                 </xsl:apply-templates>
             </xsl:variable>

             <xsl:choose>
                 <xsl:when test = "string($vShouldStop)" 
            >
                     <xsl:copy-of select = "$vResultList" 
            />
                 </xsl:when>
                 <xsl:otherwise>

                     <xsl:variable name = "vNewParams" 
            >
                         <xsl:apply-templates select 
            = "$pParamGenerator" 
            >
                             <xsl:with-param name = "pList" select = "$vResultList" 
            />
                             <xsl:with-param name = "pParams" select = "$pParam0" 
            />
                         </xsl:apply-templates>
                     </xsl:variable>

                     <xsl:call-template name = "buildListUntil" 
            >
                         <xsl:with-param name = "pGenerator" 
                          
            select = "$pGenerator" 
            />
                         <xsl:with-param name = "pController" 
                          
            select = "$pController" 
            />
                         <xsl:with-param name = "pParam0" 
                          
            select = "msxsl:node-set($vNewParams)/*" 
            />
                         <xsl:with-param name = "pParamGenerator" 
                          
            select = "$pParamGenerator" 
            />
                         <xsl:with-param name = "pElementName" 
                          
            select = "$pElementName" 
            />
                         <xsl:with-param name = "pList" 
                          
            select = "$vResultList" 
            />
                     </xsl:call-template>

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

     </xsl:stylesheet>

take

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

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

         <take-controller:take-controller/>

         <take-dynamic-controller:take-dynamic-controller/>

         <xsl:template name = "take" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pN" select = "0" 
            />
             <xsl:param name = "pGenerator" select = "/.." 
            />
             <xsl:param name = "pParam0" select = "/.." 
            />
             <xsl:param name = "pParamGenerator" select = "/.." 
            />
             <xsl:param name = "pElementName" select = "'el'" 
            />

             <xsl:variable name = "vTakeController" 
                   
            select = "document('')/*/take-controller:*[1]" 
            />
             <xsl:variable name = "vTakeDynController" 
                   select 
            = "document('')/*/take-dynamic-controller:*[1]" 
            />

             <xsl:choose>
                 <xsl:when test = "$pList" 
            >
                     <xsl:copy-of select = "$pList[position() &lt;= $pN]" 
            />
                 </xsl:when>
                 <xsl:when test = "$pGenerator" 
            >
                     <xsl:call-template name = "buildListWhile" 
            >
                         <xsl:with-param name = "pList" 
                          
            select = "/.." 
            />
                         <xsl:with-param name = "pGenerator" 
                          
            select = "$pGenerator" 
            />
                         <xsl:with-param name = "pController" 
                          
            select = "$vTakeDynController" 
            />
                         <xsl:with-param name = "pContollerParam" 
                          
            select = "$pN" 
            />
                         <xsl:with-param name = "pParam0" 
                          
            select = "$pParam0" 
            />
                         <xsl:with-param name = "pParamGenerator" 
                          
            select = "$pParamGenerator" 
            />
                         <xsl:with-param name = "pElementName" 
                          
            select = "$pElementName" 
            />
                     </xsl:call-template>
                 </xsl:when>
             </xsl:choose>
         </xsl:template>

         <xsl:template name = "takeController" 
                  
            match 
            = "*[namespace-uri()='take-controller']" 
            >
             <xsl:param name = "pParams" 
            />

             <xsl:if test = "$pParams > 0" 
            >1</xsl:if>
         </xsl:template>

         <xsl:template 
            name 
            = "takeDynController" 
                  
            match 
            = "*[namespace-uri()='take-dynamic-controller']" 
            >
             <xsl:param name = "pList" 
            />
             <xsl:param name = "pParams" 
            />

             <xsl:if test = "$pParams >= count($pList)" 
            >1</xsl:if>
         </xsl:template>

     </xsl:stylesheet>

takeWhile

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

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

         <xsl:template name = "takeWhile" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pController" select = "/.." 
            />
             <xsl:param name = "pContollerParam" select = "/.." 
            />
             <xsl:param name = "pGenerator" select = "/.." 
            />
             <xsl:param name = "pParam0" select = "/.." 
            />
             <xsl:param name = "pParamGenerator" select = "/.." 
            />
             <xsl:param name = "pElementName" select = "'el'" 
            />

             <xsl:if test = "not($pController)" 
            >
                 <xsl:message terminate = "yes" 
            >
         
            [takeWhile]Error: pController not specified.</xsl:message>
             </xsl:if>

             <xsl:choose>
                 <xsl:when test = "$pList" 
            >
                     <xsl:variable name = "vAccept" 
            >
                         <xsl:apply-templates select 
            = "$pController" 
            >
                             <xsl:with-param name = "pList" select = "$pList[1]" 
            />
                             <xsl:with-param name = "pParams" select = "$pContollerParam" 
            />
                         </xsl:apply-templates>
                     </xsl:variable>

                     <xsl:if test = "string($vAccept)" 
            >
                         <xsl:copy-of select = "$pList[1]" 
            />
                         <xsl:call-template name = "takeWhile" 
            >
                             <xsl:with-param name = "pList" 
                            
            select = "$pList[position() > 1]" 
            />
                             <xsl:with-param name = "pController" 
                            
            select = "$pController" 
            />
                             <xsl:with-param name = "pContollerParam" 
                            
            select = "$pContollerParam" 
            />
                             <xsl:with-param name = "pGenerator" 
                            
            select = "$pGenerator" 
            />
                             <xsl:with-param name = "pParam0" 
                            
            select = "$pParam0" 
            />
                             <xsl:with-param name = "pParamGenerator" 
                            
            select = "$pParamGenerator" 
            />
                             <xsl:with-param name = "pElementName" 
                            
            select = "$pElementName" 
            />
                         </xsl:call-template>
                     </xsl:if>

                 </xsl:when>
                 <xsl:when test = "$pGenerator" 
            >

                     <xsl:call-template name = "buildListWhile" 
            >
                         <xsl:with-param name = "pList" 
                          
            select = "/.." 
            />
                         <xsl:with-param name = "pGenerator" 
                          
            select = "$pGenerator" 
            />
                         <xsl:with-param name = "pController" 
                          
            select = "$pController" 
            />
                         <xsl:with-param name = "pContollerParam" 
                          
            select = "$pContollerParam" 
            />
                         <xsl:with-param name = "pParam0" 
                          
            select = "$pParam0" 
            />
                         <xsl:with-param name = "pParamGenerator" 
                          
            select = "$pParamGenerator" 
            />
                         <xsl:with-param name = "pElementName" 
                          
            select = "$pElementName" 
            />
                     </xsl:call-template>

                 </xsl:when>
             </xsl:choose>
         </xsl:template>

     </xsl:stylesheet>

Functions only implemented for finite lists:

drop

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

         <xsl:template name = "drop" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pN" select = "0" 
            />

             <xsl:copy-of select = "$pList[position() > $pN]" 
            />
         </xsl:template>

     </xsl:stylesheet>

dropWhile

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

         <xsl:template name = "dropWhile" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pController" select = "/.." 
            />
             <xsl:param name = "pContollerParam" select = "/.." 
            />
             <xsl:param name = "pParam0" select = "/.." 
            />
             <xsl:param name = "pElementName" select = "'el'" 
            />

             <xsl:if test = "not($pController)" 
            >
                 <xsl:message terminate = "yes" 
            >
        
            [dropWhile]Error: pController not specified.</xsl:message>
             </xsl:if>

             <xsl:if test = "$pList" 
            >
                 <xsl:variable name = "vDrop" 
            >
                     <xsl:apply-templates select 
            = "$pController" 
            >
                         <xsl:with-param name = "pList" select = "$pList[1]" 
            />
                         <xsl:with-param name = "pParams" 
                          
            select = "$pContollerParam" 
            />
                     </xsl:apply-templates>
                 </xsl:variable>

                 <xsl:choose>
                     <xsl:when test = "string($vDrop)" 
            >
                         <xsl:call-template name = "dropWhile" 
            >
                             <xsl:with-param name = "pList" 
                            
            select = "$pList[position() > 1]" 
            />
                             <xsl:with-param name = "pController" 
                            
            select = "$pController" 
            />
                             <xsl:with-param name = "pContollerParam" 
                            
            select = "$pContollerParam" 
            />
                             <xsl:with-param name = "pParam0" 
                            
            select = "$pParam0" 
            />
                             <xsl:with-param name = "pElementName" 
                            
            select = "$pElementName" 
            />
                         </xsl:call-template>
                     </xsl:when>

                     <xsl:otherwise>
                         <xsl:copy-of select = "$pList" 
            />
                     </xsl:otherwise>
                 </xsl:choose>
             </xsl:if>
         </xsl:template>

     </xsl:stylesheet>

split

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

         <xsl:template name = "split" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pN" select = "0" 
            />
             <xsl:param name = "pElementName" select = "'list'" 
            />

             <xsl:element name = "{$pElementName}" 
            >
                 <xsl:copy-of select = "$pList[position() &lt;= $pN]" 
            />
             </xsl:element>

             <xsl:element name = "{$pElementName}" 
            >
                 <xsl:copy-of select = "$pList[position() > $pN]" 
            />
             </xsl:element>

         </xsl:template>

     </xsl:stylesheet>

span

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

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

         <xsl:template name = "span" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pController" select = "/.." 
            />
             <xsl:param name = "pContollerParam" select = "/.." 
            />
             <xsl:param name = "pParam0" select = "/.." 
            />
             <xsl:param name = "pElementName" select = "'list'" 
            />

             <xsl:variable name = "vRTF-Positive" 
            >
                 <xsl:call-template name = "takeWhile" 
            >
                     <xsl:with-param name = "pList" select = "$pList" 
            />
                     <xsl:with-param name = "pController" 
                         
            select = "$pController" 
            />
                     <xsl:with-param name = "pContollerParam" 
                         
            select = "$pContollerParam" 
            />
                     <xsl:with-param name = "pParam0" select = "$pParam0" 
            />
                 </xsl:call-template>
             </xsl:variable>

             <xsl:variable name = "vPositive" 
                    
            select = "msxsl:node-set($vRTF-Positive)/*" 
            />

             <xsl:element name = "{$pElementName}" 
            >
                 <xsl:copy-of select = "$vPositive" 
            />
             </xsl:element>

             <xsl:element name = "{$pElementName}" 
            >
                 <xsl:copy-of select = "$pList[position() > count($vPositive)]" 
            />
             </xsl:element>

         </xsl:template>

     </xsl:stylesheet>

partition

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

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

         <xsl:template name = "partition" 
            >
             <xsl:param name = "pList" select = "/.." 
            />
             <xsl:param name = "pController" select = "/.." 
            />
             <xsl:param name = "pContollerParam" select = "/.." 
            />
             <xsl:param name = "pParam0" select = "/.." 
            />
             <xsl:param name = "pElementName" select = "'list'" 
            />

             <xsl:variable name = "vHoldsListRTF" 
            >
                 <xsl:call-template name = "map" 
            >
                     <xsl:with-param name = "pFun" select = "$pController" 
            />
                     <xsl:with-param name = "pList1" select = "$pList" 
            />
                 </xsl:call-template>
             </xsl:variable>

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

             <xsl:element name = "{$pElementName}" 
            >
                 <xsl:for-each select = "$vHoldsList" 
            >
                     <xsl:variable name = "vPosition" select = "position()" 
            />
                     <xsl:if test = "string(.)" 
            >
                         <xsl:copy-of select = "$pList[position()=$vPosition]" 
            />
                     </xsl:if>
                 </xsl:for-each>
             </xsl:element>

             <xsl:element name = "{$pElementName}" 
            >
                 <xsl:for-each select = "$vHoldsList" 
            >
                     <xsl:variable name = "vPosition" select = "position()" 
            />
                     <xsl:if test = "not(string(.))" 
            >
                         <xsl:copy-of select = "$pList[position()=$vPosition]" 
            />
                     </xsl:if>
                 </xsl:for-each>
             </xsl:element>
         </xsl:template>

     </xsl:stylesheet>