“One thing leads to another” might be the sub-title for the web. Last night I found myself by some circuitous route in LiteratePrograms, a wiki set up by Derrick Coetzee. The site incorporates a version of that earlier WEB. Donald Knuth’s tangle and weave programs allow a single literate program script to be transformed to a view which make sense to the compiler and another which makes sense to a human reader.
The wiki is a laudable effort to provide code examples, clearly explained in many languages but it is fighting a bad case of spam. Comparative examples is a valuable educational resource to show how to abstract away the specifics of a syntax to see through to the essential similarities and differences. No examples in XQuery and only a couple in XSLT however, so here’s another opportunity for an XQuery evangelist.
Fibonacci is the computer science ‘hello world’. It is well represented in the wiki in numerous languages and many algorithms. The lack of a higher order factoring of the many algorithms away from the code needs tackling. XQuery with its limited functional model, lacking such devices as higher order functions, lazy evaluation, closures and generators, restricts the algorithms to pure recursive functions. When coming to XQuery from a background in imperative, object-oriented languages, the loss of updating variables is quite a challenge. .Good old Fib is not a bad example to start with.
A recursive function which follows the definition of the Fibonacci series looks pretty much like every other language:
declare function myfn:fib-recur($n as xs:integer) as xs:integer? {
if ($n <0) then ()
else if ($n = 0) then 0
else if ($n=1) then 1
else myfn:fib-recur($n - 1) + myfn:fib-recur($n - 2)
};
The empty sequence is used here as a return when the function is undefined so the return type is an optional integer. Top-down, goal-oriented, close to the mathematical definition and but requiring repeated re-evaluations of intermediate values. So how about bottom-up, starting with the knowns and working up to the goal?
declare function myfn:fib-itr-x($n as xs:integer, $m1 as xs:integer, $m2 as xs:integer) as xs:integer {
if ($n = 1)
then $m2
else myfn:fib-itr-x($n - 1,$m2, $m1 + $m2)
};
with a ‘front-door’ function to get started:
declare function myfn:fib-itr($n as xs:integer) as xs:integer? {
if ($n < 0) then ()
else if ($n = 0) then 0
else myfn:fib-itr-x($n, 0, 1)
};
Iterative solutions in which variables are updated look rather messy by comparison with this tail-recursive formulation, a style essential to many algorithms in XQuery.
Just how much worse is the recursive formulation? We need to time the calls, and now we really could do with those higher order functions so we can pass either fib function to a timer function to execute. Step in eXists function modules. These raise XQuery from an XML query language to a viable web application platform. The util module provides two functions:
-
util:function(qname,arity)to create a function template which can be passed to -
util:call (function, params)to evaluate the function
so we can create the recursive function template with:
let $call-fib-recur := util:function(QName("http:example.com/myfn","myfn:fib-recur"),1)
The timer function takes a function, a sequence of the parameters to be passed to the function and a repetition number. The timing is based on system time and the time difference converted to seconds and then to milliseconds:
declare function myfn:time-call($function as function, $params as item()* ,$reps as xs:integer ) as xs:decimal {
let $start := util:system-time()
let $result :=
for $i in 1 to $reps
return util:call($function ,$params)
let $end := util:system-time()
let $runtimems := (($end - $start) div xs:dayTimeDuration('PT1S')) * 1000
return $runtimems div $reps
};
and call it as
myfn:time-call($call-fib-recur,10,5)
Calling the timer iteratively over a range of values will generate the required data. Rather than simply output this data, we need an intermediate XML data structure containing the results. This can then be transformed into different representations or analysed later, to fit a curve to the data perhaps or export to a spreadsheet.
let $runs :=
<dataset>
{ for $n in -1 to $max
return
<tuple>
<n>{$n}
<fib>{ myfn:fib-itr($n) } </fib>
<recursive>{ myfn:time-call($call-fib-recur,$n,$reps) }</recursive>
<iterative>{ myfn:time-call($call-fib-itr,$n,$reps) } </iterative>
</tuple>
}
</dataset>
The loop starts at minus one to check that the code really copes with invalid inputs.
This data structure can be transformed to a table, iterating over the tuples.
declare function myfn:dataset-as-table($dataset ) as element(table) {
<table>
<tr>
{for $data in $dataset/*[1]/*
return
<th>{name($data)}</th>
}
</tr>
{for $tuple in $dataset/*
return
<tr>
{for $data in $tuple/*
return
<td>{string($data)}</td>
}
</tr>
}
</table>
};
Here I use the XPath name() function to convert from the tag names (of the first tuple) to strings for the column heading. This reflection allows very generic functions to be written and is I think a key technique for making the interface between problem-specific structures and generic functions. Note that the dataset has not been typed. This is because the function is written with minimal requirements of the structure which would require a permissive schema language like Schematron to express.
For graphing, this basic matrix could be imported directly into Excel, or, thanks to the wonderful GoogleCharts, to a simple line graph. Selected columns of the dataset are extracted and joined with commas, then all datasets joined with pipes.
declare function myfn:dataset-as-chart($dataset, $vars as xs:string+) as element(img) {
let $series :=
for $var in $vars
return string-join( $dataset/*/*[name(.) = $var],",")
let $points := string-join($series ,"|" )
let $chartType := "lc"
let $chartSize := "300x200"
let $uri := concat("http://chart.apis.google.com/chart?",
"cht=",$chartType,"&chs=",$chartSize,"&chd=t:",$points)
return
<img src="{$uri}"/>
};
I really like the way the dataset can be processed row-wise for the table and column-wise for the graph with equal ease of expression.
Finally, adding some intro, some page layout and CSS we get to a complete final script
The full script, hand langled, is over on the XQuery Wikibook In fact much of this article is there too, but with a shift in emphasis and change of person from first to third. Now coping with this kind of tangling from a common single source and with the vagaries of smuggling angle brackets and ampersands into different editors is quite a challenge. I’ve been struggling with the problem of keeping executable code examples in line with the wikibook entries, but there is an obvious clash between the publicly editable pages and the private code on my server.
Literate programming provided an early take on the core problem, illustrated here both in the code and its publication, of generating views from a single, common source. I feel another project coming on - but I’d better look at the tools already out there first!
Brilliant! You have demonstrated the XQuery is clearly ready to join the big leagues as a server-based language. It is so much more then SQL will every be but it has the same data selection power. Your use of Google Charts with a simple ReST interface shows how small and elegant XQuery can be.
Bravo Chris!