💾 Archived View for idiomdrottning.org › inliniac-primes captured on 2024-03-21 at 16:04:41. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

The Inliniac Goes to Town

Let’s see what happens when we apply our Inliniac principles while refactoring some Java code.

The code example we’ll start with comes from the book Clean Code by Robert C. Martin. It’s a good example because the starting code is divided into methods in order to match a set of preconceived semantics, and the whole deal with the Inliac policy is to instead let the code itself dictate the factoring and at which levels we should abstract.

import java.util.ArrayList;

public class PrimeGenerator {
  private static int[] primes;
  private static ArrayList<Integer> multiplesOfPrimeFactors;

  protected static int[] generate(int n) {
    primes = new int[n];
    multiplesOfPrimeFactors = new ArrayList<Integer>();
    set2AsFirstPrime();
    checkOddNumbersForSubsequentPrimes();
    return primes;
  }

  private static void set2AsFirstPrime() {
    primes[0] = 2;
    multiplesOfPrimeFactors.add(2);
  }

  private static void checkOddNumbersForSubsequentPrimes() {
    int primeIndex = 1;
    for (int candidate = 3;
         primeIndex < primes.length;
         candidate += 2) {
      if (isPrime(candidate))
        primes[primeIndex++] = candidate;
    }
  }

  private static boolean isPrime(int candidate) {
    if (isLeastRelevantMultipleOfNextLargerPrimeFactor(candidate)) {
      multiplesOfPrimeFactors.add(candidate);
      return false;
    }
    return isNotMultipleOfAnyPreviousPrimeFactor(candidate);
  }

  private static boolean
  isLeastRelevantMultipleOfNextLargerPrimeFactor(int candidate) {
    int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()];
    int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor;
    return candidate == leastRelevantMultiple;
  }

  private static boolean
  isNotMultipleOfAnyPreviousPrimeFactor(int candidate) {
    for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) {
      if (isMultipleOfNthPrimeFactor(candidate, n))
        return false;
    }
    return true;
  }

  private static boolean
  isMultipleOfNthPrimeFactor(int candidate, int n) {
   return
     candidate == smallestOddNthMultipleNotLessThanCandidate(candidate, n);
  }

  private static int
  smallestOddNthMultipleNotLessThanCandidate(int candidate, int n) {
    int multiple = multiplesOfPrimeFactors.get(n);
    while (multiple < candidate)
      multiple += 2 * primes[n];
    multiplesOfPrimeFactors.set(n, multiple);
    return multiple;
  }
}

Ok, fun. Let’s start by inlining absolutely everything.

import java.util.ArrayList;

public class PrimeGenerator {
  protected static int[] generate(int n) {
    int[] primes = new int[n];
    ArrayList<Integer> multiples = new ArrayList<Integer>();
    primes[0] = 2;
    multiples.add(2);
    candidates:
    for (int primeIndex = 1, candidate = 3;
         primeIndex < primes.length;
         candidate += 2) {
      if (candidate == primes[multiples.size()]
          * primes[multiples.size()]) {
        multiples.add(candidate);
        continue;
      }
      for (int i = 1; i < multiples.size(); i++) {
        int multiple = multiples.get(i);
        while (multiple < candidate)
          multiple += 2 * primes[i];
        multiples.set(i, multiple);
        if (candidate == multiple)
          continue candidates;
      }
      primes[primeIndex++] = candidate;
    }
    return primes;
  }
}

We could stop here and that’d be fine, I’d be pretty happy with that. This version is also pretty nifty because there’s no side effects.

If we’re looking for more to do, I don’t like dealing with the continue labels so let’s start by extracting that part:

import java.util.ArrayList;

public class PrimeGenerator {
  private static int[] primes;
  private static ArrayList<Integer> multiples;

  protected static int[] generate(int n) {
    primes = new int[n];
    multiples = new ArrayList<Integer>();
    primes[0] = 2;
    multiples.add(2);
    for (int i = 1, c = 3; i < primes.length; i++, c = findNextPrime(c + 2))
      primes[i] = c;
    return primes;
  }

  private static int findNextPrime(int candidate) {
    if (candidate == primes[multiples.size()]
        * primes[multiples.size()]) {
      multiples.add(candidate);
      return findNextPrime(candidate+2);
    }
    for (int i = 1; i < multiples.size(); i++) {
      int multiple = multiples.get(i);
      while (multiple < candidate)
        multiple += 2 * primes[i];
      multiples.set(i, multiple);
      if (candidate == multiple)
        return findNextPrime(candidate+2);
    }
    return candidate;
  }
}

Now, I’m not much of a mathematician so I wouldn’t‘ve been able to make a “find next prime” function normally. It’s just the life-changing magic of refactoring.

