Laurent Petit

The Clojure Omnibus

| Comments

This post is a port of the blog post The Java Omnibus to the Clojure language.
It targets developers beginning or with some notions of Clojure, who want to quickly get up to speed with the episode’s algorithm challenge.

The Tale Of Two Servers

The goal of Code-Story episode S03E01 is to code the algorithm that moves an elevator’s cabin within a building.

There are two systems, the building, and the cabin. Two pieces of software, one for each. The Code-Story Team provides the building server and we (the competitors) write the cabin server.

The Code-Story team provides a building server, which patiently waits for cabin server registrations. You manually register your cabin server through a dedicated web page: by giving its ip and port. Then the building server starts calling your cabin server periodically.

When the building server calls your cabin server, it describes what’s happening. In this simulation, there is a limited set of events. People in the building can call the cabin from their floor. They can enter. Once inside the cabin they state at which floor they want to leave. Once the cabin is at the right floor they exit when it opens its doors.

That’s all.

The building server is going to call the cabin server through repeated http calls. For instance when someone enters the cabin, the building server calls the /userHasEntered url on the cabin server. When a user calls the elevator, the building server is going to call the /call url passing in query parameters the floor at which the call was made.

The Short Version

  • The Code-Story team will provide a server for the building

  • You need to code a cabin server

  • This cabin server code must be some kind of http server

  • It needs to listen to a few dedicated url

  • To get started, you need to register the cabin server by hand on a dedicated web page served by the building server.

Events

The starting position of the cabin is at the lowest floor, doors closed, and no user is in the building or the cabin, yet.

Here’s the list of http requests your cabin server needs to listen to. All the calls are made with a http GET verb.

  • /call?atFloor=[0-5] means someone is waiting at floor atFloor to get into the cabin

  • /userHasEntered means someone just entered the cabin

  • /go?floorToGo=[0-5] means someone, who just got into the cabin, wants to leave the cabin at floor floorToGo

  • /userHasExited means someone just exited the cabin.

  • /reset is issued to resynchronize the building and cabin states to the starting position. It can occur if the cabin made an impossible move, for instance going below the lowest floor for instance, or moving while the doors are open.

For the building server to be happy you just need to answer with a 200 OK HTTP response.

nextCommand

But the cabin needs to take some action, so answering empty text is not going to lead it anywhere.

The building server will issue regularly some /nextCommand waiting for a proper answer. The answer you can give back to the building server is one of the following

  • OPEN: you open the doors of the cabin

  • CLOSE: you close the doors of the cabin

  • UP: you want the cabin to go up one floor

  • DOWN: you want the cabin to go down one floor

  • NOTHING: the cabin does nothing.

So when the server wants to know what the cabin is doing, you must answer one of this 5 answers with a 200 OK (and a Content-Type: plain/text).

Enough Talking, Let’s Code !

Pre-Requisite

You must have:

  • Jdk7+

  • Leiningen 2

  • Git

  • Basic knowledge of http server

The Building Server

The building server can be obtained on Github at https://github.com/jeanlaurent/code-elevator

You should first get it running just to see how it works:

git clone https://github.com/jeanlaurent/code-elevator
./run.sh

Then open your favorite browser and go to http://localhost:8080/

You can register yourself with a fancy url just to see how it works. Type in your name, some email and let’s say http://127.0.0.1:9090/

It should look like this:

register

You can now have a glimpse at the cabin, and the building. The building’s server at http://localhost:8080/ tries to connect to a cabin server at http://localhost:9090/ but finds nothing, and spurs error after error.

fail

Notice the points goes down quite a bit. So you should probably unregister.

Now we need to start coding.

Simple Server

In the Clojure world, the first thing you must write is a Clojure file named project.clj like this:

