Planet XMLhack

Angle brackets are a way of life


January 19

Eric van der Vlist: Mon intervention lors de l’inauguration du Retour à la Terre Rive Gauche

En attendant la publication des photos et vidéos sur le site du Retour à la Terre, voici le texte que j’avais préparé pour mon intervention lors de l’inauguration officielle du magasin de la Rive Gauche le 18 janvier.

Catherine est inquiète parce qu’elle ne sait pas ce que je veux vous dire ce soir…

Elle me connaît pourtant bien puisque cela fait plus de trente ans que nous vivons ensemble !

Nous avons la chance d’avoir étudié dans une grande école (l’École Centrale) où nous nous sommes rencontrés mais avons toujours eu du mal à nous intégrer au monde des grandes entreprises.

Je l’ai devancé en devenant consultant indépendant il y a bientôt quatorze ans.

Lorsqu’elle a souhaité à son tour quitter Renault il y a quatre ans, nous avions un peu d’économies, pas beaucoup parce que l’argent n’a jamais été notre objectif principal mais suffisamment pour acheter par exemple un petit deux pièces dans le quartier où nous habitons.

Nous avons décidé d’utiliser ce petit pécule pour qu’elle puisse mener à bien un projet qui lui tenait à cœur et quatre ans plus tard sommes réunis ici pour inaugurer son deuxième magasin.

Le succès est donc au rendez vous.

Quarante emplois directs (et au moins la moitié d’emplois indirects) ont été crées et des dizaines de milliers de clients ont été sensibilisés aux problèmes environnementaux et ont mangé bio et d’une manière plus responsable.

Je suis très fier de Catherine pour ce succès.

Je suis également heureux de voir qu’elle s’est épanouie professionnellement pendant ces quatre années comme jamais auparavant.

Je le suis un peu moins de la voir fatiguée comme elle ne l’a jamais été.

Quand on rentre dans un des deux magasins du Retour à la Terre, ce que l’on voit peut sembler facile et tomber sous le sens.

Je vis aux côtés de Catherine et je peux vous dire que créer ce cercle vertueux est au contraire un combat de tous les instants :

Je sais que ce type de combat est chose courante pour beaucoup de nos invités.

Insecticides, plastiques, déchets, cancers, OGM, brevets sur le vivant, grande distribution, industrie de la viande, villes en transition, paysans sans terre, nucléaire, gaz de schiste, … au cours des débats organisés par Catherine, je me suis souvent senti dérouté et découragé par la diversité de ces luttes.

Il y a pourtant une constante : le refus de la marchandisation des biens communs de l’humanité.

Prenons par exemple le problème de l’eau, particulièrement éloquent parce qu’il représente un combat que beaucoup considèrent comme déjà perdu.

L’eau est essentielle à la vie, elle recouvre 72% de notre planète et notre corps est composé d’eau à 65%.

Pourtant, vous souvenez vous quand vous avez bu pour la dernière fois de l’eau qui ne soit pas « produite » par une des multinationales qui se sont emparé de son « marché » ou par une des rares compagnies des eaux qui soit publique ?

Pour moi, c’était en juillet dernier, en randonnée avec notre fils Samuel à plus de 2000m d’altitude dans les Alpes.

Et même dans un endroit aussi préservé, il nous a fallu filtrer l’eau des torrents de montagne dans un filtre en céramique, merveille de haute technologie suisse, pour la boire sans risque.

Cet accaparement de l’eau, des semences, de la nourriture, des terres, du sous sol, des idées, des déchets, de l’énergie, des logiciels, des données privées, de l’argent, … et même du « droit à polluer » par quelques privilégiés qui contrôlent une poignée de multinationales est intolérable sur le plan des principes, mais aujourd’hui il ne s’agit plus ce cela.

Le problème est pourtant simple.

Nous sommes 7 milliards sur une planète aux ressources finies qui ne peut nourrir sa population de manière durable que si ses ressources sont exploitées de manière raisonnable et distribuées avec un minimum d’équité et c’est précisément de cela dont il s’agit pour chacun de ces combats.

Combattre les dérives actuelles sous toutes leurs formes n’est plus seulement une question de principes mais une question de survie pour nous et pour notre civilisation !

Merci à tout ceux qui mènent cette lute essentielle à leur manière et sur tous les fronts.

Posted at 12:59

Edd Dumbill: Yak shaving

If your brain works the way mine does, you often find yourself doing a variety of related but not necessary tasks along the way to fulfilling a larger goal. For some reason, the history of which I’m not entirely sure, this is called “yak shaving.” Some of my finest work has been done that way, so I’m happy to embrace it, even if I do add hours to the job at hand.

This week’s yak shaving has neared epic proportions, but proved eminently satisfying. I’ve been working on collecting together an overview of big data products. It’s early days yet for Hadoop centered offerings, but 2012 will be the year that Microsoft and Oracle will join IBM and EMC Greenplum in having launched products in the marketplace.

Surveying who-offers-what is a bit like writing code. I naively started off with a spreadsheet, but I quickly realized that real life data doesn’t fit into grids. Even if you can coerce it that way, the effort required to get there is massive. Instead I wanted a structured description of the products that I could amend and refactor as the whole landscape came into perspective.

To get this done, I revived an old interest. Some years ago I contributed a little to Dave Beckett’s Redland RDF project, and so I returned to this technology. RDF is simply a machine readable way of writing descriptions about things.

The task at hand was to collect knowledge about each vendor and their products, and have this in a format that could be used to create feature tables and comparison charts.

In my little project, each vendor has a file in which I’ve written a machine-readable description of their products. Here’s a little excerpt from my description of Cloudera:

<</span>http://www.cloudera.com/hadoop/>
a :HadoopDistribution ;
dc:title "Cloudera's Distribution including Apache Hadoop" ;
:homePage <</span>http://www.cloudera.com/hadoop/> .
You can probably figure out this is the beginning of a description of Cloudera’s Hadoop Distribution. This is in the Turtle dialect of RDF, which makes the whole thing a lot more readable. I’m not an RDF purist, and don’t have plans yet to publish this data publicly. I was simply using the technology as a shorthand for writing down a large amount of semi-structured information.

After collating all the data together into a Redland database, I was able to write a small amount of Python code that queried the data, fed it into some templates, and spat out some chunks of HTML for inclusion into my article. For the curious, I used a combination of SPARQL and the regular Redland APIs to query the data, and chose the jinja2 templating engine to create my HTML. Excerpted screenshots are attached to this post.

Yes, I could have chosen XML & XSLT for this, or JSON, or, or… but that’s not really the point. The point was to have fun and learn stuff at the same time as achieving my goals. I brushed up on my Python, got some SPARQL experience in, and have content that can be easily kept up to date and repurposed.

Oh, and if you’re going anywhere near RDF technology, I can recommend Redland as a pragmatic and straightforward toolkit.

Look out for the Hadoop survey to be published tomorrow!

Posted at 00:13

January 18

Tim Bray: HttpURLConnection’s Dark Secrets

If you’re programming in the Java language and want to talk to a Web server, there are several libraries you can choose from. HttpURLConnection is one popular choice, and for Android programming, the engineering team has now officially suggested that you use it where possible.

Since there are irritating orthographical and Web-Architecture issues with the name “HttpURLConnection”, let’s just say HUC. HUC is reasonably well documented, if by “reasonably well” you mean “omits any discussion of the relationship between method calls and underlying HTTP traffic”. Let me fill that in. Who knows, maybe some JavaDocs maintainer somewhere will feel inspired to address this.

Let’s look at a snippet of the simplest possible HUC invocation, to dereference a URI and fetch the data. It would look something like this:

void get(URL url) {

  // this does no network IO 
  HttpURLConnection conn = url.openConnection();
  InputStream in;
  int http_status;
  try {

    // this opens a connection, then sends GET & headers 
    in = conn.getInputStream(); 

    // can't get status before getInputStream.  If you try, you'll
    //  get a nasty exception.
    http_status = conn.getResponseCode();

    // better check it first
    if (http_status / 100 != 2) {
      // redirects, server errors, lions and tigers and bears! Oh my!
    }
  } catch (IOException e) {
    // Something horrible happened, as in a network error, or you
    //  foolishly called getResponseCode() before HUC was ready.
    // Essentially no methods of on "conn" now work, so don't go
    //  looking for help there.
  }
  
  try {
    // now you can try to consume the data
    try_reading(in);
  } catch (IOException e) {
    // Network-IO lions and tigers and bears! Oh my!
  } finally {
    // Do like Mom said and practice good hygiene.
    conn.disconnect(); 
  }
}

Now, suppose you want to do a POST instead of a GET.

void post(URL url, byte[] payload) {

  // this does no network IO.
  HttpURLConnection conn = uri.openConnection(); 

  // tells HUC that you're going to POST; still no IO.
  conn.setDoOutput(true); 
  conn.setFixedLengthStreamingMode(payload.length); // still no IO
  InputStream in;
  OutputStream out;
  int http_status;
  try {
    // this opens a connection, then sends POST & headers.
    out = conn.getOutputStream(); 

    // At this point, the client may already have received a 4xx
    //  or 5xx error, but don’t you dare call getResponseCode()
    //  or HUC will hit you with an exception.
  } catch (IOException e) {
    // some horrible networking error, don't try any methods on "conn".
  }
  try {
  
    // now we can send the body
    out.write(payload);

    // NOW you can look at the status.
    http_status = conn.getResponseCode();
    if (http_status / 100 != 2) {
      // Dear me, dear me
    }
  } catch (IOException e) {
    // Network-IO lions and tigers and bears! Oh my!
  }

  // presumably you’re interested in the response body
  try {

    // Unlike the identical call in the previous example, this
    //  provokes no network IO.
    in = conn.getInputStream(); 
    try_reading(in);
  } catch (IOException e) {
    // Network-IO lions and tigers and bears! Oh my!
  } finally {
    conn.disconnect(); // Let's practice good hygiene
  }
}

