HXQ-0.3: index.html
<html>
<head><title>HXQ: A Compiler from XQuery to Haskell</title></head>
<body>
<center>
<h1>HXQ: A Compiler from XQuery to Haskell</h1>
</center>
<p>
<h2>Description</h2>
<p>
HXQ is a fast and space-efficient translator from XQuery to
embedded Haskell code (the translation is based on GHC templates).
It takes full advantage
of Haskell's lazy evaluation to keep in memory only those parts of XML data
needed at each point of evaluation, thus performing stream-based evaluation.
This results to an implementation that is as fast and space-efficient as
any stream-based
implementation based on SAX filters or finite state machines. Furthermore,
the coding is far simpler and extensible since its based on XML trees, rather
than SAX events.
For example, the XQuery below against the <a href="http://dblp.uni-trier.de/xml/">DBLP XML database</a>
(420MB) runs in 1.5 minutes on my laptop.
My high-performance Java implementation of XQuery, called <a href="/XQPull/">XQPull</a>,
which is stream-based (based on a StAX events), took about the same time.
<p>
HXQ uses the <a href="http://www.flightlab.com/~joe/hxml/">HXML parser for XML</a> (developed by Joe English),
which is included in the source.
I have also tried hexpat, but I found it too slow for large documents.
I haven't tried HaXML.
<p>
<h2>Installation Instructions</h2>
<p>
If you haven't done so, install the Glasgow Haskell Compiler,
<a href="http://www.haskell.org/ghc/">ghc</a>,
and the parser generator for Haskell,
<a href="http://www.haskell.org/happy/">happy</a>.
For example, in Fedora Linux, you install both using:
<pre>
yum install ghc happy
</pre>
Then download <a href="/HXQ-0.3.tar.gz">HXQ</a> and untar it.
You can either use cabal or make to build it. Then run xquery to test drive it.
<p>
<h2>Current Status</h2>
<p>
HXQ supports most essential XQuery features, although some system functions are missing (but are easy to add).
It does not have static typechecking; it leaves all checking to Haskell. This means that it distinguishes regular predicates
from indexing at run time: if an XPath predicate returns an integer at run time, it is indexing and this index is
checked against the current node position. The most important omission is backward step axes, such as /.. (parent).
Some, but not all, parent axis steps are removed using optimization rules, all others cause a compilation error.
<p>
<h2>Use</h2>
<p>
HXQ represents XML data as rose trees:
<pre>
type Tag = String
type AttList = [(String,String)]
data XTree = XElem Tag AttList [XTree]
| XText String
| XInt Int
| XFloat Float
type XSeq = [XTree]
</pre>
which basically means that one cannot implement backward navigation steps directly.
The main functions for embedding XQueries in Haskell are:
<ul>
<li> <tt>$(xe query)</tt>
<li> <tt>$(xq query)</tt>
</ul>
where <tt>query</tt> is a string value (a Haskell expression that evaluates
to a string <b>at compile-time</b>), They both translate the query into Haskell
code, which is compiled and optimized into machine code directly. The code that xe generates has type <tt>XSeq</tt> (a sequence of XML trees)
while the code that xq generates has type <tt>(IO XSeq)</tt>. If the query reads
at least one document (using doc(...)), then you should use xq since it requires
IO. To define constant XML data or a function body, it is better to use xe.
You can use the value of a Haskell variable <tt>v</tt> inside a query using
<tt>$v</tt> as long as <tt>v</tt> has type <tt>XSeq</tt>.
To use a function in a query, it should be defined in Haskell
with type <tt>(XSeq,...,XSeq) -> XSeq</tt>.
<p>
Here is an example of a main program:
<pre>
f(x,y) = $(xe "<article><first>{$x}</first><second>{$y}</second></article>")
main = do a <- $(xq ("<result>{ "
++" for $x in doc('data/dblp.xml')//inproceedings at $i "
++" where $x/author = 'Leonidas Fegaras' "
++" orderby $x/year descending "
++" return <paper>{ $i, ') ', $x/booktitle/text(), "
++" ': ', $x/title/text() "
++" }</paper> "
++" }</result> "))
putStrLn (show a)
b <- $(xq " f( $a/paper[10], $a/paper[8] ) ")
putStrLn (show b)
</pre>
Another example, can be found in <a href="Main.hs">Main.hs</a>.
<p>
If you want to extend HXQ, you need to read about <a href="http://www.haskell.org/bz/thdoc.htm">Template Haskell</a>.
Use <tt>make test</tt> to do various translation tests in ghci. You can look at the
Abstract Syntax Trees and the generated code from a query by evaluating
<tt>cq query</tt>. Basically, the way you generate Haskell code is
similar to operational semantics (where [| ... |] are syntactic brackets).
</body>
<p>
<hr>
<p>
<address>Last modified: 03/21/08 by <a href="http://lambda.uta.edu/">Leonidas Fegaras</a></address>