The International Obfuscated Clojure Coding Contest

December 29, 2014 at 11:31 am | Posted in Clojure, Programming | 3 Comments
Tags:

While some people may argue that Clojure is already obfuscated by default, I think it is about time to organise an official International Obfuscated Clojure Coding Contest similar to the IOCCC. This idea was born out of my own attempts to fit my Clojure experiments in one single tweet, that is 140 characters.

Winning IOCCC entry: flight simulator

The plan

First get some feed back from the Clojure community on this idea. You are invited to share your thoughts as comments to this blogpost. I will also twitter about this idea. If this particular tweet will get 100+ retweets, I will go ahead with the next step in the plan, which is establishing the rules for this contest.

These rules are also open to discussion. At the moment I’m considering for example a category ‘Code fits in a single tweet’ and another one like ‘Code size is limited to 1024 characters’.

After these preliminary steps I will set up a website, find a jury to judge the submissions and will continue from there.

Inspiration

Since Clojure is such a powerful language, there are also plenty opportunities to make the code more challenging to read. Mike Anderson already created a GitHub project called clojure-golf with some tricks.

You are also invited to violate the first rule of the macro club: Don’t write macros. And obviously the second rule (write macros if that is the only way to encapsulate a pattern) should be ignored as well.

Also extending datatypes in unexpected ways is alway a good idea. See for example my answer to this StackOverflow question about ‘an idiomatic clojure way to repeat a string n times‘.

Generating code on the fly is of course a breeze in a ‘code-as-data’ language like Clojure.

Finally

So if you think you can create a fully functional chess engine in 1024 characters, a Java interpreter in a single tweet or managed to make the Clojure REPL self-conscious with your obfuscated code, leave a comment. Also if you have suggestions for rules, want to help with setting up a website, want to be a judge or want to help in another way, I would love to hear from you.

And most importantly: have fun!

Advertisements

Refactoring Java using Clojure with the Eclipse Java development tools (JDT)

March 10, 2013 at 2:17 pm | Posted in Clojure, Programming | 4 Comments

Not a very catchy title this time, since this post will be mostly about hardcore nerdy coding. In my previous post I talked about the business value of elegant code. I argued that cleaning up an existing codebase in the maintenance phase still makes a lot of sense, but only if it can be done cheaply. One of the ways to make it cheap (cost-effective might be a better word if you need to sell this to your management) is of course to automate the refactoring process.

The problem

By automating I mean automating detection of code smell and automating fixing this smell. This in contrast to tools that are very good at detecting but don’t fix anything. For example Sonar. Also in contrast to most IDE’s that allow you to select a piece of code and select for example the ‘Extract method‘ action from the menu. That certainly is helpful, but your IDE will probably not detect if that is needed. It will just execute what you tell it to do.

Let me first show you an example of some Java code that I would like to refactor automatically:

public class A {
   int answer() {
      return (42);
   }
}

I case you already haven’t noticed: in the code above the return statement has an extra pair of parenthesis. You can find many discussions on the internet on why this is or isn’t a good thing, but personally I don’t like them for the simple reason that return is a keyword and not a function. Extra parenthesis just add visual noise. So what I would like to see instead is:

public class A {
   int answer() {
      return 42;
   }
}

This simple refactoring is already surprisingly difficult if you want to do this with a set of regular expressions since you need the context of the return statement. For example you have to be sure it’s not part of a comment or a string. The alternative is to fully parse the code and create an abstract syntax tree (AST). Again you can create one yourself using for example ANTLR and a grammar for the language of your choice. I decided to use the Eclipse Java development tools in combination with Clojure. The scope of my experiment: being able to refactor above example.

Preparation

I got the idea for this blogpost from ‘A complete standalone example of ASTParser‘. This post lists all the Eclipse libraries you need. You will have to add these libraries (8) to your own local Maven repository. Assuming you are using Leiningen 2, I followed these steps described by Stuart Sierra. For example to add an artifact to my local Maven repository called maven_repository within my Leiningen project, I used:

mvn deploy:deploy-file -DgroupId=org.eclipse -DartifactId=text -Dversion=3.5.200 \
-Dpackaging=jar -Dfile=/Users/maurits/development/eclipse/plugins/org.eclipse.text_3.5.200.v20120523-1310.jar \
-Durl=file:maven_repository

I added all the dependencies do my project file. It looks like this:

(defproject ast "0.1.0-SNAPSHOT"
  :description "FIXME: write description"
  :url "http://example.com/FIXME"
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :dependencies [[org.clojure/clojure "1.5.0"]
                 [org.eclipse.core/contenttype "3.4.200"]
                 [org.eclipse.core/jobs "3.5.300"]
                 [org.eclipse.core/resources "3.8.1"]
                 [org.eclipse.core/runtime "3.8.0"]
                 [org.eclipse.equinox/common "3.6.100"]
                 [org.eclipse.equinox/preferences "3.5.0"]
                 [org.eclipse.jdt/core "3.8.2"]
                 [org.eclipse/osgi "3.8.1"]
                 [org.eclipse/text "3.5.200"]]
  :repositories {"local" ~(str (.toURI (java.io.File. "maven_repository")))})

Now that the preparations are done we can finally start to write the actual refactoring code.

Refactor it!

First the code to create the AST from the Java code and the actual example I am going to use:

(ns ast.core
  (:import (org.eclipse.jdt.core.dom ASTParser AST ASTNode)))

(defn create-ast
  "Create AST from a string"
  [s]
  (let [parser (ASTParser/newParser(AST/JLS3))]
    (.setSource parser (.toCharArray s))
    (.createAST parser nil)
    ))

(def example
     (create-ast (str
                  "public class A {"
                  "   int foo() {"
                  "      return (42);"
                  "   }"
                  ""
                  "   int bar() {"
                  "      return 13;"
                  "   }"
                  "}")))

As you will notice creating an AST with the Eclipse JDT only takes a very few lines of code: on line 7 I create a JLS3 (Java Language Specification 3) parser, Line 8 tells the parser where it will get its source (in this case a string) and line 9 creates the AST. Next I need some helper functions:

(defn parenthesized-expression? [expr]
  (= (.getNodeType expr) ASTNode/PARENTHESIZED_EXPRESSION))

(defn return-statement? [stmt]
  (= (.getNodeType stmt) ASTNode/RETURN_STATEMENT))

(defn parenthesized-return-statement? [stmt]
  (and (return-statement? stmt)
       (parenthesized-expression? (.getExpression stmt))))

(defn method-declaration? [body]
  (= (.getNodeType body) ASTNode/METHOD_DECLARATION))

Details about for example ASTNode can be found in the Eclipse JDT API Specification

Next the are 4 functions that zoom in into the code we would like to refactor. You will notice that I use doseq quite a lot since the actual AST manipulation (the refactoring) will be in-place and thus has side effects. This is not always avoidable when using Java libraries from within your Clojure code. We could write an immutable version that leaves the original AST intact by returning copies of the AST though. Such functionality is supported by the Eclipse JDT.

(defn refactor-block [block]
  (doseq [stmt (filter parenthesized-return-statement? (.statements block))]
    (refactor-return stmt)))

(defn refactor-method [method]
  (refactor-block (.getBody method)))

(defn refactor-type [type]
  (doseq [method (filter method-declaration? (.bodyDeclarations type))]
    (refactor-method method)))

(defn refactor [ast]
  (doseq [type (.types ast)]
    (refactor-type type)))

As you can see we filter out the return statements that need refactoring using the parenthesized-return-statement? predicate. Only thing left is to do the actual refactoring:

(defn refactor-return [stmt]
  (let [exp (.getExpression (.getExpression stmt))
        ast (.getAST exp)
        node (ASTNode/copySubtree ast exp)]
    (.setExpression stmt node)))

In this code we first get to the expression within the parentheses, hence the double .getExpression. Note: this code only strips one level of parentheses. Next we make a copy of the expression and finally we assign it back to our return statement, effectively removing the outer parentheses.

This code is easy to test via the REPL. You will see something similar to:

ast.core=> example
#<CompilationUnit public class A {
  int foo(){
    return (42);
  }
  int bar(){
    return 13;
  }
}
>
ast.core=> (refactor example)
nil
ast.core=> example
#<CompilationUnit public class A {
  int foo(){
    return 42;
  }
  int bar(){
    return 13;
  }
}
>
ast.core=>

Finally the complete code:

(ns ast.core
  (:import (org.eclipse.jdt.core.dom ASTParser AST ASTNode)))

(defn create-ast
  "Create AST from a string"
  [s]
  (let [parser (ASTParser/newParser(AST/JLS3))]
    (.setSource parser (.toCharArray s))
    (.createAST parser nil)
    ))