If you want a look at real working code, check out getOrPost() in AppEngineClient.java.

I’m this literal-minded guy who likes HTTP; I’d have been happier if the methods lined up a little closer with the actual client/server conversation. But hey, it seems to work.

By the way, I used vogar to run the same little test program on a JVM and on my phone’s Dalvik. HUC’s behavior seems identical; and I recommend vogar, very handy.

Posted at 23:17

W3C News: XMLHttpRequest Level 2 Draft Published

The Web Applications Working Group has published a Working Draft of XMLHttpRequest Level 2. The XMLHttpRequest specification defines an API that provides scripted client functionality for transferring data between a client and a server. Learn more about the Rich Web Client Activity.

Posted at 21:30

Tim Bray: Not Piracy

Sites all over the Internet are going dark to show that they object to legislation currently before the US Congress. I’m not American but these words are coming at you from a server in LA, so I guess I can weigh in. I’ll limit my discussion to one word, “Piracy”; what the “P” stands for in SOPA.

Piracy is when people use violence, or the threat of it, to transfer your possessions to themselves (after which you no longer have them), place you in captivity in pursuit of a ransom, and in many cases inflict death on you as a side-effect of their business model. This is a very real problem right now in certain parts of the world, and I have a lot of sympathy with the 18th-century view that summary execution is an appropriate approach to dealing with it; as a backup, of course, to the traditional tactic of blowing their vessels to bits with really big guns.

The activity that the legislation tries (futilely) to prevent is when people who are too cheap or too broke to pay small amounts of money for digital goods under the (often stupid, insulting, and clumsy) terms and conditions imposed by media companies resort to the use of sleazy, inconvenient, illicit distributors to get at those digital goods without paying.

This is not piracy.

Maybe it’s a problem. I personally don’t think so, in the era of iTunes and eBooks and Google Music, but that’s a complex argument around business models and intellectual-property regulation, and I understand that reasonable people can reasonably disagree with me. It is a common political technique to place one’s opponents at a disadvantage by associating them with a damaging label, and that’s what “piracy” is being used for in this context.

But it’s not piracy.

In the big picture, the proposed legislation will be ineffective at preventing sleazebags and broke undergrads from watching movies without paying for them, but it will significantly damage the usefulness of the Internet and provide extremely dangerous openings for censorship and for incumbent oligopolists to resist useful disruption. History teaches us that these openings will be exploited to the maximum extent possible, and in the case of this legislation the maximum extent is frightening.

Dear America: Please don’t do it.

And anyone who claims that unauthorized transmission of bits is analogous to piracy is at least a liar and is deeply disrespectful of the people who are suffering the effects of theft, kidnapping, and murder right now today in the Indian Ocean. They deserve your contempt, and they have mine.

Posted at 16:18

W3C News: Workshop Report: Linked Enterprise Data Workshop

W3C today published the final report of the Linked Enterprise Data Workshop, hosted by W3C on the 6-7 December in Cambridge, MA, USA. This workshop provided a way for the community to meet and discuss some of the challenges when deploying application relying on the principles of Linked Data. The presentations covered many different topics, ranging from the benefits a set of additional conventions would bring to specific technical issues such as the challenges of dealing with the reality that URLs do change sometimes, as well as the need for a more robust security model, and specific gaps in the current set of standards.

Participants of the Workshop agreed that W3C should create a Working Group to define a “Linked Data Platform”. This is expected to be an enumeration of specifications which constitute Linked Data, with some small additional specifications to cover specific functionality such as pagination. We anticipate a draft charter will be available in the coming weeks.

Posted at 14:15

W3C News: W3C Invites Implementations of Navigation Timing

The Web Performance Working Group invites implementation of the Candidate Recommendation of Navigation Timing. User latency is an important quality benchmark for Web Applications. While JavaScript-based mechanisms can provide comprehensive instrumentation for user latency measurements within an application, in many cases, they are unable to provide a complete end-to-end latency picture. To address the need for complete information on user experience, this document introduces the PerformanceTiming interfaces. This interface allows JavaScript mechanisms to provide complete client-side latency measurements within applications. Learn more about the Rich Web Client Activity.

Posted at 08:34

W3C News: Last Call: CSS Basic User Interface Module Level 3 (CSS3 UI)

The Cascading Style Sheets (CSS) Working Group has published a Last Call Working Draft of CSS Basic User Interface Module Level 3 (CSS3 UI). The Cascading Style Sheets (CSS) is a language for describing the rendering of HTML and XML documents on screen, on paper, in speech, etc. It uses various selectors, properties and values to style basic user interface elements in a document. This specification describes those user interface related selectors, properties and values that are proposed for CSS level 3 to style HTML and XML (including XHTML and XForms). It includes and extends user interface related features from the selectors, properties and values of CSS level 2 revision 1 and Selectors specifications. Comments are welcome through 14 February. Learn more about the Style Activity.

Posted at 08:12

January 17

W3C News: Report: Social Business - Next Steps after the Jam

W3C Jam image W3C today published the final report of the Social Business Jam. The report authors recommended starting a W3C Social Business Community Group to evolve social standards around customer-driven use-cases. Participants in the the event, which took place last November using IBM's Collaboration Jam platform, explored how standards around social networking, such as those developed by the Federated Social Web XG, could lead to increased innovation throughout the business cycle. Over 1000 participants discussed topics such as identity management, mobile, attention, business processes, integration, and metrics. W3C invites people to join the Social Business Community Group.

Posted at 15:59

January 16

Michael Kay: Goodbye; see you elsewhere

With BlogHarbor closing, I've transferred all blog posts to a new location at

http://dev.saxonica.com/blog/mike

I haven't posted here for a while because I had no idea whether the articles would survive; but I will now resume writing at the new location.

Comments didn't transfer automatically, unfortunately, so some of your gems will have been lost. I've transferred some "by hand" but it was too laborious to do it for everything.

If anyone wants advice on mioving from BlogHarbor to MovableType: this is how I did it. Standard export from BlogHarbor; custom XSLT stylesheet to convert into WordPress WXR format (a variant of RSS), then import the WXR into MovableType, then update the dates of all the old posts by hand because the dates on the import file were ignored.

Posted at 18:36

Norm Walsh: The short-form week of 9–15 Jan 2012

The week in review, 140 characters at a time.

Posted at 13:50

Tim Bray: Grey and Red

The grey is one of Vancouver’s rare snowy evenings. The red is the new illuminated circumference of BC Place, our venue for football and big-name rockers and the Home/Boat show. Its new look, with illumination and slanted retaining piers, has definitely added to the visual appeal downtown.

BC Place in a snowstorm

Photogeeks may have already noticed that part of the grey is grey-as-in-grain, the result of pushing the Canon S90 to ISO1600, which is arguably outside the reach of its design goals. But in this case it degraded gracefully.

Posted at 06:17

January 15

Micah Dubinko: The ultimate breakfast smoothie

I’ve used this same recipe for three things: weight loss, after-exercise protein, and sore-teeth liquid diet. It’s great.

1 cup 2% milk

1 cup Dannon Fit & Light vanilla yogurt

1 scoop Syntha-6 protein powder (banana is great)

Mix.

This yields 450 calories with a whopping 39g of protein, 48g of carb (but only 30g of that simple sugars), 11g of fat, and 5g of fiber.

You could live off 3 or 4 of these a day. (and I have)

Posted at 19:09

Micah Dubinko: Five iOS keyboard tips you probably didn’t know

Check out these tips. The article talks about iPad, but they work on iPhone too, even an old 3G.

One one hand, it shows the intense amount of careful thought Apple puts into the user experience. But on the other hand, it highlights the discovery problem. I know people who have been using iOS since before it was called iOS, and still didn’t know about these. How do you put these kinds of finishing touches into a product and make sure the target audience can find out about them? -m

Posted at 17:21

January 14

Micah Dubinko: Call a Spade a Spade

A cautionary tale of language from Ted Nelson:

We might call a common or garden spade–

Spades, not words, should be used for shoveling. But words should help us unearth the truth.

–Computer Lib (1974), Theodor Nelson, p44

Posted at 20:45

Tim Bray: Skyrim

I bought it for the houseguests over Christmas, got mildly hooked, took a character to level 17, but that’s it, I’m bored.

Tech & production

The achievement is stupendous. The world is vast, open, and visually compelling in a way not remotely equaled by anything I’ve seen. In Skyrim you’ll regularly find yourself pausing just to admire a view.

The combat graphics are believable and fun; watching the slo-mo of your character leaping onto a dragon’s head to plant the two-handed axe has gotta make you smile.

Also, the quests and dangers are (mostly) nicely scaled so that the ones you find are within your reach, and the puzzles are (mostly) soluble given the evidence immediately to hand.

Art & Aesthetics

Those who still claim games cannot partake of the arts really need to get with this millenium; I feel no discomfort inserting this header.

For me, the best part was the game’s measured, unforced, even slow at times, pace. Yes, you will spend the next half hour working your way across rough, craggy, and very beautiful countryside to get where you’re going. And yes, you will stand still and listen to a lengthy monologue from some bandit chief, or maybe Paarthurnax.

The game will throw enough interesting side-quests into the cross-country trek, and interesting back-story into the monologue, that you won’t be bored. It may not equal the heights of a long single-take by Antonioni or Tarkovsky, but it is an all-too-rare appreciation of the virtues of sinking into the flow of elapsed time, of just Being Here Now.

Skyrim

Also, I have to tip my hat to the visual virtuosity of Blackreach; I was nodding my head in admiration as I ran around killing things.

Failures

There are two, such that I’m not playing this thing for more than a couple of weeks. First, the big bet is on breadth and scale, not intensity. The breadth and scale are amazing, but there’s no single story arc that will glue you to the keyboard the way that fighting your way into Diablo’s (or a sibling’s) lair will, or (in this century) matching wits with GLaDOS.

Maybe one day someone will build an immersive open-world environment that competes successfully with relatively linear author-has-the-steering-wheel storytelling. Me, I’m a storyteller and can’t imagine where you’d start on that project; but I hope someone is. Hard to see how you’d do it cheaply though.

