Monthly Archive for April, 2011

CouchDB-OCaml

Published
by
Victor Nicollet
on April 29, 2011
in Functional
. 0 Comments

I spent two days upgrading from the previous CouchDB library to a new one. The change involved eliminating a lot of kinks that made writing code a bit awkward, as well as a massive transition from previous imperative style to a new monadic style. As a result, the code became shorter and more elegant.

As a simple example, this is a standard library module from the Ozone framework that was originally implemented on top of the old CouchDB library. It’s a library for atomically upholding an uniqueness constraint on a value :

  • module MyUnique = Unique(MyDatabase) initializes the unique constraint in the provided database.
  • MyUnique.get "Hello" gets an unique identifier bound to the Hello string, or uses an existing one if available, as an atomic operation. The software is then expected to work with the document tied to that unique identifier (to take advantage of CouchDB transactions).
  • MyUnique.get_if_exists "Hello" only returns the identifier if it exists.
  • MyUnique.remove "Hello" releases the value, so that subsequent calls will receive a different unique identifier. This is has the elegance of a sledgehammer.
  • MyUnique.remove_atomic "Hello" old_id releases the value only if it is still owned by old_id (if it is not, then it does nothing).

The original code for the module looked like this:

type id    = Id.t
type value = string

(* We're manually constructing a format that we will need to pass to
   every database function. Not elegant. *)
type json join = < id : Id.t > ;;
let fmt = json_of_join, Fmt.protect "Unique.join" join_of_json