(def example
     (create-ast (str
                  "public class A {"
                  "   int foo() {"
                  "      return (42);"
                  "   }"
                  ""
                  "   int bar() {"
                  "      return 13;"
                  "   }"
                  "}")))

(defn parenthesized-expression? [expr]
  (= (.getNodeType expr) ASTNode/PARENTHESIZED_EXPRESSION))
  
(defn return-statement? [stmt]
  (= (.getNodeType stmt) ASTNode/RETURN_STATEMENT))

(defn parenthesized-return-statement? [stmt]
  (and (return-statement? stmt)
       (parenthesized-expression? (.getExpression stmt))))

(defn method-declaration? [body]
  (= (.getNodeType body) ASTNode/METHOD_DECLARATION))

(defn refactor-return [stmt]
  (let [exp (.getExpression (.getExpression stmt))
        ast (.getAST exp)
        node (ASTNode/copySubtree ast exp)]
    (.setExpression stmt node)))

(defn refactor-block [block]
  (doseq [stmt (filter parenthesized-return-statement? (.statements block))]
    (refactor-return stmt)))

(defn refactor-method [method]
  (refactor-block (.getBody method)))

(defn refactor-type [type]
  (doseq [method (filter method-declaration? (.bodyDeclarations type))]
    (refactor-method method)))

(defn refactor [ast]
  (doseq [type (.types ast)]
    (refactor-type type)))

As always, don’t hesitate to leave comments or email if you have questions/remarks/suggestions.

Have fun!

Lazily stealing..errr. getting data from the Dutch Rijksmuseum

November 10, 2012 at 10:46 pm | Posted in Clojure, Programming | Leave a comment

Last year the Dutch Rijksmuseum published an API that allows a developer to retrieve information and images from a collections of more than 110,000 items. You have to register for an API key first.

Unless you are looking for a specific item, the interface every time returns 100 items in XML format. You will also get a resumption token so you can query for the next 100 items. I imagined it would be useful to abstract from this, using a lazy sequence in Clojure. So let me show you the resulting code and a brief explanation:

(ns rijksmuseum.core
  (:require [clojure.xml :as xml]
            [clojure.zip :as zip]
            [clojure.data.zip.xml :as zf]))

We will have to parse some XML that is returned, so we start with adding some convenient libraries. If you are not familiar with Clojure zippers, please look it up in the documentation and numerous blogs. They make navigating XML almost painless.

(def api-key "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx")
(def base-url (str "https://www.rijksmuseum.nl/api/oai/" api-key))

In line 5 you will have to fill in your own API key. Line 7 defines the base url that is used for all queries.


(defn- build-query [resumption-token]
  (str base-url "/?verb=ListRecords&"
       (if (nil? resumption-token)
         "set=collectie_online&metadataPrefix=oai_dc"
         (str "resumptiontoken=" resumption-token))))

The routine build-query builds up a query. If there is no resumption token yet, the resulting query loads the first data. Otherwise, it will continue with the next batch of records. Currently the Rijksmuseum API supports two kinds of queries. You can either ask for a list of records (using verb=ListRecords) or you can ask for a specific record (using verb=GetRecord and an identifier). The API documentation has all the details.

We will first start with a couple of helper routines. Basically they extract the information we are interested in from a XML stream:


(defn- get-records [zipper]
  (zf/xml-> zipper :ListRecords :record))

(defn- get-resumption-token [zipper]
  (zf/xml1-> zipper :ListRecords :resumptionToken zf/text))

get-records extracts the records from the (zipped) XML response. get-resumption-token returns (I’m sure you already guessed) the resumption token for our next query.

Now comes the construction of the lazy sequence:


(defn- lazy-get-works [resumption-token]
  (lazy-seq
   (let [zipper (zip/xml-zip (xml/parse (build-query resumption-token)))
         works (get-records zipper)
         token (get-resumption-token zipper)]
     (concat works (lazy-get-works token)))))

(defn get-works
  "Return all works as a lazy sequence"
  []
  (lazy-get-works nil))

lazy-seq (line 18) is a macro that creates a lazy sequence out of a body of expressions. Next we create a query, parse the resulting XML and create a zip structure. All in one single line of code: line 19. All we have to do now is to extract the records (called works in line 20), the resumption token (line 21) and call ourselves recursively (line 22). Don’t be afraid of stack overflows: the lazy-seq macros takes care of this.