Having said that, Skyrim’s big problem is loneliness. I want some buddies there with me, so my tank has a healer and an archer along for support while I’m mano a mano with Alduin. Also so we can crack profane cynical jokes. The next step is screamingly obvious; combining this sort of scale and visual intensity with real people having fun together.

Strategy and Tactics

Up till now, in role-playing contexts I’ve tended to build “glass cannons”; characters with overwhelming attacking power that crumple if someone gets close enough to touch. I can’t remember having made a deliberate policy choice; perhaps I’m still influenced by the Amazon having been clearly the best Diablo II character.

This time, on a whim, I built the purest of pure tanks: a Nord specializing in two-hand axes. If I were doing it again the only thing I might change is swords not axes.

But it works pretty well. You pour almost all your points into Health and a few into Stamina, you find a Companion who’s got high-octane ranged attacks (I recommend Marcurio), you put most perks into Two-handed, with a few in Heavy Armor and maybe Blocking.

You totally have to do the Greybeards quest and get the Unrelenting Force shout.

There are very few enemies who can survive the combination of that shout, well-placed, followed up by a few two-handed power attacks, while your companion blasts them from a distance. This notably includes most of the ordinary dragons you’ll encounter as you quest around.

My Exit

I ran into some boss who pwned me the first couple of times in, so I hit the wiki and read up on a few strategies to get past him, and realized they’d take a half-hour each and be boring. I play games to escape boredom.

The release price of Skyrim feels a little high to me, and the quality a little low, for a single player. For a houseload of houseguests, it was just fine.

But I do suspect that some of the highest-impact games of the future are going to have learned its lessons of scale and pace.

Posted at 08:35

January 12

W3C News: W3C Invites Implementations of Multimodal Architecture and Interfaces

The Multimodal Interaction Working Group invites implementation of the Candidate Recommendation of Multimodal Architecture and Interfaces. The specification describes a loosely coupled architecture for multimodal user interfaces, which allows for co-resident and distributed implementations, and focuses on the role of markup and scripting, and the use of well defined interfaces between its constituents. Learn more about the Multimodal Interaction Activity.

Posted at 15:57

W3C News: Two Drafts Published by the HTML Data Task Force

The HTML Data Task Force of the Semantic Web Interest Group has published two documents today:

Both documents are Working Drafts, with the goal of publishing a final version as Interest Group Notes. Comments and feedbacks are welcome; please send them to the public-html-data-tf@w3.org mailing list.

Posted at 15:42

W3C News: Last Call: CSS Image Values and Replaced Content Module Level 3

The Cascading Style Sheets (CSS) Working Group has published a Last Call Working Draft of CSS Image Values and Replaced Content Module Level 3. CSS is a language for describing the rendering of structured documents (such as HTML and XML) on screen, on paper, in speech, etc. This module contains the features of CSS level 3 relating to the <image> type and replaced elements. It includes and extends the functionality of CSS level 2, which builds on CSS level 1. The main extensions compared to level 2 are the generalization of the <url> type to the <image> type, several additions to the ‘<image>’ type, a generic sizing algorithm for images and other replaced content in CSS, and several properties controlling the interaction of replaced elements and CSS's layout models. Comments are welcome through 07 February. Learn more about the Style Activity.

Posted at 15:13

Dimitre Novatchev: The set datatype implemented in XPath 3.0

In my previous two posts I introduced the binary search tree datatype, implemented in XPath 3.0. In most cases the binary search tree operations find, insert and delete have efficiency of O(log(d)) and the print/serialize operation is O(N*log(d)), where d is the maximum depth of the tree and N is the total number of tree nodes.

Today, I will show a set implemented using a binary search tree. This implementation choice means that the set datatype operations have the same efficiency as the corresponding binary search tree operations. This implementation choice also results in the constraint that the set of values for any kind of item, that we want to put in such set, must have total ordering. In other words, the standard (or user-defined) lt operation must be applicable on any pair of items belonging to the set.

Here is the code:

import module namespace set-impl =“http://fxsl.sf.net/data/set/implementation”
              at “implementations/set-implementation-as-binary-search-tree.xquery”;
             

declare namespace set =http://fxsl.sf.net/data/set

 

(:
  Create an empty set — (0×2205)
 :)
declare functionset:set()
         as
function() as item()*

{
  
set-impl:set()
};

declare functionset:empty($pSet as function() as item()*)
         as xs:boolean
{
  
set-impl:empty($
pSet)
};

declare functionset:size($pSet as function() as item()*)
         as xs:integer
{
  
set-impl:size($
pSet)
};

declare function set:equals
            (
$pSet1 as function() as item()*
,
            
$pSet2 as function() as item()*

            )
         as xs:boolean
{
   
set-impl:equals($pSet1, $pSet2)
};

declare function set:add
     (
$pSet as function() as item()*
,
     
$pItem as item
()
     )
         as
function() as item()*

{
  
set-impl:add($pSet, $pItem)
};

declare functionset:data($pSet as function() as item()*

)
         as
item()*

{
  
set-impl:data($pSet)
};

  The Set Theory belongs to (member of)   (0x22F2)
  operation
 :)
declare function set:member
     ($pItem as item()?,
     
$pSet as function() as item()*

      )
         as xs:boolean
{
  
set-impl:member($pItem, $pSet)
};

(:
 The Set Theory does not belong to (not member of)  (0×2209)
  operation
 :)

declare function set:not-member
     (
$pItem as item()?
,
     
$pSet as function() as item()*

      )
         as xs:boolean
{
  
not(set:member($pItem, $pSet))
};

declare function set:remove
     (
$pSet as function() as item()*
,
     
$pItem as item
()
     )
         as
function() as item()*

{
  
set-impl:remove($pSet[1], $pItem)
};

(:
  The classic set-theory U operation — union of two sets
:)
declare function set:U
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
  
set-impl:U($pSet1, $pSet2)
};

(:
  The classic set-theory set-difference operation \

:)
declare function set:diff
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
  
set-impl:diff($pSet1, $pSet2)
};

(: 
The classic set-theory ∩  (∩) /\
  set-intersection operation
:)
declare function set:intersect
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
 
set-impl:intersect($pSet1, $pSet2)
};
(:
The classic set-theory symmetric-difference operation
:)
declare function set:sym-diff
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
  
set-impl:sym-diff($pSet1, $pSet2)
};

(: 
The classic set-theory set (‘⊇’) operation
:)
declare function set:includes
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as xs:boolean
{
 
set-impl:includes($pSet1, $pSet2)
};

declare function set:print
     (
$pSet as function() as item()*
)
         as
element()?

{
 
set-impl:print($pSet)
};

declare function set:serialize
     (
$pSet as function() as item()*
)
         as
element()?

{
 
set-impl:serialize($pSet)
};

declare function set:deserialize
     (
$pSerialization as element()?
)
         as
function() as item()*

{
 
set-impl:deserialize($pSerialization)
};

Now, you would be right that this code shows very little, if anything, at all. However, it has at least two virtues:

Having said that, here is the “true” implementation, which is contained in the file “implementations/set-implementation-as-binary-search-tree.xquery”.

This is a separate XQuery module with its own namespace. It imports and uses the module that implements the binary search tree:

module namespace set-impl =“http://fxsl.sf.net/data/set/implementation”
              at “../../BinaryTree/bintreeModule.xquery”;

import module namespace tree =http://fxsl.sf.net/data/bintree;

The set implementation module “contains” a binary search tree. The “empty set” is nothing else than a zero-argument function that returns an empty tree:

(:
  Create an empty set — (0×2205)
 :)
declare functionset-impl:set()
         as
function() as item()*

{
  
function() {tree:tree()}   (: underlying bintree :)
};

Many of the basic set operations have their binary search tree counterparts. Here is what it means in our implementation for a set to be “empty” and how we compute the size of a set:

declare functionset-impl:empty($pSet as function() as item()*)
         as xs:boolean
{
  
tree:empty($pSet[1
]())
};

 

declare functionset-impl:size($pSet as function() as item()*)
         as xs:integer
{
  
tree:size($pSet[1
]())
};

Two sets are equal exactly when they have the same size and the sequences of their atomized values are deep-equal:

declare function set-impl:equals
            (
$pSet1 as function() as item()*
,
            
$pSet2 as function() as item()*

            )
         as xs:boolean
{
   
set-impl:size($pSet1) eqset-impl:size($pSet1)
  
and

    deep-equal(set-impl:data($pSet1), set-impl:data($pSet2))
};

Here is how we add an item to a set:

declare function set-impl:add
     (
$pSet as function() as item()*
,
     
$pItem as item
()
     )
         as
function() as item()*

{
  
function() {tree:insert($pSet[1](), $pItem)}
};

and how we atomize a set:

declare functionset-impl:data($pSet as function() as item()*)
         as
item()*

{
  
tree:data($pSet[1]())
};

When is an item member of a set:

(:
  The Set Theory belongs to (member of)   (0x22F2)
  operation
 :)
declare function set-impl:member
     (
$pItem as item()?
,
     
$pSet as function() as item()*

      )
         as xs:boolean
{
  
tree:contains($pSet[1](), $pItem)
};

and when it isn’t a member of a set:

(:
  The Set Theory does not belong to (not member of)   (0×2209)
  operation
 :)

declare function set-impl:not-member
     (
$pItem as item()?
,
     
$pSet as function() as item()*

      )
         as xs:boolean
{
  
not(set-impl:member($pItem, $pSet))
};

This is how we remove an item from a set:

declare function set-impl:remove
     (
$pSet as function() as item()*
,
     
$pItem as item
()
     )
         as
function() as item()*

{
  
function() {tree:deleteNode($pSet[1](), $pItem)}
};

The classic set theory U (union) operation returns the union of two sets. Making use of the new standard XPath 3.0 higher order function fold-left(), we add all items from the smaller of the two sets to the bigger, thus performing only the minimal possible number of add operations:

