Mu

Zen and the art of...

2009-12-31

Testing ClojureQL

After working on ClojureQL for some time, I've became tired of running manual tests all the time, even with the debug macro. So I began working on a test framework for this project. It's a combination of the test-is library and the concept of demos already built-in. For now we only have them, but they aren't very comprehensive and require a working connection for each backend you want to test. Furthermore, there's practically no validation of the results, we only know that the database accept the expression that have been sent. Now that we're approaching the release of version 1.0 we need something more flexible and exhaustive to keep the code stable.

The Plan

The idea of demo is not bad in itself, so I'll just complement it with tests that could be run without connection. It's all we need for day to day development on ClojureQL, the actual execution of the generated SQL code can be done only once in a while. To not break the DRY principle, I'll make them both use the same code, demos will be written using a special macro and tests will be generated automatically from them. The demos should also be improved by validating the results coming out of the tested databases.

The Prototype

Implementing this scheme directly into ClojureQL is not a simple task though, so I'll make a prototype to show how it works at a smaller scale. We'll use a very simple database written in Clojure and a ClojureQL-like DSL that compile to pseudo-SQL statements. No backends, no intermediate forms and only two kind of statements: inserts and selects. We'll walk through this prototype below, it's merely a hundred lines long.

The Database

All data is kept in a ref, *db*, which is a map of maps with strings as the sole data type for keys as well as for values. The only function we really need here is exec, which takes a compiled statement and returns a result if no exception is raised. I've also included a simple helper function, reset, to empty the database.

(def *db* (ref {}))

(defn reset [] (dosync (ref-set *db* {})))

(defn exec-insert [stmt]
  (let [tokens (drop 2 (seq (.split stmt " ")))
        table  (first tokens)
        values (apply hash-map (rest (rest tokens)))]
    (dosync (alter *db* assoc table
              (merge (@*db* table) values)))))