module Make = functor (DB:CouchDB.CONNECTED) -> struct

  let get_if_exists value =
    (* Also, we need to turn every value into an identifier, because this is
       what the database expects... *)
    let id = Id.of_string value in
    match DB.get fmt id with None -> None | Some join -> Some (join # id)

  let get value =
    let id = Id.of_string value in
    (* Transactions are raw "apply this function to the existing data" hammers,
       even though "insert if not exists" is not a nail, it's a screw, and
       a common one too. *)
    DB.transaction fmt id begin function
      | None -> let newid = Id.gen () in
                newid, CouchDB.Put (object method id = newid end)
      | Some o -> o # id, CouchDB.Keep
    end

  let remove value =
    let id = Id.of_string value in
    (* Deletion is fairly common, too... *)
    DB.transaction fmt id (fun _ -> (), CouchDB.Delete)

  let remove_atomic value current_id =
    let id = Id.of_string value in
    DB.transaction fmt id begin function
      | None -> (), CouchDB.Keep
      | Some o -> if o # id = current_id then (), CouchDB.Delete else (), CouchDB.Keep
    end

end

The new version looks like this instead:

(* For the |>> operator *)
open Breathe.Include

type id    = Id.t
type value = string

(* Now, formats are represented as modules *)
module Join = Fmt.Make(struct
  let name = "Unique.Join.t"
  type json t = < id : Id.t >
end)

(* And there's a wrapper to perform the value-to-id conversion
   automatically *)
module Value = struct
  type t = value
  let to_id = Id.of_string
  let of_id = Id.to_string
end

module Make = functor (DB:Breathe.DATABASE) -> struct

  (* Instead of relying on low-level "use identifiers and formats on
     every call" primitives as was done previously, we can now
     define a table with its identifier and value types described by
     modules, so conversions happen automatically. *)
  module MyTable = Breathe.Table(DB)(Value)(Join)

  let id_of x = x # id

  let get_if_exists value =
    (* Using tables and a map operator makes this shorter. *)
    MyTable.get value |>> BatOption.map id_of

  let get value =
    (* The ensure primitive eliminiates the need for specific code
       to handle this case. *)
    let fresh = lazy (object method id = Id.gen () end) in
    MyTable.transaction value (MyTable.ensure fresh) |>> id_of

  let remove value =
    (* So does the remove primitive... *)
    MyTable.transaction value MyTable.remove |>> ignore

  let remove_atomic value current_id =
    (* And the remove_if primitive... *)
    let has_id uniq = uniq # id = current_id in
    MyTable.transaction value (MyTable.remove_if has_id) |>> ignore

end

Using a monadic style for the code also has a number of advantages that did not exist with the imperative:

  • There is now a cache for values retrieved from the database. This cache is carried around when the monad-based code is evaluated, so its lifetime and scope are closely guarded by the Breathe.execute function that actually runs everything. There is no risk of an element staying in cache for hours, as the cache is discarded after every HTTP request. It also means several caches can co-exist within the application without stepping on each other.
  • Database failures are now handled by the monad : as soon as an error is encountered, monad evaluation stops and Breathe.execute reports the error instead of the expected result. This lets write-only operations report errors and interrupt the flow even though they return unit without spamming exceptions around.
  • Individual operations can be collected together and batched with the bulk API. This is something that is theoretically possible given the architecture of the library, but not implemented yet.
  • Code that involves database access is now clearly indicated as such, which helps increase its visibility and the propagation of “this might access the database” hints across the software.

On NoSQL Design Tips

Published
by
Victor Nicollet
on April 29, 2011
in Imperative
. 0 Comments

Cloud computing expert Joannes Vermorel posted a few design tips for your NoSQL app two weeks ago. As a short anecdote, Joannes is the man who (through a rather unintended and surprising chain of events) prompted us to move from SQL to CouchDB six months ago on the RunOrg project. So, here are my very own thoughts overlayed on top of Joannes’ five-point article :

You need an O/C (Object-to-Cloud) mapper : From my experience, almost all read-only code in the application involves some form of object graph traversal : select a root object, extract a list of related objects, filter the list based on a predicate… Most of the traditional Object-Relational impedance mismatch is a consequence of SQL’s insistence on performing most of that traversal on the database server using joins in a conceptually parallel environment (every non-discarded row is going to be treated the same by the join) where object-oriented strategies dictate that each object should be able to react differently based on its type. So, SQL-and-Objects leaves you with a sprinkle of duplicate traversal logic across tiers, and some low-performance application-layer graph traversal where polymorphism requires it. And by low-performance, I mean two hundred one-item requests in a row :

foreach (Document document in documents)
  owners.add(document.getOwner());

And there’s no simple way of dealing with this, short of dictating that documents don’t have owners, they have owner identifiers that can then be used to retrieve the actual owners from the database (which may be the case for persistent documents, but is a leaky abstraction that prevents the rest of your application from creating temporary in-memory documents). With a few exceptions, in NoSQL, there are no joins. On the one hand, this reduces the expressiveness of the data storage layer, but this also has the ironic consequence of making NoSQL more optimal for application-driven graph traversal. Adding insult to injury is that most key-value stores implement bulk queries which, when appropriately leveraged by the mapper, transparently improve performance. Breathe (the CouchDB mapper we use) does this :

let owners = documents |> Breathe.batch (fun doc -> doc # get_owner)

Since Breathe is purely functional and based on monads, any requests performed by the many doc # get_owner calls can be merged into a single CouchDB request using the bulk API.

Another reason why mappers are necessary is that unlike SQL, which works on an extremely simple “send query, get results” basis, most NoSQL solutions involve complex idioms using basic primitives. For instance, when dealing with CouchDB, you cannot press the “use transactions” button and expect it to work. CouchDB transactions involve posting a document, receiving a collision notification, downloading the new version of the document, applying the transformation again, posting the document again, and so on until you either run out of retries or no collision happens. And collision detection involves keeping a revision number around and passing it to the API, so your code also has to deal with whether there’s a cached in-memory copy of the object that you can use to grab the revision or if you will have to actually query the database. The public API provides nothing to relieve this pain, so it is up to the mapping system to do this :

let publish id =
  let publish article = { article with published = true } in
  Article.DB.transaction id (Article.DB.update publish)

The mapper will grab the initial page value from the database if it was not already in the cache, try the update 20 times if collisions happen, and place the latest version of the page in the cache. Using raw API calls, this would take ten lines and probably contain many bugs. And did I mention that the function above can use the bulk transaction API if placed in a loop ?

Performance is obtained mostly by design : which I would rephrase as “your O/C mapper abstracts operations, not architecture”. In short, there’s no way for your application to shield itself from the architectural consequences of NoSQL storage. For instance, CouchDB just doesn’t do multi-object transactions, so this is something that the application will have to take into account — this means that most operations are idempotent so they can be safely retried, and most cross-object invariants are expected to be eventually consistent.

And, indeed, you cannot write an application and then leave it to the database administrators to create an index wherever necessary. The good news is that most NoSQL solutions, by their simple design, make it hard to do any inefficient operations (it takes one line to do a full table scan in SQL, but it’s a lot harder to do with NoSQL, and a lot more obvious when it happens — why am I querying _all_docs again?)

The 20 updates/second limit should be taken with a grain of salt. NoSQL performance is certainly predictable, but sweeping generalizations never apply and there are many bottlenecks that you can hit in any particular order — application-database bandwidth, database-disk bandwidth, database processor usage… right now, CouchDB handles 130 updates/second (an update is a GET-PUT cycle), with the bottleneck being that the updates are synchronous on the application side, so it doesn’t send as many requests as the database could possibly handle (if you run two application instances, you can get 260 updates/second). This is a fairly healthy bottleneck to have, because it means adding more application instances solves it, and this just happens to be our scaling strategy ;-)

Go for a contract-based serializer : automatic serialization is great for one-shot messages that run between instances of the application, but a pain as soon as you need to persist them and, consequently, have the storage format evolve along with the application.

I have no opinion on the XML-vs-JSON debate, though I use JSON myself because it fits with both the database and client layers of my project.

In general, I find the use of NoSQL to be no excuse for making a mess in the database. Sure, you’re not constrained by a schema anymore, but data in the database is what you are going to manipulate ! If there isn’t a clean description of what you can find in the database, that data might as well be lost, because you will not be using it. Using application-wide conventions on data storage and representation helps developer A manipulate data generated by developer B without requiring a meeting to get everyone on the same page. Storing data in an opaque blob representation is fine for short-lived situations, obscure and rare edge cases (such as when the Lokad.Cloud queue offloads large objects into blob storage because it has to put them somewhere), but most of your data should have a clear documented schema. Your database does not need it, but your team does.

Entity isolation is easiest path to versioning : You Ain’t Gonna Need I (yes, I disagree with Joannes on this one). Unless something went terribly wrong with your code base, it’s  to duplicate your entity class when the two versioning paths actually start to diverge (and even then, you can certainly keep some common bits factored out nicely) instead of doing so from the very beginning.

With proper design, aka CQRS, needs for SQL drop to near-zero : Well, let’s face it: SQL provides a toolset that goes beyond anything any NoSQL solution in terms of general flexibility and expressiveness (including the ability to simulate key-value stores using blobs,should the need arise). NoSQL solutions remain niche solutions to niche problems because this is the way they are designed, possibly out of a fear of inadequacy and the general message “NoSQL should be used where SQL is not good enough” — most NoSQL users still use an SQL database as the primary storage, and dump data into NoSQL for a small subset of queries that need the performance boost. Companies like Lokad or RunOrg, that embrace NoSQL-only architectures, are still rare and still struggling to understand how, exactly, some things should be done in NoSQL that would take one line of SQL code. You don’t see Design Tips for SQL articles being written in 2011 ;-)

