Posted on by & filed under programming, xquery.

To meet the Connect4 challenge, Marc Moskowitz and I chose to work in XQuery. This wasn’t strictly in the spirit of the challenge, which was supposed to be about trying out something new, since both Marc and I have been working in XQuery for about 7 years now. However, we decided to use XQuery because we like it, and it’s not popular (“medieval torture device” was a colleague’s fond description). We saw this as an opportunity to show off XQuery’s utility outside its nominal sweet spot as the “XML database query language.”

About XQuery

Even programmers who are only remotely familiar with XQuery probably have at least some familiarity with its little sister XPath. If you’re new to XQuery, you could think of it as XPath on steroids: all XPath expressions are also XQuery expressions. To XPath’s base, XQuery adds: looping, sorting, variables, functions, conditionals, an explicit type system, the ability to construct XML documents, and a system for organizing code into modules. In short, it is a fairly complete functional programming language. I’m speaking here of XQuery 1.0; XQuery 3.0 will be adding a good deal more.

About Lux

Beyond XQuery itself, we had to choose an application environment and data store. In the XQuery world these two things generally come as a package since the language is so tightly bound to the XML data representation. The natural choice for us would have been MarkLogic; we’ve also used eXist, and I’ve been curious about trying BaseX for a while now. But I couldn’t resist making Marc try out an open source search engine I’ve been working on for a little while now called Lux, which is basically a mashup of Saxon XQuery processing with Solr/Lucene as a data storage engine. I originally developed Lux as a query tool for our developers who were building XML-based applications primarily in Java using Solr with some XML-aware processing at index time.

At its core, Lux provides XML-aware indexing, an XQuery 1.0 optimizer that rewrites queries to use the indexes, and a function library for interacting with Lucene via XQuery. These capabilities are tightly integrated with Solr, and leverage its application framework in order to deliver a REST service and application server. You can read all about Lux on GitHub, where its source code and documentation is freely available. It’s mostly intended as an XQuery extension to Solr, and is not really a complete system for general-purpose web development, but it does include a minimal application server which is easy to set up and provides quite a bit of functionality.


I got started coding Connect4 a few days before the challenge actually began (OK I cheated!). The first thing I did was to create a data model, and then I created a matchmaking setup. This also gave me time to shake out a few issues in the Lux application server. On the day of the challenge, Marc and I focused on implementing the logic to determine when the game was complete, and then moved on to implement two different AI players: Fezzik and Inigo, named after Wesley’s opponents in the Princess Bride. Later, we worked on Vezzini a bit, but he remains a work in progress. I’ll show some code snippets here to illustrate a few points about working with XQuery (and Lux), but if you’re interested in the complete picture, the source code is available as a demo application within the Lux distribution here. You can also run it yourself by following these steps (you will need Java to run Lux):

Once you have Lux running, you can try the Connect4 demo, which will be running on your machine, and check out the source code, which will be in the webapps/demo/connect4 folder.

The data model

Some programming languages tout as a selling point their rich library of data structures. Certainly this is true for C++ and Java. Dynamic languages like Python, Perl and Javascript tend to have simpler more general-purpose data structures as they elevate the user above petty data management concerns. But even these languages have extensions that provide for user-defined object classes. In contrast, XQuery’s structured data options are extremely limited: really all you get is scalars, sequences, and XML trees. But that’s actually quite a bit. It covers most of the ground you need. One important thing missing is maps, to provide efficient key-value lookup (coming in XQuery 3.0), and it’s also difficult to represent relationship-heavy graphs in an efficient way. Document-oriented data remains the sweet spot for XML and XQuery, but we thought it would be an interesting experiment to see how good (or bad) the fit would be in this somewhat alien “gaming” arena.

Naturally, we chose to represent our data as XML documents (there really is no other choice in this framework). In this case, it’s natural to let a single document represent a game: the game document includes an identifier, the players, and the game grid, like this:

<game id="2013-02-12T16:18:33.263-05:00" modified="2013-02-12T16:18:45.385-05:00">
                <player color="#f00">mike</player>
                <player color="#ff0">fezzik</player>

In a more complete model, we’d want to represent the players as documents as well, so that they would have persistent identity, but given the short amount of time, we chose to represent players as strings alone (consequently they can’t be renamed and can have no associated data other than their name and the games they’ve participated in).

Our data model is very simple, but it is worth remarking on the identifiers used in the model. We used a timestamp to represent each game, and the players are represented by their names. Why didn’t we generate numerical identifiers, or GUIDS? Partly the answer is laziness, but this also reflects the heritage of the underlying data store, Lucene, as a search engine rather than a database. Lucene doesn’t concern itself with referential or relational data integrity, and the datastore, which is really just a search index, doesn’t provide autoincrement keys or other support for id generation: it expects that ids will be provided by an external agency. In a more full-featured application we would want to provide a key generating function, perhaps based on a random function, or a sequential one.

