In Part II of this post a solution was given to the problem presented in Part I:

"Can we implement an algorithm for repetitive prepends that will be run by P1 in linear time, in addition to its excellent linear performance of repetitive appends?"

The solution is implemented within the function my:prepend-iter() that is defined in the following way:

The first argument passed to this function, pNumTimes, is the number of times to perform the prepend operation on the initial sequence pstartSeq, which is passed as the second argument.

The third argument has an auxiliary purpose. As its name, pInserts suggests, it contains the accumulation of all sequences that are to be prepended to pstartSeq.

The idea is to produce the final result only when pNumTimes  is zero, using at this time the accumulated prepends in pInserts and the initial sequence pstartSeq.

The idea of the algorithm is to replace the repetitive prepend operations with repetitive append operations, which are carried out by the xslt processor with linear complexity.

We notice that:

y2s ++ y1s ++ xs   =

reverse(  reverse(y1s) ++ reverse(y2s) ) ++ xs       (1)

Or in general, if we have N sequences:

y1s, y2s, ..., yNs 

to be prepended to an initial sequence xs in that order,

yNs ++ yN-1s ++ ... y2s ++ y1s ++ xs =

reverse(reverse(y1s)++reverse(y2s) ++ ...

        ...    ++ reverse(yNs) )     ++xs                 (2)

Remarkably, the argument of the outermost reverse() is a repetitive appends operation and it has only linear complexity with P1!

We have added N+1 reverse() operations, but each of them is of linear complexity, so the total complexity of implementing (2) is O(N).

Certainly, the function my:prepend-iter() we have demonstrated is a simplified case of the many different real world scenarios we may encounter that will require repetitive prepends. Nevertheless its use is sufficient to prove and demonstrate how such an O(N) algorithm can be constructed.

We could use essentially the same algorithm, with a modification that accepts as argument a function
next-prepend(), which produces the next sequence to be prepended. To signal the end of the repetitive prepend operation, we can use a convention that next-prepend() will indicate this by producing some special sequence, such as the empty sequence.

In case you may be wondering how can a function be passed as an argument to another function in XSLT, do read about FXSL.

Update: Minor code cleanup (using better names now).

In my previous post I defined the problem of improving the quadratical performance of an XSLT processor P1 when performing repetitive prepends to a sequence, while having an excellent linear repetitive appends performance.

The question asked was:

"Can we implement an algorithm for repetitive prepends that will be run by P1 in linear time, in addition to its excellent linear performance of repetitive appends?"

This transformation produces the result of repetitive prepends:

When run with the P1 XSLT processor, the results are:

So, we see that the repetitive prepends have been carried out with linear complexity! We achive a speedup that can reach thousands and even hundred of thousands times!

When carried out with P2, the time complexity remains quadratical, however the actual results are two times faster than with the non-optimized algorithm.

I will explain the algorithm implemented in the above transformation, in Part III of this post.

The book "Real World Haskell" has been nominated a JOLT Finalist.

I have been reading this book

in online form for the past month and got the hardcopy a few days ago. Two thirds through, I can confidently say that this is the best Haskell book I have read.

From the Jolt Awards Site:

"How are the winners selected?
Our judges not only examine the standard criteria of audience suitability, productivity, innovation, quality, ROI, risk and flexibility, but also seek to honor products that are ahead of the curve. Jolt-winning products are universally useful; are simple, yet rich in functionality; redefine their product space; and/or solve a nagging problem that has consistently eluded other products and books."

Update: Minor correction in the last two rows of the table -- thanks to a comment by Michael Ludwig. I will talk about the efficiency of this and other related XPath expressions in my next post.

In my first post I provided a compact one-liner XPath expression that obtains all duplicate items in a given sequence.

Since then a number of people have contacted me, asking for an explanation what this expression means and how it is really evaluated by a compliant XPath 2.0 engine.

C. M. Sperberg-McQueen, a MIT professor and member of W3C, blogged about it:

"Dimitre’s solution is beautiful and concise: 21 characters long (longer if you use variables with names longer than singler characters), and well worth the five or ten minutes it took me to work out why it works. I won’t explain it to you, dear reader; you deserve the brief puzzlement and Aha-moment of understanding it."

"Dimitre gets my vote for this month’s best programming-language application of Strunk and White’s rule: “Omit needless words!” "

I have always admired any of Michael's works and his high recognition is the best reward I would not have dared dreaming of.

Now that enough time has passed for anyone to try and understand how the solution works, let me explain it myself.

From the very start working on this problem I decided that a good solution must use the available standard functions on sequences.

While distinct-values() was mentioned by the OP, it is not directly useful here, as we are looking for any item that occurs more than once in the sequence.

We can eventually think of using exists() or empty(), however the one function that is most relevant to the task is index-of(). As explained in the F & O Spec.,

15.1.3 fn:index-of