Now we are ready to use our lazy sequence. The next example creates a list with the image url’s of the first 10 items in the collection:


(defn get-image-url [work]
  (zf/xml1-> work :metadata :oai_dc:dc :dc:format zf/text))

(map get-image-url (take 10 (get-works)))

Don’t go overboard with requesting all items in the collection at once. Retrieving 1000 items takes about 1 minute, so the calls to the API are most probably throttled. Anyhow, have fun with lazily stealing works of art!

Calculating Bell numbers in a single tweet

May 23, 2012 at 12:48 pm | Posted in Clojure, Programming | 6 Comments

Recently I stumbled upon a white paper by Roger Sessions called “The Mathematics of IT Simplification”. In this paper he describes an approach called synergistic partitioning, which is based on the mathematics of sets, equivalence relations, and partitions. One of the topics that comes up in this article is how many ways there are to partition N elements. The answer to this is well-known and called the Nth Bell number.

The 52 partitions of a set with 5 elements

The Wikipedia page that explains the Bell number also shows two implementations on how to calculate them, one in Ruby and the other one in Python. The Ruby version needs 17 lines of code, the Python version 12 lines. I have the peculiar habit of intriguing/annoying my colleagues at work with the statement that using Clojure the solution to any programming problem fits into one single tweet. In other words: 140 characters.

I’ll start with my first attempt:

(defn append-ele [s x] (concat s (list (+ x (last s)))))

(defn next-row [s]
  (reduce append-ele (list (last s)) s))