Here, by scope-lifting the vectors, we reintroduced state, which, depending on what you want to do is kinda iffy. At this point we could still instead pass those in to the subroutine—still stateful, but more explicit.

But let’s just call it, uh, “dynamic programming” and move on.

Next, I see that we’re introducing a variable, int multiple, which is fine, but often it’s interesting to consider introducing variables as arg bindings. This is definitively not a hard and fast rule, just something I’ve been toying with lately. In other words, let’s replace temp with query:

import java.util.ArrayList;

public class PrimeGenerator {
  private static int[] primes;
  private static ArrayList<Integer> multiples;

  protected static int[] generate(int n) {
    primes = new int[n];
    multiples = new ArrayList<Integer>();
    primes[0] = 2;
    multiples.add(2);
    for (int i = 1, c = 3; i < primes.length; i++, c = findNextPrime(c + 2))
      primes[i] = c;
    return primes;
  }

  private static int findNextPrime(int candidate) {
    if (candidate == primes[multiples.size()]
        * primes[multiples.size()]) {
      multiples.add(candidate);
      return findNextPrime(candidate+2);
    }
    for (int i = 1; i < multiples.size(); i++) {
      multiples.set(i, ensureBigger(multiples.get(i), primes[i], candidate));
      if (candidate == multiples.get(i))
        return findNextPrime(candidate+2);
    }
    return candidate;
  }

  private static int ensureBigger(int multiple, int prime, int candidate) {
    while (multiple < candidate)
      multiple += 2 * prime;
    return multiple;
  }
}

I’m not sure about that one. It’s a matter of taste. Either way works. Since Java is such a boiler-plate-alicious language, every time we extract, the entire file gets way bigger.

Finally, let’s extract that pesky square (I’m sure a lot of you readers were aching to do so, probably the first one I’d do too), and, optionally but until Java gets tail call elimination, let’s factor those candidates into a while loop or we’ll smash the stack on huge primes. (So weird that Java still does this.)

import java.util.ArrayList;

public class PrimeGenerator {
  private static int[] primes;
  private static ArrayList<Integer> multiples;

  protected static int[] generate(int n) {
    primes = new int[n];
    multiples = new ArrayList<Integer>();
    primes[0] = 2;
    multiples.add(2);
    for (int i = 1, c = 3; i < primes.length; i++, c = findNextPrime(c + 2))
      primes[i] = c;
    return primes;
  }

  private static int findNextPrime(int candidate) {
    while (!isPrime(candidate))
      candidate += 2;
    return candidate;
  }

  private static boolean isPrime(int candidate) {
    if (candidate == square(primes[multiples.size()])) {
      multiples.add(candidate);
      return false;
    }
    for (int i = 1; i < multiples.size(); i++) {
      multiples.set(i, ensureBigger(multiples.get(i), primes[i], candidate));
      if (candidate == multiples.get(i))
        return false;
    }
    return true;
  }

  private static int square(int x) {
    return x * x;
  }

  private static int ensureBigger(int multiple, int prime, int candidate) {
    while (multiple < candidate)
      multiple += 2 * prime;
    return multiple;
  }
}

That square is a good illustration of the principle that names should be introduced as args (in this case the x) as opposed to as variables at the call site, if only because that’s usually a pretty clean slice through the code. This principle says that if you’re finding yourself making an assigmnent:

int foo = bar + baz;
foo * foo;

You should consider making that a function call instead.

frobnicate(bar + baz);

When I’m making functions this way, I usually call them “frobnicate” and similar Zork names because I have no idea what they’re gonna be. That’s how I found findNextPrime, I just extracted that core loop, called it frobnicate, read through it, realized that it finds the next prime. All about looking at where, uh, this is gonna sound so dumb… where the code wants you to make the perfect cut, where the semantics are actually interfacing each other.

Now, which version is “better”, I dunno. Maybe you think in terms of isLeastRelevantMultipleOfNextLargerPrimeFactor and that’s a meaningful semantic abstraction to you. Refactoring is about giving you the tools you need to make your own choices. And then the Inliniac mindset is to inline everything you’re only saying once, and try to find where the code tells us to extract (for example, duplication like that square) as opposed to our preconceived abstractions.

To me, I don’t see a lot of inherent value in making a

private static int functionThatReturnsTwoPlusTwo() {
  int two = 2;
  int otherTwo = 2;
  return two + otherTwo;
}

Let me rephrase and summarize this entire post, what I think is the core of it:

My philosophy is making functions that my factoring needs, and then naming them. Love it.

The opposing philosphy is to make functions out of the names you want, and then factoring the code to match. That becomes especially cart-before-horse when the function names you want describe what you think the algorithm is, as opposed to describing the problem domain. That’s not so much my jam.

To download the example code,

git clone https://idiomdrottning.org/inliniac-primes

Inliniac

define vs let