Even with CQRS, requirement changes have a much greater impact on NoSQL application architecture than they would with SQL, because SQL mappers despite all their flaws still manage to provide a significant amount of shielding. What used to be a matter of adding a few tables and doing the right joins now turns into an uphill battle of propagating the appropriate de-normalized data into the right places to allow for an index to be built (which, by the way, leads me to believe that Aspect-Oriented Programming might be more adapted for NoSQL than standard OOP) that simply isn’t possible without a nearly extremist agile culture. Sure, with CQRS and event sourcing, this isn’t a losing uphill battle we’re fighting anymore, but it’s still uphill. I’m pretty sure the reason why Joannes does not see things this way is that Lokad has an extremist agile culture.

PayPal Spam

Published
by
Victor Nicollet
on April 19, 2011
in Random
. 0 Comments

Last year, I created a PayPal account with no associated credit card number, as I was to receive some contest prize money to pay for a specific product. Since then, I have received a lot e-mail from PayPal.

There were several dozen advertisements that I would rather not have received. There was not a single e-mail to notify me that the credit card I once entered to do a one-shot payment six months ago had instead become associated with the account and was going to be used to pay for anything PayPal thought I should pay. There was not a single e-mail to notify me that the original specific product had a one-year renewal policy which, given that there was now a credit card associated with the account, was about to charge me again. Nor was there any e-mail to notify me that I had just been charged.

