Ok, not really.

It is really my Father's Day gift from the kids. They say this is what I look like when playing guitar.

Maybe ... on a really bad hair day.

Actually, the guitar is nice. And who know, perhaps he will be fine at pairing after all.

Variation #2: Recursive

This is a standard recursive implementation of the algorithm we looked at in KataTwoVariation1. This version determines which half of the array contains our target value and recurses on the appropriate half of the array.

Code

Here’s the code …

  def chop_recursive(target, list, offset=0)
    if list.size <= 1
      (list[0] == target) ? offset : -1
    end
    mid = list.size/2
    if list[mid] > target
      chop_recursive(target, list[0...mid], offset)
    else
      chop_recursive(target, list[mid..-1], offset+mid)
    end
  end

  class TestChopRecursive < Test::Unit::TestCase
    alias chop chop_recursive
    include ChopTests
  end

Problems Encountered

In writing this version, I encountered the following issues …

• I had a problem where I miscalculated the array fragment to recurse on. The miscalculation led to a recursive call where the size of the array wasn’t decreased, and led to infinite recursion.
• Since a copy of the array is passed, we lose information on the position of the target value in the full array. I had to pass in the offset of the of start of the array fragment to correct for this.
• I refactored the method to return nil (instead of -1) when the target value was not found. I decided that it didn’t help improve the logic in any way, so I put the -1 return value back in.
• There was a performance bug where I searched both branches of the array (and then returned the one that matched).
• The size==1 test really bugs me. I made several (unsuccessful) attempts to get rid if it. (But see the next item)
• The original version of the recursive version started with …

    def chop_recursive(target, list, offset=0)
      return -1 if list.empty?
      return offset if list[0] == target
      return -1 if list.size == 1
      ...
  

  This version tests list[0] agains target at the entry to every recursive call. This is wrong. I should only test when the list is down to one element. This defect made it into the original posting and it wasn’t until I was reviewing the code for the CPS post that I discovered the error. It also might explain my discomfort with the list.size==1 test. It was actually the list.empty? test that was incorrect and the size check evolved to list.size <= 1.

Variation #3: Recursive with Explicit Limits

In variation 2, I decided to pass a copy of the sub-array in each recursive call. This is an expensive operation, but I was thinking that I could avoid passing around explicit limits this way. However, it turned out that I still needed to pass the offset, negating much of the advantage.

In variation 3 we will avoid makeing array copies by always passing the original array around. Instead of arrays, we will explicitly pass the hi/lo limits of the sub-array in the recursive call.

I think this version is not only more efficient than variation 2, it is also easier to read and understand.

Notice that the recursive call in this version takes 4 parameters, so I created a helper function (rchoplim) with the proper signature to do the recursion.

Code

Here’s the code …

  def chop_recursive_passing_limits(target, list)
    rchoplim(target, list, 0, list.size)
  end

  def rchoplim(target, list, lo, hi)
    if (hi-lo) <= 1
      list[lo] == target ? lo : -1
    else
      mid = (lo+hi) / 2
      if list[mid] > target
        rchoplim(target, list, lo, mid)
      else
        rchoplim(target, list, mid, hi)
      end
    end
  end

  class TestChopRecursiveWithLimits < Test::Unit::TestCase
    alias chop chop_recursive_passing_limits
    include ChopTests
  end

Problems Encountered

There were no problems encountered while implementing Variation 3. I think the simpler logic helped (plus I worked out a number of bugs in Variation 2).

Things to Come

In the next installment, we will explore a CPS (Continuation Passing Style) implementation.

Here’s my attempt at Variations on a Binary Search Theme.

Unit Tests

Dave provided a set of unit tests for the binary search function. The tests below assume that the functions name is chop, and that it takes the target value and the array to search as arguments. Chop should return the index position in the array where the target value was found.

We put the tests into a separate module that will be included in the real test classes below. This is a useful technique when you write tests you wish to reuse in several test classes.

  require 'test/unit'

  module ChopTests
    def test_chop
      assert_equal(-1, chop(3, []))
      assert_equal(-1, chop(3, [1]))
      assert_equal(0,  chop(1, [1]))

      assert_equal(0,  chop(1, [1, 3, 5]))
      assert_equal(1,  chop(3, [1, 3, 5]))
      assert_equal(2,  chop(5, [1, 3, 5]))
      assert_equal(-1, chop(0, [1, 3, 5]))
      assert_equal(-1, chop(2, [1, 3, 5]))
      assert_equal(-1, chop(4, [1, 3, 5]))
      assert_equal(-1, chop(6, [1, 3, 5]))
      assert_equal(0,  chop(1, [1, 3, 5, 7]))
      assert_equal(1,  chop(3, [1, 3, 5, 7]))
      assert_equal(2,  chop(5, [1, 3, 5, 7]))
      assert_equal(3,  chop(7, [1, 3, 5, 7]))
      assert_equal(-1, chop(0, [1, 3, 5, 7]))
      assert_equal(-1, chop(2, [1, 3, 5, 7]))
      assert_equal(-1, chop(4, [1, 3, 5, 7]))
      assert_equal(-1, chop(6, [1, 3, 5, 7]))
      assert_equal(-1, chop(8, [1, 3, 5, 7]))
    end
  end