Summary: Returns a sequence of positive integers giving the positions within the sequence $seqParam of items that are equal to $srchParam.

The first step in the solution is to ask the question:

How are duplicate items different from unique items (in terms of index-of() ) ?

The answer comes naturally:

For any unique item vUi, the sequence that

  index-of($vSeq, $vUi)

produces, is just of length of one.

For any duplicate item vDup, the sequence that

    index-of($vSeq, $vDup)

produces, is of length of two or more.

In other words,

    index-of($vSeq, $vDup)

always has a second item, while

  index-of($vSeq, $vUi)

never has a second item.

To express this in XPath 2.0, the expression:

index-of($vSeq, $vItem)[2]

produces the empty sequence for any unique item $vItem, and it produces an  xs:integer  index for any $vItem that occurs two or more times in the sequence.

Then one way to find all duplicate items in the sequence is to evaluate:

$vSeq[exists(index-of($vSeq, .)[2])]

In XPath 2.0 the expression in the [] brackets that follow a sequence is called a FilteringExpression. It is evaluated for every item of the sequence and only items that satisfy this predicate are produced.

Let $vSeq is defined as:

   1, 2, 2, 3, 4, 5, 5, 6, 7

Then

$vSeq[exists(index-of($vSeq, .)[2])]

produces:

  2, 2, 5, 5

This is quite close to the result we need, we just need to dedup it:

distinct-values
       ($vSeq[exists(index-of($vSeq, .)[2])])

produces the wanted result:

  2, 5

This is fine, but the last expression seems already too long. Can we do even better?

What about this one:

$vSeq[index-of($vSeq,.)[2]]

It produces :

  2, 5

exactly the wanted result and it is really tight.

The only problem is to explain how this expression "works" :)

Let me admit that on the morning after discovering this solution I found I had completely forgotten the rational behind it. After failing again and again to explain it, I finally asked the Gods for help.

Here is the explanation provided by Dr. Michael Kay:

"This expression

  $vSeq[index-of($vSeq,.)[2]]

means

   $vSeq [position() = index-of($vSeq,.)[2]]

Let's evaluate the predicate for each item in $vseq:

So the only items that match the predicate are those in positions 3 and 7, with values (2, 5)."

To summarize, the critical step in understanding how this works is to remember that if the type of the FilteringExpression is xs:integer, then

$someSequence[someFilteringExpression]

is simply an abbreviation for:

$someSequence[position() = someFilteringExpression]

Therefore,

  $vSeq[index-of($vSeq,.)[2]]

means :

All items from $vSeq such that their position is equal to the value of the index of their second occurence in the sequence.

As there is at most one item at any given position, this is how we get just one "2" and one  "5" in

2, 5

as contrasted to two of each in

2, 2, 5, 5

Concluding, here is one final note:

If you have ever used the Muenchian method of grouping, you may have spotted its resemblance to the current solution.

A typical expression used in Muenchian grouping is something like this:

<xsl:key match="person" name="kPersByName" use="@name"/>

<xsl:for-each select=
"*/person
     [generate-id()
     =
      generate-id(key('kPersByName', @name)[1])
      ]">

<!-- Do something -->

</xsl:for-each>

In the above, the role of the filtering expression is played by:

      generate-id()
     =
      generate-id(key('kPersByName', @name)[1])

and this is the same as the role played by:

  index-of($vSeq,.)[2]

in finding the duplicate items.

The Muenchian method uses an index of "1" in:

  key('kPersByName', @name)[1]

and in our solution:

   index-of($vSeq,.)[2]

a similar role is played by the index "2".

"1" in the Muenchian method means: Take one node from each group of nodes with unique keys. Because any group can consist just of only one node, it is only safe here to take the first node from any group.

In the case of finding all duplicate items in a sequence, we want to pick one index from the list of indexes of any duplicate item. Having a first index does not qualify an item as duplicate -- it needs to have at least a second index in the sequence. On the other side there may be duplicate items that occur only twice (not thrice or more times) and they will not have a third index.

Therefore, the only safe way to take an existing index for any duplicate item is to take its second index.

If you have successfully read up to here, you would have little difficulty solving the following problems, provided as exercises:

Let $vSeq be (1,  2,2,   3,3,3,    4,4,4,4,   5,5,   6,   7)

P1. Produce all items in $vSeq that occur only once in it.

P2. Produce all items in $vSeq that occur exactly two times in it.

P3. Produce all items in $vSeq that occur exactly three times in it (triples).

P4. Produce all items in $vSeq that occur exactly four times in it (quadruples).

P5. Produce all items in $vSeq that occur more than once but less than four times.

Hint: You may consider using the last() function in your solution.

Someone recently asked the following question:

"I have an XPath expression which provides me a sequence of values like the one below:

1 2 2 3 4 5 5 6 7