What is it like working with XML documents as general purpose data storage? The Connect4 game board is a 2-dimensional grid of a fixed size, which seems more naturally suited to be represented as a 2d array of some sort. XQuery can’t actually represent multi-dimensional arrays directly: you can’t have sequences of sequences (they collapse down to a single sequence), so we’re really stuck with the XML representation. The good news is it turns out to be surprisingly natural to work with using XPath. Consider this simple function for returning the value of a cell:


That’s pretty concise and at the same time a very explicit and transparent syntax, in my view. Consider how to find the bottom-most empty cell in a column (this is where a dropped token gets placed). In procedural languages a loop would be the natural way to express this; something like

  for (i = 0; i < 6; i++) {
    if (grid[i][column] == null && (i < 5 || grid[i+1][column] != null)) {
      return i;
  return null;

Using XPath’s powerfully concise syntax, we can accomplish all that in a
single neat expression like this which returns the cell, if there is one,
or an empty sequence:


Rendering the board

A key requirement for a web development platform is some convenient mechanism for rendering HTML (and Javascript, and CSS, etc). Some platforms offer a strong separation of HTML templates and procedural code; others mingle them more tightly. Some systems generate HTML, so it never appears explicitly anywhere. We think this latter approach is a mistake since it places too much reliance on the framework’s ability to generate the correct markup. But browsers change so fast and exhibit so much variety, that it is often necessary to control markup fairly precisely in order to achieve the desired result. Regarding the degree of separation of HTML templates and functional code, my bias is to design a system for smart, talented, creative people. Too many templating languages have been created with the idea that divisions of responsibility should be deepy engraved in the system design. In my view, all team members should be treated as adults who can be trusted to know what they understand and what they don’t. I’d much rather see an overzealous team member make a mistake than hear that a willing contributor is held back by an arbitrary limitation in the toolset.

In this little experiment, the same people were writing all the code and the markup, and everybody was up to speed with all the tools, so maximum flexibility was a real virtue. To see how this works in XQuery, let’s look at the way we put together the game view page (view.xqy); at the heart of it is this main method:

declare function c4:main() {
  let $game-id := util:param ($lux:http, 'game')
  let $game := collection()/game[@id=$game-id]
  (: let $winner := if ($game/@winner) then $game/@winner else () :)
  let $winner := $game/@winner
  let $player-name := util:param($lux:http, 'player')
  let $players := $game/players/player
  let $player := $players[.=$player-name]
  let $active := if (count($players) gt 1) then $game/players/player[1] else ()
  let $error := util:param($lux:http, "error")
  let $body :=
    <h2>Game: {c4:players ($game, $player), " started at ", util:formatDateTime($game-id)}
    <div>{if ($error) then <p class="error">{$error}</p> else ()}</div>
    <form action="play.xqy" method="post" name="play">
      <input type="hidden" id="player" name="player" value="{$player-name}" />
      <input type="hidden" id="game" name="game" value="{$game-id}" />
      <input type="hidden" id="col" name="col" value="" />
    { c4a:draw-grid($game) }
    <div id="turn">{
      if (not($game)) then
        ("Game ", $game-id, " not found")
      else if ($winner) then
        concat ($players[@color = $winner], " wins!")
      else if ($player is $active) then
        (attribute active { "true" }, <blink>Your turn</blink> )
      else if ($active) then
        concat($active, "'s turn")
      else (
        "Waiting for some competition to show up, ",
        " or play against: ",
        <a href="join.xqy?game={$game-id}&player=fezzik">fezzik</a>, " or ",
        <a href="join.xqy?game={$game-id}&player=inigo">inigo</a>, " or ",
        <a href="join.xqy?game={$game-id}&player=vezzini">vezzini</a>
    <p>player={$player} active={$active}</p>
    <textarea rows="8" cols="132">{$game}</textarea>
    <div><a href="test.xqy?game={$game-id}">debug</a></div>
    <script src="../js/jquery-1.8.2.min.js"></script>
    <script src="scripts.js"></script>
  return layout:outer('/connect4/view.xqy', $body)

This method demonstrates how XQuery lets us alternate naturally between markup and code. In short, angle brackets introduce markup, and curly braces, code. This is probably XQuery’s best syntactic feature, but it can be confusing for new users (and for syntax highlighters and indenters, it seems), because there is a *lot* of context-sensitivity required to parse XQuery.

XQuery’s functional style and first-class support for XML markup makes it easy to express well-formed HTML in a straightforward, logical and modular fashion. The view method above calls a function (c4a:grid) to draw the game grid inside of its own literal markup, and then calls another function (layout:outer) to embed its markup – the page’s body content – inside the page furniture that is shared by all the pages in the demo. This is easy and natural because markup is a first-class citizen and can easily be generated, manipulated and passed as the value of a variable.

To be totally fair, we should acknowledge that while it’s fairly easy to read an XML/XQuery mish-mash, when writing, subtle distinctions occasionally need to be made that can trip up neophytes. Why do I need to escape characters in one way here, but in a different way there? Why do I sometimes need to separate expressions with commas, while in other places it seems I can just string them up next to each other? After a little while though, one does become accustomed to the context switching, and the benefit is a nimble, flexible and expressive programming medium designed to consume and produce markup.

XQuery was designed for use with markup, so it had better be a good fit for that, but how is it for programming “business” logic, or in this case gameplay?

Playing the game, lazily

Connect4 gameplay is simple: the user selects a column, we check that the move is valid, and either return an error message or place the game piece on the board. Then we check if the game is over (ie there are four adjacent same-colored pieces in a row, column, or diagonal). We could have put the end-game check in the view, but it just seemed neater to put all the grid logic in one place, so we do that when a move is made and then save the end state.

The functions below handle the job of computing the winner of the game, if there is one. They operate in a fairly dumb way (keep in mind this was all written in a single four-hour session!): check-game calls compute-winner to see if there is a winner; if there is it notes this fact in its result. compute-winner checks every cell to see if any of them terminates a contiguous sequence of four cells of the same color, proceeding in the south, east, and south-east directions. Most programmers, on seeing this would groan at the obvious inefficiency. If you’ve read this far (ie have an interest in programming) and take a second to think about it, I’m pretty sure you will see what I mean: there is no early termination from the loop. In otherwords, even if we find a winner in the first cell we check, it appears that we will have to go through the effort of checking every other cell, even though there really is no chance any of them will have a winning cell (there can only be one if we enforce the rules correctly).

declare function c4a:check-game ($game as element(game))
  as element(game)
  let $winner := c4a:compute-winner ($game)
    if ($winner) then
      <game winner="{$winner[1]}">{$game/@*, $game/*}</game>

declare function c4a:compute-winner ($game as element(game))
  for $row in (1 to 7), $col in (1 to 6), $dir in $c4a:dirs//dir
  let $cell := c4a:get-cell ($game, $row, $col)
  return c4a:check-cell ($game, $row, $col, $cell, 1, $dir)

The thing is, there is no way to request an early exit from a for loop in XQuery. But, and this is a really beautiful thing about XQuery (along with other pure functional languages) – there’s no need to. Because XQuery is functional, and thus code paths are guaranteed to be free of side effects, the compiler is able to optimize by evaluating lazily: the entire tree of functions and expressions can be realized as an interconnected system of sequences represented implicitly by iterators, and results are only pulled from the iterators when required by an enclosing expression. This is actually somewhat difficult to verify, because the result is the same, whichever way the iteration is actually performed. What I did was to print out a message to a log file (Lux provides a logging function) in the check-cell method: when a winning cell is found, the iteration terminates early, as we’d expect.

Gluing it all together: the “controller”

We won’t review the rest of the code: if you’re interested in seeing how we implemented the turn-polling, or the game AIs, I encourage you to have a look at the full source. If you do that, you should find it pretty easy to navigate, but it’s probably worth mentioning what the overall control structure is (it’s pretty simple).

The Lux app server provides a very simple and easy to understand application model: file names translate directly into URLs: there is no URL translation, no need to map to an explicit model or configure any sort of controller mapping or conversational flow. This is not a “framework”, but it is an incredibly refreshing way to build a web site, if you have spent any time working with a “framework.” The app server does offer one little helpful feature: if you want “pretty” urls without .xqy extensions, you can just put a file called “index.xqy” in a folder.


Thanks for finishing this long post: in case you need a summary for your re-post or tweet, here’s what we said in a nutshell: you can program web applications in XQuery using an app server/XML datastore such as Lux. XML is a pretty good data model for a wide variety of applications, XQuery is a functional language which is great for consuming and producing markup, and the combination is a pleasure to work with.


3 Responses to “Connect4 in XQuery with Lux”

  1. Joe Wicentowski (@joewiz)

    Thanks for the great post – very interesting. I was curious to browse the source of the Connect4 app you created, but couldn’t find it. Is it in the lux git repo somewhere? Or do I have to install lux to be able to see the source of the Connect4 app? Thanks.

  2. Joe Wicentowski (@joewiz)

    Thanks for the pointer. I see. It might be interesting to try to adapt it to the EXPath Package format (which does let you declare dependencies on this/that processor) – so that it could be more easily shared (as a single .xar file), and ideally even ported to other systems. There aren’t many XQuery-based games that I know of, so it might take off ;) But I take the larger picture from your post. Lux sounds very interesting. Looking forward to following your work on this.