|
|
Dynamic Functions using FXSL: Composition, Partial Applications and Lambda Expressions
Dimitre Novatchev, February 2002
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.
The source code for this article is part of the FXSL library version 1.1 and can be downloaded here:
Using MSXML? Get the MSXML source code!
Using SAXON? Get the SAXON source code!
Using XALAN? Get the XALAN source code as adapted by Knut Wannheden !
Introduction
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.
1. Functional composition, curried functions, partial applications and lambda expressions.
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:
map (\x -> x+3/3) xs
2. Implementation of functional composition in XSLT. Examples.
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.
compose.xsl
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:
compose-flist.xsl
Let's now see an example how compose and compose-flist are used in practice.
testCompose.xsl
This transformation calculates:
(*3).(*2) 3
and
(*3).(*2).(*3) 2
The result is:
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.
For example,
multiMapR [1, 2, 3] [(+1), (*2)]
evaluates to:
[3,5,7] (This is map (+1) (map (*2) [1,2,3]) = map (+1) [2,4,6])
Or, if we find more convenient to map the functions from left to right, we can define:
multiMapL = foldl (flip map)
Then the expression:
multiMapL [1, 2, 3] [(+1), (*2)]
evaluates to:
[4,6,8] (This is map (*2) (map (+1) [1,2,3]) = map (*2) [2,3,4])
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:
MyExamples> map (multiCompose [(+1), (*2)]) [1,2,3] [3,5,7] |
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:
trim.xsl
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
Let's apply the above transformation on the following simple xml document:
The result is:
|
3. Implementation of currying and partial application in XSLT.
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:
curry.xsl