It is easy to convert this to a set of unique values "1 2 3 4 5 6 7" using the distinct-values function. However, what I want to extract is the list of duplicate values = "2 5". I can't think of an easy way to do this.
Can anyone help?"

One of the best XPath/XSLT experts, whom I greatly respect, provided the following answer:

"What about:

distinct-values(
  for $item in $seq
  return if (count($seq[. eq $item]) > 1)
         then $item
         else ())

This iterates through the items in the sequence, and returns the item if the number of items in the sequence that are equal to that item is greater than one. You then have to use distinct-values() to remove the duplicates from that list."

Can you do better?

My own solution is a 21 chars one-liner, and would only be slightly longer, if efficiency would need to be addressed.

Michael Crichton died unexpectedly at an age of 66.

As with Asimov, will miss the continuation of his writing, which I had taken for granted.

Is this really the end of an epoch?

In Part 1 of these series I described an implementation of the Finger Tree data structure in C#.

Part 2 reported the results of performance tests with the standard .NET Enumerable class and the finger-tree-based sequence

The new data provided here is the results of similar performance tests, this time between the finger-tree-based sequence and XPath 2.0 fuctions on sequences as implemented by a group of three XSLT 2.0 processors.

I apologize for not specifying the names of the XSLT 2.0 processors used in this experiment. This was done intentionally, since the purpose of the experiment was only to compare the current efficiency of the XPath sequences and strings as implemented by these XSLT processors to the efficiency of a Finger Tree - based implementation. This experiment did not have the goal of comparing the XSLT processors with each other. The results were consistent with and did not alter my prior perception of each XSLT processor's efficiency.

Also, the usual warning:

Disclaimer: This comparison was carried out on my 4-year old PC, having CPU speed of 3GHz and RAM of 2GB and running Windows XP.  Results will largely vary on other configurations, depending on CPU and memory speed, available memory, cache size, ..., etc. Another factor to consider is the time necessary for jitting the .NET IL code on initial method execution or the JVM startup time. However the observed ratios (speedup) should remain closely the same.

The following XPath 2.0 functions on sequences were tested:

fn:insert-before()

op:concatenate()

fn:remove()

fn:subsequence()

op:item-access()  (the position() function with integer argument)

fn:reverse()

The following XPath 2.0 functions on strings were tested:

fn:string-length()

fn:concat()     (with 2 arguments)

fn:substring()

The finger-tree-based sequence was implemented in such a way that an instance of it was instantiated as an extension object of the Saxon 9.1 (for .NET) XSLT processor and then the methods were referenced as extension functions.

Any of these extension functions was executed 100 000 times and the average time was recorded. Unfortunately, two of the three tested XSLT processors were very slow, which necessitated that during the tests of these XSLT processors many functions had to be executed 10 000 times or even only 1000 or, in a very few, exceptional circumstances, only 100 times.

Writing such code can be tricky, especially due to the very aggressive optimization performed by one of the tested XSLT processors.  Thus, in order to obscure from such a clever XSLT processor the fact that a variable had been defined outside of an <xsl:for-each> instruction, something like the following code had to be used:

Note how the last instruction within the <xsl:for-each> above causes a lazy-evaluating XSLT processor to finish its work and produce the complete sequence.

The sequences (and character strings) on which the above functions were performed had length of 10 000.

The code for these tests is here.

As in the .NET comparison test (reported in Part 2), there were two approaches:

• Testing "the worst or extreme case", when the argument to be inserted, concatenated, removed, used as index, ... was a value equal or very close to 10000.
• Testing "the average case": with many different values for this argument, uniformly increasing in the interval [1000, 10000].

As can be seen from these tables (my weblog host allows only limited length for an entry and could not accommodate them inline), which summarize the results of the "uniform" or "average" testing of the sequence implementations, using a Finger Tree as a general sequence data structure in XPath 2.0 may speed up sequence operations (roughly) 5 to 40 times even when only the best of the three XSLT processors' results are compared, 5 to 4500 times if all results are taken into account.

The XPath string implementation of the three XSLT 2.0 processors was tested against a finger-tree based string object and the results from the "average" tests are summarized in these tables.

As can be seen, using a Finger Tree to represent a string in XPath 2.0 may speed up string operations (roughly) 3 to 9 times even when only the best of the three XSLT processors' results are compared, 3 to 40 times if all results are taken into account.

I will conclude the series on finger trees with the following, quite

Obvious Conclusion:
Existing sequence and string implementations in .NET and in XSLT 2.0 processors can be speeded up significantly by using the Finger Tree data structure. Additionally, .NET will benefit from having a truly immutable sequence implementation.

Certainly, the question is not "if" such implementations will be produced, but only "when".

Actually, it is not a knife and is known under the name of Finger Tree. 

