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
  (+ 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 
             (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 all points
    (str "Random generation of " cnt " points...")) 
       (draw-points rpts blue-edge-stroke blue-fill)
       (print-points rpts text-input)
       ;; calc hull
    (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)
          (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.

Purely Functional Data Structures & Algorithms : Fast Fourier Transform in Qi

In this second post in this series we look at an implementation of the always useful Fast Fourier Transform.

(FFT) An algorithm for computing the Fourier transform of a set of discrete data values. Given a finite set of data points, for example a periodic sampling taken from a real-world signal, the FFT expresses the data in terms of its component frequencies. It also solves the essentially identical inverse problem of reconstructing a signal from the frequency data.

The FFT is a mainstay of numerical analysis. Gilbert Strang described it as “the most important algorithm of our generation”. The FFT also provides the asymptotically fastest known algorithm for multiplying two polynomials.

Our implementation comes in at just under 100 lines of code

(declare atan [number --&gt; number])
(define atan X -&gt; (ATAN X))

(declare cos [number --&gt; number])
(define cos X -&gt; (COS X))

(declare sin [number --&gt; number])
(define sin X -&gt; (SIN X))

(tc +)

 Complex numbers 

(datatype complex
    Real : number; Imag : number;
    [Real Imag] : complex;)

(define complex-mult
  {complex --&gt; complex --&gt; complex}
  [R1 I1] [R2 I2] -&gt; [(- (* R1 R2) (* I1 I2))
                      (+ (* R1 I2) (* I1 R2))])

(define complex-add
  {complex --&gt; complex --&gt; complex}
  [R1 I1] [R2 I2] -&gt; [(+ R1 R2) (+ I1 I2)])

(define complex-diff
  {complex --&gt; complex --&gt; complex}
  [R1 I1] [R2 I2] -&gt; [(- R1 R2) (- I1 I2)])

 Fast Fourier Transform 

(define butterfly-list
    {((list complex) * ((list complex) * (list complex)))
     --&gt; ((list complex) * ((list complex) * (list complex)))}
    (@p X (@p X1 X2)) -&gt; (if (empty? X)
                             (@p X (@p (reverse X1) (reverse X2)))
                              (@p (tail (tail X))
                                  (@p (cons (head X) X1)
                                      (cons (head (tail X)) X2))))))

(define calc-results
    {(((list complex) * (list (list complex))) * 
                        ((list complex) * (list complex)))
     --&gt; (((list complex) * (list (list complex))) * 
                            ((list complex) * (list complex)))}
    (@p (@p [W WN] [YA YB]) (@p Y1 Y2)) -&gt;
    (if (and (empty? Y1) (empty? Y2))
        (@p (@p [W WN] [(reverse YA) (reverse YB)]) (@p Y1 Y2))
         (@p (@p [(complex-mult W WN) WN]
                 [(cons (complex-add  (head Y1) (complex-mult W (head Y2))) YA)
                 (cons (complex-diff (head Y1) (complex-mult W (head Y2))) YB)])
             (@p (tail Y1) (tail Y2))))))

(define fft
    {number --&gt; complex --&gt; (list complex) --&gt; (list complex)
     --&gt; (list complex)}
    1 WN X Y -&gt; [(head X)]
    2 WN X Y -&gt; [(complex-add  (head X) (head (tail X)))
                 (complex-diff (head X) (head (tail X)))]
    N WN X Y -&gt; (let M   (round (/ N 2))
                     Inp (butterfly-list (@p X (@p [] [])))
                     X1  (fst (snd Inp))
                     X2  (snd (snd Inp))
                     Y1  (fft M (complex-mult WN WN) X1 [])
                     Y2  (fft M (complex-mult WN WN) X2 [])
                     W   [1 0]
                     Res (calc-results (@p (@p [W WN] [[] []]) (@p Y1 Y2)))
                     (append (head (snd (fst Res)))
                             (head (tail (snd (fst Res)))))))

(define dotimes-fft
    {number --&gt; number --&gt; complex --&gt; (list complex) --&gt; (list complex)
    --&gt; (list complex)}
    Iterations Size W Input Res -&gt;
    (if ( number --&gt; (list complex) 
     --&gt; (list complex)}
    Iterations Size Input -&gt; (let Pi    (* 4 (atan 1))
                                  Theta (* 2 (/ Pi Size))
                                  W     [(cos Theta) (* -1 (sin Theta))]
                                  (dotimes-fft Iterations Size W Input [])))

Let’s give it a spin …

 Square wave test 

(26-) (time (run-fft 100000 16 
             [[0 0] [1 0] [0 0] [1 0] [0 0] [1 0] [0 0] [1 0]
              [0 0] [1 0] [0 0] [1 0] [0 0] [1 0] [0 0] [1 0]]))

Evaluation took:
  2.999 seconds of real time
  2.942718 seconds of total run time (2.798716 user, 0.144002 system)
  [ Run times consist of 0.371 seconds GC time, and 2.572 seconds non-GC time. ]
  98.13% CPU
  6,282,874,678 processor cycles
  1,641,619,888 bytes consed

[[8 0] [0.0 0.0] [0.0 0.0] [0.0 0.0] 
 [0.0 0.0] [0.0 0.0] [0.0 0.0] [0.0 0.0]
 [-8 0] [0.0 0.0] [0.0 0.0] [0.0 0.0] 
 [0.0 0.0] [0.0 0.0] [0.0 0.0] [0.0 0.0]] : (list complex)

All Qi code in this post is here.