His remarks are short, so I have reproduced them here in full.

some things you just can’t test

Rubbish. Think harder.

Of course some things are very difficult to test, and in some cases the effort is not worth it when compared to the amount of risk it would mitigate - but that is a business decision rather than a purely technical one.

You can make this decision a lot easier by not putting important behaviour in things that are hard to test

But First, Some Apologies

Yes, my site was down for a few days in February. I didn’t notice it right away, and when someone at work pointed out they couldn’t get to onestepback.org I had to wait to fix it until I got home. Even then, I thought it was only down for the day. It wasn’t until I reviewed the web stats for February did I realize that it was down for at least three days.

Sorry. It turns out that the copy of apache servicing http requests had crashed and burned. The ssl server was still up so remote access to my mail was OK. I just didn’t notice that the http server was down (see, I really was busy). Nevertheless, we now have some monitoring software in place so simple crashes shouldn’t cause extended outages any more.

Directing VS Enabling

Static verses Dynamic Typing. Checked verses Unchecked Exceptions. The battle rage on (and I’ve taken part in my share of them). Martin Fowler has some keen insight into the nature of the proponents of each side of the debate. He calls it the difference between a Directing attitude and an Enabling attitude. Directors wish to make the computing environment as safe as possible and willing accept restrictions to achieve that goal. Enablers desire flexibility above (in their view unneeded) safety, and will chaffe unagainst restrictions. Read Martin’s writeup, he explains it much better than I do.

I’ve landed on both sides of the debate in the past. Lately I’ve found myself on the enabler side of the equation more often than not.

When Generic’s Aren’t

Bruce Eckel has some surprising insight on the use of generics in Java (available in Java 1.5). For those who enjoy the ad-hoc polymorphism available in C++ generics are going to be surprised by Java’s version. If Eckel is correct, then generics look like they will be great for making generic containers and little else.

See Bruce’s article for details.

And More on Latent Typing

Speaking of the Static/Dynamic typing debate, the feedback page for Eckel’s Generics article, a commenter is defends the need for interfaces with the following comment:

In java, the symantics of a method are not bound to its name, so much as they are bound to the interface the method belongs to.

Bruce responds with a followup article on Latent Typing, but I would like to add my two cents here.

Java interfaces are more about syntax than semantics. They insure that implementing classes have the proper methods defined with the proper number and type of arguments, and that the methods actually do return a value of the appropriate type. But that’s it. Interfaces do nothing to support any meaningful semantics about the methods.

If you are interested in language support for semantics, I suggest you take a look at Eiffel. When you define a interface in Eiffel (which Eiffel would call a deferred class), you not only specify the argument list for the method, you also specify the promises to which the method implementor must adhere. This set of promises (the semantics) is called a contract and leads to the concept of Design by Contract.

Even if you never program a line of Eiffel code, understanding Design by Contract is a useful skill for a developer.

Speaking of Design by Contract

And that leads us to our final posting. Artima has published a series of interviews with Bertrand Meyer, the designer of Eiffel and Design by Contract. The interviews are worth reading (here is part 4, you can find links to the other parts from there).

I find that I don’t always agree with Meyer, but when I do disagree, I think through my position very carefully.

All for Now

I’ve run out of time. Hopefully it won’t be so long before I post again.

I’ve always liked Fowlers "UML Distilled" book because it drilled down to the really important parts of UML without getting caught up in a lot of the superfluous annotations. I definitely fall into the UML-as-sketch category. Now I wonder where UML is going.

• Efficiency
• Correctness
• Maintainability
• Understandability
• Personal Expression
• Adherence to Standards
• Scalability
• Reusability
• Testability
• Portability

I’ll give our results here in a minute, but go ahead and pick your top five before reading on.

My personal picks were: Correctness, Maintainability, Understandability, Reusability and Testability.

Once everyone had picked their top five, we got together in groups of four and determine the top three items within our group of four. The top two was easy: Correctness and Maintainability. We had a tie for third place between Understandability and Reusability, and broke the tie in favor of Reusability because we felt that Understandability was intimately tied to Maintainability anyways.

Finally we surveyed the entire group and totalled the votes from each of the subgroups. Heres the results:

• 8: Correctness
• 8: Maintainability
• 3: Reusability
• 2: Efficiency
• 2: Scalability
• 1: Adherence to Standards

We see two strong winners here: Correctness and Maintainability. Every group voted for them. Beyond that, there is no clear winner. One thing I do find interesting is that Testability didn’t make the final cut in any of our groups. Even though our team is developing a strong test driven design culture, it hasn’t (yet) spread to the rest of the department. It seems we have our work cut out for us.

The scary part is that I have seen some of these in practice.

Then I remembered the C/C++ assert macro. We wrote a a series of small functions that looked something like this:

  void TestCanRun () {
      assert(   CanRun( ... ) );
      assert( ! CanRun( ... ) );
      // and so on ...
   }

I made a TestAll() function that called all my little test functions and arranged to have TestAll() called as the first thing in main(). If all the assertions worked, the program completed normally. If an assertion failed, the program would abort with an informative error message.

It worked great. I wouldn’t leave production code like that, but it was a great way to introduce Test Driven Design to someone who had not seen it before, without getting into all the nitty-gritty details of setting up a full blown test suite.

I guess my motto is that friends shouldn’t let friends program without tests.

Here are some quotes from the article

The throws clause […] requires you to either catch declared exceptions or put them in your own throws clause. To work around this requirement, people […] decorate every method with, "throws Exception." That just completely defeats the feature, and you just made the programmer write more gobbledy gunk. […]

Yep, that’s me. I use throws Exception a lot.

Anders goes on to comment that the focus is not generally on handling exceptions, but making your code robust in the presence of thrown exceptions. And that generally means finally blocks. He observers that …

In a well-written application there’s a ratio of ten to one, in my opinion, of try finally to try catch.

Interesting. I wonder how much duplication occurs in all those finally blocks. That’s why I like Ruby’s ability to abstract the finally (ensure in Ruby) to one location.

Finally, here’s where I got the title for this blog entry.

I can’t tell you how many times I’ve seen this — they say, "try, da da da da da, catch curly curly." They think, "Oh I’ll come back and deal with these empty catch clauses later," and then of course they never do.

I"m not guilty of the catch curly curly syndrome, but I’m not surprised that its a common problem. Bruce Eckel says it best when he calls Java’s checked exceptions a failed experiment.

Recap

Pragmatic Dave is up to Kata number twelve, and I’m still writing about KataTwo. I have a feeling that I’m not going to catch up any time soon.

If you recall from earlier Kata writeups (see KataTwoCps and KataTwoNoTail for details), a continuation is merely the bit of code that needs to be executed after a method returns. We can manually capture continuations as Proc objects and explicitly pass them around.

A simple example is appropriate at this point. In the following factorial function, the result of the fact(n-1) call must be multiplied by n before returning a result. That multiplication is the continuation of the fact(n-1) call.

  def fact(n)
    if n == 0
      1
    else
      n * fact(n-1)
    end
  end

We can manually capture the continuation in a proc …

  proc { |res| n * res }

Once captured, we can pass the continuation code around. In particular, we can pass it to the fact(n-1) call and let it handle its own continuation (where done is the name of the continuation passed into us) …

    fact(n-1, proc{|res| done.call(n * res) })

Rewriting our factorial function to handle its own continuation yields code like this …

  def fact_cps(n, done)
    if n == 0
      done.call(1)
    else
      fact_cps(n-1, proc {|res| done.call(res * n) })
    end
  end

Call with Current Continuation

Our "simulated" continuations are just procs (i.e. anonymous functions). They don’t really cause the function to return when called, they only calculate the return value. We must still arrange for that return value to be properly returned up the calling chain.

Wouldn’t it be nice if we could "grab" the real continuation of the current function. It would act just like our simulated continuations, but when called, it will really cause the function to return immediately.

If we had a mechanism to "grab" that current continuation, we could write a method that looked like this …

  def call_with_current_continuation
    current_continuation = #{magic to get the current continuation}
    yield(current_continuation)
  end

call_with_current_continuation yields to a block, passing in the continuation for itself. If the block ever calls current_continuation, it will immediately return from call_with_current_continuation.

If we could actually write call_with_current_continuation, then code like this is possible.

  call_with_current_continuation { |current_continuation|
    puts "This will be printed"
    current_continuation.call            # [A]
    puts "This will never get printed"
  }
  # Line [A] returns to HERE

Calling current_continuation will cause the program to go to the continuation immediately. The output will look like this …

  This will be printed

and the second puts will never be executed.

Enter Call/CC

Although we don’t have any magic code that will return the current continuation of an arbitrary method, Ruby does provide the functionality of call_with_current_continuation in the form of the callcc method. The continuation is passed to a block, and within the block we can do anything we want to with the continuation. Calling it will immediately cause the callcc call that created the continuation to return the value given to the continuation.

A Simple Example

Here is a fairly pedestrian use of callcc. This use of callcc is similar to the setjump/longjump functions in the C libarary.

  def level3(cont)
    cont.call("RETURN THIS")
  end

  def level2(cont)
    level3(cont)
    return "NEVER RETURNED"
  end

  def top_level_function
    callcc { |cc|
      level2(cc)
    }
  end

  answer = top_level_function
  puts answer        # => "RETURN THIS"

Here we are using continuations to immediately return a value from top_level, even though we are nested 3 levels deep in method calls.

Although callcc can be used to create some really mind-bending control structures, we will stick to using it to return to a point of execution higher up in the call stack in the following examples.

Variation #6: Eliminating Tail Recursion

Starting with recursive CPS version (from KataTwoCps), we replace the proc based continuations with the continuations from callcc. There is only minor differences between the proc based and callcc based versions.