Background:
Created by Ralf Hinze and Ross Paterson in 2004, and based to a large extent on the work of Chris Okasaki on Implicit Recursive Slowdown and Catenable Double-Ended Queus, this data structure, to quote the abstract of the paper introducing Finger Trees, is:

"a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece. Representations achieving these bounds have appeared previously, but 2-3 finger trees are much simpler, as are the operations on them. Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more."

Why the finger tree deserves to be called the Swiss knife of data structures can best be explained by again quoting the introduction of the paper:

"The operations one might expect from a sequence abstraction include adding and removing elements at both ends (the deque operations), concatenation, insertion and deletion at arbitrary points, finding an element satisfying some criterion, and splitting the sequence into subsequences based on some property. Many efficient functional implementations of subsets of these operations are known, but supporting more operations efficiently is difficult. The best known general implementations are very complex, and little used.
This paper introduces functional 2-3 finger trees, a general implementation that performs well, but is much simpler than previous implementations with similar bounds. The data structure and its many variations are simple enough that we are able to give a concise yet complete executable description using the functional programming language Haskell (Peyton Jones, 2003). The paper should be accessible to anyone with a basic knowledge of Haskell and its widely used extension to multiple-parameter type classes (Peyton Jones et al., 1997). Although the structure makes essential use of laziness, it is also suitable for strict languages that provide a lazy evaluation primitive."

Efficiency and universality are the two most attractive features of finger trees. Not less important is simplicity, as it allows easy understanding, straightforward implementation and uneventful maintenance.

Stacks support efficient access to the first item of a sequence only, queues and deques support efficient access to both ends, but not to an randomly-accessed item. Arrays allow extremely efficient O(1) access to any of their items, but are poor at inserting, removal, splitting and concatenation. Lists are poor (O(N)) at locating a randomly indexed item.

Remarkably, the finger tree is efficient with all these operations. One can use this single data structure for all these types of operations as opposed to having to use several types of data structures, each most efficient with only some operations.

Note also the words functional and persistent, which mean that the finger tree is an immutable data structure.

In .NET the IList<T> interface specifies a number of void methods, which change the list in-place (so the instance object is mutable). To implement an immutable operation one needs first to make a copy of the original structure (List<T>, LinkedList<T>, ..., etc). An achievement of .NET 3.5 and LINQ is that the set of new extension methods (of the Enumerable class) implement immutable operations.

In the year 2008, Finger Tree implementations have been known only in a few programming languages: in Haskell, in OCaml, and in Scala. At least this is what the popular search engines say.

What about a C# implementation? In February Eric Lippert had a post in his blog about finger trees. The C# code he provided does not implement all operations of a Finger Tree and probably this is the reason why this post is referred to by the Wikipedia only as "Example of 2-3 trees in C#", but not as an implementation of the Finger Tree data structure. Actually, he did have a complete implementation at that time (see the Update at the start of this post), but desided not to publish it.

My modest contribution is what I believe to be the first published complete C# implementation of the Finger Tree data structure as originally defined in the paper by Hinze and Paterson (only a few exercises have not been implemented).

Programming a Finger Tree in C# was as much fun as challenge. The finger tree structure is defined in an extremely generic way. At first I even was concerned that C# might not be sufficiently expressive to implement such rich genericity. It turned out that C# lived up to the challenge perfectly. Here is a small example of how the code uses multiple types and nested type constraints:

// Types:

//     U -- the type of Containers that can be split

//     T -- the type of elements in a container of type U

//     V -- the type of the Measure-value when an element is measured

public class Split<U, T, V>
    where U : ISplittable<T, V>
        where T : IMeasured<V>

Another challenge was to implement lazy evaluation (the .NET term for this is "deferred execution") for some of the methods. Again, C# was up to the challenge with its IEnumerable interface and the ease and finesse of using the "yield return" statement.

The net result: it was possible to write code like this:

public override IEnumerable<T> ToSequence()
{
     ViewL<T, M> lView = LeftView();
     yield return lView.head;

     foreach (T t in lView.ftTail.ToSequence())
          yield return t;
}

Another challenge, of course, was that one definitely needs to understand Hinze's and Ross' article before even trying to start the design of an implementation. While the text should be straightforward to anyone with some Haskell and functional programming experience, it requires a bit of concentration and some very basic understanding of fundamental algebraic concepts.  In the text of the article one will find a precise and simple definition of a Monoid. My first thought was that such academic knowledge would not really be necessary for a real-world programming task. Little did I know... It turned out that the Monoid plays a central role in the generic specification of objects that have a Measure.

I was thrilled to code my own version of a monoid in C#:

public class Monoid<T>

{

  T theZero;

  
  public delegate T monOp(T t1, T t2);

  public monOp theOp;

  public Monoid(T tZero, monOp aMonOp)

  {

    theZero = tZero;

    theOp = aMonOp;

  }

  public T zero

  {

    get

    {

      return theZero;

    }

  }

}