(defn bell [n]
  (loop [n n s '(1) b s]
    (if (= n 1)
      (reverse b)
      (recur (dec n) (next-row s) (cons (last s) b)))))

(println (bell 9))

The first function (append-ele) appends a single new element to a row in the Bell triangle (explained in the Wikipedia article). In several ways this implementation is suboptimal since concat can only concatenate sequences, so I have to convert the single element to a list first. And what’s worse, appending at the end of a sequence is expensive since it’s computation is O(N), while prepending would only take one single operation.

The function next-row calculates the next row in the Bell triangle. This row always starts with the last element of the previous row. I implemented this by a simple reduce over the elements of the previous row.

And finally the function bell returns a sequence with the first n Bell numbers. I use a loop/recur to avoid a stack overflow. The sequence of Bell numbers is constructed in reverse order, so at the end (line 9) I have to call reverse.

While this version is already pretty short (10 lines, without the printing), this still won’t fit in a single tweet. So the next step was to remove the first two helper functions and inline all the code into a single function. Warning: this is not good coding practice! With this disclaimer, here is the resulting code:

(defn bell [n]
  (loop [n n s '(1) b s]
    (if (= n 1)
      (reverse b)
      (recur (dec n)
             (reduce #(concat % (list (+ %2 (last %)))) (list (last s)) s)
             (cons (last s) b)))))

Without the whitespace this implementation is 170 characters. Almost there! As you can see there are still some ‘expensive’ keywords like concat and reverse (6 and 7 characters!) and some annoying conversions from single numbers to lists. The only way to avoid this is to use a specialized data structure like vector instead of a sequence:

(defn bell [n]
  (loop [n n s [1] b s]
    (if (= n 1)
      b
      (recur (dec n)
             (reduce #(conj % (+ %2 (last %))) [(last s)] s)
             (conj b (last s))))))

Finally the code (without the indentation) fits into 140 characters. One caveat: I use conj which nicely appends an element to the end of a vector. However this behaviour of conj is not guaranteed. It is allowed to add an element anywhere in a sequence. When you use a list for example, the element is prepended. Because of this he above algorithm is O(N^2).

I will leave it as an exercise for the reader to implement the Bell number calculation as a lazy sequence so that you can use for example (take 9 (bell)). Have fun.

Extracting data from JIRA using Clojure and REST

March 2, 2012 at 10:45 pm | Posted in Clojure, Programming | 2 Comments

I have previously written two posts about getting data from JIRA. In the first one I described how you can do that in Ruby. In the other one I used JavaScript to import JIRA data directly into Google Documents. Both methods worked and both heavily rely on the SOAP interface that JIRA offers. However, as of JIRA version 5 a REST interface is the preferred way. So I decided to try this using Clojure.

Initially this seemed to be very straightforward. I have been using a well-written Clojure lib that provides an Async Http Client in the past to extract for example Twitter stream data. So it would only take a couple of minutes to setup a new Clojure project, use basic authentication to connect to a JIRA instance at work and extract all the data I needed. Well, it didn’t.

My first goal was to list all projects. On the commandline I successfully used:

$ curl -u user:password https://intranet.mycompany.com/jira/rest/api/latest/project

In Clojure, using the aforementioned library that would become:

(ns jira.core
  (:require [http.async.client :as c])
  (:use [clojure.data.json :only (read-json)]))

(def jira-project-url "https://intranet.mycompany.com/jira/rest/api/latest/project")

(defn get-all-projects
  "Return all projects from JIRA"
  []
  (with-open [client (c/create-client) :auth {:user "user" :password "password"}]
    (let [response (c/GET client jira-project-url)]
      (c/await response)
      (read-json (c/string response)))))

However, this always returns an empty vector and I still haven’t found out why. So I started to looking for an alternative. I imagined a better way would be to setup a session, retrieve a session cookie and use that for subsequent calls. I’ll begin with showing the end result:

(ns jira.core
  (:require [http.async.client :as c])
  (:use [clojure.data.json :only (read-json json-str)]))

(def session-url "https://intranet.mycompany.com/jira/rest/auth/latest/session")

(defn login
  "Login into JIRA"
  [username password]
  (with-open [client (c/create-client)]
    (let [response (c/POST client session-url
                           :headers {:Content-Type "application/json"}
                           :body (json-str {:username username :password password}))]
      (c/await response)
      (c/cookies response))))

This is more or less the Clojure equivalent of:

$ curl -c cookie_jar -H “Content-Type: application/json” -d ‘{“username” : “user”, “password” : “password”}’ https://intranet.mycompany.com/jira/rest/auth/latest/session

With this implementation of login that returns a session cookie I rewrote get-all-projects to:

(defn get-all-projects
  "Return all projects from JIRA"
  [cookies]
  (with-open [client (c/create-client)]
    (let [response (c/GET client jira-project-url :cookies cookies)]
      (c/await response)
      (read-json (c/string response)))))

This version works perfectly and enables me to write compact code like:

(def session (login "user" "password"))
(map :name (get-all-projects session))

This example generates a map with the abbreviated names of all projects currently in JIRA.

Right now the code is mostly proof of concept. As soon as it is cleaned up a bit I will start a new project on GitHub to share it. Enjoy!

First ClojureScript experiences: using Raphaël

February 13, 2012 at 10:24 pm | Posted in Clojure, Programming | 4 Comments

I recently started to experiment with ClojureScript. In order to get a little bit beyond ‘hello world’ I decided to convert one of Raphaël‘s examples to ClojureScript. According to the projects homepage Raphaël is ‘a small JavaScript library that should simplify your work with vector graphics on the web’.

The sample I used draws a kind of clock. It can be found here. The relevant JavaScript code:

window.onload = function () {
    var r = Raphael("holder", 640, 480),
        angle = 0;
    while (angle < 360) {
        var color = Raphael.getColor();
        (function (t, c) {
            r.circle(320, 450, 20).attr({stroke: c, fill: c, transform: t, "fill-opacity": .4}).click(function () {
                s.animate({transform: t, stroke: c}, 2000, "bounce");
            }).mouseover(function () {
                this.animate({"fill-opacity": .75}, 500);
            }).mouseout(function () {
                this.animate({"fill-opacity": .4}, 500);
            });
        })("r" + angle + " 320 240", color);
        angle += 30;
    }
    Raphael.getColor.reset();
    var s = r.set();
    s.push(r.path("M320,240c-50,100,50,110,0,190").attr({fill: "none", "stroke-width": 2}));
    s.push(r.circle(320, 450, 20).attr({fill: "none", "stroke-width": 2}));
    s.push(r.circle(320, 240, 5).attr({fill: "none", "stroke-width": 10}));
    s.attr({stroke: Raphael.getColor()});
};

As you can see the JavaScript code is already quite compact. I especially like the use of the anonymous function in the inner loop. What I did next is a very straightforward conversion to ClojureScript just to see if I could get that to work. This turned out as:

 
(ns raph.hand) 
(defn clj->js
  "makes a javascript map from a clojure one"
  [cljmap]
  (let [out (js-obj)]
    (doall (map #(aset out (name (first %)) (second %)) cljmap))
    out))

(defn- attr [object attributes]
  (.attr object (clj->js attributes)))

(defn create-hand [paper]
  (.getColor.reset js/Raphael)
  (-> (.set paper)
      (.push (-> (.path paper "M320,240c-50,100,50,110,0,190")
                 (attr {:fill "none", :stroke-width 2})))
      (.push (-> (.circle paper 320 450 20)
                 (attr {:fill "none", :stroke-width 2})))
      (.push (-> (.circle paper 320 240 5)
                 (attr {:fill "none", :stroke-width 10})))
      (.attr "stroke" (.getColor js/Raphael))))

(defn create-circle [paper angle hand]
  (let [c (.getColor js/Raphael)
        t (str "r" angle " 320 240")
        circle (.circle paper 320 450 20)]
    (-> circle
        (attr {:stroke c, :fill c, :transform t, :fill-opacity .4})
        (.click #(.animate hand (clj->js {:stroke c, :transform t}) 2000 "bounce"))
        (.mouseover #(.animate circle (clj->js {:fill-opacity .75}) 500))
        (.mouseout #(.animate circle (clj->js {:fill-opacity .4}) 500)))))

(defn ^:export draw []
  (let [paper (js/Raphael 0 0 640 480)]
    (let [hand (create-hand paper)]
      (doseq [angle (range 0 360 30)]
        (create-circle paper angle hand)))))

The ClojureScript takes a couple of more lines than the JavaScript original: 36 versus 23. This has mostly to do with a couple of helper functions to convert Clojure maps to JavaScript maps.

A couple of things I learned/noticed during the conversion:

  • The threading macro (->) really is very convenient as an alternative to the fluent interface used in this example
  • It take me a couple of minutes to realize that “getColor.reset()” is a single function call instead of a reset() called on a property
  • Using macros in ClojureScript is possible, but not as straightforward as I thought. Macros are handled at compile time and you have to put them in a separate Clojure file. Next you reference them with require-macros in the namespace definition. How this is done exactly is shown here
  • I replaced the ‘clj->js’ function by a macro according to this excellent blogpost by keminglabs. However the ClojureScript compiler couldn’t find the macro on its classpath and for the moment I settled for the ‘clj->js’ function
  • There is lots of room for improvement in the code. My first idea was to make it more DSL like, using macros. But then again, SVG is already kind of a DSL, so it would probably make more sense to let the code output SVG directly instead of using Raphaël as an extra layer. David Edgar Liebke already started a project called Apogee, A ClojureScript SVG and charting library.

Finally the html code I used to test my code:

<html> 
  <head>
    <title>Hello, world</title>
    <script type="text/javascript" src="jslib/raphael-min.js"></script>
    <script type="text/javascript" src="raphtest.js"></script>
  </head>
  <body>
    <script>
      	raph.hand.draw();
    </script>
  </body>
</html>

And to compile

cljsc src '{:optimizations :advanced :output-to "raphtest.js" :externs ["lib/raphael-min.js"]}

For a really good explanation on how to set up a more robust ClojureScript development environment, have a look at Sean Corfields blog.

Find which protocols are implemented by a Clojure datatype.

January 13, 2011 at 9:26 pm | Posted in Clojure, Programming | 3 Comments

As part of a somewhat larger experiment (implementing dynamic mixins in Clojure) I needed to know what protocols are implemented for a given object (defined for example by defrecord or deftype). For example I have defined the next protocol:
 

(ns dci.core)

(defprotocol LogProtocol
  (log [x] "log method"))

And lets suppose that I have defined the following type:

(defrecord Foo [f1 f2]
  LogProtocol
  (log [this] (println (:f1 this) (:f2 this)))) 

When I now tried:

(extenders LogProtocol)

I was expecting to see Foo. What I got instead was nil.

However when I did the following:

(defrecord Bar [b1 b2])

(extend Bar 
  LogProtocol 
 {:log (fn [this] (println (:b1 this) (:b2 this)))})

(extenders LogProtocol)

I get (dci.core.Bar) as expected.

When I try to find the implemented protocol by using the ancestors function, I get the opposite result:

(ancestors Foo)

has dci.core.LogProtocol in it’s list of ancestors, while

(ancestors Bar)

doesn’t.

So there is a difference (at least in Clojure 1.2) in behavior whether you implement the protocol directly with defrecord (as done with Foo) or extend it later (Bar). I wanted a solution that works with both declarations. I first implemented a function protocol? that checks for a given symbol if it is a protocol:

(defn protocol? [maybe-p]
  (boolean (:on-interface maybe-p))) 

This implementation depends on the :on-interface key, which is undocumented. Next I created a function all-protocols that returns a list of all protocols in the current namespace (*ns*).

(defn all-protocols []
  (filter #(protocol? @(val %)) (ns-publics *ns*)))

And finally I wrote implemented-protocols to filter all protocols that are available for a given object:

(defn implemented-protocols [sym]
  (filter #(satisfies? @(val %) sym) (all-protocols))) 

The complete code with some tests:

(ns dci.core)
 
(defn protocol? [maybe-p]
  (boolean (:on-interface maybe-p)))

(defn all-protocols []
  (filter #(protocol? @(val %)) (ns-publics *ns*)))

(defn implemented-protocols [sym]
  (filter #(satisfies? @(val %) sym) (all-protocols))) 

; test protocol and records

(defprotocol LogProtocol
  (log [x] "log method"))

(defrecord Foo [f1 f2]
  LogProtocol
  (log [this] (println (:f1 this) (:f2 this)))) 

(defrecord Bar [b1 b2])

(extend Bar 
  LogProtocol 
 {:log (fn [this] (println (:b1 this) (:b2 this)))})


(println (implemented-protocols (Foo. 1 2))) 
; will output ([LogProtocol #'dci.core/LogProtocol])

(println (implemented-protocols (Bar. 3 4))) 
; will output ([LogProtocol #'dci.core/LogProtocol])

In a next blog I will tell a bit more about my dynamic mixins implementation in Clojure.

Using Google Data API’s with Clojure

October 27, 2010 at 11:38 am | Posted in Clojure, Programming | 8 Comments

With the Google Data API it is very easy to access all that information that you have trusted to ‘don’t be evil’ Google. The basic format lends itself very well to manipulating with Clojure, but in this blog I’ll just show how to access your contacts data, building on top of a Java client library.

I used Leiningen for this experiment. To start I created a new project with

$ lein new gdata

This will create a new directory structure containing our project. First we need to add some dependencies to project.clj:

(defproject gdata "1.0.0-SNAPSHOT"
  :description "Google Data API experiment"
  :dependencies [[org.clojure/clojure "1.2.0"]
                 [org.clojure/clojure-contrib "1.2.0"]
                 [com.google.gdata/gdata-contacts-3.0 "1.41.5"]]
  :repositories {"mandubian-mvn" "http://mandubian-mvn.googlecode.com/svn/trunk/mandubian-mvn/repository"})

I have added an extra dependency on line 5 because we need the Contacts Java client library. Since it isn’t included in the standard Maven repositories I also had to add an extra one. This is shown in line 6. Someone was kind enough to Mavenize all the Google Data client jars.

Make sure you check this setup by executing:

$ lein deps

Continue Reading Using Google Data API’s with Clojure…

Throwing dice with Clojure

October 16, 2010 at 8:56 pm | Posted in Clojure, Programming | 9 Comments

Recently I needed a mathematical expression for the expected value for the minimum out of n draws from a normal distribution. For example when you take only 1 sample (n = 1) every time, the minimum is the value itself. So the expected value (if I repeat this an infinite amount of times) is the average of the normal distribution, being 0.

If I sample an infinite number (n = ∞) of times, the minimum of all those samples is going to be -∞. I didn’t find an expression for n>1 samples and wasn’t able to derive it myself easily.

I decided to tackle an easier problem first: what is the expected minimum when I throw n (6 sided) dice? When you throw 1 dice at a time, the solution is easy. Each side has an equal chance. The distribution looks like this:

Possible outcomes with 1 dice

And the expected value is (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5

For 2 dice it is still easy to calculate the expected value for the minimum. There are 11 combinations for which the minimum is 1, 9 combinations for which the minimum is 2 and so on. There is only 1 combination for which the minimum is 6: you have to throw 2 sixes. When you plot the chances it looks like this:

Possible outcomes with 2 dice
For three it becomes already quite boring to write out all (216) combinations just to calculate the minimum and actually I didn’t The graph however looks like this:

Possible outcomes with 2 dice

As you can see the chance of having a lower value (1 or 2) as minimum quickly increases. Calculating all combinations on paper starts to get boring pretty fast, so I thought of writing a Clojure program that would do that for me. However I soon realized that the combination space this program had to walk becomes pretty huge when you take a larger number of dice. For 10 dice we are already talking 6^10 possible combinations. My next step was to capture this in a neat formula first. Remembering some of my statistics classes from university I came up with the following formula to calculate the possible number of combinations where x (1 <= x <= 6)  is the outcome for the minimum:

The expected value now simply becomes:

 

I took this formula as the basis for the following implementation in Clojure:

(defn ! [x] (if (= x 0) 1 (* x (! (dec x)))))

(defn m-over-n [m n] (/ (! m) (* (! (- m n)) (! n))))

(defn pow [x y] (Math/pow x y))

(defn term [x m n] (* (m-over-n m n) (pow (- 6 x) (- m n))))

(defn comb [d x] (reduce + (map #(term x d %) (range 1 (inc d)))))

(defn e-min-seq [n] (map #(* (comb n %) %) (range 1 7)))

(defn e-min [n] (/ (reduce + (e-min-seq n)) (pow 6 n)))

It turns out that most of my Clojure code is a collection of one-liners. Line 1 defines the exclamation mark (!) as a function that calculates the factorial of a number. This is a straightforward definition that doesn’t use tail recursion so it will run out of stack space for large values of x. For our goal it is sufficient. Line 3 defines the binomial coefficient. Again there are more efficient ways to calculate this. Line 9 and 13 both use reduce to calculate the two sums as seen in our formula.

Although this code gave me the expected result I still wasn’t completely happy with it. I stepped back to the drawing board in order to get a simpler formula. Our formula can be rewritten as:

Which in turn can be further simplified as:

and finally:

This final formula is coded in Clojure as:

(defn sum [n] (reduce + (map #(pow % n) (range 7))))

(defn e-min [n] (/ (sum n) (pow 6 n)))

The graph of the expected minimum now looks like this:

 

This whole solution now could fit into a one-liner. This exercises proofs two things to me: 1) it really helps to think about your solution before starting to code and 2) every Clojure solution always fits in one single tweet 🙂

Clojure micro benchmark

September 29, 2010 at 7:15 pm | Posted in Clojure, Programming | 6 Comments

First a disclaimer: benchmarking software is difficult. Furthermore, micro-benchmarks hardly ever make sense, unless you have identified that particular piece of code as a performance bottleneck. Following Donald Knuth’s famous quote: “premature optimization is the root of all evil”. Having said this, I also know that tinkering with a few lines of code and trying different versions can be a lot of fun. So that is exactly what I did when I needed some Clojure code that calculates the sum of squares of two sequences.

The algorithm itself is straightforward: it iterates through all the values of the two sequences, calculates the square of the difference for each value pair, and sums them. A perfect algorithm for a map/reduce implementation.

The first version sumsqr1 uses an anonymous function (#(* % %)) to calculate the square root. The advantage is that the subtraction y from x is only done once. The downside might be potential function call overhead.

(defn sumsqr1 [s1 s2]
  (reduce + (map (fn [x y] (#(* % %) (- x y))) s1 s2)))

The next version uses a very straightforward implementation to take the square of the difference between x and y. I was expecting this one to be the fastest.

(defn sumsqr2 [s1 s2]
  (reduce + (map (fn [x y] (* (- x y) (- x y))) s1 s2)))

And finally an implementation (sumsqr3) that uses the Java pow function.

(defn sumsqr3 [s1 s2]
  (reduce + (map (fn [x y] (Math/pow (- x y) 2)) s1 s2)))

Strictly speaking this last function is not the same as the first two ones, since it returns a floating point number, while the other two return integers. To execute my benchmark I called the three versions repeatedly like this:

(time (dotimes [_ 1e6] (sumsqr1 (range 10) (range 1 11))))

I executed all three versions in the REPL, using Clojure 1.1, 1.2 and 1.3 Alpha 1. Results are shown in the next graph:

Clojure micro benchmark

As you can see the sumsqr1 version is the fastest. Next is the version that uses Math.pow. The differences in execution time aren’t spectacular (about 10 %). What is more interesting to conclude is that in this particular micro benchmark, Clojure 1.2 is about 10 % faster than Clojure 1.1 and that Clojure 1.3 Alpha 1 is already 10 % faster than release 1.2. The developers are doing some great work here!

Next Page »

Blog at WordPress.com.
Entries and comments feeds.