When an internet service sends flurries of advertisements but fails to send relevant and important information, it’s time to leave. I realize now that I should have closed my PayPal account right away, instead of keeping it around «in case I might need it again later»

A lesson learned and an account closed.

AJAX Tiles Game

Published
by
Victor Nicollet
on April 15, 2011
in Random
. 0 Comments

I started programming life by writing an AI for a simple game called RoboWar (back when it was a shareware game on Macintosh, in the pre-OS X days). Make sure you click the “Edit” buttons at the bottom of that page to view the kind of code I had to deal with. I then moved on to HyperTalk and, when I finally got my hands on a PC, started a ten-year spree in C++.

Recently, I started toying with a similar idea: to create a game where people could write an AI that would play for them, with simple and easily modeled rules, and a really easy way to share your creations with your programmer friends (because just adding your AI to a long list of other AIs is kind of boring and not very social).

So, I wrote a simple game in JavaScript. You feed it one URL for each player, and the game connects to that URL and asks for the next move. So, your AI is one URL, which makes it easy to share. Not to mention that you can probably write that AI in any language you wish, provided it can respond to HTTP requests and read JSON arrays of characters, and you can resort to a lot of fancy stuff (cloud computing, learning from experience, genetic algorithms) that would otherwise not be available in a game like RoboWar. The game board is readily available for you to observe while the game is played. It looks like this:

The rules to the game are fairly simple: pick white tiles to paint them with your color, pick tiles you already own to nuke them (blows up that tile and the four adjacent tiles as well), and connect a large group of tiles you own to a small group of tiles your opponent owns to conquer them. The player with the most tiles when the board is covered, wins. Play it here. I’ve already programmed four different AIs:

  • http://tiles.nicollet.net/ai/?random plays randomly.
  • http://tiles.nicollet.net/ai/?expand creates one single group of tiles and expands it as fast as possible.
  • http://tiles.nicollet.net/ai/?fearful nukes its own tiles when they might become connected to enemy tiles.
  • http://tiles.nicollet.net/ai/?contain attempts to contain the enemy in a prison of nuked tiles.

None of these are particularly good, and a human player can certainly beat them quite easily, but they’re a good challenge for your own AI. If you wish to participate without starting from scratch, you can fork the sample AI on GitHub to create your own (it’s PHP code). Also, the GitHub README contains all the technical details about what data your AI URL receives and what data it should respond with. And, if you’re curious, the game rules are cleanly described in the JavaScript source code.

I’m looking forward to hearing from you. Please share your AIs in the comments below, if you please: I’m really interested in what you might come up with.

99 OCaml Problems

Published
by
Victor Nicollet
on April 13, 2011
in Functional
. 0 Comments

I find that when learning the basics of a new functional language, or introducing oneself to functional programming in general, the 99 Lisp Problems are a good start. You don’t have to run through all of them, but how fast you can solve them says a lot about your fluency in the language, and has many things to teach even to otherwise experienced programmers.

I’ve started committing solutions to those 99 problems in the Objective Caml language to GitHub ; the repository is:

https://github.com/VictorNicollet/99-Problems-OCaml

If you’re interested in starting OCaml programming, have read the manual, and are looking for exercises to get up to speed, consider spending a little time trying to come up with the solutions on your own, using my solutions as a reference. And if you’re an OCaml expert, feel free to propose corrections and improvements : this is what GitHub is for.

Other solutions for OCaml do exist, for instance from Christian Kissig, which is currently more complete than mine. Note that we don’t share the same philosophy as far as writing the code goes, so you can probably look at both sides of the issues. For example, on the “find the last element of a list” problem, Christian throws an exception if no last element exists, while I return None, because I hate exceptions.