Without going into too-much details, here is how the correct Monoids are defined in suitable auxiliary classes to be used in defining a Random-Access Sequence, Priority Queue and Ordered Sequence:

public static class Size

{

    public static Monoid<uint> theMonoid =

         new Monoid<uint>(0, new Monoid<uint>.monOp(anAddOp));

    public static uint anAddOp(uint s1, uint s2)

    {

        return s1 + s2;

    }

}

public static class Prio

{

    public static Monoid<double> theMonoid =

         new Monoid<double>

            (double.NegativeInfinity,

             new Monoid<double>.monOp(aMaxOp)

             );

    public static double aMaxOp(double d1, double d2)

    {

        return (d1 > d2) ? d1 : d2;

    }

}

public class Key<T, V> where V : IComparable

{

    public delegate V getKey(T t);

    // maybe we shouldn't care for NoKey, as this is too theoretic

    public V NoKey;

    public getKey KeyAssign;

    public Key(V noKey, getKey KeyAssign)

    {

        this.KeyAssign = KeyAssign;

    }

}

public class KeyMonoid<T, V> where V : IComparable

{

    public Key<T, V> KeyObj;

    public Monoid<V> theMonoid;

    public V aNextKeyOp(V v1, V v2)

    {

        return (v2.CompareTo(KeyObj.NoKey) == 0) ? v1 : v2;

    }

    //constructor

    public KeyMonoid(Key<T, V> KeyObj)

    {

        this.KeyObj = KeyObj;

        this.theMonoid =

         new Monoid<V>(KeyObj.NoKey,

                       new Monoid<V>.monOp(aNextKeyOp)

                      );

    }

}

Yet another challenge was to be able to create methods dynamically, as currying was essentially used in the specification of finger trees with measures. Once again it was great to make use of the existing .NET 3.5 infrastructure. Below is my simple FP static class, which essentially uses the .NET 3.5 Func object and a lambda expression in order to implement currying:

public static class FP

{

  public static Func<Y, Z> Curry<X, Y, Z>
            (this Func<X, Y, Z> func, X x)

  {

    return (y) => func(x, y);

  }

}

And here is a typical usage of the currying implemented above:

public T ElemAt(uint ind)

{
  return treeRep.Split

(new MPredicate<uint>

   (

      FP.Curry<uint, uint, bool>(theLessThanIMethod2, ind)

   ),

     0

      ).splitItem.Element;

}

Now, for everyone who have reached this point of my post, here is the link to the complete implementation.

Be reminded once again that .NET 3.5 is needed for a successful build.

In my next posts I will analyze the performance of this Finger Tree implementation and how it fares compared to existing implementations of sequential data structures as provided by different programming languages and environments.

Long time Microsoft MVP Oleg Tkachenko has joined Microsoft's Visual Studio team.

Oleg is well-known for his work on a number of popular XML/XSLT - related open source projects, such as EXSLT.NET, MVP.XML, nXslt.exe, the Iron XSLT project type of Visual Studio 2008,  ... , etc.

Oleg is also a member of the FXSL open source project.

I am glad for Oleg and want to congratulate him on his new role.

The Balisage conference program is available and a quick  look  shows there are some very interesting presentations.

A few days ago Amazon Upgrade was announced, which lets you access (some of) the books you bought from them -- for a reasonable fee.

Here's how the announcement looks like:

Now, if only this book could also be made accessible:

In her recent post "RELAX NG for matching" Jeni Tennison said:

The “grouper” is the most interesting and difficult of these. It needs to act like a tokeniser, except use regular expressions over markup rather than over text. For example, say I had:

<number>06</number><punc>/</punc><number>03</number><punc>/</punc><number>08</number>

I want to be able to create a rule that says “any sequence that looks like a number element that contains a
two-digit number between 1 and 31, followed by a punc element that contains a slash, followed by another two-digit number between 1 and 12, followed by a punc element that contains a slash, followed by another two-digit number should be wrapped in a date element”.

Now this is something that XPath is really bad at. Try writing an expression that selects, from a sequence of elements that may contain other <number> and <punc> elements as well as other elements, only those sequences of elements that match the pattern I just described. It’s something like:

number[. >= 1 and . <= 31 and string-length(.) = 2]
      [following-sibling::*[1]/self::punc = '/']
      [following-sibling::*[2]/self::number[. >= 1 and . <= 12 and string-length(.) = 2]]
      [following-sibling::*[3]/self::punc = '/']
      [following-sibling::*[4]/self::number[string-length(.) = 2]]
  /(self::number, following-sibling::*[position() <= 4])

which is fiddly and messy and only works in this particular example because I know precisely how many elements there are
supposed to be in the group.

Then she proceeds by making the suggestion that

    "As a language, RELAX NG is really good at this"

Jeni ends with the following statement:

"So I think a “grouper” component should use RELAX NG to identify sequences to be marked up. But I have no idea if there are RELAX NG libraries out there that can be used in this way: to identify and extract matching sequences rather than to validate entire documents"

It is obvious that the solution of this problem is not strictly bound to RELAX NG itself
(which just happens to be able to parse a schema defined using the RNC grammar). The tool Jeni reasons about would be any compiler writing system that allows additional grammar rules, that are not required to reach the start symbol of the language, but may be useful for other purposes.

Very fortunately, I know at least one such system:

         the Labelled BNF Grammar Formalism (LBNF).

 Jeni's "grouper" tool can be implemented by adding additional rules to the language being specified
using LBNF's "internal pragmas". 

Here's how the authors of LBNF Markus Forsberg, Aarne Ranta from Chalmers University of Technology
and the University of Gothenburg describe LBNF's internal pragmas:  

6 LBNF Pragmas

6.1 Internal pragmas

Sometimes we want to include in the abstract syntax structures that are not part of the concrete syntax, and hence not parsable. They can be, for instance, syntax trees that are produced by a type-annotating type checker. Even though they are not parsable, we may want to pretty-print them, for instance, in the type checker’s error messages. To define such an internal constructor, we use a pragma 

    "internal" Rule ";"

where Rule is a normal LBNF rule. For instance,

   internal EVarT. Exp ::= "(" Ident ":" Type ")";

introduces a type-annotated variant of a variable expression.

Of course, LBNF is a very nice and cool tool to carry out a number of really important language development tasks, besides the "grouper".

With his twelve posts under the common title of "The Wide Finder Project" Tim Bray formulated a problem, which obviously has since then stirred some people, anxious to prove that their programming language of choice fares well in implementing solutions for this class of problems.

While I am not aware of any XSLT implementation that provides explicit or implicit support for parallel processing (with the obvious goal to take advantage of the multi-core processors that have almost reached a "prevalent" status today), I was curious to determine at least two things:

• How well a good XSLT 2.0 processor and a straightforward solution fare against other languages/solutions?
• Where is the XSLT code on the scale of "beautiful code"?

Before going further let me remind that there is a popular (and as we'll see unfounded!) belief that any XSLT solution must be hugely inefficient and that any XSLT code can only be ugly. In fact, the following comment to one of Tim's posts reflects exactly this mindset:

My initial XSLT solution to Tim's problem is below. No optimization attempts have been attempted, not only because I don't have an XSLT processor that utilizes multi-core processor, but also because it seems there's only a limited possibility for optimization (adding more CPU's is not likely to speed up the reading of a huge file from a single drive).

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xsl:output method="text"/>

  <xsl:variable name="vLines" as="xs:string*" select=
   "tokenize(unparsed-text('file:///C:/Log1000000.txt'),'\n')"/>

  <xsl:variable name="vRegEx" as="xs:string" select=
"'^.*?GET /ongoing/When/[0-9]{3}x/([0-9]{4}/[0-9]{2}/[0-9]{2}/[^ .]+) .*$|^.+$'"/>

  <xsl:template match="/">
    <xsl:for-each-group group-by="." select=
    "for $line in $vLines
         return replace($line,$vRegEx,'$1')[.]">
      <xsl:sort select="count(current-group())" order="descending" />

      <xsl:if test="not(position() > 10)">
       <xsl:value-of select=
          "concat(count(current-group()),':',current-grouping-key(),'&#xA;')"/>
      </xsl:if>
    </xsl:for-each-group>
  </xsl:template>
</xsl:stylesheet>

This 22-line-transformation is performed by Saxon 9.0 on a 3GHz DELL desktop. The file Log1000000.txt was constructed using the 10000 lines file provided by Tim and copying it into another file 100 times. The size of this file is about 200MB.

The results were produced in 36.175 seconds using about 929MB of RAM. Saxon should be timed using the -repeat:3 command-line option, which performs the transformation three times. Using only the results from the first/single transformation will be misleading, as they include the time for the Java VM startup.

Discussion

To answer the questions:

1. How well a good XSLT 2.0 processor and a straightforward solution fare against other languages/solutions?

The non-optimized, uniprocessor version of this solution has a time of 36 seconds for processing about 200MB log file. It is likely the timing for the full , five times bigger log file used by Tim Bray, will be about 5 times bigger: 180 sec, or about 3 minutes. 3 minutes for processing 1GB of data is not a bad time for an XSLT transformation, considering that sizes even of a few hundreds of megs are still considered monstrous.

XSLT could be in fact one of the winners in the WF competition, had its creators stepped just a little bit further exploiting the natural, non-sequential XSLT processing model. Here I am talking about specifying a single f:parMap() function, which can be defined exactly as the current FXSL f:map() function:

   <xsl:function name="f:map" as="item()*">
      <xsl:param name="pFun" as="element()"/>
      <xsl:param name="pList1" as="item()*"/>

      <xsl:sequence select=
       "for $this in $pList1 return
          f:apply($pFun, $this)"
      />
    </xsl:function>