project.clj
(defproject elevator "0.0.1-SNAPSHOT"
  :dependencies [ [org.clojure/clojure     "1.5.1"]
                  [compojure               "1.1.5"]      ; (1)
                  [ring/ring-jetty-adapter "1.2.0"] ])   ; (2)

  1. Compojure is a library for writing Web applications. It comprises: an HTTP request/response abstraction (based on the Ring library), and features to create “HTTP Request Routes” (mapping request URLs to functions which will process the request - the handlers -). A word on Ring: it is a library which abstracts HTTP requests and responses as plain Clojure maps. The possible keys for the request and response maps are formalized in a specifications document and are an integral part of the Ring API. This is a classical trait of Clojure libraries: standardizing on information/data first, and behavior (functions) second.

  2. ring-jetty-adapter is an optional module of the Ring HTTP library for easy integration with the Jetty web server library.

Not Loosing Is Winning ?

To make things simple, first let’s start by not losing points. You lose points by actually not answering to all calls or answering them with something else than a 200 OK. So we should write a server which answers 200 OK to any call, regardless of the actual meaning of the call. And we should answer NOTHING to every /nextCommand calls.

Let’s use the Compojure web library which enables us to start quickly writing some interesting code.

Let’s create file main.clj in the src folder:

src/main.clj
(ns main
  (:use ring.adapter.jetty
        compojure.core))

(defroutes app
  (GET "/nextCommand" [] "NOTHING")   (1)
  (GET "*"            [] ""))         (2)

(defn -main []
  (run-jetty app {:port 9090}))

  1. If the route is /nextCommand answer 200 OK (implied) with NOTHING in the payload

  2. If the route is something else answer 200 OK (implied) with an empty payload

Now run the -main function of the main namespace, by invoking Leiningen on the command line:

$ lein run -m main
2013-10-24 23:54:58.424:INFO:oejs.Server:jetty-7.6.8.v20121106
2013-10-24 23:54:58.511:INFO:oejs.AbstractConnector:Started SelectChannelConnector@0.0.0.0:9090

Then register again in your building server. You should see that the score now stays at zero. You’ll notice also that some people are actually calling our cabin, but as every time the building server calls the nextCommand the cabin answers NOTHING, nothing moves, and the people can die waiting for the cabin to come.

nothing

SRP

But the server code is not going to change much, while the elevator code is. The elevator code is where everything is going to happen. And as you know your SRP principle by heart, “a function has one reason to change, and only one”, We are going to split the responsibilities: the route dispatching, the http-level request handling, and the cabin (logic stuff, http agnostic).

In a real Clojure application, we may start to engineer a little bit more, and create a separate namespace for the elevator (logic) stuff. There’s no real pressure to do so right now, so we’ll keep things simple and just use one namespace.

Change the main.clj file like so:

src/main.clj
(ns main
  (:use ring.adapter.jetty
        compojure.core))

(defn next-command [] "NOTHING")                 ; (1)

(defn next-command-handler [] (next-command))    ; (2)

(defroutes app
  (GET "/nextCommand" [] (next-command-handler)) ; (3)
  (GET "*"            [] ""))

(defn -main []
  (run-jetty app {:port 9090}))

  1. The next-command function implements the core logic. Granted, it is quite simple at the moment

  2. The next-command-handler function is the interface between the Web World and our web-agnostic algorithm in next-command. Granted, it does not do much at the moment. Be patient ;-)

  3. The routes definition directly calls next-command-handler. When time will come to e.g. extract parameters from the Request, this separation of concern will prove more useful.

Note

While we didn’t really feel any pressure to create 2 levels of indirection (next-command-handler, and then next-command), they have been introduced at once to keep this article shorter. In the real world, an intermediate shape of the code could have been to have next-command-handler directly return “NOTHING”, saving the introduction of the next-command function for later.

Clojure code puts a strong emphasis on application state management. The less state, the less moving parts, the better. So for the moment, the algorithm requires absolutely no state, and there’s indeed no state in the code. Not even yet a kind of “Cabin instance”. Just a separation of concerns via the introduction of an indirection level.

Stop and restart your server via the Leiningen command line and check that the number of points in the building server web page still doesn’t change. We have made some baby steps to be ready to code an efficient (cough, cough) algorithm now.

The Omnibus

The Omnibus Elevator algorithm is a very good starter because you only have to take care of the nextCommand call and know the number of floors in the building.

By chance we know it’s a 20 story building (it’s a little bit more dynamic than that, but at least for the first week, it’s 20 floors).

