Lambda the Ultimate

inactiveTopic Functional programming in XSLT
started 2/5/2002; 4:42:08 AM - last post 1/16/2004; 9:03:14 AM
Ehud Lamm - Functional programming in XSLT  blueArrow
2/5/2002; 4:42:08 AM (reads: 2257, responses: 10)
Functional programming in XSLT
(via the Haskell mailing list)

The purpose of this article is to demonstrate beyond any doubt that XSLT is a functional programming language in its own right. To achieve this goal, a reference XSLT implementation is provided of major FP concepts and functions. This article closely follows the contents and layout of John Hughes' article Why functional programming matters.

A proof by demonstration: go and see some XSLT code .

Of course, not everything that can be done should be done.. Anyway, demonstrations of this sort are always interesting.


Posted to xml by Ehud Lamm on 2/5/02; 4:45:13 AM

Frank Atanassow - Re: Functional programming in XSLT  blueArrow
2/5/2002; 7:34:06 AM (reads: 1671, responses: 0)
I was so deeply affected by this article, that I was moved to write a modest proposal.

Ehud Lamm - Re: Functional programming in XSLT  blueArrow
2/5/2002; 7:45:49 AM (reads: 1671, responses: 0)
Ha!

Frank Atanassow - Re: Functional programming in XSLT  blueArrow
2/5/2002; 10:58:46 AM (reads: 1661, responses: 0)
Now that I've gotten home, I tried to take a closer look at this article. (My SPARC at work runs Netscape 4.7x which makes the pages very unpleasant to read. Or, perhaps I should say, "even less pleasant.")

Well, although the article looks somewhat more readable in IE, I'm afraid I gave up after the first page which explains the principle, just because all the translated functions are so lengthy and obtuse. As I understand it (though my knowledge of XSLT is spotty at best), he uses template references to templates which match a unique node to implement higher-order functions, which is rather like what FPL compilers do when they convert a program to assembly.

Does this prove that XSLT is a higher-order functional language? I don't know. What I would like to see, rather than a laundry list of functions from Hughes' paper, is an implementation of the curry and uncurry functions and examples of their use, or (better) a semi-rigorous translation from XSLT to lambda-calculus. That is all that is required to demonstrate that XSLT is higher-order functional, and I could probably force myself to read it.

As it is, I'm still not convinced. (Possibly my fault for not reading more.) Probably XSL is higher-order functional in the same sense that C and assembly language are.

Dimitre Novatchev - Re: Functional programming in XSLT  blueArrow
2/7/2002; 10:07:10 AM (reads: 1554, responses: 1)
> Does this prove that XSLT is a higher-order functional language? > I don't know. What I would like to see, rather than a laundry

> What I would like to see, rather than a laundry
> list of functions from Hughes' paper, is an implementation of the
> curry and uncurry functions and examples of their use, or
> (better) a semi-rigorous translation from XSLT to lambda-
> calculus.</blockquote</p>
>

I wonder whether this would convince you, but I just produced the curry function. It had been high on my priority list and your questioning whether it was possible to implement curry in XSLT made this priority even higher.

The XSLT implementation of curry is more powerful than the Haskell one. Because in XSLT templates have named parameters, parameters may be specified in any order. The XSLT implementation of curry and any partial application of the curried function accept arguments by name and in any order. Functions with up to ten arguments can be curried.

I'm not providing the code, because of your comments that it's tiresome to read. In case you're interested to have a look at the code, I'd be happy to send it to you. Anyway, it would soon be published as part of a snippet, showing how to use partial applications of functions in XSLT. And certainly curry will be part of the next version of the XSLT functional library FXSL.

The uncurry function in XSLT is a most straightforward one-liner.

In your comments you're missing one very important result of the article. The fact that we now have a functional programming library (FXSL) in XSLT. This library comprises about 50 of the most needed functions from the Haskell Prolog. The library is constantly growing in number and usefulness. It is already implemented for the three most popular XSLT processors -- MSXML, Saxon and Xalan.

What is important is not that the code of the functions is quite more verbose as compared to their Haskell code, but that they are directly usable by anyone and help solve many tasks much easier than it was possible before.

The widespread use of such function libraries of higher order functions is the factor that will definitely indicate whether XSLT is a functional programming language or not -- not just the opinion of even the best Haskell specialist.

Ehud Lamm - Re: Functional programming in XSLT  blueArrow
2/7/2002; 10:23:48 AM (reads: 1637, responses: 0)
Tell us more about FXSL

Frank Atanassow - Re: Functional programming in XSLT  blueArrow
2/7/2002; 12:04:06 PM (reads: 1544, responses: 0)
I'm not providing the code [for curry], because of your comments that it's tiresome to read. In case you're interested to have a look at the code, I'd be happy to send it to you.

