Transformation Combinator

[ballsteve]

Inspired by Daniel's work on the parser combinator, why not re-imagine the evaluator engine as a function combinator?

At the moment (version 0.7/0.8), an XPath expression or XSLT stylesheet is compiled into a Sequence Constructor. This is a nested data structure that describes how a sequence should be constructed. Instead, use function combinators to build a new function that is the evaluator. That function would take a transformation context as its argument.

[ballsteve]

I've been doing some experimentation on this idea; these are in a new branch "transcomb". See transcomb.rs for the transformation combinator.

So far I have created functions: literal, context, sequence, compose, and step. These functions return a result which if successful contain a Sequence.

"sequence" takes a vector of functions. The result of each of these functions becomes an item in the returned Sequence. The original Context is used for each function.

"compose" takes a vector of functions. Each function is evaluated in turn, with the returned sequence of a function being used as the context of the next function. If each function is the "step" function, then this is an XPath path.

For example, a path in XPath such as child::node()/child::node() looks like:

compose(
  vec![
    step(NodeMatch{axis: Axis::Child, nodetest: NodeTest::Kind(KindTest::AnyKindTest)}),
    step(NodeMatch{axis: Axis::Child, nodetest: NodeTest::Kind(KindTest::AnyKindTest)}),
  ]
)

This gets evaluated by calling it with a Context:

ev(Context::new()).expect("evaluation failed")

Of course, the context needs to be a tree (RNode) to actually return anything. See the tests in the module for a more complete example.

[ballsteve]

Variables and functions now added.

[Devasta]

This is looking very promising. :D

[ballsteve]

The next step will be handling XPath patterns. The current code does this by reversing a Constructor, which is OK since it is just a data structure. Reversing a function may be challenging ;-)

[ballsteve]

Unfortunately, the transformation combinator idea hasn't worked out.

Patterns were the first to go. They are basically expression in reverse and it was too difficult to represent them as a function. However, predicates in patterns still use XPath expressions so they ended up being mixed.

When I tried to bring everything together in the XSLT module it really fell apart. The combination of transformation combinator functions with parser functions and then Pattern structures just became too complicated. :-(

[Devasta]

Was worth trying anyway! I've redone so many parts of the XML parser... nevermind the Ship of Theseus, I could build him a whole fleet! But I needed to do it to know what way to go about it.

"I have not failed. I've just found 10,000 ways that won't work.” ― Thomas A. Edison

[ballsteve]

We may revisit this at some point in the future. I've spent months working on it and it feels bad to give up on the whole approach. However, I certainly have learned a lot along the way.

I'm still using the parser combinator, just producing an Enum instead of functions.