Code

  # Setup the call with the top level continuations.  Notice that we
  # create two continuations in this function.  The outer-most one
  # (+ret+) is the normal return.  The inner continuation (+failed+)
  # is designed to indicate failure by returning a -1 from the top
  # level function

  def chop_with_cc(target, list)
    callcc { |ret|
      callcc { |failed|
        sub_chop_with_cc(target, list, ret, failed)
      }
      -1
    }
  end

  # Recursive helper function with continuations explicitly passed in.

  def sub_chop_with_cc(target, list, found, not_found)
    if list.size <= 1
      (list[0] == target) ? found.call(0) : not_found.call
    else
      mid = list.size/2
      if list[mid] > target
        sub_chop_with_cc(
          target,
          list[0...mid],
          found,
          not_found)
      else
        found.call(
          mid + callcc { |cc|
            sub_chop_with_cc(
              target,
              list[mid..-1],
              cc,
              not_found)
          } )
      end
    end
  end

  class TestChopContinuations < Test::Unit::TestCase
    alias chop chop_with_cc
    include ChopTests
  end

Mixing callcc and proc Based Continuations

One final twist before we are done. In KataTwoCps we wrote sub_chop_recursive_with_cps in a continuation passing style, but using proc based continuations. What would happed if we passed real callcc based continuations to a function expecting proc based ones?

It turns out that it works perfectly. Here’s the test code for it …

  def chop_with_cc_and_cps(target, list)
    callcc { |ret|
      callcc { |failed|
        # This function is defined in KataTwoCps
        sub_chop_recursive_with_cps(target, list, ret, failed)
      }
      -1
    }
  end

  class TestChopContinuations2 < Test::Unit::TestCase
    alias chop chop_with_cc_and_cps
    include ChopTests
  end

Next Time

Only one more variation to go, and this time it has nothing to do with continuations.

Previous Katas

• KataTwoVariation1
• KataTwoRecursive
• KataTwoCps

In KataTwoCps we talked about passing continuations into functions. It turns out that continuations were just functions (we used Proc objects) that encapsulated the rest of the calculation to be performed. Using continuations allowed us to turn normal recursive calls into tail recursion.

Variation #5: Eliminating Tail Recursion

One of the benefits of tail recursion is that it is easy to turn a tail recursive function into an iterative function. Lets try that transform on our CPS version from KataTwoCps.

Tail recursive calls can be transformed into gotos to the beginning of the function. Any parameters passed to the call are assigned to the existing parameters.

So, the following call …

  sub_chop_cps(target, list[0...mid], found, not_found)

would be rewritten as …

  target = target
  list = list[0...mid]
  found = found
  not_found = not_found
  goto BEGINNING_OF_FUNCTION

We can drop the redundant assignments (e.g. target = target). We will also cleverly use an infinite while loop instead of an explicit goto. (Ruby doesn’t have raw gotos, but if you are patient, I’ll show you how to implement gotos).

First Attempt

Here’s our first attempt at tail recursion removal.

  def chop_tail_recursive(target, list)
    sub_chop_tail_recursive(target, list, proc{|x| x}, proc{-1})
  end

  def sub_chop_tail_recursive(target, list, found, not_found)
    while (true)
      if list.size <= 1
        return (list[0] == target) ? found.call(0) : not_found.call
      else
        mid = list.size/2
        if list[mid] > target
          list = list[0...mid]
        else
          list = list[mid..-1]
          found = proc{|x| found.call(x+mid)}      # PROBLEM
        end
      end
    end
  end

Unfortunately, this code fails the unit tests.

At the line marked PROBLEM we create a Proc object that references found. The intent of this line is that sometime in the future this proc will be called and the current value of found will be used. Unfortunately, we immediately clobber the value of found, sabotaging that future call. (The mid value has a similar problem).

To fix this, we need to create a new context where the value represented by found (and mid) is not lost. If we replace the PROBLEM line with the following, our problems are solved.

  found = proc {|ret, m| proc{|x| ret.call(x+m)} }.call(found, mid)

Here we create our Proc object referencing ret and m instead of found and mid. Both ret and m are created in the scope of an enclosing block and initialized with the values of found and mid. The key is that ret and m are never reassigned, therefore they never become invalid.

Second Attempt

Our second attempt changes the PROBLEM line and works much better. Here is the complete source code.

  def chop_tail_recursive(target, list)
    sub_chop_tail_recursive(target, list, proc{|x| x}, proc{-1})
  end

  def sub_chop_tail_recursive(target, list, found, not_found)
    while (true)
      if list.size <= 1
        return (list[0] == target) ? found.call(0) : not_found.call
      else
        mid = list.size/2
        if list[mid] > target
          list = list[0...mid]
        else
          list = list[mid..-1]
          found = proc {|ret, m| proc{|x| ret.call(x+m)} }.call(found, mid)
        end
      end
    end
  end

  class TestChopTailRecursive < Test::Unit::TestCase
    alias chop chop_tail_recursive
    include ChopTests
  end

Problems Encountered

No problems were encounter other than the already discussed issue regarding the reassignment of found and mid.

References

Dan Sugalski is also talking about Continuations, CPS, TailRecursion, and more. Dan is writing the byte code engine that will eventually power Perl 6 (and perhaps Ruby and Python as well). Dan’s viewpoint is a bit more oriented toward implementation issues surrounding tail recursion and continuations, but make a nice balance to what you read here.

Next Time

We still haven’t talked about callcc. I promise we will get to it next time.