Mark Wilson I am the creator of TopXML. I am available for international and local (Australia) contracts. I am a Solution Architect/Business Analyst. I have worked in IT in several countries (NZ, Australia, South Africa, UK) building and training teams for government and very large non-governmental organizations. I am ex-Microsoft Consulting Services. I wrote the first book on Microsoft XML published in 2000 called XML Programming with VB and ASP. Most recently I have been building tools for the SEO industry. Ask me for a 37 point SEO health-checkup for your website.
This article is a follow-up from the recent publication "The Functional Programming
Language XSLT". Provided here is the answer to a FAQ about
functional programming in XSLT: Can functions be created
dynamically during run-time and what are some general ways to
achieve this?. Using the XSLT functional programming library FXSL,
examples are given of performing functional composition, currying
and partial application of functions, as well as of dynamically
creating a function, which corresponds to a lambda expression.
In a recent article [1], an XSLT implementation was provided for
higher-order functions and most of the major functional programming
design patterns and functions, e.g. as provided in Haskell's
Prelude or in John Hughes' article "Why Functional Programming
Matters" [2]. The response has been overwhelming, and the first
page of the article was accessed more than 1200 times in just three
days, the XSLT Functional Programming Library FXSL[3] was downloaded many hundreds times and a new edition of FXSL
(for Xalan) was spontaneously produced by an enthusiastic
reader.
Despite this spontaneous acceptance, there are more steps to go
until we reach a state, in which programmers will feel comfortable
and fully conversant in using the functional programming style and
techniques in XSLT:
The FXSL library should include even more FP design patterns
and functions.
FXSL documentation should be provided.
XSLT programmers need to be educated in using the FP style and
techniques.
An indication of the last need is the following frequently asked
question: "Can functions be created dynamically during run-time and
what are some general ways to achieve this?" The rest of this
article provides the answer to this question.
We start by formally defining a number of important concepts as
follows:
Functional composition.
The definition of functional composition is as follows:
Given two functions:
g :: a -> b and f ::
b -> c
Their functional composition is defined as:
(.) :: (b -> c) -> (a -> b) -> (a ->
c)
(f . g) x = f (g x)
This means that given two functions f and g, (.) glues them
together by applying f on the result of applying g.
(.) is completely polymorphic, the only constraint on the types
of f and g being that the type of the result of g
must be the same as the type of the argument of f.
Functional composition is one of the most often used ways of
producing a new function by applying two other functions in a
successive pipe-like manner.
Curried functions.
There are two ways of looking at a function that has more than
one argument. For example, we could have:
f(x, y) = x * y (1)
or
f x y = x * y
(2)
The first expression above defines a function that takes
a pair of arguments and produces their product.
In contrast, the second definition allows the function f to take
its arguments one at a time. It is perfectly possible to have the
expression:
f x
Not providing the second argument in this concrete case results
in a new function g of one argument, defined bellow:
g y = x * y
Defining a function as in (2) has the following advantages:
A uniform form of expressing function application over one or
many arguments - we write: f x, f x y, f x
y z, ... etc.
The ability to easily produce partial functions, resulting from
applying a function only on the first several of its arguments. For
example, we can also define the function g above as (x *) - a
partial application of multiplication, in which the first argument
has been bound to the value x.
A function as defined in (2) can be regarded as having just one
argument x, and returning a function of y.
Functions defined as in (2) are called curried functions
after Haskell Curry, who was one of the developers of the lambda
calculus, and after whom the Haskell programming language was
named.
Functions defined as in (1) are called uncurried.
Uncurried functions can be turned into curried ones by the curry
function, and curried functions can be turned into uncurried ones
by the uncurry function. Here's how curry and uncurry
are defined in the Haskell Prelude:
curry f x y = f(x,y)
uncurry f (x, y) = f x y
Partial applications.
A partial application is a function returned by any
application of a curried function on the first several, but not all
of its arguments. For example:
incr = (1 +)
double = (2 *)
As defined above, incr is a function that adds one to its
argument, and double is a function that multiplies its argument by
2.
Partial application in the special case when the function is an
operator is called an operator section. (1 +) and (2 *)
above are examples of operator sections.
Using partial applications it is possible to simplify
considerably many function definitions, which results in shorter,
simpler, more understandable and maintainable code. For example,
instead of defining sum and product as:
sum xs = foldl (+) 0
xs
product xs = foldl (*) 1 xs
it is possible to define them in an equivalent and much simpler
way by omitting the last identically-named argument(s) from both
sides of the definition:
sum = foldl (+)
0
product = foldl (*) 1
Producing partial applications is one of the most flexible and
powerful ways of creating dynamically new functions.
Lambda expressions.
A lambda expression (also known as anonymous function) is a
concept derived directly from Church's lambda calculus [4]. The
following are examples of lambda expressions:
\x -> x + 1
\x y -> x * y
The first expression above defines a (anonymous) function, which
increments its argument.
The second expression above defines a (anonymous) function,
which calculates the product of its two arguments.
Any partial application can be expressed as a lambda expression.
For example:
(f x ) y = \y -> (f x) y
expresses the partial application of f x
The reverse is not true - lambda expressions are more powerful
and can define functions, which are not partial applications. For
example:
\x -> f x y
is not a partial application, because it is a function of the
first argument x, while the second argument (not the first!) is
bound to the value y.
Lambda expressions are useful in all cases when it is not
necessary to name a function (e.g. when the function is to be used
only locally, or is dynamically created) but just to apply it. An
example is often the case with functions to be used with the map
function:
It is almost straightforward to implement functional composition
in XSLT, as can be seen from the source bellow. The named template
compose has three parameters, two of which are the functions
to be composed - pFun1 and pFun2 (these are actually template
references), and the third is the argument pArg1, on which pFun2
will be applied.
In many cases there are more than two functions that should be
successively applied, each using as its argument the result
returned from the previous function. In any such case it would be
inconvenient or even impossible (e.g. the number of functions to be
composed is not known in advance) to compose the functions two at a
time.
Therefore, we also provide the definition of a function, which
takes two arguments: a list of functions and an argument on which
the last function in the list is to be applied, and produces the
result of the functional composition of all functions, using that
argument:
multiCompose x [f] = f x
multiCompose x [f:fs] = f (multiCompose x fs)
Using the foldr function and the function application operator $
(f $ x = f x) we can define the multiCompose function as
follows:
multiCompose y fs = foldr ($) y fs
or even simpler:
multiCompose y = foldr ($) y
The XSLT implementation is once again very simple:
To show the big importance of having a convenient way to perform
(multiple) composition, here are two more examples.
Imagine that we have to perform a series of map-operations on a
list of values. We could define a multiMap function in the
following way:
multiMapR xs fs = foldr map xs fs
or (, which is the same) just:
multiMapR = foldr map
multiMapR will map successively all functions in the list fs (in
a right-to-left order) starting on the list xs, then on the result
of the map with the right-most function from fs,... etc.
There's only one quite unpleasant issue with the multiMapX
(where X is 'L' or 'R') functions as defined above: successive
mapping will use a lot of memory (N times the memory for the list
xs, where N = length(fs)) as every
map operation
produces a new list, which some not quite intelligent processor/garbage
collector may not reclaim in time.
The solution to this problem comes easily if we notice that the
following equation holds always true:
multiMapR xs fs = map (multiCompose fs)
xs (3)
So, only one map operation is performed in (3). Indeed, this is
what HUGS [5] will produce:
Note also, that in the above definition the first argument
passed to the map function is a partial application of
multiCompose. The proof of (3) and the XSLT implementation of
an efficient multiMapX function are left as exercise to the reader. An
obvious question will arise attempting to do so -- "how to implement
a partial application in XSLT?" The answer to this question is
provided in the next section.
The last example is strongly based on requirements that
originated from routine, practical XSLT programming.
We need to implement a trim function, which accepts a string and
produces its content stripped off any leading or trailing
white-space characters.
A definition of trim in Haskell might look like this:
trim :: [Char] ->
[Char]
trim = applyTwice
(reverse . trim1)
where trim1 = dropWhile (`elem` delim)
delim = [' ', '\t', '\n', '\r']
applyTwice f = f . f
What this says is that we are actually doing the following:
trim1 (trim the start of) the string.
reverse the left-trimmed string.
trim1 the reversed string (this will trim the left end of the
reversed string, which is actually the right end of the original
string).
reverse finally the string (it has already been trimmed from
both ends).
Note that here we're using both functional composition and
partial application almost in all possible places in the above
definition.
A simpler solution is to use just multiCompose:
trim = multiCompose [reverse, trim1,
reverse, trim1]
Here's the XSLT implementation of the above definition of
trim:
A number of other functions are used in the code: str-dropWhile,
strReverse and str-foldl.
These are part of the FXSL library as
currently available on TopXML.com. It is a general convention in
FXSL that a function named strSomeName is an implementation of the
function someName for strings. This is necessary in an XSLT
implementation, because strings in Xpath/XSLT cannot be naturally
treated as lists of characters.
Here's a simple test of the XSLT trim function:
testTrim.xsl
<xsl:stylesheetversion="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:importhref="trim.xsl"/>
<!-- to be applied on trim.xml -->
<xsl:outputmethod="text"/>
<xsl:templatematch="/">
'<xsl:call-templatename="trim">
<xsl:with-paramname="pStr" select="string(/*)"/>
</xsl:call-template>'
</xsl:template>
</xsl:stylesheet>
Let's apply the above transformation on the following simple xml
document:
The examples in the previous section demonstrated the importance
of being able to use partial applications of functions. Here we
provide an XSLT implementation of currying and partial application.
Let's recall the definition of curry:
curry f x y = f(x,y)
This means that curry f returns a (curried) function of two
arguments, and
curry f x returns a function of one argument.
An XSLT implementation of curry should therefore do the
following:
Keep a reference to the function f. This will be needed if all
arguments are passed and the value of f (as opposed to a partial
application function) must be calculated.
Keep a record of the number of arguments of f. This is
necessary, as we are departing from the above definition (taken
from Haskell's Prelude) and will try to define and implement in
XSLT a more generic currying function, that can process functions
having up to ten arguments.
Provide a reference to an internal generic partial-applicator
function, that will record and accumulate the name-value pairs of
the passed arguments and, in case all arguments have been provided,
will apply f on them and return the result. In case not all
arguments' values have yet been provided, the partial-applicator
will return a variant of itself, that knows about all the
arguments' values accumulated so far. Here's another difference
between our definition and XSLT implementation of partial
application and its Haskell counterpart: because XSLT template
parameters are known by name, they can be passed in any order -
this means that in XSLT we can implement partial application not
only when the first argument(s) are provided, but in any case in
which any subset of arguments' values have been specified. For
example, given the function:
f x y z,
in Haskell one can have the following partial
applications:
f x and f x y.
Our implementation will allow us to obtain:
f x, f
y, f z,
f x y, f x z, f y z.
But, in case we're accepting named arguments, how do we know the
names of the arguments of an arbitrary function to be curried and
partially applied? The answer is that while arguments have names,
only the names of type "arg"<N> are allowed - that is "arg1",
"arg2", ..., "arg10". This is a reasonable limitation resulting in a
much more powerful partial application through the combination of
naming and implicit ordering, indicated by the numeric part of the
names of the arguments.
Bellow is our XSLT implementation of curry and partial
application:
