# 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:

- ({}–>nil) no code at all->code that employs nil
- (nil->constant)
- (constant->constant+) a simple constant to a more complex constant
- (constant->scalar) replacing a constant with a variable or an argument
- (statement->statements) adding more unconditional statements.
- (unconditional->if) splitting the execution path
- (scalar->array)
- (array->container)
- (statement->tail-recursion)
- (if->while)
- (statement->recursion)
- (expression->function) replacing an expression with a function or algorithm.
- (variable->assignment) replacing the value of a variable.
- (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.

## One Comment

Leave a Comment## Trackbacks