(:
  The classic set-theory U operation — union of two sets
:)
declare function set-impl:U
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
  
let$vBiggerSet :=
          
if(set-impl:size($pSet1) geset-impl:size($
pSet2))
            
then$
pSet1
            
else$
pSet2,
      
$vSmallerSet :=

           if(not(set-impl:size($pSet1) geset-impl:size($pSet2)))
            
then$
pSet1
            
else$
pSet2
   
return

       fold-left(set-impl:add#2, $vBiggerSet, set-impl:data($vSmallerSet))
};

Similarly, the classic set theory \ (set difference) operation:

(:
  The classic set-theory set-difference operation \
:)
declare function set-impl:diff
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
 
fold-left(set-impl:remove#2, $pSet1, set-impl:data($pSet2))
};

And the classic set theory  intersect operation:

(:
  The classic set-theory ∩  (∩) /\
  set-intersection operation
:)
declare function set-impl:intersect
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
  
let$vBiggerSet :=
          
if(set-impl:size($pSet1) geset-impl:size($
pSet2))
            
then$
pSet1
            
else$
pSet2,
      
$vSmallerSet :=

           if(not(set-impl:size($pSet1) geset-impl:size($pSet2)))
            
then$
pSet1
            
else$
pSet2,
      
$to-be-removed :=

          
filter(set-impl:not-member(?, $
vBiggerSet),
                     
set-impl:data($
vSmallerSet)
                     )
   
return

       fold-left(set-impl:remove#2, $vSmallerSet, $to-be-removed)
};

Two more set theory operations – symmetric difference:

(:
  The classic set-theory symmetric-difference operation
:)
declare function set-impl:sym-diff
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as
function() as item()*
{
 
set-impl:U(set-impl:diff($pSet1, $pSet2), set-impl:diff($pSet2, $pSet1))
};

and (non-strict) set inclusion:

(:
  The classic set-theory set (‘⊇’) operation
:)
declare function set-impl:includes
     (
$pSet1 as function() as item()*
,
     
$pSet2 as function() as item()*

     )
         as xs:boolean
{
 
empty(set-impl:data($pSet2)[set-impl:not-member(.,$pSet1)])
};

And finally, three infrastructural operations: print(), serialize() and deserialize() :

declare function set-impl:print
     (
$pSet as function() as item()*
)
         as
element()?

{
 
tree:print($pSet[1]())
};
 

declare function set-impl:serialize
     (
$pSet as function() as item()*
)
         as
element()?

{
 
set-impl:print($pSet)
};

declare function set-impl:deserialize
     (
$pSerialization as element()?
)
         as
function() as item()*

{
 
function() {tree:deserialize($pSerialization)}
};

Here is a test of our set implementation:

let$set0 :=set:add(set:set(), 2),
    
$set1 :=set:add(set:add(set:add(set:set(), 10), 5), 17
),
    
$set2 :=set:remove($set1, 5
),
    
$set3 :=set:remove($set1, 12
),
    
$set4 :=set:add(set:set(), 2
),
    
$set4 :=set:add(set:add(set:add(set:set(), 8), 4), 9
),
    
$set5 :=set:add(set:add(set:add(set:set(), 17), 10), 19
)
 