Enjoy.

Object-Oriented For the Win.

Published
by
Victor Nicollet
on April 1, 2011
in Imperative
. 2 Comments

Readers, beware: this is an opinionated piece. Feel free to curse appropriately in the comments below, should you find the need to do so. I’m writing this because of yet another encounter with an object-oriented zombie, and one without the excuse of being fresh out of school. They all stand united behind the motto that Object-oriented programming makes your code easy to reuse, debug, maintain and extend and I happen to disagree.

Something interesting happened in the Pacific Ocean after World War II: during the war, American soldiers had set up air strips on Pacific islands, complete with little control towers that had radio stations. And the natives observed that those soldiers would speak into a weird piece of metal, and a giant iron bird would land from the sky and deliver food and supplies. Then, the war ended, the soldiers went home, and the natives tried to bring the giant iron birds back by building shacks that looked like legitimate control towers, and spoke strange words into rocks that looked like legitimate microphones, and it worked!

No, it didn’t. Cargo planes did not come back because it was not the shape of the microphone and antenna that brought in the planes, it was their invisible electromagnetic properties. These are the cargo cults: imitating the outside appearance of things that work and expecting the imitation to work as well. The same happens with object-oriented programming — the use of classes, or inheritance, or design patterns is not the reason why good code is good: they are merely tools which happened to be applied by knowledgeable and skilled programmers in order to avoid problems that they knew would happen if they did not preempt their appearance. To look at their code, find out that they used classes, and deduce that classes were responsible for their success is about as rational as expecting to steal the strength of your defeated foe when you eat his flesh. Object-oriented programming can only solve design problems you know you need to solve.

Imagine a piece of old, spaghetti C code written in procedural style, with functions calling each other and accessing global variables all over the place. I suspect many young graduates these days never had to deal with these — and I wouldn’t have either, were it not for my unrequited love for mental anguish and programmer pain. Back to the point: in your mind, draw an arrow from A to B if function B calls function A or accesses global variable A. This is a dependency graph: if you were to change the run-time behavior of A, then the behavior of B would almost certainly change as well. By following all outgoing arrows from the point you altered, you can find every element that could possibly be affected by it.

No programming style or design methodology on earth is going to change this ; whether object-oriented or aspect-oriented or functional, functions call other functions, and changing one part will have an impact on many other parts. That is something we accept, because propagating changes is part of the programming job, and we have even elevated refactoring — the propagation of the absence of changes — to the level of a good thing since sliced bread.

And since we have to track down all the dependencies of a given entity sooner or later, our national sport is to make it as easy as possible. One way is to let the compiler or build process help — compilers detect type mismatches that are usually a hint of non-propagated major behavior changes, while automated unit tests and regression tests handle more subtle changes, and both of these are fairly independent of your programming style. Another way is to willingly reduce the number of dependencies through architectural constraints — Model-View-Controller prevents a model from being dependent on a controller, because altering a controller should not change the behavior of a model. These are fairly common ways to reduce static dependencies.

Then, there are the dynamic dependencies — functions which alter the behavior of other functions at run-time. Remember those global variables from the C program? If function A writes to the global variable and function B reads from the global variable, then calling A will probably change the behavior of B. Runtime dependencies are fairly obvious to map: every time a function writes to a global variable, draw an arrow from the function to the global variable and mark the function as having a side-effect. Then recursively do the same for every function that calls it, and so on until you run out of functions. Your dependency graph just became a lot hairier than it was before.

Such dependencies are the reason why working on the report-printing feature in your invoicing software somehow managed to break the database storage : even though both modules are independent and the static dependency tree for report-printing does not flow into the static dependency tree for database storage, there are a handful of global variables that allow your changes to follow dynamic dependencies and leave a flag unset when it should have been set and ultimately blow up the nuclear silo.