(defn exec-select [stmt]
  (let [tokens (drop 1 (seq (.split stmt " ")))
        table  (last tokens)
        keys   (take (- (count tokens) 2) tokens)]
    (map #((@*db* table) %) keys)))

(defn exec [stmt]
  (condp #(.startsWith %2 %1) stmt
    "INSERT INTO " (exec-insert stmt)
    "SELECT "      (exec-select stmt)
    (throw (SQLException. "error: unrecognized statement."))))

(defn insert [name & key-val-pairs]
  (apply str "INSERT INTO " name " VALUES " (interpose " " key-val-pairs)))

(defn select [name & keys]
  (str "SELECT " (apply str (interpose " " keys)) " FROM " name))

Our DSL is composed of the insert and select functions, which output the compiled pseudo-SQL code that the database can execute. It's a really dumb system, but we don't need more for the purpose of this experiment.

The Demos

The demos will remain the heart of the ClojureQL testing framework. The main objectives of the following code is to make it easy to define demos and to make their output human-readable. The trick is to also make them reusable, so demos will be defined as data, not code.

(defmacro defdemo [demo & stmts-results]
  `(def ~demo
     ~(vec (map #(vector (list 'quote (first %))
                         (list 'quote (second %)))
             (doall (partition 2 stmts-results))))))

(defdemo demo1
  (insert 'test1 'foo 1) {"test1" {"foo" "1"}}
  (select 'test1 'foo)   ("1"))

(defdemo demo2
  (insert 'test2 'foo 1 'bar 2) {"test2" {"bar" "2", "foo" "1"}}
  (select 'test2 'foo 'bar)     ("1" "2"))

(defn run-demo [name]
  (reset)
  (println "\n===" name "===\n")
  (doall
    (map (fn [[stmt expected-result]]
           (println "statement: " stmt)
           (let [compiled-stmt (eval stmt)
                 result        (exec compiled-stmt)]
             (println "compiled:  " compiled-stmt)
             (println "result:    " result "\n")
             (is (= result expected-result)))) (eval (symbol name)))))

(def demos ["demo1" "demo2"])

(defn run-demos []
  (every? identity
    (apply concat (map run-demo demos))))

The run-demo function test everything in a demo and provide a nice output. It returns a boolean that is the result of the assertion made at the end.

The Tests

We can now use the above to write some tests. The demos ensure us that the compiled statements are all valid. After that it's simply a matter of generating Clojure code, to define tests, and writing it to a file. The gen-test function will take care of the first part and write-tests the second one.

(defn gen-test [name]
  (let [demo (eval (symbol name))]
    `(deftest ~(symbol (.replace name "demo" "test"))
       ~@(map (fn [[stmt _]]
                `(is (= ~stmt ~(eval stmt)))) demo))))

(defn write-tests [filename]
  (when (run-demos)
    (with-open [writer (java.io.FileWriter. filename)]
      (binding [*out* writer]
        (newline)
        (doseq [demo demos]
          (pprint (gen-test demo))
          (newline))))))

(write-tests "tests.clj")

(load-file "tests.clj")

Once the tests file written, we can load it to run the tests it contains. So now we can use run-demos to test everything and run-tests to test compilation only.

Conclusion

There's still many details to figure out before implementing this framework. The namespace layout to be used for example or how to integrate the test-is library depending on what Clojure version we end up targeting. This is a work in progress so I'll keep this post updated until it's done. In the meantime, any comments or suggestions are welcomed.

Happy New Year!

2009-12-21

What the Hell is Happening at ATI?

I got an ATI card for building my last box, would have prefered a Nvidia one, but got a good deal on this card. Overall it's been a good investment, but the situation is slipping down. There have been more and more driver updates lately and now it's getting desperate. I rarely play these days, but all the time I tried in the past months, lots of games were crashing in various ways. Hoping to get these problems resolved, today I tried to install the new Catalyst 9.12 driver, but the installer fails, it simply vanish while using 10% of the processor! To figure out that one, I googled to see if I wasn't alone and there happen to be quite a lot of forum posts discussing the issue. Seeing their content wasn't really comforting either, lots of steps to fix the problem, too much for my current motivation. I'd rather get an Nvidia card instead, but can't currently fit this in my (ramen) budget, even tho entry-level cards are now really powerful. So no gaming for the future ahead, programming is much more fun anyway.

Writing a Help Macro.

Emacs may seems like a pretty barebone tool for the uninitiated, but pack a lot of things under the hood. Especially when you're coding with a Lisp, Emacs really shines thanks to its renowned slime mode. Yet, most of the power of using a Lisp-like language with any editors lies in the use of the REPL. Clojure has a great set of functions and macros available to help you code using it, but these are dispersed around many libraries contained in clojure-contrib. As there's lots of such helpers, you have to remember a bunch of names and refer to documentation often before getting used to all of them. Having these functionalities packed into a single command could be very useful for beginners as well as for practitioners. We'll first pass trough the code and review it, then we'll show how to use the help macro.

Help Macro

We'll proceed in a top-bottom manner, starting with the namespace definition. We'll need some Java classes from clojure.lang package and also add some aliases for the clojure-contrib libraries we'll be using.

(ns help-macro
  "The help macro regroups clojure-contrib most useful help functions and
  macros into a single call."
  (import [clojure.lang IFn PersistentList Symbol])
  (require
    [clojure.contrib.classpath  :as classpath]
    [clojure.contrib.repl-utils :as repl-utils]
    [clojure.contrib.str-utils  :as str-utils]
    [clojure.contrib.ns-utils   :as ns-utils]))

Then comes the definition of *help-usage*, a simple var containing a string explaining how to use the help macro. That could have been included in the docstring, but I chose to emulate the way command line scripts work instead.

(def *help-usage*
  #^{:doc "Help macro usage text."}
  (str
    "Usage: (help pwd)\n"
    "       (help classpath)\n"
    "       (help dir <ns>)\n"
    "       (help docs <ns>)\n"
    "       (help vars <ns>)\n"
    "       (help source <symbol>)\n"
    "       (help <class> [<n>])\n"
    "       (help <expr>)\n"
    "       (help <string>)\n"
    "       (help ? <query-type>)"))

As you see, we'll support nine kinds of help queries, six of which use a command symbol while the three others are dispatched on the class of their first argument. Lets review each types of queries:

  • pwd - Returns the current working directory.
  • classpath - Prints the current classpath.
  • dir - Prints a sorted directory of public vars in a namespace.
  • docs - Prints documentation for the public vars in a namespace.
  • vars - Returns a sorted seq of symbols naming public vars in a namespace.
  • source - Returns a string of the source code for the given symbol, if it can find it.
  • <class> - Get help on class members, like clojure.contrib.repl-utils/show.
  • <expr> - Get help on the result of an expression, like clojure.contrib.repl-utils/expression-info.
  • <string> - Like find-doc, but easier to type.

The help usage message is nice, but it would be great to have more specific ones for each types of queries, like the above list. To do this, we'll create a help-usage function that will print various messages depending on the symbol given as first argument.

(defn help-usage
  "Returns documentation on help macro usage."
  [query-type & args]
  (condp = query-type
    'class     (doc clojure.contrib.repl-utils/show)
    'expr      (doc clojure.contrib.repl-utils/expression-info)
    'string    (doc find-doc)
    (println
      (condp = query-type
        'pwd       "Returns the current working directory."
        'classpath "Prints the current classpath."
        'dir       "Prints a sorted directory of public vars in a namespace."
        'docs      "Prints documentation for the public vars in a namespace."
        'vars      "Returns a sorted seq of symbols naming public vars in a namespace."
        'source    "Returns a string of the source code for the given symbol, if it can find it."
        "This type of help query is not recognized."))))

Each symbols are separated in two categories. For the simpler queries, we only display a description of what they do. For more complex ones though, we show the documentation for the original function or macro using the doc macro. The function accept other arguments only to prevent exceptions in case of unintentional input.

We'll now look at the generic-help multimethod, which will dispatch calls on the class of its first argument. We'll only respond to three classes: Class, Clojure's PersistentList and String.

(defmulti generic-help
  "Makes the help macro generic on its first argument if no command found."
  {:arglists '([query args])}
  (fn [query _] (class query)))

(defmethod generic-help Class
  [query args]
  (apply repl-utils/show (cons query args)))

(defmethod generic-help PersistentList
  [query args]
  (repl-utils/expression-info (second query)))

(defmethod generic-help String
  [query args]
  (find-doc query))

A thing to note here is the reason why we take the second argument of the list in the PersistentList method. This is so because the help macro quote all arguments it receives, but the expression query must be already quoted.

We'll also add a default dispatch method which displays a warning message followed by the help macro usage.

(defmethod generic-help :default
  [query _]
  (println "No help available for object of type " (class query))
  (help-usage))

All simple commands are contained in the *help-command* map, which is used by the help* function following it.

(def *help-commands*
  #^{:doc "This is a map containing all the commands for the help macro."}
  { 'pwd       #(.getCanonicalPath (java.io.File. "."))
    'classpath #(println (str-utils/str-join "\n" (classpath/classpath)))
    'dir       ns-utils/print-dir
    'docs      ns-utils/print-docs
    'vars      ns-utils/ns-vars
    'source    (comp println repl-utils/get-source)})

(defn help*
  "Driver for the help macro."
  [query args]
  (if-let [sc (get *help-commands* query)]
    (apply sc args)
    (generic-help (if (symbol? query)
                    (resolve query)
                    query) args)))

This function look into the *help-command* map to see if it contains the given query symbol. If found, it calls the associated runnable, else it calls generic-help. Before calling the multimethod, we first try to resolve the query quoted expression in case it's a symbol. This is because this function receives only the symbol of a class when help is called with a class name.

Finally, here's the help macro in all it's glory.

(defmacro help
  "Get help for various kind of expressions, use without arguments for
  detailed usage."
  ([] `(println *help-usage*))
  ([query & args]
    (let [quoted-args (map #(list 'quote %) args)]
      (if (= '? query)
        `(help-usage ~@quoted-args)
        `(help* '~query (list ~@quoted-args))))))

Usage

Here's some examples of using the help macro:

user> (help pwd)
"C:\\"
user> (help classpath)
g:\libraries\java\swank-clojure-1.0-SNAPSHOT.jar
g:\libraries\java\servlet-api-2.5-20081211.jar
...
nil
user> (help dir help-macro)
*help-commands*
*help-usage*
generic-help
help
help*
help-usage
nil
user> (help docs help-macro)
-------------------------
help-macro/*help-commands*
nil
  nil
...
nil
user> (help vars help-macro)
(*help-commands* *help-usage* generic-help help help* help-usage)
user> (help source +)
(defn +
  "Returns the sum of nums. (+) returns 0."
  {:inline (fn [x y] `(. clojure.lang.Numbers (add ~x ~y)))
   :inline-arities #{2}}
  ([] 0)
  ([x] (cast Number x))
  ([x y] (. clojure.lang.Numbers (add x y)))
  ([x y & more]
   (reduce + (+ x y) more)))
nil
user> (help String)
===  public final java.lang.String  ===
[ 0] static CASE_INSENSITIVE_ORDER : Comparator
[ 1] static copyValueOf : String (char[])
...
nil
user> (help String 1)
#<Method public static java.lang.String java.lang.String.copyValueOf(char[])>
user> (help '1)
{:class java.lang.Integer, :primitive? false}
user> (help '(int 1))
{:class int, :primitive? true}
user> (help "help")
-------------------------
clojure.main/help-opt
([_ _])
  Print help text for main
-------------------------
clojure.main/main
([& args])
...

Installing

You can find the complete code here. To use it, place that file in your classpath and create an user script to be called when stating a REPL. From there, you simply have to add the help-macro namespace with the use function if you want to be able to just type "(help...". To have it around in every namespace, you could add the following function in the same file than the macro and use it instead of in-ns.

(defn to-ns [n]
  (in-ns n)
  (use 'help-macro))

Any comments, suggestions, improvements, insults?

2009-12-15

Reading The F*ck!ng Manual

While contributing code to ClojureQL, I made a huge mistake. That is, commiting changes to the master branch directly instead of using a development branch. I had made a dozen commits, but in the meantime Lau merged the dev branch on ClojureQL's main repository. The end result was that the pull request I made after was incredibly huge as it included all changes in the merge.

I'll walk you through all steps I've taken to fix this problem. We'll first create a dev branch, it should be a copy of the current master branch, which is the default behavior.

$ git branch dev

This will create a new branch named dev that will be a copy of the current one, master. We'll then search for the first commit we've made using git log.

commit 07a516b03287b606d6a40b2e073cd3e3a1a74244
Author: Nicolas Buduroi 
Date:   Wed Dec 9 18:52:35 2009 -0500

    Removed global connection support for MySql demo as it breaks the build process when MySql is not installed.

commit cc8f234fb61739fca36e982f68eef005b3d4389c
Author: Lau_of_DK 
Date:   Tue Dec 8 23:18:03 2009 +0100

:

We must return the master branch to the state it was before commiting our first change. We can achieve this by using the reset command.

$ git reset --hard cc8f234fb61739fca36e982f68eef005b3d4389c
.gitignore: locally modified
build.xml: locally modified
ivy.xml: locally modified
ivysettings.xml: locally modified
...

Notice that you should use the --hard flag to make sure Git clean up the working repository. We can then update our master branch with the main repository. This assume you've already set up a remote Git repository named main-repo, check this page to see how to make one.

$ git pull main-repo master
From git://gitorious.org/clojureql/clojureql
 * branch            master     -> FETCH_HEAD
Updating cc8f234..b85d55b
Fast forward
 build.gradle                                       |   64 +++++++
 build.xml                                          |  182 --------------------
 ivy.xml                                            |   31 ----
 ivysettings.xml                                    |    9 -
 src/{dk/bestinclass => }/clojureql.clj             |    4 +-
...

Now, we need to switch to our dev branch with git checkout dev, and there, issue the rebase command.

$ git rebase master
First, rewinding head to replay your work on top of it...
Applying: Removed global connection support for MySql demo as it breaks the build process when MySql is not installed.
error: src/dk/bestinclass/clojureql/demos/mysql.clj: does not exist in index
Using index info to reconstruct a base tree...
Falling back to patching base and 3-way merge...
Renaming src/dk/bestinclass/clojureql/demos/mysql.clj => src/clojureql/demos/mysql.clj
Auto-merging src/clojureql/demos/mysql.clj
Applying: Made demos code formatting more uniform.
error: src/dk/bestinclass/clojureql/demos/derby.clj: does not exist in index
error: src/dk/bestinclass/clojureql/demos/mysql.clj: does not exist in index
error: src/dk/bestinclass/clojureql/demos/postgres.clj: does not exist in index
Using index info to reconstruct a base tree...
Falling back to patching base and 3-way merge...
Renaming src/dk/bestinclass/clojureql/demos/derby.clj => src/clojureql/demos/derby.clj
Auto-merging src/clojureql/demos/derby.clj
CONFLICT (rename/modify): Merge conflict in src/clojureql/demos/derby.clj
Renaming src/dk/bestinclass/clojureql/demos/mysql.clj => src/clojureql/demos/mysql.clj
Auto-merging src/clojureql/demos/mysql.clj
CONFLICT (rename/modify): Merge conflict in src/clojureql/demos/mysql.clj
Renaming src/dk/bestinclass/clojureql/demos/postgres.clj => src/clojureql/demos/postgres.clj
Auto-merging src/clojureql/demos/postgres.clj
CONFLICT (rename/modify): Merge conflict in src/clojureql/demos/postgres.clj
Failed to merge in the changes.
Patch failed at 0002.

When you have resolved this problem run "git rebase --continue".
If you would prefer to skip this patch, instead run "git rebase --skip".
To restore the original branch and stop rebasing run "git rebase --abort".

OK, that doesn't look good: error, conflict, failed... Not reassuring, but looking more closely, this message concerns only the first patch, which I have to revert anyway. Lets see how to resolve this. You can find the conflicting files with git status. Here's an example of such a file:

<<<<<<< HEAD:src/clojureql/demos/derby.clj
(ns clojureql.demos.derby
=======
;; TEST ====================================================

(ns dk.bestinclass.clojureql.demos.derby
>>>>>>> Made demos code formatting more uniform.:src/dk/bestinclass/clojureql/demos/derby.clj

Fix the conflict by picking one of the offered options. Then, once everything is cleaned up, you can tell the merge process to accept your changes with git add and restart the rebase one.

$ git add .

$ git rebase --continue
Applying: Made demos code formatting more uniform.
Applying: Added build directory to ignored files.
Applying: Changed PostreSQL backend to be more like MySQL one, follow non-nulls new standard.
Applying: Updated create-table docstring to reflect recent changes.
Applying: Added a shortcut in create-table's options to make all columns non null.
Applying: Added support for multiple primary keys to create-table.
Applying: Changed EmbedConnection class to EngineConnection interface for added flexibility in Derby backend.
Applying: Removed useless prefer-method.
Applying: Added the :unique option to create-table for all backends, needs refactoring.
Applying: Refactored contraints using a list as argument for all backends.
Applying: Refactored column options for all backends, made minor changes to list-constraint and cleaned up a little.
Applying: Added new derivation for ::Generic as java.sql.Connection proxies are confused with com.mysql.jdbc.Connection ones, put prefer-method back in Postgres backend as it now cause problems.
Applying: Added primary-key, unique and non-nulls options to generic create-table.
Applying: Added the :defaults option to create-table for all backends.

We must now return to the master branch where we'll merge the rebased patches.

$ git merge dev
Updating b85d55b..5f771d6
Fast forward
 .gitignore                         |    1 +
 src/clojureql/backend.clj          |   49 ++++++++++++++++++++++++++++++++++-
 src/clojureql/backend/derby.clj    |   31 +++++++++++-----------
 src/clojureql/backend/mysql.clj    |   36 ++++++++++++++------------
 src/clojureql/backend/postgres.clj |   42 ++++++++++++++++++------------
 src/clojureql/demos/derby.clj      |   11 ++++---
 src/clojureql/demos/mysql.clj      |   16 ++++-------
 src/clojureql/demos/postgres.clj   |    2 +-
 src/clojureql/frontend.clj         |   18 ++++++++++---
 9 files changed, 134 insertions(+), 72 deletions(-)

That was simple, isn't it? Joking aside, this may look complex to the uninitiated, but it all make sense once you get used to it. One last thing, after going through this, I had still to push my rebased commits to the Gitorious clone. It didn't worked!

$ git push origin master
Enter passphrase for key '/home/budu/.ssh/id_rsa': 
To git@gitorious.org:~budu/clojureql/budu-clojureql.git
 ! [rejected]        master -> master (non-fast forward)
error: failed to push some refs to 'git@gitorious.org:~budu/clojureql/budu-clojureql.git'

That problem happen to be caused by a safety measure that prevents users from pushing a "non-fast forward" branch to a remote repository. Simply put, when you mess to much with your repository it could end up causing troubles, here's a message from Git's mailing list archives explaining things more properly. You need to use the --force option to circumvent that protection.

$ git push --force origin master
Enter passphrase for key '/home/budu/.ssh/id_rsa': 
Counting objects: 117, done.
Compressing objects: 100% (41/41), done.
Writing objects: 100% (103/103), 17.40 KiB, done.
Total 103 (delta 70), reused 80 (delta 62)
To git@gitorious.org:~budu/clojureql/budu-clojureql.git
 + 42eb50e...5f771d6 master -> master (forced update)
=> Syncing Gitorious... [OK]

I wrote this post for those who are in a hurry and didn't had the time to learn Git properly before contributing to some project. But remember that it's always better to RTFM!

RTFM

2009-12-14

Debugging ClojureQL

Since last week, I embarked on a new endeavor, contributing to ClojureQL. My future projects involving Clojure will need to access some databases, some of which doesn't behave in the same way. Sure, there is already clojure.contrib.sql that give you a wrapper around JDBC, but there are two problems with this approach. First, JDBC is quite good at what it does, yet is not a very sophisticated tool. It gives you access to a portable subset of SQL, that mainly support querying and updating data. This leaves a lot of advanced features out of the deal, these are still available, but in a non-portable way. The other way around, if a database system doesn't support a common feature, JDBC cannot do anything about it, the driver can though. Second, the clojure.contrib sql API has a very procedural feeling to it, it doesn't even let you play with an intermediary form as it executes statement directly. That's enough for basic database interactions, but not for serious database agnostic development.

Lets put off advocacy and talk about something concrete. While contributing to ClojureQL, I realized there was some issues with debugging. It was working well for Postgres (which I had an instance running), I simply had to use the compile-sql method. A problem arise when you're testing changes that affect all backends. In this case, to verify the SQL generated, you need a server for each DBMS you want to test. After looking at the code for some time, I found an easy way of compiling statements without a connection. We can create mock objects using Clojure's proxy macro and use them instead of live connections. For now, it's really simple as no backend implementations are actually using the connector. To put this idea into practice, I wrote a macro to debug multiple databases.

(defmacro debug [db ast]
  (let [connector (.getName (db *connectors*))]
    `(compile-sql ~ast (proxy [~(symbol connector)] []))))

It uses a map containing the interfaces used by all backends with keywords as keys.

(def *connectors* {
  :postgres org.postgresql.PGConnection
  :mysql    com.mysql.jdbc.Connection
  :derby    org.apache.derby.iapi.jdbc.EngineConnection
  :generic  Object})

With this code you can easily debug statements for every databases ClojureQL support. We can add a final touch to be able to see the SQL output for all backends with a single command.

(defmacro debug-and-print-all [ast]
  (let [longest (reduce max (map (comp count str) (keys *connectors*)))
        debug-and-print (fn [db] `(println (format (str "%1$-" ~longest "s : %2$s")
                                           ~(subs (str db) 1)
                                           (debug ~db ~ast))))]
    `(do ~@(map debug-and-print (keys *connectors*)))))

Finally, you can see an example output of the debug-and-show-all macro at the REPL using my ClojureQL clone.

clojureql-test> (debug-and-print-all (create-table test [id int title text date date] :non-nulls * :primary-key id :auto-inc id :unique title))
postgres  : CREATE TABLE test (id SERIAL,title text NOT NULL,date date NOT NULL,PRIMARY KEY ("id"),UNIQUE ("title"))
mysql     : CREATE TABLE test (id int NOT NULL  AUTO_INCREMENT ,title text NOT NULL ,date date NOT NULL ,PRIMARY KEY (`id`),UNIQUE (`title`)) 
derby     : CREATE TABLE test (id int NOT NULL  GENERATED ALWAYS AS IDENTITY ,title text NOT NULL ,date date NOT NULL ,PRIMARY KEY ("id"),UNIQUE ("title"))
generic   : CREATE TABLE test (id int NOT NULL ,title text NOT NULL ,date date NOT NULL ,PRIMARY KEY ("id"),UNIQUE ("title"))

This code is not working properly on the main repository for the moment, as there's some issues with Derby and the generic backend. It's enough for this post, I'll go back hacking my way through ClojureQL code to find other useful tricks and speed up version 1.0 release.

2009-12-08

Somalia's Customary Law

In recent years, there have been a growing interest for decentralization in information technologies. It started a long time ago when personal computers (and before them mini computers) replaced the gigantic computers of yore. Today many topics in software development are focused on decentralization like distributed version control, offline web applications or database sharding. This concept can be applied to many things around us, it's not only pertaining to our domain. Lately I've been thinking about what I called then a decentralized legal system. That name wasn't quite good and I learned that the correct term is polycentric law. This type of legal structure has not been studied widely, and only managed to gather interest from researchers since the beginning of the nineties. It's at that time that Tom W. Bell wrote a paper entitled "Polycentric Law" in which he described various examples of such systems like the Anglo-Saxon customary law. For him, there are six main features that embodies this concept:

  • Focus on individual rights
  • Law is enforced by reciprocal agreement between the victim(s) and the accused party
  • Common procedures to help maintain order
  • Punitive actions are centered around paying back for the wrong deeds committed
  • Social exclusion is used as a powerful incentive
  • Laws are more adaptive to traditions and customs.

Anglo-Saxon's customary law had a surety mechanism known as borh (not to be confused with a Burh) that was the foundation of their whole system of law. It was really simple, you take a dozen persons and then bind them together by making them pledge to be responsible for each others' actions. If one of them got a fine, the group must pay it, thus ill-behaving members were not very popular and could even be expelled . It's sure such a system wouldn't work well in modern time Britain, or in other prosperous countries for that matter, but at the time these were very coercive incentives. There were a lot of other similar customary law in ancient times, but we can find other kinds of decentralized systems in more civilized political structures. The Roman law for example allowed indigenous legal systems for non-Romans, some of which being polycentric, and we could also consider the European Union has a form of decentralized (or multi-layered) superstate, but it would be a stretch to call these polycentric.

This brings us to the subject of the day, Somalia's customary law, the Xeer legal system. It's what has defined Somalia since its inception and is more than thirteen centuries old. It has been and still is the principal way for Somalis to resolve their disputes despite the introduction of the Shari'a (which by the way is widely used for common civil cases like marriage, divorce, inheritance, etc.) and the Italian colonial government's attempt to get rid of traditional laws before the independence. The Xeer is considered to be completely indigenous and is perhaps the most evolved form of polycentric legal system still in use today. In spite of all the political instability, piracy and other problems plaguing this country, Somalia's economy is thriving compared to most other African nations and some people are attributing that to their customary law. Even the government of the autonomous Somaliland region have tried to make themselves more legitimate in the eyes of their citizens by appointing elders (the Xeer system's judges) into the upper house of parliament, but that apparently didn't worked so well. I must note that Xeer's popularity in that part of Somalia is more pronounced as a consequence of the more relaxed British attitude toward their colonies. Since the Somalis gained their independence in the sixties, the state of Somalia had introduced various civil law systems, but the Xeer always prevailed, even with Siad Barre efforts to forbade clanism and promote centralization.

The law is defined in terms of property rights, which make it more compensatory than punitive. This characteristic by itself position this system as a great example of the previously defined concept of polycentric law. Another aspect is shown in the way fines are being paid, not to a court or the government, but directly to the victim(s). There's also many traditions that aren't polycentric, like bigger fines for prominent members of society than for commoners and a staunch opposition to any form of taxation. It's a very secular system too, keeping religious concerns out of the way. It also normally takes precedence over the Shari'a, even though both systems generally occupy different niches. There's a saying in Somalia that say:

Diinta waa labaddali karaa, xeer se lam baddali karo

That means "One can change his religion, one cannot change the law", which shows how secularism is ingrained into Somalis collective consciousness, especially when considering the predominance of a single religion in that country for centuries. But their secularism go even further than what is known elsewhere, as the law is even considered to be separated from the government. The Xeer system is administered and enforced by civilians, not government officials.

There's an insurance mechanism not unlike the bohr surety system. Generally the family of the offender is designated to be responsible for its actions, thus rehabilitation of criminals is the business of their respective family. In extreme cases, the family can disown one of its member, who then automatically becomes an outlaw. In such case, the only option left for the criminal is to leave the country. The way everything works can bear surprising resemblance to modern systems of law. There is specialized functions that can be related to the common court and law enforcement functions:

  • Odayal (Judges)
  • Xeer Boggeyaal (Jurists)
  • Guurtiyaal (Detectives)
  • Garxajiyaal (Attorneys)
  • Murkhaatiyal (Witnesses)
  • Waranle (Police officers)

Each Somali is appointed an Odayal at birth, chosen after long deliberation by the elders of the clan. That title can be lost at some point if the community decide so, making judges more careful and taking the interest of the collectivity before their own clan. The way everything work is intimately tied to the complex Somali family clan structure. This system is even scalable, as the Xeer not only rule disputes inside and between clans, but also across regions, between alliances of clans called jilibs. I won't go into the details of court procedures as this is pretty boring stuff (comically googling "pretty boring stuff" yields `Pretty Boring Stuff': District Judges and Housing Possession Proceedings as first result!) One thing to note is the preponderance of oaths to settle complex situations, for instance when the witnesses contradict each other or if there's not enough witnesses to confirm a story. In these times, the person in question is asked to take an oath like "I swear by my virility." or "I swear by Allah.". Some oaths can even have consequences like the divorce oath that, if broken, make a marriage vow null and void. There's also a oath of innocence that the accused must take when the plaintiff fails to convince the judge of the validity of his case.

To wrap up everything, the long time appreciation of the Xeer by Somalis seems to be in sharp contrast with the usual cynicism most peoples have toward their legal system. Even though Somalia as its problems, which are less dramatic than some would have us to believe, it doesn't mean there's nothing to be learned from them.

Further Readings

2009-12-03

Closure Library Tutorial: Tasks (part 1)

Today we'll create something with the recently released Closure Library. Nothing amazing, just a simple application to manage daily tasks (I would have liked to say a 'task manager' but that could be confusing). JavaScript has finally matured and with this library, we nearly have all the bells and whistles of a desktop environment graphical user interface.

The Closure Library is part of a set of tools that Google's engineers have been working on for quite some time and they have more than proved their worth. Even though not directly based on it, this library has been greatly influenced by the Dojo Toolkit. I've never used that framework before, most of my experience being with jQuery, so I'm not really qualified to compare them, learning Closure will be enough for now. Lets list some of the features offered by this library:

  • History management
  • Solid and portable event handling (with a timer class and ways to delay or throttle events)
  • Internationalization
  • Basic support for spell checkers
  • A complete debugging and testing framework
  • DOM manipulation helpers
  • Code to help working with data sets
  • Cross-browser support for drawing using SVG, VML or the new HTML5 canvas element
  • A module system to dynamically load compiled JavaScript code
  • UI widgets and effects

And there's much more! All that backed up by the company that dominate the web, how could we ask for more? So in this tutorial we'll concentrate on two areas: UI widgets and event handling. I know, this is already covered in the Google code tutorial, but I found it to be plain and boring, that library deserves more.

This tutorial will build upon the official one, just refer to it if you're lost at some point. We begin by declaring the namespaces we'll be providing and we'll also require the goog.dom namespace and the UI widgets we need.

goog.provide('mu.tutorial.tasks');
goog.provide('mu.tutorial.tasks.Task');

goog.require('goog.dom');
goog.require('goog.ui.CustomButton');
goog.require('goog.ui.Toolbar');
goog.require('goog.ui.ToolbarButton');
goog.require('goog.ui.Zippy');

First thing to note is that we have to provide not only the namespace, but the name of all classes in that namespace. That's because classes aren't really classes, they're still just plain JaveScript prototypes. So class names are simply namespaces and are thus orthogonal to the inheritance mechanism. You can inherit from classes that aren't being provided by any namespace. The provide and require functions are only there to check for dependencies and are also used by the debug resolver.

Now lets add something new, a toolbar. Before delving into code, we'll have to go fetch the stylesheet and images that can be found in the goog/demos folder. In the meantime you can also get those for the button widget that we'll use later on. Another file not to forget is the common.css stylesheet that contains styles common to all widgets. Here's all the code needed to create our toolbar.

mu.tutorial.tasks.switchPanel = function(target) {
    return function() {
        goog.dom.$('taskList').style.display = "none";
        goog.dom.$('completedTaskList').style.display = "none";
        goog.dom.$('deletedTaskList').style.display = "none";
        goog.dom.$('settings').style.display = "none";
        goog.dom.$(target).style.display = "block";
    }
}

mu.tutorial.tasks.attachToolbarButton = function(toolbar, label, tooltip, target) {
    var button = new goog.ui.ToolbarButton(label);
    button.setTooltip(tooltip);
    toolbar.addChild(button, true);
    goog.events.listen(button.getContentElement(), goog.events.EventType.CLICK,
        mu.tutorial.tasks.switchPanel(target));
}

mu.tutorial.tasks.attachToolbar = function(container) {
    var toolbar = new goog.ui.Toolbar();

    mu.tutorial.tasks.attachToolbarButton(toolbar, 'Tasks', 'List currently active tasks.', 'taskList');
    mu.tutorial.tasks.attachToolbarButton(toolbar, 'Completed', 'List completed tasks.', 'completedTaskList');
    mu.tutorial.tasks.attachToolbarButton(toolbar, 'Trash', 'List deleted tasks.', 'deletedTaskList');
    mu.tutorial.tasks.attachToolbarButton(toolbar, 'Settings', 'Settings', 'settings');

    toolbar.render(container);
}

First, we create a toolbar, then attach all buttons and finally render everything in the given container. There's a function to help us attach buttons, it add a tooltip and an event listener to switch between the various panels. Those panels are just a bunch of divs that are shown successively by changing their display attribute, using the switchPanel function.

For an application managing tasks, we better create a Task class. This part of the tutorial is very similar to Google's one. Task objects are structurally identical to Note objects, with summary instead title and description instead of content as properties.

mu.tutorial.tasks.Task = function(data, container) {
    this.summary = data.summary;
    this.description = data.description;
    this.priority = data.priority;
    this.parent = container;
}

mu.tutorial.tasks.Task.prototype.closeEditor = function() {
  this.contentElement.innerHTML = this.description;
  this.contentElement.style.display = "block";
  this.editorContainer.style.display = "none";
};

mu.tutorial.tasks.Task.prototype.openEditor = function(e) {
  this.editorElement.value = this.description;
  this.contentElement.style.display = "none";
  this.editorContainer.style.display = "inline";
};

mu.tutorial.tasks.Task.prototype.save = function(e) {
  this.description = this.editorElement.value;
  this.closeEditor();
};

As you see, there's nothing new here. I've also included the functions that will be used by the editor, then again, same thing as the official tutorial. We'll only add one new kind of action. In fact this is a function returning a closure that will move a task to the desired panel.

mu.tutorial.tasks.Task.prototype.clickActionButton = function(task, element, target) {
    return function(e) {
        var parent = element.parentNode;
        parent.removeChild(element);
        if (parent.childNodes.length == 0)
            mu.tutorial.tasks.noTasks(parent);

        task.parent = mu.tutorial.tasks.taskLists[target];
        if (task.parent.childNodes[0].className == 'empty')
            task.parent.removeChild(task.parent.childNodes[0]);

        task.makeDom();
        e.stopPropagation();
    };
}

Here, the noTasks function only create an h2 header tag to tell the user there's no tasks in that panel. The taskLists namespace variable is a simple dictionary that we'll fill later.

We're now ready to jump to the makeDom function, where we create the DOM structure for a task, add buttons, wire up event listeners and use the Zippy class.

mu.tutorial.tasks.Task.prototype.makeDom = function() {
    this.summaryDiv = goog.dom.createDom('div', { 'class': 'summary' }, this.summary);
    this.contentElement = goog.dom.createDom('div', { 'class': 'description' }, this.description);
    this.editorElement = goog.dom.createDom('textarea', null, '');

    this.editorContainer = goog.dom.createDom('div', {'style': 'display:none;'},
                                              this.editorElement);

    this.descriptionContainer = goog.dom.createDom('div', null,
                                                   this.contentElement,
                                                   this.editorContainer);

    var taskDiv = goog.dom.createDom('div', { 'class': 'task' },
                                     this.summaryDiv,
                                     this.descriptionContainer);

    this.parent.appendChild(taskDiv);

    this.makeButtons(this, taskDiv);

    goog.events.listen(this.contentElement, goog.events.EventType.CLICK,
                       this.openEditor, false, this);

    this.zippy = new goog.ui.Zippy(
        this.summaryDiv,
        this.descriptionContainer);
}

There is two type of button for tasks, action buttons that will use the clickActionButton function and editor buttons for the editor. Each type of button has a function to create them, add a class name, render them and add an event listener.

mu.tutorial.tasks.Task.prototype.makeActionButton = function(task, element, target, name) {
    var button = new goog.ui.CustomButton(name);

    button.addClassName('taskButton');

    button.render(element.childNodes[0]);

    goog.events.listen(
        button.getContentElement(),
        goog.events.EventType.CLICK,
        this.clickActionButton(task, element, target));
}

mu.tutorial.tasks.Task.prototype.makeEditorButton = function(element, name, callback) {
    var button = new goog.ui.CustomButton(name);

    button.addClassName('editorButton');

    button.render(element.childNodes[1].childNodes[1]);

    goog.events.listen(
        button.getContentElement(),
        goog.events.EventType.CLICK,
        callback, false, this);
}

Here's the makeButtons function.

mu.tutorial.tasks.Task.prototype.makeButtons = function(task, element) {
    if (task.parent.id == 'taskList') {
        this.makeActionButton(task, element, 'completed', 'Done');
        this.makeActionButton(task, element, 'deleted', 'Delete');
    }
    else
        this.makeActionButton(task, element, 'active', 'Undo');

    this.makeEditorButton(element, 'Save', this.save);
    this.makeEditorButton(element, 'Cancel', this.closeEditor);
}

The action buttons are attached to each tasks depending if the given task is active or not. Active tasks can be deleted or marked as completed and we can reactivate them after that. All tasks will remain editable for now, so we add the editor buttons to each one of them.

Finally, the last function takes a bunch of raw task data, create Task objects and call their makeDom method, inserting them into the given container. It also fills the taskLists dictionary entry for that list.

mu.tutorial.tasks.makeTasks = function(name, data, container) {
    if (data.length == 0)
        mu.tutorial.tasks.noTasks(container);
    else
        for (var i = 0; i < data.length; i++) {
            var task = new mu.tutorial.tasks.Task(data[i], container);
            task.makeDom();
        }

    mu.tutorial.tasks.taskLists[name] = container;
}

We still have to make use of all that code, an HTML page will contain the remaining parts. We only need one div for the toolbar, then four others for each sections of our application. After that we add some more JavaScript to attach the toolbar and create some tasks to test if everything is working.

  <body>
    <h1>Closure Library Tutorial</h1>
    <div id="menu"></div>
    <div id="taskList"></div>
    <div id="completedTaskList"></div>
    <div id="deletedTaskList"></div>
    <div id="settings">TODO...</div>
    <script type="text/javascript">
      function main() {

          var menu = document.getElementById('menu');
          mu.tutorial.tasks.attachToolbar(menu);

          var makeTaskData = function(summary, description, priority) {
              return { 'summary': summary, 'description': description, 'priority': priority };
          };

          var taskList = document.getElementById('taskList');
          mu.tutorial.tasks.makeTasks('active', [
              makeTaskData("Make the toolbar actually do something.", "Need more studying of Toolbar demo.", 99),
              makeTaskData("Make tasks editable.", "Like in the Closure Library Notes tutorial.", 88),
              makeTaskData("Create different task lists.", "One for active tasks, another for completed ones and finally a list containing deleted tasks.", 100)
              ], taskList);

          var completedTaskList = document.getElementById('completedTaskList');
          mu.tutorial.tasks.makeTasks('completed', [], completedTaskList);

          var deletedTaskList = document.getElementById('deletedTaskList');
          mu.tutorial.tasks.makeTasks('deleted', [
              { 'summary': 'test', 'description': 'test', 'priority': 1 }
              ], deletedTaskList);
      }
      main();
    </script>
  </body>

You can grab the full HTML file here (look at the source or use "Save Link As...") and the JavaScript used there. When testing it, you'll notice the loading time can be long for a static page. Using Firebug net panel, we can see that the page ask for no less than 54 JavaScript files, that's a lot of requests! Over the wire, this can quickly become a problem, especially for high latency connections. To fix this problem, we'll use the calcdeps.py script found in the bin directory. You simply have to call it like that:

> ./closure/bin/calcdeps.py -i tasks.js -p . -o script > tasks.nodeps.js

Still, it makes our little JS file a lot heavier, it now weight in at 656KB, 650 more than the original. That's a lot, but can be mitigated by server settings like file compression and expire headers.

Here's a demo if you're not interested by setting up everything yourself. In the next tutorial we'll learn to use sliders and color pickers to make the settings panel do something and we'll make the active task list sortable by priority.

Any questions, corrections or insults?

2009-12-02

Overlooking the Obvious

Monday, Tim Bray posted another article on Clojure in his Concur.next series. In there is some beautiful code (as idiomatic Clojure usually is) written by John Evans, in which there was a function I wasn't familiar with.

user> (doc merge-with)
-------------------------
clojure.core/merge-with
([f & maps])
  Returns a map that consists of the rest of the maps conj-ed onto
  the first.  If a key occurs in more than one map, the mapping(s)
  from the latter (left-to-right) will be combined with the mapping in
  the result by calling (f val-in-result val-in-latter).

Although I get the general idea I think it's preferable to perform experiments after reading some documentation, just to be sure.

user> (merge-with #(+ %1 %2) {:a 1} {:a 2 :b 3} {:a 4 :b 5 :c 6})
{:c 6, :b 8, :a 7}
user> (merge-with #(list %1 %2) {:a 1} {:a 2 :b 3} {:a 4 :b 5 :c 6})
{:c 6, :b (3 5), :a ((1 2) 4)}

It does pretty much what the docs say, it's always great to find about a useful function you didn't knew about! Let's see some real code using this function.

(defn- merge-map
  "Merges an inner map in 'from' into 'to'"
  [to key from]
  (merge-with merge to (select-keys from [key])))

This was extracted from Compojure source code for response handling. It's used to merge the response's headers and session maps when the update-response multi-method is called on an object of the Map class. That gave me an idea: the principle of using merge as the with function could be generalized into a function that recursively merges maps. Let's to do it manually.

user> (merge {:a 1} {:a 2 :b 3} {:b 4 :c 5})
{:c 5, :b 4, :a 2}
user> (merge-with merge {:a {:a 1 :b 2}} {:a {:a 3 :c 4}} {:a {:b 5 :c 6}})
{:a {:c 6, :a 3, :b 5}}
user> (merge-with (partial merge-with merge) {:a {:a {:a 1} :b {:b 2}}} {:a {:a {:a 3} :c {:c 4}}} {:a {:b {:b 5} :c {:c 6}}})
{:a {:c {:c 6}, :a {:a 3}, :b {:b 5}}}

That's surely feasible, but I can't seems to find any use for such a function, so I'll leave it as an exercise. The complexity of this task certainly negate the actual benefits gained from its limited usefulness anyway. Is there anybody who disagree?

Update: Mister Bray posted yet another article on Clojure yesterday and proggit bursted in flames with relatively interesting (but heated) discussions on Clojure versus everything under the sun. It also provoked craziness!

About Me

My photo
Quebec, Canada
Your humble servant.