return

    (
           
‘ set:empty(set:set()): ‘,
             
set:empty(set:set
()),
             
‘ set:size(set:set()): ‘
,
             
set:size(set:set
()),
             
‘ set:size($set0): ‘
,
             
set:size($
set0),
             
‘ set:size($set1): ‘
,
             
set:size($
set1),
             
‘ set:data($set1): ‘
,
             
set:data($
set1),
             
‘ set:member(10,$set1): ‘
,
             
set:member(10,$
set1),
             
‘ set:member(17,$set1): ‘
,
             
set:member(17,$
set1),
             
‘ set:member(5,$set1): ‘
,
             
set:member(5,$
set1),
             
‘ set:member(2,$set1): ‘
,
             
set:member(2,$
set1),
             
‘ set:member(15,$set1): ‘
,
             
set:member(15,$
set1),
             
‘ set:data($set2): ‘
,
             
set:data($
set2),
             
‘ set:data($set3): ‘
,
             
set:data($
set3),
             
‘ set:data($set4): ‘
,
             
set:data($
set4),
             
‘ set:data(set:U($set1,$set4)): ‘
,
             
set:data(set:U($set1,$
set4)),
             
‘ set:print(set:U($set1,$set4)): ‘
,
             
set:print(set:U($set1,$
set4)),
             
‘ set:print(set:U($set4,$set1)): ‘
,
             
set:print(set:U($set4,$
set1)),
             
‘ set:print(set:U($set1,$set2)): ‘
,
             
set:print(set:U($set1,$
set2)),
             
‘ set:equals($set1, set:U($set1,$set2)): ‘
,
             
set:equals($set1, set:U($set1,$
set2)),
             
‘ set:data($set1): ‘
,
             
set:data($
set1),
             
‘ set:data($set4): ‘
,
             
set:data($
set4),
             
‘ set:data(set:U($set1,$set4)): ‘
,
             
set:data(set:U($set1,$
set4)),
             
‘ set:print(set:U($set1,$set4)): ‘
,
             
set:print(set:U($set1,$
set4)),
             
‘ set:data($set1): ‘
,
             
set:data($
set1),
             
‘ set:data($set2): ‘
,
             
set:data($
set2),
             
‘ set:data(set:diff($set1,$set2)): ‘
,
             
set:data(set:diff($set1,$
set2)),
             
‘ set:print(tree:print(set:diff($set1,$set2)): ‘
,
             
set:print(set:diff($set1,$
set2)),
             
‘ set:data($set1): ‘
,
             
set:data($
set1),
             
‘ set:data($set2): ‘
,
             
set:data($
set2),
             
‘ set:data(set:intersect($set1, $set2)): ‘
,
  
set:data(set:intersect($set1, $
set2)),
             
‘ set:data($set1): ‘
,
             
set:data($
set1),
             
‘ set:data($set5): ‘
,
             
set:data($
set5),
             
‘ set:data(set:sym-diff($set1, $set5)): ‘
,
  
set:data(set:sym-diff($set1, $
set5)),
             
‘ set:includes($set1, $set2): ‘
,
  
set:includes($set1, $
set2),
             
‘ set:includes($set1, $set5): ‘
,
  
set:includes($set1, $
set5),
             
‘ set:includes($set1, set:set()): ‘
,
  
set:includes($set1, set:set
()),
             
‘ set:member((), $set1): ‘
,
  
set:member((), $
set1),
             
‘ set:member((), set:set()): ‘
,
  
set:member((), set:set
()),
             
‘ set:serialize($set5): ‘
,
  
set:serialize($
set5),
             
‘ set:data(set:deserialize(set:serialize($set5))): ‘
,
  
set:data(set:deserialize(set:serialize($
set5))),
             
‘ set:size(set:deserialize(set:serialize($set5))): ‘
,
  
set:size(set:deserialize(set:serialize($
set5)))
             )

When this test is executed, the expected, correct results are produced:

set:empty(set:set()):  true
set:size(set:set()):  0
set:size($set0):  1
set:size($set1):  3
set:data($set1):  5 10 17
set:member(10,$set1):  true
set:member(17,$set1):  true
set:member(5,$set1):  true
set:member(2,$set1):  false
set:member(15,$set1):  false
set:data($set2):  10 17
set:data($set3):  5 10 17
set:data($set4):  4 8 9
set:data(set:U($set1,$set4)):  4 5 8 9 10 17
set:print(set:U($set1,$set4)):

<treeNode>

   <value>10</value>
   <treeNode>
      <value>5</value>
      <treeNode>
         <value>4</value>
      </treeNode>
      <treeNode>
         <value>8</value>
         <treeNode>
            <value>9</value>
         </treeNode>
      </treeNode>
   </treeNode>
   <treeNode>
      <value>17</value>
   </treeNode>
</treeNode>
set:print(set:U($set4,$set1)):
<treeNode>
   <value>8</value>
   <treeNode>
      <value>4</value>
      <treeNode>
         <value>5</value>
      </treeNode>
   </treeNode>
   <treeNode>
      <value>9</value>
      <treeNode>
         <value>10</value>
         <treeNode>
            <value>17</value>
         </treeNode>
      </treeNode>
   </treeNode>
</treeNode>
set:print(set:U($set1,$set2)):
<treeNode>
   <value>10</value>
   <treeNode>
      <value>5</value>
   </treeNode>
   <treeNode>
      <value>17</value>
   </treeNode>
</treeNode>
set:equals($set1, set:U($set1,$set2)):  true
set:data($set1):  5 10 17
set:data($set4):  4 8 9
set:data(set:U($set1,$set4)):  4 5 8 9 10 17
set:print(set:U($set1,$set4)):

<treeNode>
   <value>10</value>
   <treeNode>
      <value>5</value>
      <treeNode>
         <value>4</value>
      </treeNode>
      <treeNode>
         <value>8</value>
         <treeNode>
            <value>9</value>
         </treeNode>
      </treeNode>
   </treeNode>
   <treeNode>
      <value>17</value>
   </treeNode>
</treeNode>
set:data($set1):  5 10 17
set:data($set2):  10 17
set:data(set:diff($set1,$set2)):  5
set:print(tree:print(set:diff($set1,$set2)):

<treeNode>
   <value>5</value>
</treeNode>
set:data($set1):  5 10 17
set:data($set2):  10 17
set:data(set:intersect($set1, $set2)):  10 17
set:data($set1):  5 10 17
set:data($set5):  10 17 19
set:data(set:sym-diff($set1, $set5)):  5 19
set:includes($set1, $set2):  true
set:includes($set1, $set5):  false
set:includes($set1, set:set()):  true
set:member((), $set1):  true
set:member((), set:set()):  true
set:serialize($set5):
<treeNode>
   <value>17</value>
   <treeNode>
      <value>10</value>
   </treeNode>
   <treeNode>
      <value>19</value>
   </treeNode>
</treeNode>
set:data(set:deserialize(set:serialize($set5))): 10 17 19
set:size(set:deserialize(set:serialize($set5))):  3

In a few of my next posts I will show other interesting applications of the two new datatypes: the set and the binary search tree.

Useful utility: Zip Codes – Free zip code lookup and zip code database download.


Posted at 12:30

Tim Bray: Blue on Blue and Brown

A string of Christmas lights lingers into mid-January.

Blue on Blue and Brown

This is on Main Street, a part of Vancouver that I especially care for.

Posted at 02:55

January 11

W3C News: W3C Advisory Committee Elects Technical Architecture Group Participants

The W3C Advisory Committee has elected Robin Berjon (unaffiliated) and re-elected Henry Thompson (U. of Edinburgh) to the W3C Technical Architecture Group (TAG). W3C Director and TAG co-Chair Tim Berners-Lee also re-appointed Noah Mendelsohn (unaffiliated) and Jonathan Rees (Creative Commons). They join continuing participants Peter Linss (HP), Ashok Malhotra (Oracle), Larry Masinter (Adobe), and Jeni Tennison (unaffiliated). Many thanks to Dan Appelquist whose term ends this month. The mission of the TAG is to build consensus around principles of Web architecture and to interpret and clarify these principles when necessary, to resolve issues involving general Web architecture brought to the TAG, and to help coordinate cross-technology architecture developments inside and outside W3C. Read the TAG's December 2011 finding Identifying Application State and learn more about their public work plan.

Posted at 21:32

Tim Bray: Newsworthy Tablet Launches

I glanced at my newsreader yesterday and gave up almost instantly because it was full of irrelevant fluff from CES. Particularly irritating was a post over at The Verge announcing breathlessly that a vendor not worth mentioning here was... wait for it... planning to release a tablet in 2012! I twitterbitched: Dear Verge: “X plans to launch a tablet in 2012” is not a news story for ANY value of X. Which was clearly wrong; many people tweeted back values of X for which it would be newsworthy: Cracker Barrel, Macdonalds, NASA, Vladimir Putin, a lost Amazonian tribe, the US Government, Pfizer, and God via Moses. Any others?

Posted at 19:41

Dimitre Novatchev: Part 2: The Binary Search Data Structure with XPath 3.0, Deleting a node

In the first part of this post I presented a Binary Search Tree implemented in pure XPath 3.0. Some new nice features of XPath 3.0 were shown in action and other, still missing but very important features were identified and discussed.

The only operation that was missing was the deletion of a node from the tree. I show how to do this now.

This is the function that consumers will use:

(:
Delete from $pTree the node containing $pItem.
:)

declare function tree:deleteNode
         (
$pTree as (function() as item()*)*
,
         
$pItem as item
()
         )
        
as (function() as item()*)*

{
 
tree:deleteNode($pTree, $pItem, 1)
};

It simply delegates to a similar internal function that also requires a third argument – the depth of the (sub)tree on which the delete is performed. Why is the depth necessary? The answer will come later.

(:
Delete from $pTree the node containing $pItem.
$pTree has a depth of $pDepth (1 if not a subtree)
:)

declare function tree:deleteNode
         (
$pTree as (function() as item()*)*
,
         
$pItem as item
(),
         
$
pDepth as xs:integer
         )
        
as (function() as item()*)*

{
if(tree:empty($pTree))
  
then $
pTree
  
else

     let $top   := tree:top($pTree),
        
$left  := tree:left($
pTree),
        
$right := tree:right($
pTree)
     
return

         if($pItem eq $top)
          
then tree:deleteTopNode($pTree, $
pDepth)
          
else

            if($pItem lt $top)
             
then

                (
                 
function() {tree:top($pTree)},
                 
function
()
                  {
tree:deleteNode(tree:left($
pTree),
                                  
$
pItem,
                                  
$pDepth+1
)
                  },
                 
function() {tree:right($
pTree)}
                 )
             
else

                (
                 
function() {tree:top($pTree)},
                 
function() {tree:left($
pTree)},
                 
function
()
                  {
tree:deleteNode(tree:right($
pTree),
                                             
$
pItem,
                                             
$pDepth+1
)
                  }
                 )
};

We see that the deleteNode() function simply dispatches the operation to the left or right subtree and calls another function – deleteTopNode() – whenever the item to be deleted happens to be the value of the top node.

declare function tree:deleteTopNode
         (
$pTree as (function() as item()*)*
,
         
$
pDepth as xs:integer
         )
        
as (function() as item()*)*

{
 
let $left := tree:left($pTree),
     
$right := tree:right($
pTree)
   
return

      if(tree:empty($left) and tree:empty($right))
       
then tree:tree
()
       
else

         if(tree:empty($left) and not(tree:empty($right)))
          
then

             (
              
function() {tree:top($right)},
              
function() {tree:left($
right)},
              
function() {tree:right($
right)},
              
function() {tree:size($right) -1
}
              )
          
else

            if(not(tree:empty($left)) and tree:empty($right))
            
then

             (
              
function() {tree:top($left)},
              
function() {tree:left($
left)},
              
function() {tree:right($
left)},
              
function() {tree:size($left) -1
}
              )
            
else  (: both subtrees are non-empty :)

               if($pDepth mod 2 eq 0)
               
then

                  let $subtree := tree:right($pTree),
                     
$vItem := tree:top(tree:leftmost($
subtree)),
                     
$newSubtree :=

                         tree:deleteNode($subtree, $vItem, $pDepth+1)
                   
return

                      (function() {$vItem},
                      
function() {$
left},
                      
function() {$
newSubtree},
                      
function() {tree:size($pTree) -1
}
                       )
               
else

                  let $subtree := tree:left($pTree),
                     
$vItem := tree:top(tree:rightmost($
subtree)),
                     
$newSubtree:=

                         tree:deleteNode($subtree, $vItem, $pDepth+1)
                   
return

                      (function() {$vItem},
                      
function() {$
newSubtree},
                      
function() {$
right},
                      
function() {tree:size($pTree) -1
}
                       )
};

deleteTopNode() does the real deletion work. The operation is straightforward in the case when the tree is empty or either the left subtree or the right subtree is empty.

It becomes interesting when both subtrees are non-empty. In order to understand what the last 20 lines of this code mean, it is best to read a good source on the binary search tree delete operation.

In a few words:

Why is this different processing done, depending on the oddness of the depth of the subtree? If we always used the leftmost node of the right subtree, then a series of deletions would create a severely imbalanced (to the right) tree. Imbalanced trees lose the advantages of the binary search tree with search and insertions becoming of linear complexity (instead of O(log(N))  ) and sorting becoming O(N^2) instead of O(N*log(N)).

Thus, in order to avoid this deteriorating effect, we need to use with a pseudo-random frequency both the left and the right subtrees. In most cases this can be achieved simply by using the oddness of the depth of the tree, whose top node is to be replaced.

Below is the complete code of the Binary Search tree. Do note that I have added a new “property” to the tree datatype – “size”. Also, note the functions tree:leftmost() and tree:rightmost() – used by tree:deleteTopNode()

Another change is that now the second argument of tree:contains()   is of type  item()?   — that is, it can be empty. By definition, any tree contains the “empty item”.

Finally, there is a new pair of functions: tree:serialize() and   tree:deserialize() . The former is a synonym of  tree:print() and the latter loads the XML representation created by  tree:serialize() into a tree.

module namespace tree = “http://fxsl.sf.net/data/bintree”;

declare function tree:top
         (
$pTree as (function() as item()*)*
)
         as
item()?

{
if(empty($pTree))
  
then
()
  
else

     $pTree[1]()
};
 
 

 

declare function tree:left
         (
$pTree as (function() as item()*)*
)
        
as (function() as item()*)*

{
if(empty($pTree[2]))
then tree:tree
()
else

   $pTree[2]()
 
  
 

 

declare function tree:right
         (
$pTree as (function() as item()*)*
)
        
as (function() as item()*)*

{
if(empty($pTree[3]))
  
then tree:tree
()
  
else

     $pTree[3]()
};
  
declare function tree:size
         (
$pTree as (function() as item()*)*
)
         as xs:integer
{
if(empty($pTree[4
]))
  
then 0

   else
     $pTree[4]()
};
  
declare function tree:tree()
        
as (function() as item()*)+
{};
   (
    function() {()},   (: top() :)
    function() {()},   (: left() :)
    function() {()},   (: right() :)
    function() {0}     (: size() :)
   )
};
declare function tree:empty
         (
$pTree as (function() as item()*)*
)
         as xs:boolean
{
empty($pTree) or empty($pTree[1
]())
};

 declare function tree:contains
         (
$pTree as (function() as item()*)*,
         
$pItem as item()?
         )
         as xs:boolean
{
 
if(empty($pItem))
  
then true()
  
else
   
if(tree:empty($pTree))
     
then false()
     
else
       
let $top := tree:top($pTree)
        
return
            (
$pItem eq $top)
          
or
            (
$pItem lt $top
           
and
            
tree:contains(tree:left($pTree),$pItem)
             )
          
or
            (
$pItem gt $top
           
and
            
tree:contains(tree:right($pTree),$pItem)
             )
};

(:
Delete from $pTree the node containing $pItem.
:)
declare function tree:deleteNode
         (
$pTree as (function() as item()*)*
,
         
$pItem as item
()
         )
        
as (function() as item()*)*

{
 
tree:deleteNode($pTree, $pItem, 1)
};
declare function tree:deleteNode
         (
$pTree as (function() as item()*)*
,
         
$pItem as item
(),
         
$
pDepth as xs:integer
         )
        
as (function() as item()*)*

{
if(tree:empty($pTree))
  
then $
pTree
  
else

     let $top   := tree:top($pTree),
        
$left  := tree:left($
pTree),
        
$right := tree:right($
pTree)
     
return

         if($pItem eq $top)
          
then tree:deleteTopNode($pTree, $
pDepth)
          
else

            if($pItem lt $top)
             
then

                (
                 
function() {tree:top($pTree)},
                 
function
()
                  {
tree:deleteNode(tree:left($
pTree),
                                  
$
pItem,
                                  
$pDepth+1
)
                  },
                 
function() {tree:right($
pTree)}
                 )
             
else

                (
                 
function() {tree:top($pTree)},
                 
function() {tree:left($
pTree)},
                 
function
()
                  {
tree:deleteNode(tree:right($
pTree),
                                             
$
pItem,
                                            
$pDepth+1
)
                  }
                 )
};
 

declare function tree:deleteTopNode
         (
$pTree as (function() as item()*)*,
         
$pDepth as xs:integer
         )
        
as (function() as item()*)*
{
 
let $left := tree:left($pTree),
     
$right := tree:right($pTree)
   
return
     
if(tree:empty($left) and tree:empty($right))
       
then tree:tree()
       
else
        
if(tree:empty($left) and not(tree:empty($right)))
          
then
           
$right
          
else
           
if(not(tree:empty($left)) and tree:empty($right))
            
then
              
$left
            
else  (: both subtrees are non-empty :)
              
if($pDepth mod 2 eq 0)
               
then
                 
let $subtree := tree:right($pTree),
                     
$vItem := tree:top(tree:leftmost($subtree)),
                     
$newSubtree :=
                        
tree:deleteNode($subtree, $vItem, $pDepth+1)
                   
return
                      (
function() {$vItem},
                      
function() {$left},
                      
function() {$newSubtree},
                      
function() {tree:size($pTree) -1}
                       )
               
else
                 
let $subtree := tree:left($pTree),
                     
$vItem := tree:top(tree:rightmost($subtree)),
                     
$newSubtree:=
                        
tree:deleteNode($subtree, $vItem, $pDepth+1)
                   
return
                      (
function() {$vItem},
                      
function() {$newSubtree},
                      
function() {$right},
                      
function() {tree:size($pTree) -1}
                       )
};

 
(:
  Find/Return the leftmost node of the
  non-empty tree $pTree
:)
declare function tree:leftmost
         (
$pTree as (function() as item()*)+
)
        
as (function() as item()*)*

{
 
let $left := tree:left($pTree)
   
return

      if(tree:empty($left))
       
then $
pTree
       
else tree:leftmost($
left)
};
 

 

 
declare function tree:rightmost
         (
$pTree as (function() as item()*)+
)
        
as (function() as item()*)*

{
 
let $right := tree:right($pTree)
   
return

      if(tree:empty($right))
       
then $
pTree
       
else tree:rightmost($
right)
};
 declare function tree:insert
         (
$pTree as (function() as item()*)*
,
         
$pItem as item
()
         )
        
as (function() as item()*)+

{
  
if(tree:empty($pTree))
     
then

      (
      
function() {$pItem},        (: top()   :)
       function() {tree:tree()}, (: left()  :)
       function() {tree:tree()}, (: right() :)
       function() {1}                     (: size()  :)
       )
     
else
       if($pItem lt tree:top($pTree))
        
then

          (
          
function() {tree:top($pTree)},
          
function() {tree:insert(tree:left($pTree), $
pItem)},
          
function() {tree:right($
pTree)},
          
function() {tree:size($pTree)+1
}
           )
        
else

          if($pItem gt tree:top($pTree))
          
then

           (
           
function() {tree:top($pTree)},
           
function() {tree:left($
pTree)},
           
function() {tree:insert(tree:right($pTree), $
pItem)},
           
function() {tree:size($pTree)+1
}
           )
          
else

            $pTree
};
declare function tree:print
        (
$pTree as (function() as item()*)*
)
        as
element()?

{
  
if(not(tree:empty($pTree)))
   
then

     <treeNode>
      <value>{tree:top($pTree)}</value>
       {
       
tree:print(tree:left($pTree)),
       
tree:print(tree:right($
pTree))
       }
    
</treeNode>

    else ()
};
  

declare function tree:serialize
        (
$pTree as (function() as item()*)*)
        as
element()?
{
  
tree:print($pTree)
};

declare function tree:deserialize($pXml as element()?)
             
as (function() as item()*)*
{
 
if(empty($pXml))
 
then tree:tree()
 
else
   
let $left := tree:deserialize($pXml/treeNode[1]),
       
$right := tree:deserialize($pXml/treeNode[2])
    
return
      (
      
function() {$pXml/value/node()[1]},
      
function() {$left},
      
function() {$right},
      
function() {tree:size($left)+tree:size($right)+1}
      )
};

 

(: tree:data()
  Prints only the data — depth first.
   In effect this is sort() — quite good
   for random data.
:)
declare function tree:data
        (
$pTree as (function() as item()*)*
)
        as
item()*

{
if(not(tree:empty($pTree)))
  
then

    (
    
tree:data(tree:left($pTree)),
    
tree:top($
pTree),
    
tree:data(tree:right($
pTree))
     )
  
else
()
};

Now, let’s test just the deleteNode operation:

let $vBigTree :=
       tree:insert(tree:insert(tree:insert(tree:tree(),10),5),17),
   
$vBigTree2 :=

       tree:insert(tree:insert(tree:insert($vBigTree,3),8),14),
   
$vBigTree3 :=

       tree:insert(tree:insert(tree:insert($vBigTree2,20),6),9),
   
$vBigTree4 :=

       tree:insert(tree:insert(tree:insert($vBigTree3,12),15),7)
   
return

      (‘ tree:print($vBigTree4): ‘,
      
tree:print($
vBigTree4),
      
‘ tree:data($vBigTree4): ‘
,
      
tree:data($
vBigTree4),
      
‘ ====================================’
,
      
‘ tree:print(tree:deleteNode($vBigTree4, 7)): ‘
,
      
tree:print(tree:deleteNode($vBigTree4, 7
)),
      
‘ tree:data(tree:deleteNode($vBigTree4, 7)): ‘
,
      
tree:data(tree:deleteNode($vBigTree4, 7
)),
      
‘ ====================================’
,
      
‘ tree:print(tree:deleteNode($vBigTree4, 12)): ‘
,
      
tree:print(tree:deleteNode($vBigTree4, 12
)),
      
‘ tree:data(tree:deleteNode($vBigTree4, 12)): ‘
,
      
tree:data(tree:deleteNode($vBigTree4, 12
)),
      
‘ ====================================’
,
      
‘ tree:print(tree:deleteNode($vBigTree4, 6)): ‘
,
      
tree:print(tree:deleteNode($vBigTree4, 6
)),
      
‘ tree:data(tree:deleteNode($vBigTree4, 6)): ‘
,
      
tree:data(tree:deleteNode($vBigTree4, 6
)),
      
‘ ====================================’
,
      
‘ tree:print(tree:deleteNode($vBigTree4, 5)): ‘
,
      
tree:print(tree:deleteNode($vBigTree4, 5
)),
      
‘ tree:data(tree:deleteNode($vBigTree4, 5)): ‘
,
      
tree:data(tree:deleteNode($vBigTree4, 5
)),
      
‘ ====================================’
,
      
‘ tree:print(tree:deleteNode($vBigTree4, 10)): ‘
,
      
tree:print(tree:deleteNode($vBigTree4, 10
)),
      
‘ tree:data(tree:deleteNode($vBigTree4, 10)): ‘
,
      
tree:data(tree:deleteNode($vBigTree4, 10
))
      )

And here are the results:

tree:print($vBigTree4):

<treeNode>

      <value>10</value>

      <treeNode>

            <value>5</value>

            <treeNode>

                  <value>3</value>

            </treeNode>

            <treeNode>

                  <value>8</value>

                  <treeNode>

                        <value>6</value>

                        <treeNode>

                              <value>7</value>

                        </treeNode>

                  </treeNode>

                  <treeNode>

                        <value>9</value>

                  </treeNode>

            </treeNode>

      </treeNode>

      <treeNode>

            <value>17</value>

            <treeNode>

                  <value>14</value>

                  <treeNode>

                        <value>12</value>

                  </treeNode>

                  <treeNode>

                        <value>15</value>

                  </treeNode>

            </treeNode>

            <treeNode>

                  <value>20</value>

            </treeNode>

      </treeNode>

</treeNode>

tree:data($vBigTree4):

3 5 6 7 8 9 10 12 14 15 17 20

====================================

tree:print(tree:deleteNode($vBigTree4, 7)):

 

<treeNode>
  
<value>10</value>
  
<treeNode>
     
<value>5</value>
     
<treeNode>
        
<value>3</value>
     
</treeNode>
     
<treeNode>
        
<value>8</value>
        
<treeNode>
           
<value>6</value>
        
</treeNode>
        
<treeNode>
           
<value>9</value>
        
</treeNode>
     
</treeNode>
  
</treeNode>
  
<treeNode>
     
<value>17</value>
     
<treeNode>
        
<value>14</value>
        
<treeNode>
           
<value>12</value>
        
</treeNode>
        
<treeNode>
           
<value>15</value>
        
</treeNode>
     
</treeNode>
     
<treeNode>
        
<value>20</value>
     
</treeNode>
  
</treeNode>
</treeNode>

 

tree:data(tree:deleteNode($vBigTree4, 7)):

3 5 6 8 9 10 12 14 15 17 20

====================================

tree:print(tree:deleteNode($vBigTree4, 12)):

<treeNode>

      <value>10</value>

      <treeNode>

            <value>5</value>

            <treeNode>

                  <value>3</value>

            </treeNode>

            <treeNode>

                  <value>8</value>

                  <treeNode>

                        <value>6</value>

                        <treeNode>

                              <value>7</value>

                        </treeNode>

                  </treeNode>

                  <treeNode>

                        <value>9</value>

                  </treeNode>

            </treeNode>

      </treeNode>

      <treeNode>

            <value>17</value>

            <treeNode>

                  <value>14</value>

                  <treeNode>

                        <value>15</value>

                  </treeNode>

            </treeNode>

            <treeNode>

                  <value>20</value>

            </treeNode>

      </treeNode>

</treeNode>

tree:data(tree:deleteNode($vBigTree4, 12)):

3 5 6 7 8 9 10 14 15 17 20

====================================

tree:print(tree:deleteNode($vBigTree4, 6)):

<treeNode>

      <value>10</value>

      <treeNode>

            <value>5</value>

            <treeNode>

                  <value>3</value>

            </treeNode>

            <treeNode>

                  <value>8</value>

                  <treeNode>

                        <value>7</value>

                  </treeNode>

                  <treeNode>

                        <value>9</value>

                  </treeNode>

            </treeNode>

      </treeNode>

      <treeNode>

            <value>17</value>

            <treeNode>

                  <value>14</value>

                  <treeNode>

                        <value>12</value>

                  </treeNode>

                  <treeNode>

                        <value>15</value>

                  </treeNode>

            </treeNode>

            <treeNode>

                  <value>20</value>

            </treeNode>

      </treeNode>

</treeNode>

tree:data(tree:deleteNode($vBigTree4, 6)):

3 5 7 8 9 10 12 14 15 17 20

====================================

tree:print(tree:deleteNode($vBigTree4, 5)):

<treeNode>

      <value>10</value>

      <treeNode>

            <value>6</value>

            <treeNode>

                  <value>3</value>

            </treeNode>

            <treeNode>

                  <value>8</value>

                  <treeNode>

                        <value>7</value>

                  </treeNode>

                  <treeNode>

                        <value>9</value>

                  </treeNode>

            </treeNode>

      </treeNode>

      <treeNode>

            <value>17</value>

            <treeNode>

                  <value>14</value>

                  <treeNode>

                        <value>12</value>

                  </treeNode>

                  <treeNode>

                        <value>15</value>

                  </treeNode>

            </treeNode>

            <treeNode>

                  <value>20</value>

            </treeNode>

      </treeNode>

</treeNode>

tree:data(tree:deleteNode($vBigTree4, 5)):

3 6 7 8 9 10 12 14 15 17 20

====================================

tree:print(tree:deleteNode($vBigTree4, 10)):

<treeNode>

      <value>9</value>

      <treeNode>

            <value>5</value>

            <treeNode>

                  <value>3</value>

            </treeNode>

            <treeNode>

                  <value>8</value>

                  <treeNode>

                        <value>6</value>

                        <treeNode>

                              <value>7</value>

                        </treeNode>

                  </treeNode>

            </treeNode>

      </treeNode>

      <treeNode>

            <value>17</value>

            <treeNode>

                  <value>14</value>

                  <treeNode>

                        <value>12</value>

                  </treeNode>

                  <treeNode>

                        <value>15</value>

                  </treeNode>

            </treeNode>

            <treeNode>

                  <value>20</value>

            </treeNode>

      </treeNode>

</treeNode>

tree:data(tree:deleteNode($vBigTree4, 10)):

3 5 6 7 8 9 12 14 15 17 20

 

In my next posts I’ll show some of the most important applications of the Binary Search tree.




Posted at 10:30

January 10

W3C News: Last Call: WAI-ARIA 1.0 User Agent Implementation Guide

The Protocols and Formats Working Group has published a Last Call Working Draft of WAI-ARIA 1.0 User Agent Implementation Guide. This document describes how user agents should support keyboard navigation and respond to roles, states, and properties provided in Web content via WAI-ARIA. These features are used by authors creating accessible rich internet applications. Users often access the content using assistive technologies that rely on platform accessibility APIs to obtain and interact with information from the page. The WAI-ARIA User Agent Implementation Guide defines how implementations should expose content to accessibility APIs, helping to ensure that this information appears in a manner consistent with author intent. This document is part of the WAI-ARIA suite described in the WAI-ARIA Overview. Comments are welcome through 17 February. Learn more about the WAI Technical Activity.

Posted at 17:23

W3C News: First Drafts of Two Provenance Specifications Published

The Provenance Working Group has published two First Public Working Drafts:

Learn more about the Semantic Web Activity.

Posted at 17:16

Norm Walsh: XML Calabash 0.9.44

Announcing what I hope is the last pre-1.0 beta release of XML Calabash.

Posted at 15:10

January 09

Norm Walsh: The short-form week of 2–8 Jan 2012

The week in review, 140 characters at a time.

Posted at 16:45

Dimitre Novatchev: The Binary Search Tree Data Structure–having fun with XPath 3.0

For a long time I have wanted to play with XSLT 3.0 and XPath 3.0. Despite these being in their WD status, the new features are so powerful and overwhelming.

Take just these: Higher Order Functions and the ability to create new anonymous functions in XPath.

In my quest to accomplish what no one has ever done before with XPath I was helped by the existence of an early Saxon implementation – Saxon 9.3.04 offers these in its XQuery 3.0 implementation and the XSLT 3.0 implementation will hopefully be soon fully usable, after fixing a few bugs. The beautifully high-lighted XQuery code below was copied from oXygen 12.1 and pasted onto Word, then to Windows Live Writer.

I decided to start with something not too-complex (are you dreaming of a finger tree written entirely in XPath ?) and the Binary Search tree persistent functional data structure fits well this requirement.

So, let’s start:

As always:

declare namespace tree =http://fxsl.sf.net;

A tree is a sequence (triple) of functions. Here is the definition of an empty tree:

declare functiontree:tree()
        
as (function() as item()*)+

{ 
  (function() {()},   (: top() :)
    function() {()},   (: left() :)
    function() {()}    (: right() :)
  )
};
 

The first function produces the top of the tree, which is the value ( item() ) of its top node.

The second function produces the left sub-tree, which is another sequence (triple) of functions.

The third function produces the right sub-tree, which is another sequence (triple) of functions.

Do you see the problem with the type of the tree:tree()  function? What would happen if I accidentally returned only a pair of functions? Nothing! No static or runtime error would occur and I could spend a lot of time trying to find this simple error. Obviously, a tuple datatype would solve this problem completely.

Now, the three functions top(), left() and right() :

declare function

 tree:top
         (
$pTree as (function() as item()*)*
)
         as
item()?

{
 
if(empty($pTree))
  
then
()
  
else

     $pTree[1]()
};

 

declare function
tree:left
         (
$pTree as (function() as item()*)*
)
        
as (function() as item()*)*

{
 
if(empty($pTree[2]))
 
then
()
 
else

   $pTree[2]()
};
  
 
declare function
tree:right
         (
$pTree as (function() as item()*)*
)
        
as (function() as item()*)*

{
 
if(empty($pTree[3]))
  
then
()
  
else

     $pTree[3]()
};

A tree is empty when:

declare function tree:empty
         (
$pTree as (function() as item()*)*
)
         as xs:boolean
{
 
empty($pTree) orempty($pTree[1
]())
};
 

When does a tree contain an item?

declare function tree:contains
         ($pTree as (function() as item()*)*
,
          $pItem as item
()
         )
         as xs:boolean
{
 if(tree:empty($
pTree))
   then false
()
   else

     let $top := tree:top($pTree)
      return

         ($pItem eq $top)
        or

         ($pItem lt $top
         and

          tree:contains(tree:left($pTree),$pItem)
          )
        or

         ($pItem gt $top
         and

          tree:contains(tree:right($pTree),$pItem)
          )
};

How to add a new node to a tree?

declare function tree:insert
         ($pTree as (function() as item()*)*
,
          $pItem as item
()
         )
         as (function() as item()*)+

{
  
if(tree:empty($pTree))
      then

      (
      
function() {$pItem},   (: top()   :)
       function() {tree:tree()},         (: left()  :)
       function() {tree:tree()}          (: right() :)
       )
     
else
       if($pItem lt tree:top($pTree))
         then

          (
          
function() {tree:top($pTree)},
           function() {tree:insert(tree:left($pTree), $
pItem)},
           function() {tree:right($
pTree)}
           )
         else

          if($pItem gt tree:top($pTree))
           then

           (
           
function() {tree:top($pTree)},
            function() {tree:left($
pTree)},
            function() {tree:insert(tree:right($pTree), $
pItem)}
           )
           else

            $pTree
};

How to present a tree?

declare function tree:print
        ($pTree as (function() as item()*)*
)
        as element()?

{
  if(not(tree:empty($pTree)))
     then

      <treeNode>
           <value>{tree:top($pTree)}</value>
           {
           
tree:print(tree:left($pTree)),
            tree:print(tree:right($
pTree))
           }
     </treeNode>

     else ()
};

How to atomize a tree (and get a good sorting function as a side effect)?

(: tree:data()
  Prints only the data — depth first.
   In effect this is sort() — quite good
   for random data.
 :)
declare function tree:data
        ($pTree as (function() as item()*)*
)
        as item()*

{
  
if(not(tree:empty($pTree)))
     then

     (
     
tree:data(tree:left($pTree)),
      data(tree:top($
pTree)),
      tree:data(tree:right($
pTree))
      )
     else
()
};

How to return a subtree and its depth?

declare function tree:findSubtree
         ($pTree as (function() as item()*)*
,
          $pItem as item
()
         )
         as (function() as item()*)*

{
 
if(tree:empty($pTree))
   then (tree:tree(), function() as item()* {-1
})
   else

     let $depth := 1,
         $top := tree:top($
pTree)
       return

         if($pItem eq $top)
           then ($pTree,function() as item()* {$
depth})
           else

             if($pItem lt $top)
               then

                 let $lsubtree
                       := tree:findSubtree(tree:left($pTree),$
pItem),
                     $ldepth := $lsubtree[4
]()
                   return

                     if($ldepth eq -1)
                       then $
lsubtree
                       else

                         (subsequence($lsubtree,1,3),
                          function() as item()* {1+$
ldepth}
                          )
               else

                 let $rsubtree
                       := tree:findSubtree(tree:right($pTree),$
pItem),
                     $rdepth := $rsubtree[4
]()
                   return

                     if($rdepth eq -1)
                       then $
rsubtree
                       else

                         (subsequence($rsubtree,1,3),
                          function() as item()* {1+$
rdepth}
                          )

};

Finally, lets see how all this executes together:

let $vEmptyTree := tree:tree(),
    $vFilledTree := tree:insert($vEmptyTree,5
)  ,
    $vFilledTree2 := tree:insert($vFilledTree,3
),  
    $vFilledTree3 := tree:insert($vFilledTree2,7
),
    $vFilledTree4 := tree:insert($vFilledTree3,1
),
    $vFilledTree5 := tree:insert($vFilledTree4,9
)
    return

      (tree:print($vFilledTree5),
       ‘ tree:contains($vFilledTree5,1): ‘
,
       tree:contains($vFilledTree5,1
),
       ‘ tree:contains($vFilledTree5,9): ‘
,
       tree:contains($vFilledTree5,9
),
       ‘ tree:contains($vFilledTree5,2): ‘
,
       tree:contains($vFilledTree5,2
),
       ‘ tree:contains($vFilledTree5,11): ‘
,
       tree:contains($vFilledTree5,11
),
       ‘ tree:findSubtree($vFilledTree5,9)[4](): ‘
,
       tree:findSubtree($vFilledTree5,9)[4
](),
       ‘ tree:findSubtree($vFilledTree5,1)[4](): ‘
,
       tree:findSubtree($vFilledTree5,1)[4
](),
       ‘ tree:findSubtree($vFilledTree5,3)[4](): ‘
,
       tree:findSubtree($vFilledTree5,3)[4
](),
       ‘ tree:findSubtree($vFilledTree5,7)[4](): ‘
,
       tree:findSubtree($vFilledTree5,7)[4
](),
       ‘ tree:findSubtree($vFilledTree5,5)[4](): ‘
,
       tree:findSubtree($vFilledTree5,5)[4
](),
       ‘ tree:findSubtree($vFilledTree5,12)[4](): ‘
,
       tree:findSubtree($vFilledTree5,12)[4
](),
       ‘ tree:data($vFilledTree5): ‘
,
       tree:data($
vFilledTree5)
      )

And the result:

<treeNode>
   <value>5</value>
   <treeNode>
      <value>3</value>
      <treeNode>
         <value>1</value>
      </treeNode>
   </treeNode>
   <treeNode>
      <value>7</value>
      <treeNode>
         <value>9</value>
      </treeNode>
   </treeNode>
</treeNode>
tree:contains($vFilledTree5,1):  true
tree:contains($vFilledTree5,9):  true
tree:contains($vFilledTree5,2):  false
tree:contains($vFilledTree5,11):  false
tree:findSubtree($vFilledTree5,9)[4]():  3
tree:findSubtree($vFilledTree5,1)[4]():  3
tree:findSubtree($vFilledTree5,3)[4]():  2
tree:findSubtree($vFilledTree5,7)[4]():  2
tree:findSubtree($vFilledTree5,5)[4]():  1
tree:findSubtree($vFilledTree5,12)[4]():  -1
tree:data($vFilledTree5):  1 3 5 7 9

What next?

As you, my observant reader, probably have noticed, there is no tree:deleteItem() yet. This is a little bit more tricky and will be the topic for my next post.

Summary: A fully functional, persistent functional data structure – the Binary Search Tree has been implemented in pure XPath 3.0. We have observed how the new features of HOF and dynamically created anonymous function items make XPath 3.0 shine and how severely it lacks a simple yet most needed datatype – the tuple – to make our code more elegant and reliable.


Posted at 14:30

January 08

Uche & Chime Ogbuji: The Nigerian fuel subsidy quagmire

I caught rumblings of the fuel subsidy removal affair while on my holiday travels, but only in the past few days have I gained a sense of just what a delicate moment in time this is for Nigeria.

Dr. Ngozi Okonjo-Iweala, for whom I've always expressed much admiration, wasted no time after being installed as Finance Minister and over the past quarter, working tirelessly to convince the Federal Government of Nigeria to eliminate the subsidy on motor fuel forthwith. The subsidy was removed as of the first of this year, triggering immediate protests. This is not the first time the government has tried to eliminate the subsidy, and it has always backed down due to popular response, but this time the government seems determined to hold its ground, and Okonjo-Iweala has been quite tough in defending her position. She points out that Nigeria is in danger of financial meltdown to rival that of Greece because of the unsustainable borrowing, much of which goes straight back out of the country in subsidy payments.
  6052f_120103050754-ireport-nigeria-fuel-protest-horizontal-gallery.jpg
The protests across Nigeria have looked to build on the extraordinary scope of popular actions in 2011, in which Time Magazine famously dubbed the protester Person of the Year, including the use of social media, where on Twitter they have adopted the hashtag "#OccupyNigeria."  Of course the "Occupy Wall Street" protests that have lent vocabulary to so many subsequent protests were against policies that support the so-called "1%" of people who make fortunes off globalized finance, while most of the U.S. is facing a harsh recession. There were actually plans for similar "Occupy Nigeria" protests even before the motor fuel subsidy removal, but the popular response against the fuel subsidy provided a spark that no protest organizer could possibly pass up.
shepard-fairey-time-magazine-of-the-year-cover-0.jpg
I do think this convergence of events has led to an unfortunate side-effect. Rightly or wrongly "Occupy Nigeria" has become seen as a vehicle for protest against subsidy removal rather than a protest against the corruption and mismanagement that in effect creates Nigeria's version of the "1%." The danger, however, is that I think most commentators would agree that at some point the fuel subsidy does need to be eliminated, and the real problem is not the subsidy elimination but the likelihood that the cash that the government would save thereby would just also be siphoned into the pockets of Nigeria's "1%".
Prof. Adeola Adenikinju of the University of Ibadan has been one of the most sensible commentators on the issue, which should not surprise anyone, as there are fewer more coherent discussions of the fuel subsidy conundrum than his 2009 presentation at OECD's Global Forum on Trade and Climate Change. That presentation, "Energy pricing and subsidy Reforms in Nigeria", should be required reading for anyone pondering these current events. He argues convincingly the economic case for subsidy removal, but he also admits the considerable present obstacles. He concludes:

Nigeria needs to keep to a formula based approach for determining fuel prices in the short term, while expediting actions in respect of putting in place a vibrant domestic refining industry.

This is where I think even the brilliant Okonjo-Iweala has missed the road, and at the same time I think the "Occupy Nigeria" crowd must learn the lesson of the accusations of incoherence and unthinking populism leveled against "Occupy Wall Street." Okonjo-Iweala is all about GDP growth, and that one measure can be a powerful blinder for economists. I remember watching her famous TED talk headlined "Want to help Africa? Do business here" and thinking: "OK I can sympathize with the desire to focus on foreign development as a vehicle for recovery on our continent, but isn't it even more important to focus on domestic industry?"
Why must we slaves to the mechanisms imposed by the IMF and The World Bank when China shows that there is more than one way to turn around an economy? We are coming from a similar historical and demographic place with the immense damage caused by Chairman Mao not so different from that caused by decades of African despots and colonial meddling. Yes, I do realize that the biggest issue with that thinking is that no African nation has the combination of ruthless and effective leadership of Deng Xiaoping. Surely there is a middle path, an African path.
Nigeria_china
I can hardly think of a more apt fulcrum for weighing out such a middle path than this fuel subsidy crisis. Imagine a timetable that clearly leads up to later subsidy removal through a series of confidence-building measures, some of which Prof. Adeola Adenikinju outlines in his presentation. Even Okonjo-Iweala has been forced to articulate a bit better the material gains to the people she expects from the savings from subsidy removal, mentioning health and social welfare programs, urban mass transit and more, but coming as it has, after the fact of the precipitous subsidy removal decision, this satisfies no one.
Unfortunately present discussion has sometimes broken down into he-said-she-said, for example whether subsidy removal was supposed to wait until April, or claims that Okonjo-Iweala has threatened to resign if any compromise is made on subsidy removal. All this heat without light is not helping matters at all. Even shotgun measures such President Goodluck Jonathan's pledge this morning to slash government salaries by 25% are not enough to grow from this crisis into a pattern of long-term solutions. A continued loss in confidence the current president and his talented Finance Minister could play into the hands of the many darker interests in the nation who have been the main actors in the historical sabotage of Nigeria's welfare. I to truly fear the emergence of some player, perhaps even an agent of the "1%," who claims the populist card against the current government and ends up taking Nigeria even further into the dark ages.
Jonathan and Okonjo-Iweala need to repeat their decisiveness in applying the fuel subsidy removal policy, but this time they must rapidly decide on reform of that policy. They need to articular a clear timetable and plan to tackle corruption, addressing the fact that declared government salaries are a fraction of the mismanagement problem. They need to take firm steps to shore up the domestic, refined petroleum industry. They need to deliver credible assessments of the effectivity of the social welfare institutions that Okonjo-Iweala is promising to support with proceeds from subsidy elimination. A solid, independent advisory panel of the likes of Prof. Adeola Adenikinju and former Petroleum Minister Professor Tam David West, among other specialists, could draw up such a timetable for government approval, acting under the highest standards of transparency.
Jonathan_okonjo-iweala
Would such a course be an easy one? Of course not. But I suspect it would be less difficult than navigating the economic (inflationary pressure) and political (popular revolt) perils of the present course.
Above all, I do hope that the government and its security apparatus sees fit to let the protesters have their say. I'm very troubled by reports of hardships suffered by the protesters, and I hope that we can show the first glimmers of a new, modern Nigeria in the treatment of dissent. President Goodluck Jonathan is no Bashar al-Assad, and shouldn't even take a step in the direction of the Syrian crackdown.  I do find myself hopeful that of all the post-war Nigerian governmental regimes, Jonathan's is the most likely to act with the necessary balance and prudence to turn this crisis around and start on the long, hard road to recovery for our nation.

Permalink | Leave a comment  »

Posted at 21:10

Copyright © XMLhack. A Useful Production. Contact us.