So, when you have global mutable state, then changes can jump from module to module through those pieces of global state. Procedural programming mostly dealt with this by cleanly wrapping up any global state in a module, and having modules interact with each other by means of interfaces that managed to guarantee some invariants on the global state. But still, some problems remained. I am reminded here of the code to Dungeon Crawl, an open-source game written in procedural style, where the module responsible for dealing damage to the player will make frequent calls to the module responsible for outputting messages about the damage being dealt (“The hobgoblin hits you!”). As written, you cannot use the damage-dealing code without displaying messages, so writing an AI module that tries to predict the outcome of an attack is harder than it seems, because it cannot use the existing damage-dealing code to run predictions.

They actually have sludge elves.

Functional programming solved the global mutable state issue by eliminating global mutable state altogether. In the aforementioned example, the damage-dealing module would return the new damaged player along with a list of messages that were generated, and these messages could then be discarded silently in the AI subroutine, or forwarded to the screen in the main routine. I am a big fan of functional programming, but let’s face it: not only is it harder on the brain than good old set-variable-values-everywhere programming, but it does not suit well to situations which have an implicit reliance on global mutable state — such as web servers connected to a persistent database. I look forward to a pure functional friendly database, but it’s not there yet.

Both of these solutions rely on encapsulation: whatever happens to be the implementation of a procedural or pure functional module is hidden, and only available through those functions. This creates a dependency bottleneck, so any changes performed within the implementation can only leak out through the interface in tightly controlled ways — at compile-time, those are called contracts, at run-time they are called invariants.

Object-oriented programming works by deprecating global mutable state. It’s not completely gone, and some programmers yearning for the good old days still try to enjoy some global goodness by using the Gang of Four Singleton pattern, but it’s mostly deprecated. The sickle and hammer of object-oriented programming are dependency injection and late binding, and it uses them to break down the structure of static dependency graph bourgeoisie.

Yes, object-oriented programming is all about building the dependency graph at run-time. Then again, a program that generates machine code at run-time does the same. Object-oriented programming merely provides a set of tools that are easier on the human brain than the extremes of generating machine code at run-time. As an aside, keep in mind that it is not the only toolbox available to you: any language with closures can do the same, and although closures are both more elegant and slightly more complex to handle in the general case, they have found their way into event-based programming because an event handler is just, well, a closure. This is why jQuery passes functions around everywhere instead of requiring the user to implement an IAjaxResultVisitor interface: it’s shorter, but still fairly easy to understand in that context. If you push things far enough, most objects are usually nothing more than dictionaries of closures.

Back to the point: writing a proper object-oriented program with those tools is about the same as creating a statue out of stone using sculpting tools, and inheritance will not turn someone into an object expert any more than holding a chisel turns them into a mutant ninja turtle disambiguation page. How does it happen?

The original problem with procedural programming was that there was no easy way to unplug the damage-dealing module from the message-printing module. Dependency injection means that the damage-dealing module (which is now an object) does not know about the message-printing module (which is now also an object), instead, whoever needs to use damage-dealing code must provide it with a message-printing object that will be used to print whatever messages come up. That message-printing object might actually print those messages to the screen, or it might silently discard them, or it might keep them around and only display them to the screen if a specific event happens, or it might be an unit testing mock, or any other amount of different behaviors. In terms of dependency graphs, there is no static connection between damage-dealing and message-printing: the program decides at run-time what message-printing object should be bound to what damage-dealing object, and can create new objects on the fly should the situation require it.

Aside from that, there are no significant architectural benefits to using objects or classes — although touted as an object-oriented achievement, encapsulation is commonly available in functional and procedural programming as well, and using object.function() instead of function(object) is a matter of taste, not architecture.

As a final word, I am fairly doubtful of the ability of schools to teach their students about good object-oriented programming. They can certainly teach them how to use the tools, but the pains that object-oriented programming is meant to solve only become obvious when you have to work with a large, multi-developer project over a long duration and with changing requirements — anything less, and your pains will be subtle feelings of awkwardness instead. Definitely not something you can learn from. If you have never written an unmaintainable piece of mud, you cannot know how object-oriented programming can keep you from writing one.

You may now dish out punishments in the comment box below. Have fun.

1342 feed subscribers
(readers who polled a feed this week)