Clojure

Clojure, introduced in 2007, is an interesting beast – a Lisp for the JVM. Not only will you be able to sneak a Lisp into your workplace, but it is a first-class citizen, able to utilize all your existing Java libraries. Clojure is distributed simply as a jar file that you add to your JVM. Give it a try!

Here is Euler1 in Clojure. It uses a list comprehension and reduce. It looks even simpler than my first Lisp example; Clojure has a range function built in, for example:

; Euler1 in Clojure

(defn euler1 [x]
    (reduce +
        (for [n (range x) :when (or (= (mod n 3) 0) (= (mod n 5) 0))]
            n)))

(pr (euler1 1000))

Here is another version, which took me an hour to write. It’s analogous to my Standard ML version, which uses tail recursion and an accumulator. Notice also the multiple method signatures for euler1() – the first one takes one param while the second takes two. This lets us internally initialize an accumulator for our recursion:

; Euler1 in Clojure

(defn euler1
    ([n] (euler1 n 0))
    ([n acc] (if (= n 0)
        acc
        (if (or (=(mod n 3)0) (=(mod n 5)0))
            (recur (- n 1) (+ acc n))
            (recur (- n 1) acc)))))

(pr (euler1 999))

Here’s a rewrite of my third Lisp example, in which I recursively pass around a list instead of an integer. It’s very similar to the Lisp version:

; Euler1 in Clojure

(defn mod-3-5 [n]
    (if (or (=(mod n 3)0) (=(mod n 5)0))  n  0))

(defn euler [lst acc]
    (if (not-empty lst)
        (recur (rest lst) (+ acc (mod-3-5 (first lst))))
        acc))

(defn euler1 [n]
    (euler (range n) 0))

(pr (euler1 1000))

Let’s write a Quicksort variant – break the list up into halves and a middle element, call euler1() recursively on both halves, and return a value for the middle element plus the return value of both halves. I couldn’t find an array slicing function, so let’s also roll our own. This version also shows the use of local variables with the let statement:

; Euler1 in Clojure

(defn slice [coll a b]
    ; a - 1-based starting index
    ; b - inclusive ending index
    (let [[x y] (split-at (dec a) coll)]
        (take (inc (- b a)) y)))

(defn mod-3-5 [n]
    (if (or (=(mod n 3)0) (=(mod n 5)0))  n  0))

(defn euler1 [coll]
    (if (empty? coll)
        0
        ; find the midpoint of the list
        (let [pivot (quot (count coll) 2)]
            ; return a value for the middle element
            (+ (mod-3-5 (nth coll pivot))
                ; plus the calculated value of the first half of the list
                (euler1 (slice coll 1 pivot))
                ; plus the calculated value of the last half of the list
                (euler1 (slice coll (+ pivot 2)(count coll)))))))

(println (euler1 (range 1000)))

Here’s a version in which I define my own map/filter/reduce functions, and then simply apply them. Map’s only purpose here is for illustration, since it returns itself. Map and filter demonstrates use of a lambda – an anonymous function. Note that there is no recursion or looping involved:

; Euler1 in Clojure

(defn myMap [lst]
    (map (fn [x] x) lst))

(defn myFilter [lst]
    (filter
        #(or (= (mod % 3) 0) (= (mod % 5) 0))
        lst))

(defn myReduce [lst]
    (reduce + lst))

(defn euler1 [lst]
    (myReduce (myFilter (myMap lst))))

(pr (euler1 (range 1000)))

Functions in Clojure are first-class, meaning they are as easy to manipulate as data. Let’s build off the previous example, but this time we’ll store our map/filter/reduce functions in a list. We’ll pass the functions and the integers into _euler1(), and recursively apply the first function to the integers until the function list is empty:

; Euler1 in Clojure

(defn myMap [lst]
    (map (fn [x] x) lst))

(defn myFilter [lst]
    (filter
        #(or (= (mod % 3) 0) (= (mod % 5) 0))
        lst))

(defn myReduce [lst]
    (reduce + lst))

(defn euler1 [fns data]
    (if (not-empty fns)
        (recur (rest fns) ((first fns) data))
        data))

(pr (euler1 [myMap myFilter myReduce] (range 1000)))

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation. I couldn’t find an exponent function, so I rolled my own. Also, Lisps seem to suck at making long math expressions legible, so I’ve attempted to clarify it with indentation:

; Euler1 in Clojure

(defn expt
    ([n x] 
        (expt n x 1))
    ([n x acc]
        (if (= 0 x)
            acc
            (expt n (- x 1) (* n acc)))))

(defn mySum [n size]
  (* n 
    (int 
      (/
        (+ 
          (expt (int (/ size n)) 2) 
          (int (/ size n)))
        2))))

(defn euler1 [size]
  (- (+ (mySum 3 size) (mySum 5 size)) (mySum 15 size)))

(pr (euler1 999))

One of Lisp’s greatest claims to fame is its regular syntax. It may appear illegible at first, but Lisp is not designed for human-readability – it’s designed for machine-readability. Unlike other languages where your code is written as a bunch of text, Lisp is written as collection of syntax symbols having a regular grammar. Lisp also has a precompilation stage called macros which generate and substitute code using user-defined routines, allowing you to extend the language arbitrarily. What does all this mean? Since I’m a macro novice myself, I’ll borrow some material from this StackOverflow answer. Let’s say you’re fond of the Python lisp comprehension syntax:

    S = [x for x in range(1000) if x%3==0 or x%5==0]

Well, Clojure doesn’t have anything like that, but don’t despair – Clojure lets you roll your own! The macro stage takes source tokens as input, transforms it, and then returns syntax that replaces the original tokens. I’ve attempted to use emojis to show how the the function parameters map to the arguments passed in for ease of illustration. Notice we do nothing with the tokens in and conditional – they exist merely as part of our list comprehension’s grammar:

; Euler1 in Clojure

(defmacro lcomp [⚡️expression⚡️ 🍰for🍰 🌵var🌵 🅰️in🅰️ 🗡list🗡 🌍conditional🌍 🇬🇦conditional-test🇬🇦]
    `(🍰for🍰 [~🌵var🌵 ~🗡list🗡 :when ~🇬🇦conditional-test🇬🇦] ~⚡️expression⚡️))

(defn mod-3-5 [n]
    (or (=(mod n 3)0) (=(mod n 5)0)))

(prn (reduce + (lcomp ⚡️x⚡️ 🍰for🍰 🌵x🌵 🅰️in🅰️ 🗡(range 1000)🗡 🌍if🌍 🇬🇦(mod-3-5 x)🇬🇦)))

The following code is what is generated in my environment, returned by the macro and substituted for the original tokens:

    (clojure.core/for [x (range 1000) :when (mod-3-5 x)] x)

Life with Clojure isn’t all roses. It took me most of a day to write the first simple example. This is due to the fact that Clojure just feels ‘beta’. Runtime error messages are good – they’re JVM stack traces. But compile-time error messages are rather cryptic and take some getting used to.

To run a Clojure program under Linux, simply add clojure.jar to your classpath, then execute clojure.jar, passing it your program as an argument:

$ export CLASSPATH=/usr/share/java/clojure.jar
$ java clojure.main euler1.clj
233168

For those following along with cygwin, be careful. Java doesn’t understand cygwin paths – they’ll need to be converted first:

$ java -jar `cygpath -m /usr/share/java/clojure.jar` euler1.clj
233168

Clojure sports a spiffy REPL which I was able to get to work with Windows but not with cygwin.