Clojure’s growing popular mind share

Popular interest in Clojure has rapidly increased over the last few years since 2008, almost to the level of Java (the language) today, which has dropped off significantly. (At least according to Google web trends.)
In contrast, popular interest in Common Lisp seems to have dropped off steadily since 2004.

Clojure vs. Java vs. Common Lisp

I used “java language” instead of “java” because it is ambiguous enough to mean the language, framework, JVM, the island or the coffee.

My earlier outlook on Clojure’s prospects circa 2009.

Purely Functional Data Structures & Algorithms : Selection Sort

*Updated @ 2012-08-31 02:08:58 due to internet pedantry*

Previously, previously.

According to Wikipedia :

In computer science, a Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

(A functional implementation of selection sort is however, not an in-place sort.)
Behold the abomination which is the imperative implementation (from the Wikipedia link) :

int i,j;
int iMin;

for (j = 0; j < n-1; j++) {
    iMin = j;
    for ( i = j+1; i < n; i++) {
        if (a[i] < a[iMin]) {
            iMin = i;
        }
    }

    if ( iMin != j ) {
        swap(a[j], a[iMin]);
    }
}

Now, the functional equivalent in Haskell :

selectionSort :: [Int] -> [Int] -> [Int]
selectionSort sorted [] = reverse sorted
selectionSort sorted unsorted = selectionSort (min:sorted) (delete min unsorted)
                     where min = minimum unsorted

Or in Shen :

(define selection-sort-aux
  { (list number) --> (list number) --> (list number) }
  Sorted []       -> (reverse Sorted)
  Sorted Unsorted -> (let Min (minimum Unsorted)
        (selection-sort-aux (cons Min Sorted) (remove-first Min Unsorted))))

Yes. These functional snippets use their respective implementations of the list type (which is not an efficient persistent data type in either Haskell or Shen for accesses or updates). Replacing the List type with Data.Sequence(a persistent data type with efficient constant access and update) for the Haskell snippet is trivial. I’ll leave that as an exercise to the reader. Shen is too new to support these efficient persistent types at the moment but implementations will appear in the future and changing the snippet would also be trivial. A Clojure implementation using it’s already built in efficient persistent types would also be trivial.

The complete code can be found here.

Happy Pi Day in Shen

Here’s a port of the previous Qi II code to Shen.
Run with Hakan Raberg’s 0.1.4 version of shen.clj (Shen implemented in Clojure !).

*
  Accurately calculates N digits of Pi using Machin's formula
  with fixed point arithmetic and variable guards digits. 

  Depends on the maths library -->
    http://www.shenlanguage.org/library.html
*

(tc +)

(define arccot-
  {number --> number --> number --> number --> number --> number} 
  X N XPOWER    0 _ -> 0
  X N XPOWER TERM 1 -> (+ (arccot- X (+ N 2) (floor (/ XPOWER X)) 
                                     (floor (/ XPOWER N)) 0) 
                          (floor (/ XPOWER N)))
  X N XPOWER TERM 0 -> (- (arccot- X (+ N 2) (floor (/ XPOWER X))
                                      (floor (/ XPOWER N)) 1) 
                          (floor (/ XPOWER N))))

(define arccot
  {number --> number --> number}
  X UNITY -> (let XPOWER (floor (/ UNITY X))
                  (arccot- (* X X) 1 XPOWER (floor XPOWER) 1)))