Variation #1: Iterative with Loop Invariants

I first read about using loop invariants on a binary search algorithm, so I thought it would be a good variation to start with.

If you have not used loop invariants in the past, they are a useful technique for understanding loops. You specify an condition that is true for every single iteration of the loop. This condition is called the loop invariant.

For the binary search, I used the following invariant.

Where lo and hi are indices into the array and result is the location in the array where our target value lies (i.e. the result of the binary search function). All this invariant states is that the final result index will be between position lo and hi. (Note that I’m assuming that the target value is in the array. We will deal with that assumption later).

The invariant must be true when we start the loop, but that is easy to handle. Just set lo to zero (the result index must be greater than or equal to zero), and set hi to one more than the largest index value (list.size works for this).

The second piece you need is a loop termination condition. Each time through the loop we will adjust hi and lo so that they move closer together (without violating the loop invariant). When the difference between the hi and lo values is 1, we can exit the loop.

Here is the termination condition.

When the loop exits, the condition TERM will be true. And the invariant INV will also be true (because it is true for every iteration). If TERM and INV are both true, then that implies that result must be equal to lo! Or in other words, when the loop exits, our search target value must be in the array indexed by lo (if it is in the array at all).

Using the above invariant and termination conditions, we can be certain that our loop will be correct (as long as they are faithfully implemented, which is not a minor problem).

Code

Here’s the code. Notice that INV will be true the first time we enter the loop. Inside the loop, we calculate the midpoint of the lo/hi indices, and compare the value at the midpoint to our target value.

If the value at the midpoint is larger than our target, then the range (lo..mid) still satisfies the invariant and we can adjust hi down to mid. Otherwise we can be sure that the range (mid..hi) satisfies the invariant, and we adjust lo up to the value of mid.

The "list[lo] == target" test at the end checks our assumption that the target value was in the array. If we found the value, we return the lo value. Otherwise we return -1.

  def chop_iterate(target, list)
    lo = 0
    hi = list.size
    while (hi-lo) > 1
      mid = (hi+lo) / 2
      if list[mid] > target
        hi = mid
      else
        lo = mid
      end
    end
    list[lo] == target ? lo : -1
  end

  class TestChopIterative < Test::Unit::TestCase
    alias chop chop_iterate
    include ChopTests
  end

Problems Encountered

So, did all that work figuring out a loop invariant help us? Perhaps. I did have one bug where a typo slipped into the calculation of the midpoint. I typed "(hi-lo)/2" by accident and had to scratch my head for a few minutes.

After fixing the typo, the rest of the algorithm worked without a hitch.

Where’s the Invariant?

An interesting thing happened to our invariant and termination conditions. The termination condition was inverted to "(hi-lo) > 1" instead of the "(hi-lo) <= 1" we originally used. That’s because the while statement expects a "stay-in-the-loop" test instead of a "get-out-of-the-loop-test".

But more importantly, our loop invariant has disappeared! It has no representation in the source code at all, except as an implicit constraint on the loop values. This is unfortunate because some important information is lost that should have been communicated to the reader.

The loop construct in the Eiffel language allows you to directly specify the loop invariants. The same loop in Eiffel would look something like this …

           from
               lo := list.lower
               hi := list.upper + 1
           invariant
               lower_limit: -- lo <= Result
               upper_limit: -- hi <  Result
           variant
               hi - lo
           until
               (hi-lo) <= 1
           loop
               mid := (hi+lo) // 2
               if list.at(mid) > target then
                   hi := mid
               else
                   lo := target
               end
           end

Although rather verbose, notice how every part of the loop has its proper place. The termination condition is expressed as an "until" condition, therefore it isn’t inverted.

The invariants are expressed directly. It turns out that our invariants cannot be checked at runtime (since we don’t know the actual value of Result until after the loop terminates), so we expressed them as comments. However, if they were executable, Eiffel would check them at runtime for us.

The "variant" section is interesting. The variant is an non-negative integer expression that must be smaller each time through the loop. Providing a valid variant proves that your loop eventually terminates.

Even the initialization of the loop variables (hi and lo) have their own section.

Next Time …

I was going to write up all 9 variations at once, but this is long enough now for a posting. I’ll hit the two recursive variations in the next installment.

For example, the other night I was testing some CGI code. To display a page of HTML, my object under test calls a print_template method on an object in the CGI framework I am using. It needs to pass in the template name and a hash table of template values to be substituted in the template. The test code might look something like this …

    def test_error_page
      web = CGI::Template.new        # Object from the CGI framework
      page = ErrorPage.new(web)
      page.error_message = "Oops!"
      page.render
      # test that "Oops!" was properly passed to the template object.
    end

The last line of the test wants to validate that the error message was properly passed to the web template. We could check this by parsing the HTML output from the CGI::Template, but that is a lot of work (not to mention error prone as well).

A much better way is to directly test that the parameters are passed to the CGI framework object correctly. We do that by replacing the CGI framework object with out own mock object.

Something like this (lines numbered for reference)…

  01:  def test_error_page
  02:    FlexMock.use { |web|
  03:      web.mock_handle(:print_template, 1) { |template_name, hash|
  04:        assert_equal 'Oops!', hash['error_message']
  05:      }
  06:      page = ErrorPage.new(web)
  07:      page.error_message = "Oops!"
  08:      page.render
  09:    }
  10:  end

In line 2, the FlexMock.use method creates a mock object and passes it to the given block. At the end of the block (line 9), FlexMock.use will verify that all expected calls were actually made to the mock object.

In line 3, we inform the mock web object what methods calls it should expect by passing the name of the expected method to mock_handle. Since we are only interested in the print_template call, that is all we define. The number 1 in the calling sequence tells our mock object to expect exactly one call.

The mock_handle method also gets a block (still on line 3). This block is executed whenever print_template is called in our test. The block object parameters (template_name and hash in this case) should match the parameters of the print_template method.

It is the hash argument to print_template that hold our interest. We need to make sure that the hash table passed to the template engine correctly defines our error message as "Oops!". We verify this in line 4.

The rest of the test method just creates an ErrorPage and feeds it the mock object primed for testing. In line 8 we invoke the render method that should eventually format our page and call the print_template method of the mock object.

By using the mock object, we avoid a lot of setup details that would be required for a real CGI framework object (which in turn might require more objects with more setup). Using a mock object allows us to concentrate on the details of what is being tested without constructing an elaborate framework of live objects merely to support a quick test.

On the other hand, be careful. It is easy to get carried away with mocking to the point where it is more work to create a web of mock objects than it is to just create a network of live objects in the first place. When you start creating mock object that return other mock objects, you should take one step back and reassess your code base.

There are other Mock objects implementations. The original ruby-mock object is a bit rigid for my tastes. You need to know exactly what methods are called and in what order, and that over constrains the solution to your test. The test-unit-mock object is much more flexible than ruby-mock (or even FlexMock), it is just complicated enough that I forget how to use it between the times I need it. FlexMock seems to fit in that middle of the position where, for me, it does what I need without extra stuff.

You can find FlexMock at onestepback.org/software/flexmock.

New features include …

Updated Software Packages …

Rake (onestepback.org/software/rake)

A Make-like scripting language written entirely in Ruby. I have been using Rake for all my recent projects.

Source2Html (onestepback.org/software/source2html)

Convert source files to nicely formatted HTML pages. Source2html will automatically create links between files in a project. Works with Ruby, Python, Java, Eiffel and a number of other languages.

Updated Articles …

Same Fringe, Iterating Parallel Lists in Ruby (onestepback.org/articles/same_fringe)

A short article on parallel lists and iterating schemes in Ruby. We touch on generators and continuations.

I can identify with that. I’ve downloaded most of my brain into Emacs macros so that I find it difficult to survive without a fully functional Emacs available. However, when it comes to editting Java code, it is tough to beat Eclipse (or IntelliJ/IDEA, or any number of similar IDEs). Although I still like Emacs for pure code/text entry, Eclipse really shines when you need to do browsing, refactoring or even CVS integration.

This is one gotcha, however. Whenever I save a file in Emacs, I hit

• Control-A (goto the beginning of the line), then
• Control-X Control-S (save a file).

Over the years I have learned that frequent saving is a good thing, and I perform that sequence of keystrokes without even thinking.

However, that same key combination in Eclipse performs …

• Control-A (select all)
• Control-X (cut selection)
• Control-S (save file)

Oops! Thankfully, Control-Z (undo) forgives all sins.

Using the standard shapes example, I posted some code in C showing how to do runtime polymorphism using pointers to functions. I also include C++ and Java examples. Then everybody got in the act and we ended up with this (onestepback.org/articles/poly).

Some of the source files are missing, and I’ll replace them when I can. In the meantime, enjoy.

Feel free to provide feedback at jweirich@one.net.