Skip to content
February 3, 2011 / marrowboy

Implementing (is-prime? n) in Clojure. Uncle Bob’s improved transformation priority list

Uncle Bob is onto something.  He’s developing a system of “transformation priorities” (TP), which say that when my code has to change to meet some requirement, then I ought to consider certain kinds of changes preferable to others.

The original TP post: http://cleancoder.posterous.com/the-transformation-priority-premise

Using TP to build a better sort: http://cleancoder.posterous.com/transformation-priority-and-sorting

TP ammended after feedback: http://cleancoder.posterous.com/fib-the-transformation-priority-premise

So, I’m going to take his new set literally, to implement a clojure function:
(is-prime? n)

Here’s the ammended list, for reference:

  1. ({}–>nil) no code at all->code that employs nil
  2. (nil->constant)
  3. (constant->constant+) a simple constant to a more complex constant
  4. (constant->scalar) replacing a constant with a variable or an argument
  5. (statement->statements) adding more unconditional statements.
  6. (unconditional->if) splitting the execution path
  7. (scalar->array)
  8. (array->container)
  9. (statement->tail-recursion)
  10. (if->while)
  11. (statement->recursion)
  12. (expression->function) replacing an expression with a function or algorithm.
  13. (variable->assignment) replacing the value of a variable.
  14. (case) adding a case (or else) to an existing switch or if

I’ll use these test-cases:

(fact (is-prime? 1) => false)
(fact (is-prime? 2) => true)
(fact (is-prime? 3) => true)
(fact (is-prime? 4) => false)
(fact (is-prime? 5) => true)
(fact (is-prime? 6) => false)
(fact (is-prime? 7) => true)
(fact (is-prime? 31) => true)
(fact (is-prime? 32) => false)

Edit: Stop. Think about it. What will my first bug report be? Ok, now read on…

Iteration #1:

(unfinished is-prime?)

The excellent Midje allows us to use unfinished to say “I haven’t written this yet”.
Result: all tests fail.

Apply TP#1: ({}–>nil)

Iteration #2:

(defn is-prime? [n]
  nil)

Result: all tests still fail.

Apply TP#1: (nil->constant)

Iteration #3:

(defn is-prime? [n]
  false)

Result: 4/9 passed

Apply TP#6: (unconditional -> if)

Iteration #4:

(defn is-prime? [n]
  (if (= n 1)
    false
    true))

Result: 6/9 passed

Ok now we’re getting somewhere interesting. The remaining test failures are 4, 6 & 32. So this is easy to fix by just killing off even numbers. I count this as a re-use of #6, not #14 because the ifs are nested not in serial:

Apply TP#6: (unconditional -> if)

Iteration #5:

(defn is-prime? [n]
  (if (= n 1)
    false
    (odd? n)))

Result: 8/9 passed

GAH! In my haste I have broken the previously-passing test for

(is-prime? 2)

How to fix this?
Candidate #1: Add a special case for n=2:

(defn is-prime? [n]
  (if (= n 1)
    false
    (if (= n 2)
      true
      (odd? n))))

This is an application of the dreaded #14, the lowest of the low, over which any other change is preferable! What else could I do?

Candidate #2: Add a test for n=2 into the test for divisibility by 2:

(defn is-prime? [n]
  (if (= n 1)
    false
    (or (= n 2) (odd? n))))

Hmm, what’s this? Is it just another, sneaky way to implement #14? No, I don’t think so – I’ve changed the condition of the final if, but there’s no new branches. That’s a new type of thing, adding more conditions to an existing conditional – I can’t see that covered in any of the existing TPs.

Apply TP#??: (conditional -> more complex conditional)

Iteration #6:

(defn is-prime? [n]
  (if (= n 1)
    false
    (or (= n 2) (odd? n))))

Result: 9/9 passed!!!!

Brilliant, I’m all finished now lets put it live and watch the money, fame, etc roll in!

The first bug report

Surely not? This is tested code! But, after careful checking, I have to conceed that 9, 15, 21 and many other numbers are in fact not prime and the algorthim doesn’t really work. So, I added a bunch more tests, and in the end the code looked like this:

(defn is-prime? [n]
  (if (= n 1) false
    (every? false?
      (map #(= 0 (mod n %1)) (range 2 n)))))

To get to this point, I had to use #7 (scalar to array, changing “2” to (range 2 n)), and #10 (if to while), to loop over the range. That must be a common pair!. I felt a lot of #12 going on as every expression is also a function but I’ll only claim it for the anonymous function used in the mapping. As a bonus, I got to remove the check for the specific case of n=2. Splendid.

This is still pretty inefficient for large numbers. (range 2 n) really only needs to be (range 2 (+ 1 (Math/sqrt n))), but I don’t see how TDD is going to force me to make an improvement like that.

In the end

I think there is a case for a new TP: “conditional to more complex conditional”, and the effect of being able to make a negative transformation (ie to remove some code) ought to be weighed along with the cost of creating new code when considering your next step.

Advertisements

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

%d bloggers like this: