Bucket sort (Clojure)

(defn bucket-sort
  "Runs in O(n) time."
  [items]
  (let [len (count items)
        mx (apply max items)
        bucket-size (inc (int (/ mx len)))
        buckets (reduce (fn [v n] (conj v [])) []
                        (range (+ bucket-size (/ mx bucket-size))))]
    (letfn [(distrib-nums [v n]
                          (let [ind (int (/ n bucket-size))
                                bucket (nth v ind)]
                            (assoc! v ind (conj bucket n))))]
      (let [pre-buckets (persistent!
                         (reduce distrib-nums (transient buckets) items))]
        (apply concat (map (fn [bucket]
                             (when (> (count bucket) 0)
                               (insertion-sort bucket))) pre-buckets))))))

Runs slightly faster than Clojure’s built-in sort (at least on integers in the range 0 to 1E6) :

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)

(let [cnt 1e6
      rnums (map (fn [n] (int (rand cnt))) (range cnt))]
  ;; warmup
  (doseq [c (range 10)]
    (take 10 (bucket-sort rnums))
    (take 10 (sort rnums)))
  ;; run
  (println (time (take 10 (bucket-sort rnums))))
  (println (time (take 10 (sort rnums)))))


"Elapsed time: 676.618148 msecs"
(0 0 1 1 4 4 5 7 8 10)
"Elapsed time: 897.640471 msecs"
(0 0 1 1 4 4 5 7 8 10)

The code.

A molecule viewer in Clojure

Here’s a molecule viewer using OpenGL in Clojure. Implemented so that I could compare this type of development with Common Lisp (and also with using OpenGL development in C). OpenGL with Clojure can be really fun using Zach Tellman’s Penumbra. Coming at OpenGL from a more functional angle (e.g. not mutating global vars etc.) can be a little different but not difficult for anyone who has done enough functional programming.
The code is here.




* Update 2010-03-31 * Fixed bug where light was moving with molecule and added some performance tweaks (thanks Zach).

Do you really know Lisp ?

DISCLAIMER :
THIS IS A LANGUAGE RANT. DO NOT READ IF YOUR BPF* IS LESS THAN 0.37.
SIDE EFFECTS MAY INCLUDE SEVERE CONFUSION, UNJUSTIFIED ANGER, GASSY DISCHARGE,
INCOMPREHENSIBLE DIALOG, ERRATIC DEGRADATION OF CHARACTER AND POSSIBLY A
COMPLETE EMOTIONAL MELTDOWN.

 

Performance is one important aspect that people might want in a language. One language that continually surprises me in this regard is Haskell. Seriously, it’s simply amazing. But performance is only one important consideration when using a language. Abstraction is another.

What about more powerful levels of abstraction such as meta-programming ?

Haskell has very powerful functional idioms but it(and many other languages) are left at the door beyond which even more unfathomable worlds of expression are possible in the way of meta-programming. Unfortunately, as cool as Template Haskell is, it does not gain Haskell entry into the warp speed meta-programming universe. In Lisp there is no distinction between the syntax and the AST. In Template Haskell the AST is modeled using explicit data types.

In Template Haskell, ordinary algebraic data types represent Haskell program fragments. These types modeled after Haskell language syntax and represents AST (abstract syntax tree) of corresponding Haskell code. There is an Exp type to represent Haskell expressions, Pat – for patterns, Lit – for literals, Dec – for declarations, Type – for data types and so on. You can see definitions of all these types in the module Language.Haskell.TH.Syntax.”.
Haskell is still a great language !

Beyond the door is another universe where Lisp macros make warp speed exploration possible. Lisp users travel this world freely and playfully looking for the next interesting practical joke to play on other language users(ofcourse that means writing more Lisp code !). Beware : travelling the universe at warp speed is quite dangerous, but probably not any more dangerous than driving your car. Can any other language pass through this door without embracing symbolic expressions (which make Lisp macros possible) ? Why not leave right now and find out ?

Seriously, I’ll be patiently waiting right here until you return. I’m not going anywhere.

Ah ! you’re back, great. Find anything ? Please email me !

Lisp does not need to prove anything.

The endless neophitic whining about Lisp not having a killer application is annoying. It’s annoying because we all know this is a very old joke. You do know it’s a very old joke don’t you ? There are many killer applications, they have existed for the past 50 years. One reason that they are likely unknown might be because they aren’t social networking sites or any of the other dehumanizing, reductive web 2.0 ilk that is so commonly marketed as ‘innovative’. In other words : certain persons might simply have tunnel vision or be plainly ignorant regarding Lisp’s so-called killer applications. Another reason is that the military, aerospace and other companies use Lisp but you and I will never get to see these applications(let alone the source code !). With Clojure becoming more popular this may all just change in the next few years : the web 2.0 places may start using the language. But really, any application written in Lisp is a killer application !

Something else to carefully note is how often Lisp’s most vehement opponents know the smallest amount of Lisp syntax and sadly they often know nothing more. Or they have enough of a superficial knowledge to argue with those that have been using it for decades. The ditto heads scream about there being too many parenthesis. Funny because Java code often has more parenthesis than Lisp, it’s just that they are in different places !

It’s my own fault, I sometimes try engaging certain superficial functional and Lisp crowds on the internet. Comments are quickly down-voted because of the prevalent mob mentality and inability for independent thought. Have we all not yet evolved beyond peer pressure ? Really ? Sometimes there are some gems when an independent thinker has something to add to the conversation instead of mob screech and splintered egos that ruin the dialog. I basically end up writing my own posts on my own site to summarize and lower the signal-to-noise ratio.

Not many comp-sci people would argue the value of studying boolean algebra, graph theory, algorithms or any of the other fundamental topics related to their field. Why the aversion to Lisp then ? Maybe it’s because some people(including computer scientists) have an aversion to Math ? I believe it’s because they have not taken the time to learn it. It’s not that Lisp is difficult to learn really. In fact newbie programmers find the syntax quite easy. What’s difficult is un-learning the imperative approach that they may have been used to for years. Computers are often treated as binary soup buckets ! Yes, binary soup buckets ! Stir, taste and then repeat the steps until the desired application flavor is acquired for whatever software broth it is that you might be cooking up. Scratch on the same location in memory until the desired outcome is obtained. This is the stuff of real nerd stand-up comedy folks. I could get into the Lisp machine rant but I’ll leave that for another time.

Even if a single useful Lisp application had still not been written yet, it would make no difference at all. Lisp stands on it’s own merits in just the same way that pure mathematics does.

In fact, Lisp basically IS Math : Lambda Calculus, Set Theory etc. but really an implementation of those ideas for a computer. This is one reason that certain mathematicians love Lisp. Interesting to note is that the first computers only existed in Math papers. For reasons why programming languages should be ‘mathy’ and why they are important to theorem proving, read Chaitin. Seriously go read anything by Chaitin right now.

If Lisp was a character from Star Trek it would be Q : despised and misunderstood by the many and loved by the few, which are usually savvy starship captains and smoking-hot babes of various intergalactic species. Women always seem to ‘get-it’ long before men do, why is that ? Something to do with their often higher BPF ?

Thanks for the applause, I’ll be here all week !

*BPF – Brain Plasticity Factor. Where IQ measures ‘intelligence’, BPF is a measure of a person’s ability to consider more than a single perspective. i.e. a flexible vector based intelligence as opposed to a more rigid scalar based intelligence. Low BPFs usually indicate a tendency toward mechanical thinking and often a pre-disposition to fundametal religious outbursts(sometimes fatal), in other words : they just aren’t fun to be around.

High BPFs on the other hand display far greater degrees of intelligence, actual wisdom(not only knowledge), an ability to think independently, increased happiness(not to be so quickly devalued – ask the Ruby guys), an incredibly high-tolerence for those with low BPFs, a certain way with the opposite(or same) sex(remember Einstein with the ladies !) and an all round appreciation for the uniqueness of the human being. Warning : these people can be really fun at parties !

Palindromes (Clojure)


