Clojure Kata Two: Karate Chop (Pt. 5)

April 1, 2010

Lying ill in bed probably isn’t the most conducive environment for programming. I’ll spare you the full medical details, but in a strange way it put me in an evil mood… the kind of mood that seemed fitting to give macros a go.

I’ve never really seen the point of macros, but then again my experience of them has been the watered-down variety featured in languages like C. Reading up on macros in Scheme and Clojure more recently, macros come across as predominantly a way to do evil things. I say predominantly, because I accept that there are very rare occasions when a macro makes profound sense. Please note that the fifth solution I am about to present is definitely not an example of a good reason.

Last week, I was re-reading Jon Bentley’s excellent Programming Pearls book. I had been trying to avoid reading anything about binary searches while working on the code katas, so I picked a completely inappropriate book because binary searches are featured quite a bit. With my brain now sullied by a classic binary search algorithm, I went and undertook the fourth solution and tried to be a bit radical. It failed.

For the fifth one, I decided not to come up with my own solution but try a couple of things. The first was to implement Bentley’s algorithm in Clojure, and the second was to try and make it more compact through the use of macros – as a cheeky excuse to give them a try. The algorithm is already pretty elegant anyway, so I wasn’t sure what I could improve.

As ever, the code is on BitBucket at: http://bitbucket.org/metaljoe/metaljoe_codekata/

First thing was to implement the original algorithm in Clojure: (edited from changeset 9b3ef06116fd for clarity)

(defn chop [ item list ]
  (loop [ lower 0
          upper (- (count list) 1) ]
    (let [ mid (quot (+ lower upper) 2) ]
      (if (> lower upper)
        -1
        (if (< (get list mid) item)
          (recur (+ mid 1) upper )
          (if (= (get list mid) item)
            mid
            (recur lower (- mid 1))))))))

Okay, the first thing that stands out is the let, which holds the value of mid. Wouldn’t it be great to get rid of that? However, copying the code for mid back into the references would bloat the code out. I could use a function, but I’d be passing three parameters and it wouldn’t aid readability much. I would probably leave it for production code, but since I have a macro hammer in my hand, this looks like a macro nail waiting to be banged.

(defmacro mid []
  (list 'quot '(+ lower upper) 2) )

This will replace mid with the appropriate code in the macro. I create a list, all Clojure code is a list, and turn off parsing for quot and the lower + upper addition. If I don’t do that, they will both be evaluated in that context and will fail because neither are available in the namespace. I feel bad about these references, but this is just an exercise. I also realised at this point that list already exists in Clojure, and I should’ve used a different name for the argument to chop!

Once I’ve created the macro, I need to adjust the references to mid in the code. The references need to be wrapped in parentheses to avoid an error.

The next observation is that “(get list mid)” is repeated twice. It hasn’t quite reached the three-strikes rule, but it is duplication. I could set a variable to hold the value of the list at mid, or I could write a function to do it. The former would add an extra line to the code, and I would like to reduce the amount of variables if possible, especially as I’ve just gotten rid of one. The latter option wouldn’t offer much advantage because I’d still be passing list and mid to a function, and probably one with a less concise name than “get”. Basically, it’s another contrived situation for me to try a macro – though I would not do this in production code.

(defmacro get-mid []
  (list 'get 'list '(mid)))

This follows the same pattern as the mid macro – and even calls said macro.

(defn chop [ item list ]
  (loop [ lower 0
          upper (- (count list) 1) ]
    (if (> lower upper)
      -1
      (if (< (get-mid) item)
        (recur (+ (mid) 1) upper )
        (if (= (get-mid) item)
          (mid)
          (recur lower (- (mid) 1)))))))

Not a massive improvement to the code readability, and I’m not entirely happy with get-mid as a name. The nicest thing is that the let statement has been removed.

How about dealing with the statement to initialise the upper variable? Shunning a more obvious function…

(defmacro get-upper []
  (list '- '(count list) 1 ))

Okay, time for one more thing… well, two actually. The recur statements are fine, but perhaps we could make them more declarative?

(defmacro look-left []
  (list 'recur 'lower '(- (mid) 1)))

(defmacro look-right []
  (list 'recur '(+ (mid) 1) 'upper ))

This changes the loop code to read:

(loop [ lower 0
        upper (get-upper) ]
  (if (> lower upper)
    -1
    (if (< (get-mid) item)
      (look-right)
      (if (= (get-mid) item)
        (mid)
        (look-left))))))

In fact, while typing this up, it looks odd now because it’s defining two variables that are apparently never updated.

First off, let’s remove the last visible references to lower and upper, using (surprise!) a suitably named macro…

(defmacro search-exhausted []
  (list '> 'lower 'upper))

Now time to deal with that loop statement. Well, my plan was to create a macro like this:

(defmacro do-search [ & body ]
  `(loop [ ~'lower 0
           ~'upper (get-upper) ] ~@body
     {:lower ~'lower :upper ~'upper }))

This macro is based on Stuart Halloway’s evil-bench example from the Programming Clojure book code, which is very evil. But since this kata solution is all about evilness, I only feel slightly guilty.

The aim was to replace the loop with code that looks like this:

(do-search
  (if (search-exhausted)
    -1
    (if (< (get-mid) item)
      (look-right)
      (if (= (get-mid) item)
        (mid)
        (look-left))))))

Unfortunately, this raises the following exception:

Exception in thread "main" java.lang.UnsupportedOperationException: Can only recur from tail position (code_kata_2e.clj:64)

The macroexpand and macroexpand-1 functions weren’t giving me anything useful, probably because they were overwhelmed by nastiness. Oh well, not to matter as I don’t exactly grok macros just yet and I’m happy overall with what I’ve learnt this time. The code is on BitBucket, so if anyone with better macro development skills can point out the problem, please let me know.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 626 other followers

%d bloggers like this: