Re: [xml-dev] Converting schema to schematron

[Michael Kay <mike@saxonica.com>]

> 
> 3) It is difficult to structure and handle so many steps in a pipeline with XSLT.  There were lots of parts where a language with mutable tree would have been much more straightforward.

John Lumley has been working on (and presented at Balisage) an implementation of XSLT written in XSLT. This has similar challenges, I suspect. (I also touched on the issue years ago in my ExtremeMarkup paper on writing an optimizer in XSLT). I think we can solve the problem by maintaining intermediate data structures as lots of small XML trees indexed by maps and arrays. The reason these work better than XML trees is that we have efficient immutable implementations of maps and arrays: that is, implementations that are immutable at the level of the exposed operations, but where making a small change does not involve making a full copy -- for example we implement maps using an immutable hash trie.

I've been thinking about whether it's possible to have an implementation of XDM node-trees with similar properties, and I think I have convinced myself that we can: the key requirement is to get rid of parent pointers, which immediately makes subtrees shareable. Getting rid of parent pointers doesn't actually inhibit full XPath navigation, it just means that a "node" returned by an XPath expression is a composite of two things: persistent information about the underlying node in memory, and transient information about how you reached it, so that you can retrace your steps.

Once you have this basic support at the data structure level, you probably need to introduce operations that take advantage of it: rather like map:put which creates a new map as a modified copy of an existing map, with a delta implementation underneath, you need operations that create a new tree which is a delta copy of an existing tree differing only in small details, e.g. a change in the value of a single attribute.

Michael Kay
Saxonica