The Omnibus idea is to go to each floor, open the doors, close them and go to the next floor. We do this up and down, all the time. By doing this, we are pretty sure to get anyone waiting in the cabin, and anyone who may want to leave can since we stop at any floors by going up or down. This is not efficient. But this is a very good first baby step into the problem to learn more on the way.

One thing to know, or notice by doing that, is that all the people waiting at a given floor will rush into the cabin as soon as it opens, and all the people inside will rush out at the same time. So you don’t need to wait for people to get in or out.

We should start using the other commands at our disposal, rather than answering NOTHING.

At a given floor we should first answer OPEN, then at the next nextCommand call we should answer CLOSE, then move UP or DOWN depending on the current direction of the cabin (ascending or descending phase).

So we have to issue 19 times a OPEN, CLOSE, UP commands and then OPEN, CLOSE, DOWN. Rather than keeping records of what floor the cabin currently is at, and writing the conditional logic for issuing an OPEN, CLOSE, UP or DOWN command, we can predetermine the full commands by creating an infinite lazing sequence cycling through the alternating 5x3 commands while the elevator is going up then 5x3 commands while the elevator is going down:

(defn make-omnibus [nb-floors]
  (let [up   (repeat (dec nb-floors) ["OPEN", "CLOSE", "UP"])     ; (1)
        down (repeat (dec nb-floors) ["OPEN", "CLOSE", "DOWN"])
        up-then-down (flatten (concat up down))]                  ; (2)
    (concat ["NOTHING"] (cycle up-then-down))))                   ; (3)

  1. dec is the decrement function: (dec 2) returns 1 (see ClojureDocs or Reference Doc). (repeat n a-sequence) produces a sequence repeating a-sequence n times: (repeat 3 ["O", "P"]) returns (["O", "P"], ["O", "P"], ["O", "P"]) (see ClojureDocs or Reference Doc)

  2. concat concatenates its sequence arguments: (concat [1 2] [3 4]) returns (1 2 3 4) (see ClojureDocs or Reference Doc). flatten transforms nested sequences into a flat sequence: (flatten [ [1 2] [3 4] ]) returns (1 2 3 4) (see ClojureDocs or Reference doc)

  3. cycle creates an infinite sequence as if concatenating its sequence argument to itself, again and again and again: (cycle [1, 2, 3, 2]) returns (1 2 3 2 1 2 3 2 1 ...) (see ClojureDocs or Reference Doc). You may have noted that the input types are of the type [ xx, yy ] while the output types are of the type ( xx, yy ). [1 2] is a vector, a datastructure. (1 2) is a seq(uence). repeat, concat and cycle return lazy seqs: their elements aren’t all computed yet ; they are computed just in time, when their are traversed.

The function make-omnibus returns a lazy-sequence whose shape depends on the number of floors. For 2 floors, it would return ("NOTHING", "OPEN", "CLOSE", "UP", "OPEN", "CLOSE", "DOWN", "OPEN", "CLOSE", "UP", "OPEN", "CLOSE", "DOWN", "OPEN" .....).

For the Omnibus algorithm, we need to store the state of the elevator cabin.
Clojure promotes strict separation of concepts of identity, state and value. In a nutshell, it means we will use pure functions at the core of our algorithm, and manage state change at the boundaries of the program. Request handlers will be responsible for managing the state of the elevator cabin (get the previous state, store the new state. The hard work will be delegated to pure functions).

Note

The nextCommand event is interesting. It acts both as an event indicating that the elevator should compute its next command, and it also acts as a getter to query the new state. As you may have learned from good principles from Object Orientation, it’s generally not a good idea to have a getter that also changes the internal state of the object.
The same applies to Clojure.

In the Omnibus algorithm, the state is an infinite list of pre-determined commands to issue. To compute the next state, we just remove one element from the list and make this the new state.

We cannot change the external API of our cabin, it is dictated by the rules of the contest. But we can avoid to propagate this design decision to the core of our algorithm. So we’ll deal with a coumpound nextCommand at the request handler level: we’ll split the nextCommand into a tick state-altering Event and a next-command state-preserving/idempotent Getter.

(defn tick [elevator] (rest elevator))           ; (2)
(defn next-command [elevator] (first elevator))  ; (3)