The only difference is that f:parMap() adds to the semantics of f:map() the hint to use as many available CPU processors as appropriate when evaluating the "for" expression in the code of the function.

Yes, this can be done for any "/" operator or for any "for" expression such as the one used in lines 13 - 14 in our XSLT solution:

"for $line in $vLines
     return replace($line,$vRegEx,'$1')[.]"

and for any <xsl:apply-templates .../> instruction, and for any <xsl:for-each .../> instruction, and for any <xsl:for-each-group ...> instruction and ... and ... and ...

Judging from the published results, this straightforward, non-optimized uniprocessor XSLT solution comes not too-far behind some of the optimized for multi-processing solutions. I hope that in the not so distant future there will be XSLT processors exploiting the inherent non-sequential nature of XSLT processing to implement highly-optimized multi-processing solutions.

2. Where is the XSLT code on the scale of "beautiful code"?

By its compactness (22 lines) it is in 3rd place and rivals the 2nd place (17 lines), as we could easily remove 4 lines (3 of them blank) used to add readability. One of Tim's criteria for "beautiful code" is avoiding awkwardness.He speaks about Ruby not needing ending semicolons or variable type declarations. However, Tim's solution still had to use two lines for defining a hash and setting its default to 0. By contrast, the XSLT solution above does not require the programmer to introduce and initialize a special data structure -- the support for grouping is right there in the core of the language. There is simply no way the programmer can do something wrong in declaring or using a hash table.

What could the XSLT processor do better?

Both the timing and especially the amount of RAM used indicate how the XSLT processor did its work:

Imagine that the XSLT Processor is really lazy:

• It will not read any contents of the file and will not do any tokenization, until absolutely necessary.
• Whenever it is really necessary to use the next token (line), only the text necessary to determine that line shall be read.
• Whenever a token/line is produced, all previously used / unused text shall be marked-for-garbage-collection/discarded/reused.
• Whenever a string from $vLines is consumed and processed by the <xsl:for-each-group .../> instruction, this string is no-longer used and shall be marked-for-garbage-collection/discarded/reused.

Using these rules a truly lazy XSLT processor will only need space large enough for the longest line, and for a hash table to keep the keys and counters for all different articles being grouped. In this case there are just 562 unique values extracted from the strings of $vLines.

In this way, the processing -- reading a line, finding the article it contains and feeding this to the hash table --  could be accomplished in streaming mode while reading the text file. Upon reaching the end of the file, there would be very little left to do, and thus almost nothing to be further optimized.

Conclusion

I truly believe that the described improvements can be implemented by at least some of the best XSLT 2.0 processors around here. For many years I have been using Saxon and am very grateful to its developer Dr. Michael Kay. The performance efficiency has been constantly growing -- a very good example to follow by all other XSLT vendors and if they do there will be competition, and competition is good for us all.

In a recent post to the xml-dev mailing list, "XSLT question on transitive closures", Rick Jelliffe wrote:

"Am I right in thinking that

 1) XPath2 functions don't have have a function for transitive closure (along provided xpaths)

2) SAXON 8 does not have the saxon:closure() extension function that older versions of SAXON had

3) The one to use is probably still Christian Nentwich's code from circa 2001 as adopted into EXSLT ?"

Michael Kay replied:

"I think it would be nice to do it properly based on FXSL higher-order functions, which are much more cleanly specified. Perhaps there is already a suitable function in FXSL.

The other thing that's needed is the ability to check for cycles. Simply blowing the stack or looping isn't good enough."

David Carlisle replied by providing a solution that would dynamically generate a new XSLT stylesheet and a closure function in it that uses only a specific function and implements its closure. He also said:

"> I think it would be nice to do it properly based on FXSL higher-order

True (but I'll leave that for Dimitre  :-)"

Thanks to these nice people I felt just like... something had been left for me  :o)

So, now we have in FXSL the function

   f:closure()

which, given a function pFun and a starting set of items pstartSet, produces the transitive closure of pFun.

While the complete 47 lines of code can be viewed using the above link, the essence of the implementation is in the following 20 lines:

 <xsl:function name="f:closure" as="node()*">
    <xsl:param name="pFun" as="element()"/>
    <xsl:param name="pstartSet" as="node()*"/>
    
    <xsl:sequence select="f:closure2($pFun, $pstartSet,$pstartSet)"/>
  </xsl:function>
  
  <xsl:function name="f:closure2" as="node()*">
    <xsl:param name="pFun" as="element()"/>
    <xsl:param name="pCurClosure" as="node()*"/>
    <xsl:param name="pstartSet" as="node()*"/>
    
    <xsl:if test="exists($pstartSet)">
      <xsl:variable name="vNew" select=
          "f:map($pFun,$pstartSet) except $pCurClosure"/>
      <xsl:sequence select=
           "$pstartSet 
           | $vNew 
           | f:closure2($pFun,$pCurClosure | $vNew, $vNew)"/>
    </xsl:if>
  </xsl:function>