Sorry if I was too abrasive. XSL's verbosity is not your fault, and the result is of independent interest anyway. I will wait for the snippet you mentioned to examine it.

What is important is not that the code of the functions is quite more verbose as compared to their Haskell code, but that they are directly usable by anyone and help solve many tasks much easier than it was possible before.

That depends on how much notational overhead is involved in making a call to one of these functions, especially when the user has to pass a HOF to one of them. If the overhead is low, then the curry function will help a great deal.

Dimitre Novatchev - Re: Functional programming in XSLT  blueArrow
2/7/2002; 12:29:53 PM (reads: 1547, responses: 1)
Tell us more about FXSL

What can I tell more about FXSL? This library was announced just a few days ago in the article and initially (in November 2001 when the article was written) contained the following 35 functions:

foldl

foldr

sum

product

sometrue

alltrue

minimum

maximum

append

map

doubleall

sumproducts

foldl-tree

sumTree

productTree

tree-labels-list

mapTree

buildListWhile

buildListUntil

take

takeWhile

drop

dropWhile

splitAt

span

partition

within

sqrt

buildListWhileMap

easyDiffList

elimError

improve

improvedDiff

partialSumsList

improvedIntegration

 

Now it contains the following additional functions. A "str" prefix starting a function name indicates that this is the function's implementation for strings (in XSLT strings are not treated as lists of characters, therefore strings require separate functions). A "dvc" prefix indicates that this is a "divide and conquer" implementation of the corresponding function. Some functions target difficult to solve in XSLT 1 text-processing problems (str-reverse, strSplit-To-Lines, strSplit-To-Words, transformAndSum, trim), or problems that are not solved efficiently in the proposed WD of XPath 2.0, like producing a running total of sales (scanl, scanl1), or just illustrating how to create and return a new function on the fly (store implements an updatable store for variables of a calculator -- a la example from Simon Thompson's book):

alltrueP
compose
compose-flist
str-foldl
dvc-foldl
dvc-str-foldl
getWord
makeDistinct
reverse
scanl
scanl1
someTrueP
split-to-lines
store
str-buildListUntil
str-dropWhile
str-dvc-map
str-foldl
str-map
str-reverse
strSplit-To-Lines
strSplit-To-Words
str-takeWhile
transformAndSum
trim
withinRelative
zipWith
curry

The FXSL library will constantly be extended with new useful functions and successive releases of FXSL will be available from the TopXML.com downloads site.

The use of some of these functions has been demonstrated in the past few months in the xsl-list forum and there has been a considerable interest and willingness to use a functional style of programming. At present there is a well-expressed demand that the next version of XPath (2.0) should have a native support for higher-order functions. The decision for this is in the hands of the XPath 2.0 WG, but regardless of whether or not they give the green light, functional libraries like FXSL have future, because they help people solve easily (otherwise difficult) problems, and also because the functional programming style results in a more compact, elegant, understandable and maintainable code.

Frank Atanassow - Re: Functional programming in XSLT  blueArrow
2/7/2002; 12:44:42 PM (reads: 1619, responses: 0)
It seems like XSL is becoming more and more like DSSSL, only with a more politically correct syntax.

Frank Atanassow - DSSSL  blueArrow
2/7/2002; 12:52:24 PM (reads: 1545, responses: 0)
It seems like XSL is becoming more and more like DSSSL, only with a more politically correct syntax.

I guess I should explain this remark.

DSSSL is to SGML as XSL is to XML, except that DSSSL is based on a side effect-free (nearly) sublanguage of Scheme. Of course it has HOFs, etc.

I used to work at a company which produced an implementation of DSSSL, and wrote DSSSL scripts for my living, which is part of the reason I try to avoid SGML and XML as much as possible now. :)

Benjamin Rosenbaum - Re: Functional programming in XSLT  blueArrow
1/16/2004; 9:03:14 AM (reads: 152, responses: 0)
The FXSL library seems really cool as a proof-of-concept and possibly as a working tool.

The syntax, though, seems prohibitively complex to use directly.

What would be cool is some kind of preprocessor that would parse simplified extra tags in XSL files and generate postprocessed XSL files using the FXSL library.

And what would be REALLY cool (while I'm dreaming) is a preprocessor for XSL files that would allow you to use (a subset of?) Haskell expressions, suitably delimited, in place of or in combination with XPath -- supported by the FXSL library as a back-end!

Actually, I think the committe that determines the XSLT standards is more likely to incorporate these features if someone writes a preprocessor and it actually starts getting used in production systems, than if it's a request purely on the grounds of language esthetics and expressive power. (And there is, after all, a long history of language features starting out as preprocessors and later being incorporated into the official language itself -- C macros, and C++ itself, come to mind).