The Paisley architecture is a light-weight EDSL for non-deterministic pattern matching. It automates the querying of arbitrary objectoriented data models in a general-purpose programming language, using API, libraries and simple programming patterns in a portable and noninvasive way. The core of Paisley has been applied to real-world applications. Here we discuss the extension of Paisley by pattern iteration, which adds a Kleene algebra of pattern function composition to the unrestricted use of the imperative host language, thus forming a hybrid object-oriented{functional{logic framework. We subject it to a classical practical problem and established benchmarks: the node-set fragment of the XPath language for querying W3C XML document object models.
The Paisley embedded domain-speci c language (EDSL) and library adds the
more declarative style of pattern matching to the object-oriented context of
Java programming [
The non-deterministic aspects of Paisley have been demonstrated to provide
a fairly powerful basis for embedded logic programming in the object-oriented
host environment. In [
Here we describe and evaluate recent extensions to Paisley that greatly
increase its capabilities as an embedded functional-logic programming system,
supporting more complex control and data ow than the combinatorial
generate&test tactics of [
boolean sideways) f if (node instanceof Element) f
Element elem = (Element)node; if (elem.getTagName( ).equals(variant == 1 ? ”a” : ”p”) ) f if (variant > 1) f
CollectionhElementi sub = variant == 2 ? results : new ArrayListh i( ); collect(1, elem, sub, false); g if (variant == 1 && !elem.getAttribute(”href”).equals(””) jj
variant == 3 && !sub.isEmpty( ) ) results.add(elem); g
g g if (node.getFirstChild( ) != null)
collect(variant, node.getFirstChild( ), results, true); if (sideways && node.getNextSibling( ) != null) collect(variant, node.getNextSibling( ), results, true); // solution // depth // breadth The basic motivation for a pattern matching EDSL is that patterns as language constructs make data-gathering code more declarative, and thus more readable, more writable and more maintainable. If done properly, this additional expressive power can be used to factor code compositionally in ways that are not straightforwardly possible in a conventional object-oriented approach, where the logic and data ow of a complex query often appear as cross-cutting concerns.
As an example that highlights the issues of logical compositionality, consider a family of three related XPath expressions, depicted in Fig. 1, that select nodes from XHTML documents. The rst selects, from the context node and its descendants, all <a> elements (hyperlink anchors) that have a href (target) attribute speci ed. The second selects only those <a> elements with href attributes that are nested within <p> elements (paragraphs). The third selects all <p> elements that have some <a> element with href attribute nested within.
The task is to implement the speci ed search procedures, as object-oriented queries of the standard W3C X(HT)ML Document Object Model. Evidently, one wishes to implement most of the operational code generically, with reuse and minimal adaptation for each of the three variants. Additionally, the second and third variant should be able to use the rst recursively. To emphasize the role of reuse in this example, Fig. 1 gives a uni ed implementation, where the identi er variant is grayed out to emphasize that all its occurrences serve only the static choice between the variants. The common algorithm is to traverse nodes by depth- rst search, and add all valid matches, possibly repeatedly, to a results collection supplied by the caller. Two further improvements of the solution are suggested as exercises to the reader: 1. Of course, code that works for these three, but no other XPath expressions is hardly generic. Abstract to a large, preferrably unbounded, set of useful XPath expressions. Refactor the code to separate commonalities and individual degrees of freedom, as cleanly as possible. 2. The use of a Collection for matches implies eager evaluation. This is not e cient for the recursive calls from variant 3 to variant 1, where searching can be aborted after the rst successful match (which falsi es sub.isEmpty( )).
Refactor the code to allow for lazy evaluation, as transparently as possible.3 See section 5 and Fig. 4 below for our proposed solution. We do not claim that these refactoring steps are infeasible in any particular previous framework. But we shall demonstrate that the Paisley approach naturally gives both pragmatic design guidelines, and a concrete notation for the adequate, abstract, modular and e cient expression of the underlying algorithm and its instantiations. 3
The design principles, semantics and APIs of Paisley patterns have been discussed
in detail in [
The root of the pattern hierarchy is the abstract base class PatternhAi of patterns that can process objects of some arbitrary type A. A pattern PatternhAi p is applied to some target data x of type A by calling p.match(x), returning a boolean value indicating whether the match was successful.
Complex patterns are composed from application-layer building blocks that implement classi cations and projections, the rei cation of instance tests and getter methods, respectively. These can be de ned independently for arbitrary (public interfaces of) data models, requiring no intrusion into legacy code. Paisley comes with prede ned bindings for common Java data models, such as the Collection framework; more can be added by the user. Each projection x from type A to B induces by contravariant lifting a construction of type PatternhAi from PatternhBi, conveniently implemented as a method PatternhAi getX(PatternhBi p).
Information is extracted from a successfully matched pattern via embedded
pattern variables. A pattern VariablehAi v matches any value A x, and stores a
reference to x that can be retrieved by invoking v.getValue( ). Variables behave like
imperative rather than logical variables; subsequent matches merely overwrite
the stored value, no uni cation is implied.4
3 This task is inherently much more di cult in conventional programming languages
than in logic and lazy functional approaches; cf. [
both(Patternh? super Ai first, Patternh? super Ai second); public static hAi PatternhAi
either(Patternh? super Ai first, Patternh? super Ai second); public PatternhAi someMatch( ); class VariablehAi extends PatternhAi f public A getValue( ); public hBi ListhAi eagerBindings(Patternh? super Bi root, B target); public hBi IterablehAi lazyBindings(Patternh? super Bi root, B target); public hBi PatternhBi bind(Patternh? super Bi root, Patternh? super Ai sub); public PatternhAi star(Patternh? super Ai root); public PatternhAi plus(Patternh? super Ai root);
Patterns can be composed conjunctively and disjunctively by the binary combinators both and either, or their n-ary variants all and some (not shown), respectively. As in traditional logic programming, disjunction is realized as backtracking: After each successful match for a pattern p, p.matchAgain( ) can be invoked to backtrack and nd another solution. Solutions can be exhausted, in an imperative style of encapsulated search, by the following programming idiom: if (p.match(x) ) do
doSomething( ); while (p.matchAgain( ) ); When not using an exhaustive loop, the computation of alternative solutions can be deferred inde nitely; the required state for choice points is stored residually in the instances of the logical combinators themselves.
The search construct can be abbreviated further to a functional style if the desired result of each match is the value stored in a single pattern variable v. Invoking v.eagerBindings(p, x) or v.lazyBindings(p, x) returns objects that give the value of v for all successive matches, collected beforehands in an implicit loop, or computed on iterator-driven demand, respectively. The latter can also deal with in nite sequences of solutions.
For cases where only the satis ability of a pattern p, but not the actual sequence of solutions, is of concern, one can invoke p.someMatch( ), yielding a wrapper that cuts all alternatives after the rst solution. Thus, laziness is exploited for e ciency and, when used in conjunction with other patterns with multiple relevant solutions, spurious multiplication of solution sets is avoided.
As discussed in [
A variable v known to occur5 in a pattern p can be substituted by a subpattern q, by invoking v.bind(p, q), mnemonically read as ( v: p)q. The implementation delegates to p and q sequentially, and hence does not require access to the internals of either operand.
Substitution can also be given a recursive twist; a pattern p with a \hole" v can be nested. The patterns v.star(p) and v.plus(p) correspond to the and +-closures, respectively, of the search path relation between p and v, in the sense that the usual recursive relations hold, v.star(p) v.plus(p) either(v, v.plus(p) ) v.bind(p, v.star(p) ) which is already almost the complete, e ective implementation, up to lazy duplication of v.plus(p) for each iteration level that is actually reached. Note that iteration depth is conceptually unbounded, and solutions are explored in depthrst pre-order, due to the way either is used. Thus patterns form a Kleene algebra up to equivalence of solution sets but not sequences.
Using these iteration operators, complex nondeterministic pattern constructors can be de ned concisely. For instance, the contravariant lifting of the multivalued, transitive descendant projection in XML document trees, applied to a pattern p, becomes simply
v.bind(v.plus(child(v) ), p) where VariablehNodei v is fresh, and the multi-valued projection PatternhNodei child(PatternhNodei ) is implemented in terms of the org.w3c.dom.Node getter methods getFirstChild( ) and getNextSibling( ). Note how the two sources of nondeterminism, regarding horizontal (child) and vertical (plus) position in the document tree, respectively (cf. the distinct recursive calls in Fig. 1), combine completely transparently. 4.2
Functions taking patterns to patterns have so far featured in two important roles. In operational form, implemented as lifting methods, they are the basis for contravariant representation of projection patterns. In algebraic form, as bind-based abstractions from a variable, they enable pattern composition and iteration. Being so ubiquitous in the Paisley approach, they deserve their own 5 The actual condition is de nite assignment rather than occurrence, for technical reasons. public static hAi MotifhA, Ai id( ); public hCi MotifhC, Bi on(MotifhC, ? super Ai other); public static hAi MotifhA, Ai star(MotifhA, ? super Ai f); public static hAi MotifhA, Ai plus(MotifhA, ? super Ai f); public IterablehAi lazyBindings (B target); public ListhAi eagerBindings(B target); g g class VariablehAi extends PatternhAi f // : : : public hBi MotifhA, Bi lambda(PatternhBi root); rei cation. Fig. 3 shows the relevant API. An instance of class MotifhA, Bi is the rei ed form of a function taking patterns over A to patterns over B, or by contravariance, the pattern representation of an access operation that takes data of type B to data of type A, by its apply method.
The Motif class provides the algebra of the category of patterns, namely the identical motif id( ) and the type-safe composition of motifs by the on(Motif) instance method. The variable-related operations star/plus and lazy-/eagerBindings each have a point-free counterpart in Motif, which create anonymous variables to hold intermediate results on the y. For instance, the XML descendant pattern de ned above can be expressed less redundantly in point-free form as plus(child).apply(p) given a child access rei cation MotifhNode,Nodei child.
Conversely, motif abstraction is de ned for pattern variables, which obeys the beta reduction rule: v.lambda(p).apply(q) v.bind(p, q)
There is often a trade-o in convenience between functions in operational and rei ed form, that is as either pattern lifting methods or motifs. Since there is no automatic conversion between methods and function objects in Java prior to version 8, our strategy in the Paisley library is to provide both redundantly. 5
Figure 4 repeats the XPath examples expressions, now contrasting the domainspeci c XPath code with the general-purpose Java/Paisley code. The latter has been underlined for easy reference. The solution makes full use of the shared PatternhNodei dslash(String name, PatternhElementi: : : constraints) f
return descendantOrSelf(element(both(tagName(name), all(constraints) ) ) ); VariablehElementi outerVar = new Variableh i ( ); PatternhNodei outerForm = dslash(”p”, outerVar); VariablehElementi innerVar = new Variableh i ( ); PatternhNodei innerForm = dslash(”a”, innerVar, attr(”href”, neq(””) ) ); IterablehElementi collect1(Document root) f
return innerVar.lazyBindings(innerForm, root); g IterablehElementi collect2(Document root) f
return innerVar.lazyBindings(outerVar.bind(outerForm, innerForm), root); g IterablehElementi collect3(Document root) f
return outerVar.lazyBindings(outerVar.bind(outerForm, innerForm.someMatch( ) ), root); common structure of the three variants, and achieves complete separation of concerns: { The search procedure implied by the operator // is not spread out as recursive control ow, but rei ed and encapsulated as the descendantOrSelf pattern lifting, prede ned in the XPathPatterns static factory class of Paisley, discussed in detail in the following section. { XPath subexpressions are denoted concisely and orthogonally.
The generic form .//tag. . . that reoccurs in all variants is abstracted as the extensible pattern construction dslash.
The particular inner and outer forms, .//a[@href] and .//p, respectively, are de ned once and for all, independently of each other. { The semantics of XPath queries are e ected concisely and orthogonally.
The general principle of encapsulated search is expressed naturally by a call to lazyBindings. The third variant concisely prunes the recursively encapsulated search after the rst solution, via the pattern modi er someMatch( ).
The particular con guration of subexpressions for all variants boils down to a simple choice of the bound variable and pattern-algebraic composition. Note that both are rei ed and hence rst-class citizens of Java. Thus, each variant boils down to a one-line expression, where the points of variability are ordinary subexpressions that can be chosen statically (as shown) or dynamically, with arbitrarily complex meta-programming. g g g g g enum Axis f
public Motifh? extends Node, Nodei getMotif( ); abstract class Predicate f public abstract boolean accepts(NodeSet context, int position, Node candidate); public Motifh? extends Node, Nodei apply(Motifh? extends Node, Nodei base); class NodeSet f private Collectionh? extends Nodei elems; public NodeSet(Iterableh? extends Nodei elems); public int size( ); public IterablehNodei filter(Predicate pred); class Path f
Path(Motifh? extends Node, Nodei motif);
public Motifh? extends Node, Nodei getMotif( );
public Path step(Axis axis, Test test, Predicate: : : predicates);
As a case study of real-world data models and queries, we have implemented
the navigational (proper path) fragment of the XPath 1.0 language as a Paisley
pattern combinator library. The complete implementation consists of the factory
classes XMLPatterns for generic DOM access and XPathPatterns for XPath speci cs,
with currently 433 and 282 lines of code, respectively. Given an XPath parser,
it can be extended to a full- edged interpreter, and hence a non-embedded DSL,
by a straightforward mapping of abstract syntax nodes to pattern operations.
The XPath 1.0 language comes with many datatypes and functions that do not
contribute directly to its main goal, namely the addressing of nodes in an XML
document. For simplicity, we restrict our treatment of the language to a fragment
streamlined for that purpose. Typical uses of XPath within XSLT or XQuery [
Here axis is one of the twelve XPath document axes, omitting the deprecated namespace declaration axis. The nonterminal test is the tautological test node(), the text node test text() or an explicit node name test. For predicate, used to lter selected nodes, we accept not the full XPath expression language, but only predicate ::= path j integer j not predicate j ( predicate (and j or) predicate ) where a path predicate holds if and only if it selects at least one node (existential quanti cation). Positive and nonpositive integer predicates [ i] select the i-th node from the candidate sequence, and the (n i)-th node, respectively, from the sequence of n candidates in total. The former is a valid abbreviation for [position()==i] in standard XPath; we add the latter as an analogous abbreviation for [position()==last()-i]. Logical connectives on predicates are de ned as usual.
Various abbreviation rules apply; for instance, the shorthand .//a[@href] expands to the verbose form self::node()/descendantOrSelf::node()/child ::a[attribute::href]. This translates to the following semantic object: relative( ).step(Axis.self, node( ) ) .step(Axis.descendantOrSelf, node( ) ) .step(Axis.child, name(”a”),
exists(relative( ).step(Axis.attribute, ”href”) ) )
The relation between XPath predicates and candidate sequences, misleadingly called \node-sets" in the standard, is rather idiosyncratic (they can not be modeled adequately as plain sets) and the major challenge in this case study. A node-set is implicitly endowed with either of two prede ned orders, namely forward or reverse document order. These orders are loosely speci ed by a preorder traversal of nodes, up to attribute permutation. A predicate lters the nodes in a node-set not purely by point-wise application, but may depend on some context, namely the position of the node in the node-set, starting from one, and the total number of members. This information is available in XPath via the \functions" position() and last(), respectively. It is realized in the API by the parameter position of method Predicate.accepts and the method size( ) of class NodeSet, respectively, to be supplied from the method filter of class NodeSet. 6.2
The node-extracting semantics of the XPath language can be rendered naturally in the Paisley framework by contravariant lifting. An XPath expression can be ancestor ancestorOrSelf plus(parent) star(parent)
descendant descendantOrSelf plus(child) star(child) followingSibling plus(nextSibling) precedingSibling plus(previousSibling) following
ancestorOrSelf.on(followingSibling).on(descendantOrSelf) preceding ancestorOrSelf.on(precedingSibling).on(descendantOrSelf)
self id applied to any node of an XML document, here implemented as DOM, and extracts some other nodes, possibly of a more special type, such as elements or attributes. This gives rise to a semantic type Motifh? extends Node, Nodei.
Except for the context-sensitivity of predicates, all language constructs could simply been given motif semantics and lumped together by composition.
XPath axes are all de ned concisely in terms of motifs. Primitive DOM access operations from factory class XMLPatterns directly de ne the attribute, child and parent axes. Given the additional primitives next-/ previousSibling, which are only implicit in the XPath standard, all other axes are de nable in terms of elementary motif algebra; see Figure 6. Node tests are straightforward applications of test pattern lifting.
Atomic path expressions are realized by the document root access motif and the identity motif, for absolute and relative paths, respectively. Composite path expressions conceptually compose their constituents left to right. The exception are predicates, which are implemented as motif transforms in order to deal with context sensitivity. These are applied in order to the step basis, that is the composition of axis and test, for local ltering, and the result is then composed with the front of the path expression; see Fig. 7.
The real challenge is the implementation of node-set predicates: On the one hand, context information about relative element position and total node-set size must be provided, which transcends the context-free realm of pattern and motif composition. On the other hand, elements should be enumerated lazily, in class Predicate f // : : : gg; gg; g g class NodeSet f // : : : public MotifhNode, Nodei apply(final Motifh? extends Node, Nodei base) f return new Motifh? extends Node, Nodei ( ) f public PatternhNodei apply(Pattern h? super Nodei p) f return new MultiTransformhNode, Nodei (p) f protected IterablehNodei apply(Node n) f
return new NodeSet(base.lazyBindings (n) ).filter(Predicate.this); // [ ] public NodeSet(Iterable h? extends Nodei elems) f
this.elems = cache(elems) ; g public IterablehNodei filter(final Predicate pred) f return new IterablehNodei ( ) f public IteratorhNodei iterator( ) f return new FilterIteratorhNodei (elems.iterator( ) ) f int i = 0; protected boolean accepts(Node candidate) f
return pred.accepts(NodeSet.this, ++i, candidate); gg; gg; g g public static Predicate exists(final Path cond) f return new Predicate( ) f public boolean accepts(NodeSet context, int position, Node node) f
return cond.getMotif( ).apply(any ( ) ).match (node); g g; g
g g; g public static Predicate index(final int i) f return new Predicate( ) f public boolean accepts(NodeSet context, int position, Node node) f return position == (i > 0 ? i : context.size( ) i); order to make tests for non-emptiness e cient and avoid scanning for unneeded solutions. Obviously, evaluation must switch transparently from lazy to eager strategy if the size of the node-set is observed. And lastly, for elegance reasons, we strive for an implementation that is as declarative as possible, with very limited amounts of speci c imperative coding.
The solution is depicted in Figure 8. Generic Paisley API method calls are underlined for easy reference. The action of a predicate on a base motif requires control over the solution node-set. Hence it needs to intercept both the pattern parameter at the motif level and the target node parameter at the pattern level, by means of two nested anonymous classes. Then a lazy disjunction is spliced in, which enumerates the solutions of the base motif, wraps them in a local node-set and lters them context-sensitively.
The counterpart on the node-set side of the implementation works as follows: It wraps the lazy enumeration of candidate nodes is a collection, via the auxiliary method cache (de nition not shown). This collection caches enumerated items for repeated access, and forces eager evaluation if its size( ) method is called.
The actual ltering operation yields a lazy enumeration that intercepts iterator creation, again by means of two nested anonymous classes. The iterator of the cached candidate collection is overwritten by an instance of the auxiliary abstract class FilterIteratorhAi (de nition not shown) that in-/excludes elements ad-hoc, determined by the result of its method boolean accepts(A). This acceptance test is then routed back to the context-sensitive acceptance test of the given predicate, by addition of a single minuscule piece of explicit imperative (stateful) programming, namely a counter i for the relative position. Note that, Java formal noise apart, the actual problem-speci c code consists of ve singleline statements, marked with [ ].
Existential predicates forget their results, hence the invocation of the catchall pattern any( ). They prune the search after the rst hit, as witnessed by the absence of a call to matchAgain( ) on the freshly created pattern. Eager evaluation is only ever triggered by index predicates via a call to context.size( ). Logical predicate connectives are de ned point-wise (not shown). 7
We have tested the performance and scalability of our implementation using
material from XMark [
For each pair of data le and query expression, we processed the document
with lazyBindings of the XPath motif, and computed running times for extracting
Query XPath Expression
Q01 /site/open auctions/open auction/bidder[
Timing values were obtained as real time with System.nanoTime( ), median value of ten repetitions, with interspersed calls to System.gc( ). In order to compensate deferred computation costs in the DOM implementation, we reused the same document instances for all successive queries. All experiments were performed on an Intel Core i5-3317U quad-core running at 1.70 GHz, with 8 GiB of physical memory, under Ubuntu 14.04 LTS (64bit), and Oracle Java SE 1.8.0 05b13 with HotSpot 64bit Server VM 25.5-b02 and 800 MiB heap limit.
Our rst quantitative goal, beyond highlighting the elegance and e ectiveness of Paisley-style pattern speci cation, is to demonstrate the e ciency payo of lazy pattern execution. Our second quantitative goal comes back to methodological arguments from the motivation section of this paper. Pattern matching has been hailed as a declarative tool that brings expressiveness for data querying extremely close to the hosting programming language environment. Tools for non-embedded domain-speci c languages may be more powerful in many respects, but the burden of proof is on them that this power is worth the trouble incurred by the impedance mismatch with ordinary host code. Nevertheless, we should verify that the bene ts of tight embedding produced by our methodological approach are not squandered by the implementation.
To that end, we repeated our experiments with the next-closest tool at hand, namely the Java on-board XPath implementation accessible as javax.xml.xpath. .6 We compared both preparation and running times of Paisley XPath patterns with XPathExpression objects obtained via XPath.compile(String). The rst solution and all solutions were obtained by calling XPathExpression.evaluate with the type parameter values NODE and NODESET, respectively.
The Paisley approach fares well, even as a non-embedded DSL. The Paisley preparation process (a simple recursive descent parser for full XPath generated with ANTLR7, followed by direct translation of abstract syntax nodes to pattern operations) is consistently faster than on-board compilation to XPathExpression objects, although the task may have been sped up marginally by considering 6 In our Java environment, com.sun.org.apache.xpath.internal.jaxp.XPathImpl. 7 http://www.antlr.org/
Q06
Q15
Q16
Q01
Q06
Q15
Q16 only a subset of the language after parsing. (See Table 2 in the appendix for details.) When patterns are constructed in embedded DSL style, using the API rather than textual input, static safety is improved, and even the small overhead eliminated, at the same time.
The di erences in running times are so drastic that they can only be visualized meaningfully in logarithmic scale. Proportions range from on-board facilities being 13 % faster for all solutions of Q06 at size 0.04, to being over 26 000 times slower for the rst solution of Q06 at size 0.40. With the exception of the exhaustion of \brute-force" case Q06, Paisley is 1{2 (all solutions) or 2{4 ( rst solution) orders of magnitude faster, respectively; see Fig. 10. Accessing only the rst solution with the on-board tools is particularly disappointing, being only marginally faster than exhausting all solutions. It appears that our motivation is con rmed, and conventionally developed tools are ill-suited to scalable lazy evaluation, where external demand governs internal control. (More detailed results are given in Fig. 12 the appendix.) 8
The experimental gures for the on-board tools have been obtained without any
tweaking of features; hence there is large uncertainty in the amount of possible
improvements. Therefore the comparison should not be taken too literally. But
we feel that it is fair in a certain sense nevertheless: Our Paisley implementation
has been obtained in the straightest possible manner, also without any tweaking.
Its advantage lies thus chie y in the fact that we have chosen the application
domain, namely the speci ed XPath fragment, and tailored the tool design to
avoid any complexity inessential to the task at hand. It is this light-weight
exibility by e ective manual programming we wish to leverage with the Paisley
approach { the capabilities of existing, more heavy-weight tools with respect to
automated, adaptive specialization are generally no match.
Related work with regard to language design and implementation, and to
objectoriented-logic programming, has been discussed in [
Purely declarative accounts of XPath, although theoretically interesting, have
little technical impact on our main concern, the concrete embedding in a
mainstream programming language. A few random examples: In [
6 6 5 5 4 4 3 3 0 0
Q06 on−board eff on−board first on−board all 0.04 Fig. 12. Running times for Paisley and Java on-board XPath implementations. Logarithmic scale; lower end of scale arbitrary.