And here is my reply to David's post (code hyperlinked, full code omitted):

"
>> I think it would be nice to do it properly based on FXSL higher-order

> > True (but I'll leave that for Dimitre:-)

I am sorry I only read this a few days ago. Below is the code of the FXSL function. While the code is straightforward, the following must be noted:

1. The "set" at present is only a set of nodes. I will probably produce a more general f:closure() function, which operates on any set of items. Then this function should be also passed as parameters a "union" and a "difference" functions.

2. It seems that David's solution would go into an infinite loop for more involved examples (see the second test with reachability of nodes in cyclic graphs below). Therefore, the algorithm was slightly changed and works correctly. The following files can be downloaded from the CVS of the FXSL project:

func-closure.xsl.

testFunc-closure.xsl,

testFunc-closure2.xsl

The last transformation should be applied on the following xml file:
testFunc-closure2.xml

The result from running the second test transformation above (two cases of finding all nodes of a given graph, reachable from a specific node. In the second case there is a cycle involving the nodes V2, V6, V7) is:

 === Reachable from V1 =======

<node id="V1"/>
<node id="V3"/>
<node id="V4"/>
<node id="V5"/>
=======================

=== Reachable from V2 =======
<node id="V2"/>
<node id="V4"/>
<node id="V5"/>
<node id="V6"/>
<node id="V7"/>
=======================

Due to its generality, the f:closure() function is a useful addition to the FXSL library.

Cheers, Dimitre Novatchev
"

Using this title Kurt Cagle writes:

"I'd like to push a proposal to both the XML and AJAX communities, something that I think needs to be taken up by the W3C, the OpenAJAX alliance and JSON.org especially. Establish a set of conventions within JSON that most readily facilitate JSON being used in an XML context. These conventions should be syntactical, things that can be done with hash key naming conventions that can be picked up by a JSON/XML bridge to transform between the two formats."

Hmm...  here's what I have to say:

Kurt, this was quietly done some time ago. Just have a look at my blog ("Transforming JSON"). M.David. Peterson has a nice web-service based example, which in real time gets the XML out of the JSON produced by the Yahoo's Traffic Service.

This example just uses the JSON to XML convertor provided by FXSL -- that is the function f:json-document(), written in pure XSLT.

So, no conventions are necessary for transforming JSON to XML !

After so many nice experiences with XSLT text processing: dictionary lookup, spelling checking and suggesting candidate words, text justifying. text search and replacement, concordance over large corpora, even parsing LR-1 languages, I almost had decided that there was nothing much left to do in this area.

These days, while some people, who don't know what they are talking about are discussing in the XSL-List "Is XSLT dead?", it suddenly came to me that yes, there was something left: finding anagrams

It turns out that finding anagrams with XSLT is as easy and elegant as shown in the following code:

The Anagram Key of a word is specified as the following XPath expression:

  codepoints-to-string(f:qsort(string-to-codepoints(.)))

where string-to-codepoints()  and codepoints-to-string()  are standard XPath 2.0 functions and  f:qsort()  is a function from FXSL.

In the code above the English dictionary is indexed using as key (yes!) the Anagram Key for each word. Then we get all words that have the same Anagram Key as the word "trace". The result is:  

<

While it is nice to be able to implement such functionality just with a few lines of code, it is not wise to index the huge English dictionary each time we need to get some anagrams. In fact this indexing operation takes a lot of time -- in the example above it took about 280 seconds.

The next logical step is to persist the indexed document into an Anagram Dictionary and reuse it from here on. Here is the XSLT transformation, which creates the Anagram Dictionary:

This creates an xml document with 2396 anagram sets (chains) and below is the start of this document:

There longest chains consist of 8 anagrams. There are some pretty interesting ones, like:

<

<aChain key="acdeerrt"><w>cratered</w><w>retraced</w><w>terraced</w></aChain>
<aChain key="acdeert"><w>catered</w><w>created</w><w>reacted</w></aChain>
<aChain key="acdegln"><w>clanged</w><w>glanced</w></aChain>
<aChain key="acdehmr"><w>charmed</w><w>marched</w></aChain>
<aChain key="acdehs"><w>cashed</w><w>chased</w></aChain>
<aChain key="acdeilm"><w>claimed</w><w>decimal</w><w>medical</w></aChain>
<aChain key="acdeinotu"><w>auctioned</w><w>cautioned</w><w>education</w></aChain>

And obtaining all anagrams of "trace" now takes only 78 milliseconds.

All files shown and discussed here can be accessed at the CVS of FXSL.