|
|
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
The above code might seem overwhelming in size, however it is very easy to understand. If we ignore the error detection/processing and the treatment of up-to 10 arguments, then the code that does the useful work is just a few lines.
The curry function is very simple. It takes a function (a template reference) and a second argument, which is the number of the arguments of this function.
It produces a partial application of the function with no arguments' values specified.
Then, it checks if values of arguments were specified, and if yes, it applies the internal partialApplicator function to produce the result as a partial application.
The internal partialApplicator function accepts up to ten arguments, whose names follow the convention "arg"<N>, and a special argument named "args", whose purpose will be explained later. All arguments have the empty node-set as default value and any of them may not be specified on an actual instantiation of the function.
The code finds any specified argument using the simple rule, that if the N-th argument is not specified, then "arg"<N> should be false (either the empty node-set or the empty string). All specified arguments are appended to an internal structure, containing elements with names "arg"<N> and values - the value specified for the "arg"<N> argument. For example, if f has 6 arguments and 3 of them were specified, the partialApplicator's internal store could look like this:
Notice that exactly the above structure is returned as the result of applying f with three arguments (arg1 = "a", arg3 = "b", arg5 = "c") -- in fact this is a new template reference to the implementation of partialApplicator, which has recorded all the (partial) arguments' values provided so far.
Whenever values for all arguments will be provided, the code
above instantiates the template that implements the f function -
the template reference to it is stored in the
<fun>
element.
One last question remains - what if we need to pass as some argument's value the empty string (node-set)? This is the only situation, which requires that the "args" argument of partialApplicator or curry be used. As an example, let's assume that we need to pass null string values for arg2 and arg4. Then the value of the args argument must be the following node-set:
Note that this situation will only happen rarely, so it is generally very convenient to create a partial application providing the arguments in the traditional XSLT way.
Let's test currying and partial application of a curried function with a simple example. We'll curry the multiply function, defined as:
multiply (x,y) = x*y
and then obtain its partial application for x=5 ( the function (5*)). Finally, we'll apply the so obtained (5*) on the argument with a value 2 - that is, we'll calculate:
(5*) 2
and the answer should be as expected, 10.
testCurry.xsl
The uncurry function (I doubt someone will really need it) is very straightforward. It just returns (xsl:copy-of) the "fun" child of the curried function.
4. Using currying and partial application - the iter and power functions.
In this section we solve a practical problem by passing a specific function to a much more generic one.
First, let's define the function iter:
iter n f
| n > 0 = f .
iter (n-1) f
| n == 0 = id
| otherwise = error "[iter]: Negative argument!"
As defined, iter takes a non-negative number n and a function f and returns another function, which is the composition of f with itself n-1 times.
We want to use iter in order to define a function pow, which takes a non-negative argument n and a real argument x and produces x to the power of n (x^n):
power n x = iter n (multByX x) 1
where
multByX x y = (*x) y
Note the use of the partial application in multByX. There are cases when we might know in advance that we need a particular partial application (e.g. (+1), (*3), etc.) and in any such case we might implement a specific function for that. However, multByX is defined completely dynamically, depending on the value of x. To implement power as defined above, we must create the multByX function dynamically at run time, whenever power is invoked.
Bellow is the xslt code for iter.
iter.xsl
There's nothing special in the above code except that it implements a DVC (divide and conquer) algorithm in order to avoid crashing of non-smart XSLT processors due to stack overflow in deep recursive processing.
The code for power is more interesting:
pow.xsl
As can be seen, we curry the myMultiply function and at the same time dynamically create its partial application, binding the second argument to the value of pX. Then we pass this dynamically created partial application as argument to iter.
And here's how pow works:
testPow.xsl
Applying the above transformation produces the following result in just 2 sec. (MSXML4 on a W2K 800MHz 128MB RAM Pentium):
|
5. Creating a new function dynamically - the calculator store problem.
Here's an example, taken right from the book of Simon Thompson "Haskell: The Craft of Functional Programming" [6].
Suppose we are to build a calculator for numerical expressions. As part of our system we need to be able to model the current values of the user-defined variables, which we might call the store of the calculator.
To model the store, we define an abstract data type (ADT), which has the following signature:
initial :: Store
value :: Store -> Var -> Int
update :: Store -> Var -> Int -> Store
The function "initial" produces an initial (empty) store.
The function "value" retrieves from the store the value (Int) of a variable name.
The function "update" updates the store with a new (variable-name, value) association.
This ADT can have different implementations, e.g. by keeping an internal list of pairs (varName, value), or by implementing a function that given a variable name returns its value.
The latter implementation is defined in Haskell in the following way:
newtype Store = Sto (Var -> Int)
initial :: Store
initial = Sto (\v -> 0)
value :: Store -> Var -> Int
value (Sto sto) v = sto v
update :: Store -> Var -> Int -> Store
update (Sto sto) v n
= Sto (\w -> if v == w then n else sto w)
Under this implementation:
- The initial store maps every variable to 0.
- To look up a value of a variable v the store function sto is applied to v.
- In the case of an update, the new store returned has a function, which is identical to sto of the updated object, except on the variable, whose value is changed.
Here's the corresponding XSLT implementation:
What is important to note in this example is that on every call of the updateStore function, it creates a new store containing a template reference for a new getValue function, like this:
This template reference always initiates the same template rule, but for a different function. As we see, a function is not identical to the template rule that implements it, it is a tree, in which useful data can be stored, that fully defines the function.
This function may call a chain of previously defined getValue functions for the previous stores, until the first occurrence of a variable name is found, or if not, then finally the initial getValue function instantiates another template rule to return the value 0.
This example has big importance in that it shows how we can implement objects in XSLT. Under this interpretation store is an object with getInitialStore as constructor. It also has two methods - getValue, which performs a lookup for a variable's value given its name, and updateStore, which creates a new store object. We have also showed how to model inheritance and virtual functions. Indeed, every newly created store object can be regarded as derived from the base store object and with a new getValue virtual function. The getValue function has two different implementations - one for the getValue function of an initially constructed store object (this function returns 0 regardless of any given variable name), and another, which performs the lookup. As can be seen in the test of our store implementation bellow, we can invoke any of these functions using the same linguistic construct - which function will be invoked depends on the store object, against the context of which the call is performed. Different implementations of a virtual function all have template references with the same local-name(), but belonging to different namespaces.
And here's the test of our implementation of store.
testStore.xsl
The result from the above test is:
Conclusion
This article demonstrated and explained the details of an XSLT implementation of three major ways of dynamically creating functions and using them:
- Single and multiple function composition.
- Currying of functions and partial application of curried functions.
- Lambda expressions.
The XSLT implementation of partial application is more powerful than the Haskell one, because it allows binding of arguments regardless of order. At the same time partial application in XSLT is very convenient, using the traditional XSLT way of specifying arguments through xsl:with-param.
Currying and partial application support has been included in the latest release of the functional programming library FXSL.
Also demonstrated was a general way to model and implement in XSLT objects having inheritance and virtual functions.
Resources
[1] The Functional Programming Language XSLT - A proof through example
By D.Novatchev
The first in a series of articles, demonstrating the implementation of functional programming in XSLT and its practical use.
[2]Why Functional Programming Matters
By John Hughes
A brilliant paper, explaining the essence and beauty of the most important FP concepts. Multiple, very nice examples. Beautiful and elegant -- this is a "must read" for everyone who needs to understand what FP is all about.
[3] The FXSL functional programming library
A download from the project release files at sourceforge.net. Contains the source code of the functions from [1] and much more. FXSL editions exist for: Saxon, MSXML and Xalan (adapted by Knut Wannheden).
[4] Church, A. 1941. The Calculi of Lambda Conversion. Princeton, NJ: Princeton University Press.
[5] The Haskell Interpreter Hugs
This small, portable Haskell interpreter written in C runs on almost any machine. Hugs is best used as a Haskell program development system: it boasts extremely fast compilation, supports incremental compilation, and has the convenience of an interactive interpreter. Available for all Unix platforms including Linux, DOS, Windows 3.x, and Win 32 (Windows 95, Win32s, NT) and Macintoshs. It has many libraries including Win32 libraries, a foreign interface mechanism to facilitate interoperability with C and the Windows version has a simple graphical user interface.
[6] Haskell: The Craft of Functional Programming
By Simon Thompson,
Second Edition, Addison-Wesley, 507 pages, paperback, 1999. ISBN 0-201-34275-8.
This book is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice and program design, testing, problem solving and how to avoid common pitfalls.
|
|
