Let me see

When I saw this post by Matteo Vaccari about code that should speak, I immediately though about a similar situation I experienced while trying to design an algorithm for dichotomic search.

Here’s the problem: imagine you are in a Desktop Publishing software environment, dealing with pages containing images, graphical elements and frames containing text. You just built a frame with default width and height and wrote some text in it. Now you would like to shrink it vertically, by moving the bottom side upwards, until the size is just right for the text contained within. Like this:

We can ask the frame whether its content is overflowing via method isOverflowing() and, in case it’s not, we can tell it to change its current height via method setHeight(newValue).

One simple way to solve the problem is to progressively decrease the height by a fixed small amount (say 0.1 mm) each time testing for overflow until we finally reach the right size. The “right size” is an approximation of course, but we’re ok with that.

Dichotomic search (and specifically in this case, Binary search) is a more efficient algorithm to solve the same problem: instead of decreasing the height always by the same small amount, we first try to adjust it in large steps and then progressively decrease the amount of change in the tested height until we get near the right size within the desired approximation. A pascal implementation of this algorithm has been given by Niklaus Wirth in 1975, in the context of finding a value in a sorted array:

  i := 1;
  j := N;
  repeat
    k := (i + j) div 2;
    if x > A[k] then
      i := k + 1
    else
      j := k - 1;
  until (A[k] = x) or (i > j);

This is a python implementation of the same algorithm for the problem of fitting a frame:

def fitFrame1(frame, initialHeight, precision):
    top = 0
    bottom = float(initialHeight)
    while bottom - top > precision:
        middle = (top + bottom) / 2.
        frame.setHeight(middle)
        middleIsTooSmall = frame.isOverflowing()
        if middleIsTooSmall:
            top = middle
            # Put it back to not overflowing state
            frame.setHeight(bottom)
        else:
            bottom = middle

We have noticed that in the past we’ve been re-implementing slight variations of this algorithm several times, and we have at least 3 versions in our code base right now, all being used. I guess one reason are corner cases: depending on the context, you may have to deal with frames with no text, frames that start off in overflowing state right from the beginning, in which case you may or may not want to try and enlarge it, and other factors. Every time there is a slightly different need and you are tempted to write the algorithm from scratch. After all, the concept is pretty simple to grasp conceptually. Maybe even simpler than actually understanding the code, expecially when corner cases are handled (not this example).

If we could make the code so speaking that understanding is made trivial, maybe we would stop rewriting the algorithm, thus saving time and brain power. We might even get some code that can actually be extended to handle further corner cases, where each extending implementation would have a natural place to go.

This is what we ended up with (note: the code was slightly different in the original version of this post. Thank you Raffaele Salmaso for pointing out that using @propery is more pythonic):

def fitFrame2(frame, initialHeight, precision):
    tester = FrameOverflowTester(frame)
    rangeSplitter = HalfRangeSplitter(tester)
    range = Range(0, initialHeight)
    while range.size > precision:
        range = rangeSplitter.split(range)

class FrameOverflowTester(object):
    def __init__(self, frame):
        self._frame = frame
        self._currentHeight = None

    def isTooSmall(self, newHeight):
        self._frame.setHeight(newHeight)
        tooSmall = self._frame.isOverflowing()
        if tooSmall:
            # Put it back to not overflowing state
            self._frame.setHeight(self._currentHeight)
        else:
            self._currentHeight = newHeight
        return tooSmall

class Range(object):
    def __init__(self, top, bottom):
        self.top = float(top)
        self.bottom = float(bottom)

    @property
    def size(self):
        return self.bottom - self.top

    @property
    def middle(self):
        return (self.top + self.bottom) / 2.

class HalfRangeSplitter(object):
    def __init__(self, valueTester):
        self._valueTester = valueTester

    def split(self, range):
        if self._valueTester.isTooSmall(range.middle):
            return Range(range.middle, range.bottom)
        else:
            return Range(range.top, range.middle)

This code is much longer that the first, true. But it introduces three objects: Range, FrameOverflowTester and HalfRangeSplitter. Each of them represents a concept that belongs to the domain of our problem, and uses a terminology that quickly recalls the steps of the algorithmic solution. The core of the algorithm is coded in lines 4-6 and does not read very differently than how we would describe it in natural language. The same consideration holds for the intelligent part of the algorithm, i.e. choosing the right subrange, coded in lines 40-44. The only tricky part of the technical solution to our problem, the one that makes it different from the classic version described by Wirth, is the fact that once a height has been tested, if the frame is overflowing, it needs to be put back to a not-overflowing state, otherwise the machinery stops working. I’m glad to see that this code ended up conveniently isolated inside a method called isTooSmall(), of the FrameOverflowTester object.

So, all in all, I think that this new implementation speaks a lot better than the first and is much more open to extension, while still being closed to modification (see the Open/closed principle on Wikipedia and in this paper).

If you want to see the whole code, here it is: dicho.zip

I’m pretty sure there are much better implementations (please post a comment if you have one), but I just wanted to reinforce the point made by Matteo: the code should speak the model language.

How did we get this design? Well, we stood up in front of a whiteboard trying to reason abstractly about our previous implementations, until we realized what I think was the key insight: we needed a Range object. Given that, we considered what actions needed to be taken on this object, and tried to assign their responsibility to the most proper objects. This way the HalfRangeSplitter was born. Soon after was the turn of FrameOverflowTester, needed for completing the algorithm.

Dear reader, I hope you liked this analysis. I thought the example was simple enough to blog about it.