(def nb-floors 20)
(def cabin (atom (make-omnibus nb-floors)))      ; (1)
(defn next-command-handler []                    ; (4)
  (let [new-state (swap! cabin tick)]
    (next-command new-state)))

(defroutes app
  (GET "/nextCommand" [] (next-command-handler)) ; (5)
  ...)

  1. The cabin is the piece of state of the application. Here we just encapsulate the state in an atom. An atom is one of the simplest state referencing types of Clojure: an atom holds a value, and has clearly established synchronous functions that can be applied to it to change the value it contains. Underneath, it really is a java.util.concurrent.Atom instance (see ClojureDocs or Reference Doc).

  2. The tick function removes the head of the list and returns the new list. The effect is that the state rotates the list of one element.

  3. The next-command just returns the head of the list. Note that it’s an idempotent function. It does not change the state of the cabin.

  4. The next-command-handler modifies the cabin state: swap! calls the tick function to the current state value, and the state becomes the result of the call to tick (see ClojureDocs or Reference Doc). Then next-command is called on the new state.

  5. Note that we changed the name of the handler for the /nextCommand route from next-command to next-command-handler

Now stop and start the server again, via Leiningen. You should see your elevator going up and down, starting to get people on board.

omnibus

Final code

Since there is still so little code for the Omnibus implementation, please find it all below:

project.clj
(defproject elevator "0.0.1-SNAPSHOT"
  :dependencies [ [org.clojure/clojure     "1.5.1"]
                  [compojure               "1.1.5"]
                  [ring/ring-jetty-adapter "1.2.0"] ])
src/main.clj
(ns main
  (:use ring.adapter.jetty
        compojure.core))

(defn make-omnibus [nb-floors]
  (let [up   (repeat (dec nb-floors) ["OPEN", "CLOSE", "UP"])
        down (repeat (dec nb-floors) ["OPEN", "CLOSE", "DOWN"])
        up-then-down (flatten (concat up down))]
    (concat ["NOTHING"] (cycle up-then-down))))

(defn tick [elevator] (rest elevator))
(defn next-command [elevator] (first elevator))

(def nb-floors 20)
(def cabin (atom (make-omnibus nb-floors)))
(defn next-command-handler []
  (let [new-state (swap! cabin tick)]
    (next-command new-state)))

(defroutes app
  (GET "/nextCommand" [] (next-command-handler))
  (GET "*"            [] ""))

(defn -main []
  (run-jetty app {:port 9090}))

Laurent Petit

Note

To keep this post short and friendly for people new to Clojure, I’ve intentionally made some choices in what is presented. For instance, I’m not talking about interactive development at all. I’m also using the short (:use) directive in the namespace declaration instead of (:require).
I’ve also made the choice in this first version to explain how to start the project from the command line. I intend to adapt it to Counterclockwise + Eclipse, especially to make it easier for Windows people to start.

Code Story, Clojure Et Moi

| Comments

Cet article est le premier d’une série visant à présenter le langage Clojure via l’implémentation d’une solution tout Clojure au challenge CodeStory.

C’est à quel sujet ?

J’ai eu le plaisir de participer et me qualifier à la première phase du concours de programmation Code Story 2013.

Pour y parvenir j’ai choisi d’utiliser le langage Clojure.

Je voulais apporter un peu d’exotisme en utilisant la programmation fonctionnelle, pour changer un peu de toutes les contributions qui allaient utiliser le même paradigme impératif (Java, Kotlin, Ceylon, Groovy, Scala, etc.).

Ce premier article se concentre sur quelques caractéristiques du concours, et pourquoi Clojure est un langage de choix pour les adresser

Web Services

Pour participer à l’épreuve, il fallait mettre en place un serveur Web. Toutes les questions, y compris les énoncés, ont été envoyées par HTTP GET ou POST.

Ring est la librairie standard Clojure pour écrire des applications Web. C’est une abstraction “minimaliste” (mais pas simpliste !) d’un serveur web.

Clojure+Ring pour faire une appli Web : c’est simple, lisible, concis

TDD

Le déroulement des épreuves imposait un format analogue à la méthodologie TDD (Test-Driven Development) :

  • Envoi d’un test en boucle sur nos serveurs, jusqu’à obtention d’une réponse correcte
  • Complexification incrémentale des tests envoyés

Dans ces conditions, il n’est pas rare (ni anormal) d’avoir à réécrire de grandes portions de code. Une étape de refactoring entre chaque nouveau test est généralement nécessaire en TDD

Il est naturel d’adopter l’approche TDD en Clojure, car le langage :

  • Facilite l’écriture des tests : les tests sont concis, lisibles, faciles à refactorer.
  • Facilite l’écriture du code : écrire du nouveau code en Clojure est une danse entre l’éditeur et l’environnement dynamique d’exécution. Tout nouveau code est façonné / testé dans l’environnement d’exécution. Imaginez le remplacement à chaud du mode Debug de votre IDE, “on steroïds”.
  • Favorise le refactoring : le code Clojure est généralement très concis. Souvent 3 à 10 fois plus concis que son équivalent Java, par exemple. La masse de code à modifier fait moins peur. De plus, l’unité de réutilisation de code étant la fonction, et non la classe, le code est naturellement plus facile à refactorer.

Clojure pour faire du TDD, c’est efficace, lisible, simple, concis

Performances

Le dernier exercice du concours a soumis nos méninges à rude épreuve. Il ne suffisait pas d’avoir un code qui fonctionne, il fallait trouver un code “performant”.

Mais pas “Performant” comme dans “comment gagner quelques microsecondes dans l’exécution d’une requête portant sur quelques éléments à traiter”. NON. “Performant” comme dans “écrire un algorithme pouvant traiter une requête portant sur plusieurs centaines de milliers, ou des millions, d’éléments”.

Pour cette épreuve, écrire un algorithme récursif “naïf”, puis tenter des optimisations locales dessus, c’était un peu comme être sur le Titanic pendant le naufrage, à s’acharner à graisser les portes de la salle de réception. Ça occupe, mais ça ne sert à rien. Au-delà de 100 entrées, un algo “naïf” prenait déjà plusieurs dizaines de secondes. Pour CodeStory, il fallait être capable de traiter des requêtes de 50.000 éléments ou plus ! On attend toujours que les algorithmes récursifs aient fini de répondre … (pauvres chatons)

Pour être honnête, sur ce genre de problème, le langage de programmation importe peu

Si vous n’avez pas le bon algorithme, aucun langage ni aucun ordinateur si puissant soit-il ne vous viendra en aide : vous n’y arriverez pas. Un algorithme de complexité algorithmique quasi linéaire (dont le temps de réponse est proportionnel, ou légèrement proportionnel au nombre d’éléments à traiter) l’emportera haut la main sur n’importe quel algorithme de complexité exponentielle, et ce dès que la taille du problème dépassera quelques dizaines d’éléments.

Là encore, soulignons les caractéristiques de Clojure qui ont facilité la résolution de ce problème:

  • Facilité de prototypage : la librairie de base de Clojure est riche en fonctions de manipulation de collections. Les sort, group-by, max-key, etc. y sont presque toutes !
  • Facilité de refactoring : le code produit restant concis, il est facile de le refactorer, d’en produire une version différente. Le fait de manipuler des fonctions plutôt que des classes est un accélérateur de ce phénomène.
  • Code performant : à algorithme identique, il reste important que le langage utilisé ne soit pas extrêmement plus lent que les langages “concurrents”. En utilisant du Clojure “idiomatique”, sans chercher à optimiser, sans compromettre la lisibilité (sous réserve de connaître Clojure et les fonctions standards utilisées, oeuf de course), le code produit s’est avéré du même ordre de grandeur que les solutions concurrentes. En moyenne seulement 2, parfois 3 fois moins rapide. Il serait possible d’optimiser pour aller “talonner” les langages impératifs (utilisation de tableaux, par ex.), mais c’était juste non requis, donc non nécessaire.

C’est tout pour aujourd’hui

Si ce premier article vous a mis l’eau à la bouche, et que vous souhaitez que je continue la série avec des articles techniques et du code, envoyez-moi un petit mot d’encouragement :–).

Merci de m’avoir lu.