* Update 2009-12-27 * Using lists instead of vectors brings the Clojure version down from around 20x to 10X slower than the CL version. One reader correctly stated that when doing performance comparisons between languages and implementations you want the code and data structures to be as identical as possible.

“A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted.”

Here we look at an implementation of a function(in Clojure) that finds the longest palindrome in some text. Let’s also look at the worst case time and space performance.

First a naive version of the core function :

(defn longest-pals-naive
  "O(n^2) time complexity, O(n) space complexity"
  [text]

  (let* [afirst 0
         alast (dec (count text))
         positions (transient [])]

        (letfn [(ext-pal-around
                 [start end]
                 (if (or (< start 0) (> end alast) 
                         (not (= (nth text start) (nth text end))))
                   (- end start 1)
                   (recur (dec start) (inc end))))
                
                (pal-len-around
                 [position]
                 (let [pos (long (/ position 2))
                       nstart (dec (+ afirst pos))
                       nend (cond (even? position) (+ afirst pos)
                                  (odd? position) (+ afirst pos 1))]
                   (ext-pal-around nstart nend)))]

          (dotimes [n (* 2 (inc alast))]
            (conj! positions (pal-len-around n)))
          (persistent! positions))))

The best of 3 runs on a very underpowered netbook (1.6GHz atom cpu) :

user=> (#'i27.palindromes/big-test)
1000 X ' amanaplanacanalpanama ' 
naive : "Elapsed time: 6011.032 msecs"

Now a more optimized and slightly more complex version that runs in linear time :

(defn longest-pals-fast
  "O(n) time & space complexity"
  [text]

  (letfn [(final-centers
           [n tcenters centers]
           (cond
            (<= n 1)
            centers
            true 
            (let [n (dec n)]
              (recur n
                     (rest tcenters)
                     (concat (vector 
                              (min (first tcenters) n))
                             centers)))))
          
          (ext-centers
           [strn n centers tcenters cdist]
           (cond
            (= 0 cdist)
            #(ext-tail strn (inc n) 1 centers)
            (= (dec cdist) (first tcenters))
            #(ext-tail strn n (first tcenters) centers)
            true
            #(ext-centers strn n 
                          (concat 
                           (vector (min (first tcenters) (dec cdist))) 
                           centers)
                          (rest tcenters) (dec cdist))))

          (ext-tail
           [strn n curr-tail centers]
           (cond 
            (> n (dec (count strn)))
            #(final-centers curr-tail centers
                            (concat (vector curr-tail) centers))
            (= (- n curr-tail) 0)
            #(ext-centers strn n 
                          (concat (vector curr-tail) centers)
                          centers curr-tail)
            (= (nth strn n) (nth strn (- n curr-tail 1)))
            #(ext-tail strn (inc n) (+ 2 curr-tail) centers)
            true
            #(ext-centers strn n
                          (concat (vector curr-tail) centers)
                          centers curr-tail)))
          
          (pal-around-centers
           [strn]
           (reverse (trampoline #(ext-tail strn 0 0 []))))]

    (pal-around-centers text)))

It’s obviously much quicker than the naive version and some Clojure experts might even be able to come up with a few tricks for tweaking the code (possibly using lists instead of vectors and consing instead ?).

user=> (#'i27.palindromes/big-test)
1000 X ' amanaplanacanalpanama '
fast  : "Elapsed time: 524.958 msecs"

A Common Lisp implementation looks very similar …

(defun longest-pals-fast (text)
  "O(n) time & space complexity"

  (declare (optimize (speed 3) 
                     (compilation-speed 0) 
                     (space 0) (debug 0)))

  (labels ((final-centers (n tcenters centers)
             (cond
               ((<= n 0) centers)
               (t
                (let ((n (- n 1)))
                  (final-centers 
                   n
                   (rest tcenters)
                   (cons 
                    (min n (first tcenters))
                    centers))))))
           
           (ext-centers (text n centers tcenters cdist)
             (cond
               ((= 0 cdist)
                (ext-tail text (+ 1 n) 1 centers))
               ((= (- cdist 1) (first tcenters))
                (ext-tail text n (first tcenters) centers))
               (t
                (ext-centers text n 
                             (cons 
                               (min (- cdist 1) (first tcenters))
                              centers)
                             (rest tcenters) (- cdist 1)))))
    
           (ext-tail (text n curr-tail centers)
             (cond 
               ((> n (- (length text) 1))
                (final-centers curr-tail centers 
                               (cons curr-tail centers)))
                ((= (- n curr-tail) 0)
                 (ext-centers text n 
                              (cons curr-tail centers)
                              centers curr-tail))
                ((eql (elt text n) (elt text (- n curr-tail 1)))
                 (ext-tail text (+ 1 n) (+ 2 curr-tail) centers))
                (t
                 (ext-centers text n
                              (cons curr-tail centers)
                              centers curr-tail))))
    
           (pal-around-centers (text)
             (ext-tail text 0 0 '())))
    
    (pal-around-centers text)))

… except that the CL version is about 20X quicker :

triton:palindromes jgrant$ sbcl --noinform --load palindromes.lisp  
                                --eval "(progn (big-test) (quit))"

1000 X ' amanaplanacanalpanama ' 

fast : 
Evaluation took:
  0.024 seconds of real time
  0.023747 seconds of total run time (0.022532 user, 0.001215 system)
  100.00% CPU
  38,248,776 processor cycles
  460,656 bytes consed

All code can be found here :
Clojure,
Common Lisp and
Go
(an imperative implementation for comparison but beware it’s buggy !).

Pong! (in Clojure)

* UPDATED : 2009-09-17 * – rewritten in a functional style that is more idiomatic of Clojure.

A nostalgic attempt to try and learn some GUI programming in Clojure. Inspired by Pong in Haskell.
Play online here.

The computer seems unbeatable(but it’s not thanks to a bug as things get faster).
Have fun !

< 200 lines of code :

;;;;
;;;; Pong!
;;;;
;;;; Justin Grant
;;;; 2009/09/12

(ns i27.games.pong
  (:import (java.awt Color Toolkit Font GraphicsEnvironment Graphics2D)
           (java.awt.image BufferStrategy)
           (java.awt.event ActionListener MouseMotionListener KeyListener
                           MouseEvent KeyEvent)
           (javax.swing JFrame Timer)))

(defstruct ball :h :w :x :y :sx :sy)
(defn new-ball [&amp; [h w x y sx sy]] (atom (struct ball h w x y sx sy)))
(defn set-ball-size [b h w] (swap! b assoc :h h :w w))
(defn set-ball-speed [b sx sy] (swap! b assoc :sx sx :sy sy))
(defn set-ball-position [b x y] (swap! b assoc :x x :y y))

(defstruct paddle :h :w :x :y)
(defn new-paddle [&amp; [h w x y]] (atom (struct paddle h w x y)))
(defn set-paddle-size [p h w] (swap! p assoc :h h :w w))
(defn set-paddle-position [p x y] (swap! p assoc :x x :y y))

(defstruct game :h :w :timer :score :started :my)
(defn new-game [&amp; [h w timer score started my]]
  (atom (struct game h w timer score started my)))
(defn set-game-size [g h w] (swap! g assoc :h h :w w))
(defn set-game-timer [g t] (swap! g assoc :timer t))
(defn set-game-score [g s] (swap! g assoc :score s))
(defn set-game-mouse-y [g my] (swap! g assoc :my my))
(defn stop-game [g]
  (swap! g assoc :started false) (let [#^Timer t (@g :timer)] (.stop t)))
(defn start-game [g]
  (swap! g assoc :started true) (let [#^Timer t (@g :timer)] (.start t)))
(defn reset-game [g b p c]
  (set-ball-size b (* (@g :h) 0.0335) (* (@g :h) 0.0335))
  (set-ball-position b
                     (- (/ (@g :w) 2) (/ (@b :w) 2))
                     (- (/ (@g :h) 2) (/ (@b :h) 2)))
  (set-ball-speed b 15 15)
  (set-paddle-size p (* (@b :h) 5) (@b :w))
  (set-paddle-position p 35 (- (/ (@g :h) 2) (/ (@p :h) 2)))
  (set-paddle-size c (@p :h) (@p :w))
  (set-paddle-position c (- (@g :w) (@p :x) (@p :w)) (@p :y))
  (set-game-score g 0))

(defn pong-frame [g b p c f1 f2]
  (proxy [JFrame ActionListener MouseMotionListener KeyListener] []
    (paint [grf]
           (let [#^JFrame me this
                 #^BufferStrategy bs (.getBufferStrategy me)
                 #^Graphics2D gr (if (not= nil bs) (. bs getDrawGraphics) nil)]
             (if (not= nil gr)
               (do
                 (.setColor gr Color/BLACK)
                 (.fillRect gr 0 0 (@g :w) (@g :h))
                 (.setColor gr Color/WHITE)
                 (.setFont gr f1)
                 (.drawString gr (str "SCORE " (@g :score)) 20 20)
                 (.fillRect gr (@p :x) (@p :y) (@p :w) (@p :h))
                 (.fillRect gr (@c :x) (@c :y) (@c :w) (@c :h))
                 (if (@g :started)
                   (.fillRect gr (@b :x) (@b :y) (@b :w) (@b :h))
                   (do
                     (.setFont gr f2)
                     (.drawString gr "PONG!"
                                  (- (/ (@g :w) 2) 46) (- (/ (@g :h) 2) 16))
                     (.setFont gr f1)
                     (.drawString gr "PRESS 'S' TO START, 'Q' TO QUIT"
                                  (- (/ (@g :w) 2) 200) (+ (/ (@g :h) 2) 30))))
                 (. gr dispose)
                 (. bs show)))))

    (mouseMoved [#^MouseEvent e]
                (set-game-mouse-y g (.getY e))
                (if (&gt; (+ (@g :my) (/ (@p :h) 2)) (@g :h))
                  (set-game-mouse-y g (- (@g :h) (/ (@p :h) 2))))
                (if (&lt; (@g :my) (/ (@p :h) 2))
                  (set-game-mouse-y g (/ (@p :h) 2)))
                (set-paddle-position p (@p :x) (- (@g :my) (/ (@p :h) 2)))
                (let [#^JFrame me this] (.repaint me)))

    (mouseDragged [e])

    (keyPressed [#^KeyEvent e]
                (when (and (not (@g :started)) (= (. e getKeyChar) s))
                  (reset-game g b p c) (start-game g))
                (when (= (. e getKeyChar) q) (System/exit 0)))

    (keyReleased [e])

    (keyTyped [e])

    (actionPerformed [e]
                     ;; update ball position
                     (set-ball-position
                      b (+ (@b :x) (@b :sx)) (+ (@b :y) (@b :sy)))
                     ;; update ball y direction
                     (when (or (= (+ (@b :y) (@b :h)) (@g :h)))
                       (set-ball-speed b (@b :sx) (* -1 (@b :sy))))
                     ;; check if player returns ball
                     (when (and (= (+ (@b :y) (@b :h)) (@p :y))
                                ( (@b :x) (@p :x)))
                       (set-ball-speed b (* -1 (@b :sx)) (@b :sy))
                       (set-game-score g (inc (@g :score)))
                       (set-ball-speed b (+ 1 (@b :sx)) (@b :sy))) ; game gets faster
                     ;; check when computer returns ball
                     (when (and (&gt;= (+ (@b :x) (@b :w)) (@c :x))
                                (&gt;= (+ (@b :y) (@b :h)) (@c :y))
                                ( (+ (@c :y) (/ (@p :h) 2)) (/ (@g :h) 2))
                           (set-paddle-position
                            c (@c :x) (- (@c :y) (* -1 (@b :sx))))
                           (set-paddle-position
                            c (@c :x) (+ (@c :y) (* -1 (@b :sx))))))
                       (if ( (+ (@c :y) (@p :h)) (@g :h))
                       (set-paddle-position c (@c :x) (- (@g :h) (@p :h))))
                     ;; check game over
                     (when (or (&lt; (+ (@b :x) (@b :w)) 0)
                               (&gt; (+ (@b :x) (@b :w)) (@g :w)))
                       (set-paddle-position p (@p :x)
                                            (- (/ (@g :h) 2) (/ (@p :h) 2)))
                       (stop-game g))
                     (let [#^JFrame me this]
                       (.repaint me)))))

(defn -main []
  (let [tk (. Toolkit getDefaultToolkit)
        ge (GraphicsEnvironment/getLocalGraphicsEnvironment)
        gd (. ge getDefaultScreenDevice)
        thegame (new-game (.. tk getScreenSize height)
                          (.. tk getScreenSize width))
        theball (new-ball)
        theplayer (new-paddle)
        thecomputer (new-paddle)
        #^JFrame screen (pong-frame
                         thegame theball theplayer thecomputer
                         (Font. "Courier New" Font/BOLD 24)
                         (Font. "Courier New" Font/BOLD 44))]
    (set-game-timer thegame (Timer. 20 screen))
    (if (not (. screen isDisplayable)) (. screen setUndecorated true))
    (.setVisible screen true)
    (. (.getContentPane screen) setBackground Color/BLACK)
    (. (.getContentPane screen) setIgnoreRepaint true)
    (doto screen
      (.setResizable false)
      (.setBackground Color/BLACK) (.setIgnoreRepaint true)
      (.addMouseMotionListener screen) (.addKeyListener screen))
    (. gd setFullScreenWindow screen)
    (. screen createBufferStrategy 2)
    (reset-game thegame theball theplayer thecomputer)))

(-main)

Calculating π in Clojure (Salamin-Brent)

Took a shot at implementing a PI digit generator in Clojure using a ‘fast’ algorithm.
It seemed like a decent enough excercise to try and understand something about performance in Clojure.

MacBook Pro – Intel Core 2 Duo 2.26 GHz – 4GB RAM
Java(TM) SE Runtime Environment (build 1.6.0_15-b03-219)
Java HotSpot(TM) 64-Bit Server VM (build 14.1-b02-90, mixed mode)
Clojure 1.1.0-alpha-SNAPSHOT (Aug 20 2009) git commit f1f5ad40984d46bdc314090552b76471ee2b8d01

Clojure matches the performance of Java in this example.

The Clojure code :

(import 'java.lang.Math)
(import 'java.math.MathContext)
(import 'java.math.BigDecimal)


(defn sb-pi [places]
  "Calculates PI digits using the Salamin-Brent algorithm
   and Java's BigDecimal class."

  (let [digits (.intValue (+ 10 places)) ;; add some guard digits
        round-mode BigDecimal/ROUND_DOWN]

    (letfn [(big-sqrt[#^BigDecimal num]
             "Calculates square root using Newton's method."
             (letfn [(big-sqrt-int 
                      [#^BigDecimal num #^BigDecimal x0 #^BigDecimal x1]
                      "aux function for calculating square root"
                      (let [#^BigDecimal x0new x1
                            #^BigDecimal x1new (-> num (.divide x0new digits round-mode))
                            #^BigDecimal xsum (+ x1new x0new)
                            #^BigDecimal x1tot (-> xsum (.divide 2M digits round-mode))]
                        (if (= x0 x1)
                          x1tot
                          (recur num x1 x1tot))))]
               (big-sqrt-int
                num 0M (BigDecimal/valueOf
                        (Math/sqrt (. num doubleValue))))))
            (sb-pi-int [#^BigDecimal a #^BigDecimal b 
                        #^BigDecimal t #^BigDecimal x #^BigDecimal y]
             "aux function for calculating PI"
             (let
                 [#^BigDecimal y1 a
                  #^BigDecimal absum (+ a b)
                  #^BigDecimal a1 (-> absum (.divide 2M digits round-mode))
                  #^BigDecimal b1 (big-sqrt (* b y1))
                  #^BigDecimal ydiff (- y1 a1)
                  #^BigDecimal t1 (- t (* x ydiff ydiff))
                  #^BigDecimal x1 (* x 2M)]               
               (if (== a b)
                 (let [#^BigDecimal absum1 (+ a1 b1)
                       #^BigDecimal absqrd (* absum1 absum1)
                       #^BigDecimal u (* t1 4M)]
                   (-> absqrd
                       (.divide u digits round-mode)
                       (.setScale places round-mode)))
                 (recur a1 b1 t1 x1 y1))))]
      
      (sb-pi-int 1M (-> 1M (.divide #^BigDecimal (big-sqrt 2M) digits round-mode))
                       (/ 1M 4M) 1M nil))))


(time (println (sb-pi (Integer/parseInt (second *command-line-args*)))))


$ time clj pi.clj 1               -->       3.403 msecs
$ time clj pi.clj 10              -->       3.956 msecs
$ time clj pi.clj 100             -->      10.630 msecs
$ time clj pi.clj 1000            -->     141.937 msecs
$ time clj pi.clj 10000           -->    3316.180 msecs

The same algorithm in Java (but using iteration instead of recursion) :


import java.math.BigDecimal;
import static java.math.BigDecimal.*;

class Pi {
  private static final BigDecimal TWO = new BigDecimal(2);
  private static final BigDecimal FOUR = new BigDecimal(4);
  private static int ROUND_MODE = ROUND_DOWN;

  public static void main(String[] args) {
    long start = System.nanoTime();
    System.out.println(pi(Integer.parseInt(args[0])));
    System.out.println("Elapsed time: " + 
                       ((System.nanoTime() - start) / 1E6) + " msecs");  
  }
    
  // Salamin-Brent Algorithm
  public static BigDecimal pi(final int digits) {
    final int SCALE = 10 + digits;
    BigDecimal a = ONE;
    BigDecimal b = ONE.divide(sqrt(TWO, SCALE), SCALE, ROUND_MODE);
    BigDecimal t = new BigDecimal(0.25);
    BigDecimal x = ONE;
    BigDecimal y;
        
    while (!a.equals(b)) {
      y = a;
      a = a.add(b).divide(TWO, SCALE, ROUND_MODE);
      b = sqrt(b.multiply(y), SCALE);
      t = t.subtract(x.multiply(y.subtract(a).multiply(y.subtract(a))));
      x = x.multiply(TWO);
    }
        
    return a.add(b)
      .multiply(a.add(b))
      .divide(t.multiply(FOUR), SCALE, ROUND_MODE)
      .setScale(digits, ROUND_MODE);
  }
    
  // square root method (Newton's)
  public static BigDecimal sqrt(BigDecimal A, final int SCALE) {
    BigDecimal x0 = new BigDecimal("0");
    BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
        
    while (!x0.equals(x1)) {
      x0 = x1;
      x1 = A.divide(x0, SCALE, ROUND_MODE);
      x1 = x1.add(x0);
      x1 = x1.divide(TWO, SCALE, ROUND_MODE);
    }
        
    return x1;
  }
}


$ time java Pi 1         ---->         2.162 msecs
$ time java Pi 10        ---->         2.425 msecs
$ time java Pi 100       ---->         7.897 msecs
$ time java Pi 1000      ---->       150.610 msecs
$ time java Pi 10000     ---->      3009.705 msecs

Clojure : The zombie-reanimated corpse of Lisp

* updated 2009-08-21 ** updated 2009-08-20 *

!!! DISCLAIMER !!!

Nowadays it’s frowned upon to criticize anything in society. It’s quite pervasive.
That is unless you happen to also be criticizing the same thing that a group of other people are also criticizing.
We hardly speak our minds, instead it’s more common to take a passive-aggressive and sometimes socio-pathic approach when any type of issue arises. Annoying as they can be there just aren’t enough Zed’s in the world. We’d rather be part of the herd and not admit it to ourselves. We don’t want to be shunned, we don’t want to lose friends, our homes, wives and the stuff that we accumulate.
So we go with the flow at the expense of the dream and what is better in the long term. After
all everyone’s been doing just that since the beginning of time right ? And besides
won’t we make more money if we just go along with everyone else ? Hardly, look at
the current state of the world economy. Astonishing even as we’re told to buy that it’s looking better, it has to, we don’t want to believe the alternative.

!!! DISCLAIMER !!!

On that note, this is my satiric rant regarding what many are hyping as the future of Lisp, so be warned.
I dedicate it to the Zed’s of this world. It’s abrasiveness is meant to counter the ‘mega-hype’ that accompanies Clojure’s sales pitch. Clojure is not worthy of the Lisp name. It is the antithesis of the Lisp machine in every way. It has little regard for the intellectual rigor and cohesiveness of Lisp.

Whether it’s author and followers are even aware or willing to acknowledge this :
Clojure has inherited many of Java’s idioms and problems.
Clojure is not only built on top of the JVM. It is also built on the Java language.

For better or worse this means that many Clojure types are Java types underneath.
This is a fundamental and idiomatic clash in Clojure’s type system and this effects the way that software can be written in Clojure. Java is an imperative language while Clojure is a ‘trying much too hard to be pure’ functional language. Clojure is hyped for it’s immutable strictness of local variables to the extent that some refer to it as if it’s a ‘silver bullet’ for issues related to writing software for multi-core platforms (STM etc.).

It’s dictator doesn’t provide much of a reason for enforcing the immutability of local variables. Yes, I’ve read the long thread on CLL that ‘explains’ some of the reasons. I’m still not convinced why concurrent programming support had to be implemented at the language level. The focus on concurrent programming assumes much in the way that immutable types are forced on the programmer unless they decide to stoop to using Java’s mutable types.

Why not simply add support for concurrent programming as a library instead ?

Why not provide both immutable and mutable versions of the same data types ?

Why not let the programmer decide what paradigm works best for themselves ?

The reasoning for implementing Clojure on the JVM is understandable, there is much that the JVM has to offer : memory models, GC, overall maturity etc.
The hype about ‘getting all that for free’ is very optimistic. The JVM was designed specifically for the Java language, so draw your own conclusions.

That seems to be changing more recently
. Supporting other languages on the JVM may turn out to be ‘a good thing’ depending on what your favorite language is on that platform.

There are an abundance of Java libraries that Clojure fans will be glad to have access to now.
The hype about having access to all these libraries ‘for free’ is ironic. Many Java libraries only exist
due to limitations of the Java language itself. Also when writing real-world software, what about the effort required to align the multitude of Java libraries that assume an imperative environment with Clojure ? Can these libraries be used easily, safely and with the same performance ?
You just have to picture all the newbie Clojure programmers when they hit this wall.
No problem right ? They can just wrap all the imperative Java libraries using their newly discovered hammer : macros. Hopefully many of these old libraries are used only as a bridge until they are replaced by more shorter idiomatic functional versions.

Clojure introduces new problems(ok ‘challenges’ if you will) having discarded enough of the last half-century
of Lisp progress. Sure, Common Lisp has it’s problems but hailing Clojure as it’s future is a new low in the community. Another lisper put it so bluntly :  “Clojure is the gutted and zombie-reanimated corpse of a dream.”

If anything, Clojure is hopefully the future of the JVM. It is definitely a step up the language continuum, for those who decide to move from Java to Clojure.

The hype, guru-worship, immaturity of the language and the benevolent dictatorship of Clojure are rapidly catalyzing something in the world of commercial software development. This can be an indicator of trouble ahead. There’s good reason that Haskell’s motto has long been “Avoid success at all costs.”
Clojure is popular right now and in a few years it’ll be used in common “tech” speak by clueless managers
and inexperienced programmers who consider Clojure their first exposure to a functional “Lisp”.
Many of us will inevitably be using Clojure in our day jobs in the same way that we currently have little choice in
using whatever the required and popular lowest common denominator is at a company.
At least Clojure is a real improvement over the status quo, I can appreciate that.