(define machin-pi
  {number --> number} 
  DIGITS -> (let GUARD (+ 10 (ceiling (log' DIGITS 10)))
                 UNITY (expt 10 (+ DIGITS GUARD))
                 (floor (/ (* 4 (- (* 4 (arccot 5 UNITY))
                                   (arccot 239 UNITY)))
                           (expt 10 GUARD)))))




(1+) (time (machin-pi 100))

run time: 2.56899999999996 secs
31415926535...4350265344N : number

Clojure/Conj 2011

Sold out attendance marked this being the second premiere conference for Clojure. What I realized is just how great the people are in this community. No, seriously. There’s far less ego than with many other communities. This is a great sign for the future of Clojure. Particularly because Rich is such a great guy. He even gave a public apology for something or other that he said(on a mailing list) which he felt was not in the spirit of the Clojure community.

As for the conference, some of the more mathematically inclined talks were especially exciting and encouraging because they highlight how Clojure is facilitating rigorous and ground-breaking work in the sciences :

Arnoldo Jose Muller-Molina : Hacking the Human Genome using Clojure and Similarity Search

“The Genome inside each cell works like a massively parallel computer. Some proteins called Transcription Factors (TF) attach into specific regions called “promoters”. This attachment starts a complex process that can have different outcomes. One of the possible outcomes is the creation of another TF that will in turn attach to some promoter(s) creating a cascade of events. TFs are like functions that have side effects, call other TFs and also can call themselves recursively. In this talk, I will describe a machine learning technique that attempts to reverse engineer the Genome. To achieve this tricky task, you need versatile tools. First of all, Clojure plays an instrumental role in the development of visualizations and data processing pipelines. Clojure makes it really easy to filter, visualize, and synthesize many gigabytes of data. In addition, similarity search is used extensively to find patterns in a huge set of possibilities. I hope to convince you here that similarity search is the next “NoSQL” and that Clojure is an ideal tool for data science projects.”

Chas Emerick : Modeling the world probabilistically using Bayesian networks in Clojure

“Some of the most challenging problems that programs can face include classification, prediction, and making decisions in the face of messy or incomplete observations, data, or understanding. Bayesian networks provide a basis for implementing solutions to many of these sorts of problems, and Clojure offers excellent raw materials for building them. This talk will briefly introduce the concepts of Bayesian probability and networks, demonstrate the usage of an open source generalized Bayesian network modeling library, and discuss its implementation – highlighting the Clojure facilities that made it possible.”

Christophe Grand : From Linear to Incremental

“In this talk I expose some of some of the insights I gathered while turning an inherently linear process (parsing) into a sublinear (bestcase logarithmic) process. This is a tale of datastructures (featuring 2-3 and fingertrees), inversion of control, twisted memoization strategies, profiling and optimizing.”

Ambrose Bonnaire-Sergeant : Introduction to Logic Programming with Clojure

“A well written logic program is a gold mine. Logic programming represents a problem as a set of declarative logical axioms, or facts, which a logic engine uses to construct a proof. With a set of facts, the programmer can offload the work of collecting results to a logic engine in exciting ways. Beyond these wonderful properties, writing a logic program is tremendous fun! We will use Clojure’s logic engine core.logic to introduce these concepts and jump into the fascinating world of logical programming.”

For the Artistically inclined there was

Sam Aaron’s Programming Music with Overtone :

“Can programming languages help us to free our creative potential? Formalised descriptions of data, events and process have been used to great effect within industrial settings but could they also be useful in artistic contexts? This presentation introduces Overtone – a Clojure front-end to the state-of-the-art realtime sound synthesis engine SuperCollider – currently being established as a music platform for both research and performance. Overtone facilitates a truly exciting high-level exploration of musical ideas such as the design and structure of sound, the coordination of multiple concurrent performers and even new forms of musical notation. Through live coding, monome button bashing and loud music performances such as synthesized dubstep, we’ll dive into the architecture of the system and explore some of the deeper computational questions that working in a musical context forces you to answer. Ultimately we will see how Clojure can manage so much more than the representation of business logic or the construction of web apps. We will cover a lot of ground – so hold onto your ears!”
(See this earlier post to get a better idea.)

There were many more great talks too. The full list is here.

Overtone

Overtone is an open source audio environment being created to explore musical ideas from synthesis and sampling to instrument building, live-coding and collaborative jamming.


In this video Sam Aaron gives a fast-paced introduction to a number of key live programming techniques such as triggering instruments, scheduling future events and synth design. Finally, the viewer is shown how a simple musical sequence may be composed and then converted into an intricate Reich phase. The main body of the video was recorded in one take and features an Emacs buffer (using the Live Coding Config (is.gd/​live_coding_emacs) for editing text and communicating with Overtone (is.gd/​overtone), an expressive Clojure front-end to SuperCollider. Clojure is a state-of-the-art functional lisp emphasising immutability and concurrency (clojure.org).

Shen/Kl arrive

The first publicly available version of Shen/Kl has been released.

The Shen mission is to develop an ultra-portable version of Qi that can run under a wide variety of platforms and which incorporates missing features in Qi such as streams. The targeted platforms are CL, Clojure, NewLisp, Emacs Lisp, ECL, Scheme, Javascript and Python as well as C/C++, DVM, CLR or the JVM. This approach involved rewriting and redesigning Qi to fit within the smallest feasible instruction set.

Kl is intentionally a small ‘Lisp assembly language’ that enables Qi to be built on top of it.

more …

Shen Downloads.

ClojureScript Demo : Convex Hull

Update : bug-fix when hull was being incorrectly calculated due to there being duplicate points generated in the random set.




ClojureScript looks like a solid approach to building applications that target JavaScript VMs. It’s built on top of Google’s Closure Compiler/Library which is very intruiging and is the best approach that they could have taken (now that I’ve a played with it a little). Being new to both Closure and ClojureScript I was curious about what it might feel like to build an application using these tools. I’ve mostly despised programming in JavaScript for browsers no matter what hyped-up library is available (this includes JQuery which is the best of a bad bunch in my opinion). So I decided to write a ClojureScript application that runs in the browser based on a previous Clojure implementation of a Convex Hull algorithm with heuristics.

This was a piece of cake. I really like the pre-compiled approach that relies on the Closure compiler/library. It just feels like you’re writing a regular application instead of trying to force the browser to do the ‘correct’ thing with run-time code and the DOM. There are a few differences that I ran into, a few functions don’t yet exist and using macros is not as clean as I’d expect. Macros have to be implemented in Clojure and then referenced from ClojureScript. No big deal really.

Here’s the demo

Here’s all the UI code. Not much really at < 100 lines. Very cool.

(def edge-stroke (graphics/Stroke. 1 "#444"))
(def blue-edge-stroke (graphics/Stroke. 1 "#66b"))
(def green-edge-stroke (graphics/Stroke. 1 "#0f0"))
(def white-fill (graphics/SolidFill. "#fff"))
(def blue-fill (graphics/SolidFill. "#66b"))
(def green-fill (graphics/SolidFill. "#0f0"))
(def trans-fill (graphics/SolidFill. "#0f0" 0.001))

(def g
  (doto (graphics/createGraphics "440" "440")
    (.render (dom/getElement "graph"))))

(defn draw-graph 
    []
    (let [canvas-size (. g (getPixelSize))]
     (.drawRect g 0 0 
            (.width canvas-size) (.height canvas-size) 
            edge-stroke white-fill)))

(defn scale-coord
    [coord]
  (+ 20 (* 4 coord)))

(defn draw-points
    [points stroke fill]
    (doseq  [[x y :as pt] points]
        (.drawEllipse g (scale-coord x) (scale-coord y) 
               3 3 stroke fill)))

(defn draw-convex-hull
    [points stroke fill]
    (let [path (graphics/Path.)
      [xs ys :as start] (first points)]
     (.moveTo path (scale-coord xs) (scale-coord ys))
     (doall (map (fn [[x y :as pt]]
             (.lineTo path (scale-coord x) (scale-coord y)))
             (rest points)))
     (.lineTo path (scale-coord xs) (scale-coord ys))
    (.drawPath g path stroke fill)))

(defn print-points
    [points el]
    (doseq [pair points]
       (dom/append el
               (str " [" (first pair) " " (second pair) "]"))))

(defn ^:export rundemo
  []
  (let [cnt 1E2
        rpts (apply 
             vector 
             (map (fn [n] 
                  [(rand-int (inc cnt))
                   (rand-int (inc cnt))])
              (range 1 cnt [])))
       text-input-title (dom/getElement "text-input-title")
       text-input (dom/getElement "text-input")
       text-results-status (dom/getElement "text-results-status")
       text-results (dom/getElement "text-results")]
       (draw-graph) 
       ;; draw all points
       (dom/setTextContent 
    text-input-title 
    (str "Random generation of " cnt " points...")) 
       (draw-points rpts blue-edge-stroke blue-fill)
       (print-points rpts text-input)
       ;; calc hull
       (dom/setTextContent 
    text-results-status 
    (str "Calculating convex hull ...")) 
       (let [r1 (randomset rpts false)
         r2 (randomset rpts true)]
         (dom/append text-results-status (str " done.n")) 
         ;; update the results
         (print-points r2 text-results)
         (dom/append
          text-results-status
          (str "Convex hull has " (count r1) " points.n"))
         ;; draw hull points
         (draw-points r1 green-edge-stroke green-fill)
         ;; draw hull
         (draw-convex-hull r1 green-edge-stroke trans-fill)
         ;; return the results
         [rpts r2])))

;; Auto-update
(defn ^:export poll
  []
  (let [timer (goog.Timer. 15000)]
    (do (rundemo)
        (. timer (start))
        (events/listen timer goog.Timer/TICK rundemo))))

The future of client-side programming just got way better thanks to Rich and team !
All code is here.

Happy PI day ! (in QiII)

Qi is the future of Lisp.
It is Lisp with many great features such as pattern-matching, a turing complete static type system (even more powerful than Haskell’s type system) and many others.

So in the spirit of PI day, here’s an implementation that calculates PI using Machin’s formula.

(define ceiling 
  X -> (CEILING X))
(declare ceiling [number --> number])

(define expt 
  X Y -> (EXPT X Y))
(declare expt [number --> number --> number])

(define floor 
  X Y -> (FLOOR X Y))
(declare floor [number --> number --> number])

(define log
  X Y -> (LOG X Y))
(declare log [number --> number --> number])

(tc +)

(define arccot-
  {number --> number --> number --> number --> number --> number} 
  X N XPOWER    0 _ -> 0
  X N XPOWER TERM 1 -> (+ (arccot- X (+ N 2) (floor XPOWER X) 
                                     (floor XPOWER N) 0) (floor XPOWER N))
  X N XPOWER TERM 0 -> (- (arccot- X (+ N 2) (floor XPOWER X) 
                                      (floor XPOWER N) 1) (floor XPOWER N)))

(define arccot
  {number --> number --> number}
  X UNITY -> (let XPOWER (floor (/ UNITY X) 1)
                  (arccot- (* X X) 1 XPOWER (floor XPOWER 1) 1)))

(define machin-pi
  {number --> number} 
  DIGITS -> (let GUARD (+ 10 (ceiling (log DIGITS 10)))
                 UNITY (expt 10 (+ DIGITS GUARD))
                 (floor (* 4 (- (* 4 (arccot 5 UNITY)) 
                                (arccot 239 UNITY))) (expt 10 GUARD))))

And the output …

(time (machin-pi 10000))

Evaluation took:
  0.379 seconds of real time
  0.372112 seconds of total run time (0.269730 user, 0.102382 system)
  [ Run times consist of 0.055 seconds GC time, and 0.318 seconds non-GC time. ]
  98.15% CPU
  903,769,308 processor cycles
  78,698,160 bytes consed

314159265358979323846264338327950 ... 1655256375678 : number

Compared with Common Lisp, Haskell and Clojure.

So you say that programming language choice does not matter …

One popular interview question that never dies : write some code to reverse a singly linked-list.
Now understanding the problem for interviewees is one thing but getting it right in an imperative language seems to be quite a feat based on my experience as an interviewer. Most take 15-20 minutes to get this completely correct and sometimes even longer.

Here’s a quick solution that took me 10 minutes (in C) :

#define LIST_SIZE 10000000
#define SHOW_SIZE 5


typedef struct node {
  struct node* next;
  int   val;
} node; 


int main(int argc, char* argv[]) 
{
  int i;
  long start, end;
  node* head = malloc(sizeof(node));
  node* cur = head; node* cur2 = head;
  node* prev = NULL; node* next = NULL;

  // init linked list
  printf("         linked list : ");
  for (i=1; i <= LIST_SIZE; i++)
  {
    cur->val = i;
    if (i < SHOW_SIZE) printf("%d -> ", cur->val);
    if (i != LIST_SIZE) cur->next = malloc(sizeof(node));
    cur = cur->next;
  }
  cur = NULL;
  printf(" ... (%d more)n", LIST_SIZE - SHOW_SIZE);

  // reverse linked list
  start = clock();
  while (cur2 != NULL)
  {
    next = cur2->next;
    cur2->next = prev;
    prev = cur2;
    cur2 = next;
  }
  node* head2 = prev;
  end = clock();

  printf("reversed linked list : ");
  for (i=1; i <= LIST_SIZE; i++)
  {
    if (i < SHOW_SIZE) printf("%d -> ", head2->val);
    head2 = head2->next;
  }
  printf(" ... (%d more)n", LIST_SIZE - SHOW_SIZE);

  printf("Elapsed time: %.3lf msecsn", (double)(end - start));
}

The code is fairly straight-forward for anyone familiar with C. Think about it though, when someone is under pressure to answer this question and they are coding this up on paper for the interviewer there are about 50 lines of code in which the interviewee can go wrong.
This is the imperative paradigm that most programmers live with on a daily basis and which they need to prove they can deal with in many interviews every day around the world. To make it worse this is also the only paradigm that most interviewers really know.

Now the equivalent in a functional language is a one-liner (in Clojure) :

(let [nums (range 1 1e6)] 
     (time (take 5 (reduce (fn [rlst item] (cons item rlst)) '() nums))))

So at the low-level of a developer’s daily life experience with imperative languages, how many programming bugs happen as a result ? What about lost time and the individual productivity ?
Moving up a level : what does this do to the team’s productivity ? What is the ‘new feature vs. fire drill’ ratio for this team that is forced to worship at the altar of imperative languages by academia and industry ?
Now on the macro level translate all this into costs in time and lost revenue for a company. What is the estimated percentage of lost revenue and profit due to being stuck with this paradigm ?
Middle-management’s sales-pitchy MBA approach to software developer fungibility and hence their love of lowest common denominator languages costs companies untold losses in the millions. They have also been much of the cause for a generation of below-average programmers.
(The cancer that is the MBA club in the world of software development is a topic for another essay).

Language matters at all levels.

Convex Hull with Aki-Toussaint heuristics

;; Calculates the convex hull of a set of points using the Graham scan
;; algorithm.

(ns i27.geom.convex-hull
  (:use [i27.geom.misc :only (angle cross-product)]))


(defn presort-points [pts]
  "Presorts the cartesian points in descending order by angle.
   The point with lowest y value is last in the vector."
   (let [pts (distinct pts)] ;; must be distinct or else errors ...
    (letfn [(find-start [[x1 y1 :as pt1] [x2 y2 :as pt2]]
                (cond (< y1 y2) pt1
                  (= y1 y2) (if (< x1 x2) pt1 pt2)
                  true pt2))]
           (let [pt (reduce find-start pts)
             npts (remove (fn [[x y :as cpt]]
                      (and (= (first pt) x) (= (last pt) y))) pts)]
          (conj (apply vector
                   (sort (fn [pt1 pt2]
                     (> (angle pt pt1) (angle pt pt2))) npts))
            pt)))))


(defn convex-hull
  "Calculates the convex hull given a set of points in the cartesian plane.
   Uses the Graham scan algorithm. Performance is O(n lg n) time."
  [pts]
  (when (>= (count pts) 3)
    (let [start (apply vector
                       (reverse (subvec pts (- (count pts) 3) (count pts))))
          other (reverse (subvec pts 0 (- (count pts) 3)))]
      (letfn [(popstack [stk pt]
                        (if (not (> (cross-product
                                     (last (pop stk)) (last stk) pt) 0))
                          stk (recur (pop stk) pt)))
              (scan [res pt]
                    (conj (popstack res pt) pt))]
        (reduce scan start other)))))


(defn elim-points
  "Prepare data with Aki-Toussaint heuristics before passing to convex hull function.
   Performance is O(n) time regardless of the convex hull algorithm used."
  [pts]
  (when (>= (count pts) 4)
    (letfn [(find-quad
             [[[x1 y1 :as pt1] [x3 y3 :as pt3]
               [x2 y2 :as pt2] [x4 y4 :as pt4] :as quad] [xc yc :as cpt]]
             [(if (> x1 xc) cpt pt1) (if (> y3 yc) cpt pt3)
              (if (< x2 xc) cpt pt2) (if (< y4 yc) cpt pt4)])]
      (let [poly (distinct (reduce find-quad (take 4 pts) pts))
            ;; generate the line segments that form the convex polygon
            lines (conj (reduce (fn [lines pt] (conj lines [(last (last lines)) pt]))
                                [[(first poly) (second poly)]] (rest (rest poly)))
                        [(last poly) (first poly)])
            ;; filter out all points that fall inside the convex polygon
            pts (filter
                 (fn [tpt]
                   (not (reduce (fn [b v] (and b (neg? v))) true
                                (map (fn [pt]
                                       (cross-product tpt (first pt) (last pt)))
                                     lines))))
                 pts)]
        pts))))

Timing without heuristics :

java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8) (6b18-1.8-0ubuntu1)
OpenJDK 64-Bit Server VM (build 14.0-b16, mixed mode)

generating 1000000 random points ...
"Elapsed time: 896.39526 msecs"
sorting 1000000 points ...
"Elapsed time: 52142.589419 msecs"
calculating convex hull for 1000000 points ...
"Elapsed time: 5370.579308 msecs"
[[246336 0] [516315 0] [332671 0] [920929 0] [992271 1]] - 35 points
"Elapsed time: 57547.947404 msecs"

Timing with heuristics :

java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8) (6b18-1.8-0ubuntu1)
OpenJDK 64-Bit Server VM (build 14.0-b16, mixed mode)

generating 1000000 random points ...
"Elapsed time: 897.92648 msecs"
heuristic elimination of points ...
"Elapsed time: 264.116189 msecs"
sorting 510685 points ...
"Elapsed time: 25988.023392 msecs"
calculating convex hull for 510685 points ...
"Elapsed time: 3159.032778 msecs"
[[246336 0] [516315 0] [332671 0] [920929 0] [992271 1]] - 35 points
"Elapsed time: 32544.642604 msecs"

The code.