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.

elastiC. Quite an interesting language; Pythonic in many ways. At first glance, it seems to combine some good stuff from Python, Perl, Smalltalk, Lisp and C. …

Ok, sounds interesting. I always enjoy new languages. So I clicked over for a quick look at the elastiC site. With the exception of C-Like syntax and small footprint, the list of languages features were very reminiscent of Ruby. I did a quick scan of the language docs and it reminded me a lot of Objective-C, but I didn’t see anything to hold my interest.

As I return to Hans’ blog entry, I noticed his next sentence …

… Yet (again at first glance) it doesn’t seem as kludgy as Ruby.

What!? Ruby? Kludgy? Certainly not!

And yet, Hans seems to think so. Perhaps Hans has given Ruby the same quick once over that I just gave elastiC and didn’t see the unifying principles behind Ruby. If so, I can forgive him the slight.

And then again, maybe Hans just has different tastes in programming languages. After all, my daughter professes that GoldStar Chili is the best in the world, while I maintain that Skyline Chili has no peer — and we are able to live in the same house.

It sounds like Hans is a Gold Star type of guy.

That’s OK, because I going to continue eating at Skyline.

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.

A Word on Organization

The Saturday writeup mentioned a mixup with Hotel venues before the conference and may have left an impression that the conference was unorganized. Quite the contrary. Everything was very well put together. Seminars started on time, ended (more or less) on time, and the break times always had cookies available. As far as I could tell, Jay Zimmerman ran the whole show with the help of one assistant, and did a very fine job. I was very impressed with the little touches. For example, the binders everyone got when they registered was personalized with their name on the front cover, and the summary of the conference schedule on the back.

You should also see ChadFowler's comments on the conference.

Building a Data Persistence Tier — Leveraging Object Relational Bridge (OJB) (John Carnell)

Sunday morning started out with a double session on the OJB Object/Relational mapping tool. OJB uses an XML mapping file to define the relationships between the object model and the relational database. I see the value in the O/R mapping, but it seems to me that the mapping file can be quite complex, and that worries me to some degree. XDoclet can probably help here, but then that’s yet another tool in the mix. (update: Ryan tells me he has download OJB and started looking at the tutorials and was very impressed with them).

John started out the session with an example of code that had a subtle JDBC bug. The code forget to close a prepared statement and the program would receive an "open cursor" error under heavy load. At the break, I couldn’t resist pointing out to John over the break that Dave’s Ruby talk showed how to address that problem in Ruby so it can’t happen by accident.

• Cool Quote: Beware of refactoring through search and replace.

Lunch Time Quiz (Jay Zimmerman)

After lunch time, we played a little question and answer time with Jay giving prizes. Our table got a J2EE question, but unfortunately we had no J2EE experts sitting with us and we were clueless. Jay was nice enough to give us a second chance with a simpler question on ant. This time we got it right and won a pen.

The next game one where we guessed a phrase that was presented in a Wheel of Fortune style format. We tried to answer as Jay slowly filled in the letters. I actually won a Compuware polo shirt in this game. Great fun.

Applied Ant (Erik Hatcher)

I missed Erik’s intro to Ant, but did catch the follow on session. This talk mainly presented a bunch of different targets and goals that ant was capabile of handling (some with additional jar files).

Some things I came away with …

• I really dislike reading XML, and especially dislike having to manually maintain XML files.
• I use a small Ruby script called rake to do a lot of my builds. Although rake is not nearly as mature as ant, it is interesting to compare the design choices. Needless to say, rake does not use XML as input (rakefiles contain normal Ruby code).
• Ant has a lot of really cool build targets that are well suited for Java development. It would be worth my time to study these (for rake enhancements).
• Someone said that the native C/C++ compilation in ant is very nicely done. Ok, here’s another thing to look at in ant.

Agile Practices for Code Reuse (Maciej Zaawadzki)

Its getting late and I must confess that my information overload meter was in the red for the past two sessions. I only heard about half of what Maciej had to say. He has some good ideas in this area. I especially like his idea for a code station, a binary artifact repository. It sounds a bit like source control applied at a binary file (e.g. jar file) level.

The Conference Closes

Somehow for me, the end of a conference is rather anti-climatic. The last session is over and everyone just … walks out the door. It is a bit of a let down. But by Sunday afternoon, everyone was dead tired, and I know a couple folk left before the start of the final session.

Was the weekend worthwhile? Absolutely. Few technical conferences ever make it to Cincinnati, so I applaud Jay Zimmerman (the conference organizer) for bringing his road show to the "heartland". It really makes this kind of training more available to your average programmer. If a NoFluffJustStuff conference comes to a city near you, I strongly recommend that you grab everyone in your development organization and take advantage of the situation.

A Flash-Back to the Week Before the Conference

A week before the conference started, someone at work noticed that the nofluffjuststuff.com site gave directions to the Marriott Northeast facility, but the map on the web page was Marriott North site. I volunteered to call around to see what the story was.

I first called the Marriott Northeast. Once I got the sales department, the conversation went something like this …

Ok, so its not at Marriott Northeast. I call the Marriott North and asked the same question to their sales department. I got much the same response, but nothing was registered under the "No Fluff, Just Stuff" name. After they got done laughing over the name, we finally thought to look it up under Jay Zimmerman’s name. Finally, it turns up under the "Complete Programmers Network".

Ok, now I’m thoroughly confused, but I have a new name to check out. Calling back to the Marriott Northeast …

Fine. Mystery solved. It turns out the both Marriotts are north of the city, both on major highways, and both off exit 19 on those highways. Add in the fact that their names are so similar and so they are confused a lot.

Time to get back to the conference.

Decoupling Patterns (Dave Thomas)

The first seminar starts promptly at 9:00 with Dave Thomas talking about the problems with coupled code and how to write the code to reduce that coupling.

Of course, you can’t get rid of all coupling. Dave quoted Noel Coward: "Familiarity breeds contempt, but without a little familiarity it’s impossible to breed anything."

Another quote that caught my eye: "Decoupling code is like organizing spy cells … if one is broken, the other cells are safe."

Dave used the example of mixing a pina colada to demonstrate temporal coupling amoung steps of an algorithm. He suggested using the mediator pattern with a state machines to decouple parallel tasks. I’ve not seen that in action (note to self, check that out).

Ruby for Java Programmers (Dave Thomas)

Ok, I went to the Ruby talk just for fun. I didn’t expect to pick up much about Ruby (I’ve been using it for 3 1/2 years), but really to pick up on Dave’s presentation technique. How do you persuade a Java programmer that a dynamically typed, object oriented scripting language could might be a viable alternative for certain jobs? Dave’s approach was real world examples where Ruby’s simplicity shines.

Panel Discussion

Jay welcomed everyone to the panel discussion and laid down the rules (i.e. there are no rules). He then asked the panel to introduce themselves.

The quesions and responses are highly edited and paraphrased. I can’t type fast enough to capture the entire conversation, so I tried to capture the ideas as best I could. If I made an substantial errors, let me know so they can be corrected.

The panel consisted of …

Venkat Subramaniam (V), Bruce Tate (B), Dave Thomas (D), John Carnell (J), Erik Hatcher (E), Stuart Halloway (S), Maciej Zawadzki (M).

Jay asked each panel member to give a brief introduction to themselves.

Then the questions started.

Naked Objects (Dave Thomas)

In Dave’s final talk of the day, he demonstrated a system called "Naked Objects". The idea behind Naked Objects to present the business objects to the end user in a way they can be directly manipulated with little structure imposed by the user interface. As developers, all we do is program the objects and the natural interface is automatically generated. This techniques puts a lot of trust in the users, and is directly opposed to the idea of dumbing down the user interface to prevent the user from making mistakes. All in all, a fascinating idea. I’ve already downloaded the Naked Objects package and have tried it out. (See www.nakedobjects.org/ … some firewalls may complain :-)

Intro to XDoclet (Erik Hatcher)

I attended Erik Hatcher’s seminar on XDoclet as the last session of the day. XDoclet simplifies J2EE development by using Javadoc tags to control the generation of all the sundry files need for a full bore J2EE environment. My J2EE experience is quite low, but XDoclet seems to be a simple tool for solving a complex problem.

That wraps up Saturday. We’ll talk about Sunday next time.

Registration started at 12:00 noon on Friday (July 11) at the Mariott Northeast. I got there plenty early and had plenty of time to go through the material before the actual conference started.

Compuware sponsership was very prominent (full disclosure: I am a consultant for Compuware, although that affiliation had little to do with my attendance). Everyone got a cool pen (the kind that lights up!) with a Compuware logo. Our notebook with the seminar schedule included a whitepaper on MDA development by Tom Blankers (Compuware’s OptimalJ Product Manager). And who could miss that huge Compuware/OptimalJ banner that was hung behind the speaker in the main room.

At 1:00 Jay Zimmerman, the conference organizer, gave a short welcome talk and the conference was started.

Java Persistence Frameworks (Bruce Tate)

The Cincinnati symposium had three tracks going at once. The topics I wanted to hit were Java persistence and J2EE issues, so the first talk by Bruce Tate was right on target.

I’m not going to record all the details of each presentation, but rather record my overall impressions and capture some thoughts.

I’m relatively new to Java persistence beyond the basic JDBC stuff, so there was lots of good information here. Bruce tends to favor JDO over EJB persistence. How JDO uses byte code enhancements to get the necessary persistence hooks is interesting. There was some discussion of how AOP might mitigate the need for byte code enhancement in the future.

Break

I was reviewing the conference schedule on Thursday night, and my teenage daughter was helping me choose topics (well, at least she was giving me her opinions). She told me to make sure I attended the breaks because they were likely to have snacks.

Bitter EJB (Bruce Tate)

Bruce’s next talk based on his latest book Bitter EJB. Basically, Bitter Java/EJB concentrats on identifying systemic failures, i.e. Antipatterns.

Some good quotes and other stuff that stuck in my head:

• "Good guitar players know what notes to play. Great guitar players know what notes not to play. The same is true for programmers and code."
• Use a Wiki for group communication.
• "Every 10 or 15 years the industry will come up with a new framework."
• "EJB is ripe for AntiPatterns"
• Bruce compared EJBs to Tolkien’s ring of power.
• Beware of the Design by Resume pattern

Agile Software Development (Dave Thomas)

Dave was one of the original signers of the Agile Manifesto. He shared his insights of what the manifesto means and gave an overview of the different agile methodologies.

Here’s a quote that I like:

"Without excellent personnel, even good to excellent processes can only achieve marginal results." — Capers Jones, Software Assessments, Benmarks, and Best Practices, Addison-Wesly, 2000.

There was an added bonus at Dave’s talk. Chad Fowler, a fellow rubyist, was there. Chad had recently returned from a 1 1/2 year stint in India so it was great to catch up with him.

Dinner

Keynote: Intro to Pragmatic Programming (Dave Thomas)

Dave gave his views on the state of the software industry and some things we need to do to address the issues. Here are some frightening statistics…

• Almost 60 Billion dollars per year are wasted due to buggy software
• That’s about $20,000 per developer! (I’m glad they don’t want it back).
• The defect rate per 1000 lines of code has remained relatively constant over the past 20 years.

Dave shared his "pragmatic principles" for becoming a great software developer. If you haven’t read The Pragmatic Programmer, then immediately go out get a copy to read.

After Hours

After the keynote talk, several of us wondered over to the hotel restaurant for drinks and talk. Over the course of the evening Dave Thomas, John Carnell, and Stuart Halloway stopped by for conversation. Topics covered many areas, including

• The state of Microsoft (Dave and Stuart predicted that Microsoft would be a major open source vender in 5 years)
• Books, both technical and non-technical
• The heavy infiltration of Mac laptops at recent conferences (in particular OSSCON). It seems that Mac has become the machine of choice alpha geeks.

At one point we were discussing technical interviews. I shared that I often asked what technical books an applicant had read in the past half year. Someone else shared that they asked what authors they have been reading; an interesting twist.

We finally broke up around 11:00. It was a long day. More on about Saturday and Sunday when I get it ready.

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.

Introduction

I wrote this article on Design by Contract and Unit Testing to go along with the EiffelUnit documentation. I'm no longer maintaining EiffelUnit (I recommend using Gobo Eiffel Test instead), but thought the article was worth publishing independently. Hence this blog entry.

The article was written three years ago, so I added a postscript to the conclusions that reflects my current experience.

Design by Contract and Unit Testing

I've been using Eiffel for almost three years, and have been exploring some Extreme Programming ideas for the past 6 months. In particular, I've been using XP's "Test-First" desgin process in conjunction with Eiffel. Here are some of my thoughts on how unit testing and Design by Contract fit together. The presentation is in the form of a question/answer session. If you have comments on this topic, I would be glad to here them at jweirich@one.net.

The first part of this page covers Design by Contract for those who are new to the idea. Eiffel programmers may want to skip directly to the section on Unit testing. Those whose time is limited may want to jump directly to the conclusions.

What is Design by Contract? Isn't it just adding assertions to your code?

In short, Design by Contract starts by specifying the conditions under which it is legal to call a method. It is the responsibility of the client software to ensure these conditions (called preconditions) are met.

Given that the preconditions are met, the method in the supplier software guarantees that certion other conditions will be true when the method returns. These are called postcondition, and are the responsibility of the supplier code in ensure.

What's the advantages of identifying contracts?

How does this work with inheritance?

Ok, seriously. Contracts are inherited by child classes. If a child class overrides a method in a parent class, it needs to make sure the method's new implementation conforms to the contract of the parent class. By conforming, we mean that the child class is not allowed to tighten the preconditions of the parent class, or is it allowed to loosen the postconditions. We remember this by using the slogan...

Require no more, promise no less.

By the way, Eiffel automatically handles preconditions and postconditions in child classes without any need to copy and paste them from the parent.

This sounds complicated. Is it really useful?

So where do the assertions come in?

Note that the checking (assertions) are merely a way of verifying that everyone is playing by the rules. We should be able to remove the assertions without effecting program correctness. In fact, Eiffel allows you to specify several different levels of assertion checking.

What is unit testing?

Eiffel has Design by Contract. Why do we need unit testing?

• Better code coverage. Unit tests provide more thorough code coverage than what a typical application would do. DbC assertions are useless if the code is never called.
• Repeatable. Unit tests are automatic and repeatable. You don't have to rely on a user manually running a program.
• Reportable. The results of the unit test are easily summarized for reporting (e.g. 2 out of 200 unit tests failed).

Ok, so if we have unit tests, why do we still need DbC?

Wait a minute! I can check preconditions in my unit test!

From a Design by Contract perspective, this is not testing preconditions. Preconditions define when it is legal to invoke a particular method. According to DbC, calling a method when its preconditions are not established results in undefined behavior. How can you test for undefined behavior?

What the unit tester has really done is changed the contract on the tested code. They replaced the existing precondition with True (the universal precondition ... methods with a precondition of True may be called at any time). They also changed the postcondition to a stronger, more complicated one.

Can you give me an example?

    push (value: INTEGER)
        require
            not is_full
        ensure
            count = old count + 1
            top = value

When you do robustness checking in a unit test, you generally transform the contract into something slightly different. This is often called "defensive programming".

    push (value: INTEGER)
        -- Note: no precondition
        ensure
            success: (not old is_full) implies
                         ((count = old count + 1) and
                          (top = value))
            failure: (old is_full) implies
                         ((count = old count) and
                          (top = old top))
            error_set: old is_full = error

In this version, we added an error flag. We could have also specified an exception should be thrown.

But isn't defensive programming good thing?

Unfortunately, that's not necessarily the case.

  -- Design by Contract version
  if not stack.is_full then
      stack.push (value)
  else
      -- handle full stack
  end

  -- Defensive Programming Version
  stack.push (value)
  if stack.error then
      -- handle full stack
  end

Defensive programming can also hide problems in the code. By ignoring bad values, bad data can propagate further in a program.

But what does this have to do with precondition checking?

By enabling contract precondition checking, we can immediately detect interface irregularities whenever they happen, whether in function tests or unit tests.

Ok, checking contract preconditions sounds useful. But what about postconditions?

Although they are checking the same kind of behavior, their focus is different. DbC postconditions are general and answer the question of how a method responds under all possible legal conditions. Unit tests focus on how a method responds under certain, specific situations specified in the test.

Because DbC postconditions are general, they are able to check every invocation of the method for the proper behavior. They can be run during unit testing, but they also are in effect during functional testing (and normal program execution, assuming they aren't disabled), checking each and every invocation of the method. In contrast, unit tests only check a limited number of specific invocations.

Because they are more general, DbC postconditions are more difficult to write. In fact, sometimes the postcondition of a method can be more complicated that the actual code of the body.

Can you give me an example of a complicated postcondition?

   resize (min_index, max_index: INTEGER)
      -- Resize to bounds `min_index' and `max_index'.
      -- Do not lose any item whose index is in both
      -- `lower..upper' and `min_index..max_index'.
   require
      valid_bounds: min_index <= max_index + 1
   ensure
      new_lower: lower = min_index
      new_upper: upper = max_index
      default_if_too_small:
         min_index < old lower implies subarray
          (min_index, max_index.min (old lower - 1)).all_default
      default_if_too_large:
         max_index > old upper implies subarray 
          (min_index.max (old upper + 1), max_index).all_default
      stable_in_intersection:
         subarray ((min_index.max (old lower)).min(old upper + 1), 
            (max_index.min (old upper)).max(old lower - 1)).same_items
               (old subarray ((min_index.max (lower)).min(upper + 1), 
               (max_index.min (upper)).max(lower - 1)))

Wow, what would the unit test code for the same thing look like?

The number of lines in the test case is actually longer that the postcondition above. But each individual test is simple and direct, and easy to verify that it is correct.

    array: ARRAY[INTEGER]

    test_same_range is
        do
            array := <<1, 2, 3>>;
            array.resize (1,3)
            assert_array (1, 3, <<1, 2, 3>>, array)
        end

    test_included_range is
        do
            array := <<1, 2, 3>>;
            array.resize (1,1)
            assert_array (1, 1, <<1>>, array)
        end

    test_big_range is
        do
            array := <<1, 2, 3>>;
            array.resize (0, 5)
            assert_array (0, 5, <<0, 1, 2, 3, 0, 0>>, array)
        end

    test_high_overlap is
        do
            array := <<1, 2, 3>>;
            array.resize (2, 5)
            assert_array (2, 5, <<2, 3, 0, 0>>, array)
        end

    test_low_overlap is
        do
            array := <<1, 2, 3>>;
            array.resize (-1, 1)
            assert_array (-1, 1, <<0, 0, 1>>, array)
        end

    test_no_overlap is
        do
            array := <<1, 2, 3>>;
            array.resize (5, 7)
            assert_array (5, 7, <<0, 0, 0>>, array)
        end

Note for non-Eiffel programmers: The form <<1, 2>> is a manifest array of two elements.

Any other postcondition examples?

I'm glad you asked. Consider the push and pop methods on a STACK. push is fairly easy to specify using DbC...

    push (value: INTEGER)
        ensure
            count = old count + 1
            top = value

But pop is more difficult.

    pop
        ensure
            count = old count - 1
            -- What is the value of `top'

What is the value of the top of the stack after pop completes? Well, it depends upon the history of pushing and popping leading up to a given call to pop. The logic required to write a postcondition specifying the value of pop

Unit tests don't suffer the same problem. Since we are only testing a specific scenario, we know what the value of the top of the stack should be.

    test_push_and_pop is
        do
            stack.push(5)
            assert_equal ("push5", 5, stack.top)
            stack.push(123)
            assert_equal ("push123", 123, stack.top)
            stack.pop
            assert_equal ("pop5", 5, stack.top)
            stack.pop
            assert ("empty", stack.is_empty)
        end

Conclusion

We see that although unit tests and Design by Contract assertions have a lot of overlap, but each has a different focus and different strong points. DbC preconditions are useful for checking inter-module correctness. Unit testing and DbC postconditions validate individual module behavior, with unit testing focusing on specific situations an DbC postconditions focusing on general behavior.

So, what does this mean in practice? I find that when I am doing Eiffel, I tend to specify preconditions along with a good set of unit tests. If the postconditions are obvious and easy to write, I will include them (mainly because postcondition are included in the short form view of a class). If the postconditions are difficult to specify in general, I might include them in comment form for the short view.

When I'm using something Java, or some other language with weaker support for Design by Contract, I definitely would use unit tests for checking individual modules. Depending on the availability of tools (e.g. some kind of assert mechanism), I would still do some level of precondition specification.

Postscript

At the time of writing the original text (sometime in 2000), I was doing a lot of DbC and Eiffel programming and had just started using XP style unit tests. Today (sometime in 2003) I am no longer writing Eiffel code and doing very little "formal" DbC. I find that I still think of interfaces in terms of contracts with pre/post conditions, but instead using Eiffel-like assertions to define the pre/post-condition assertions, I now use unit tests to drive and define the shape of the software.

Although the unit tests have a different focus than assertions (as noted in the article), I find that they are quite suitable for my needs and rarely find it necessary to supplement the coce with any additional pre/post-condition assertions.

That discussion eventually led to the creation of Rake. But it seems others seem to have similar thoughts.

James Duncan Davidson, the original ant developer, writes …

When I first chose XML as the configuration format for Ant, I figured it was a great way to replace the simple properties files that I was using before with a structure that could define hierarchical data. However, as time goes on the XML format becomes more and more burdensome to actually getting something done. […] For a long time, I’ve thought that the way to alleviate the burden for Ant would be to use some sort of scripting language to front end the Ant task object model under the covers.

Jonathon Simon is also talking about scripting ant, but using Jython access the ant object module. In an email to the ant-dev mailing list, he lays out some of his ideas. (He even mentions using JRuby.)

It will be interesting to watch where this goes. I suspect that the XML ant build script may have its days numbered.

Where Were We?

KataTwoVariation1

We explored an iterative solution using loop invariants.

KataTwoRecursive

We looked at two recursive solutions, one that passed array slices and one that passed explicit limits.

Variation #4: Continuation Passing Style

Let’s start by looking reviewing variation 2 in KataTwoRecursive. When we recurse, we need to carefully pass in the position of the subarray in the whole array so that the final result is correctly positioned in the whole array. The recursive calls looks like this …

    if list[mid] > target
      chop_recursive(target, list[0...mid], offset)
    else
      chop_recursive(target, list[mid..-1], offset+mid)
    end

Note that if we didn’t have to worry about the returning a -1 when the target value is not found, we could have written the recursive calls like this.

    if list[mid] > target
      chop_recursive(target, list[0...mid])         # [1]
    else
      chop_recursive(target, list[mid..-1]) + mid   # [2]
    end

As chop_recursive unwinds the stack, the correct offsets are added one by one until the final result correctly represents the correct value for the whole array.

Tail Recursion

There is an interesting difference between the recursive call at [1] and the recursive call at [2]. The call at [1] is tail recursive. This means that the result returned by the call at [1] is the result for the entire function. Once the call at [1] terminates, there is nothing to do but immediately return the result we just received.

A smart optimizing compiler can turn tail recursive calls into a jump to the beginning of the function (after reassigning the function parameters). In other words, tail recursion can be implemented using iteration without any stack growth.

There are a few languages where the tail recursion optimization is guaranteed by the language. Scheme is one such language. In Scheme, you never have to write a loop, the language will turn your tail recursive calls into loops automatically.

Unfortunately, the recursive call at [2] is not tail recursive. When [2] returns, it must continue to execute adding mid to result before returning. This little bit of work that must be done between the return of the call at [2], and the return of the main function call is called the continuation of [2]. It is where call [2] continues when it is done.

Continuations As Functions

Wouldn’t it be nice if we could turn the call at [2] into a tail recursive call? Then our entire function would be tail recursive and it could be implemented without stack growth.

This is actually not hard to do. Suppose we had a function that handled that little "+ mid" code for us. When we are ready to return a value, then we just need to let the contination handle any of the "adjustments" before returning the value. We could pass in the continuation function as an argument to the function and call it when we need to return.

Something like this …

  def chop_cps(target, list, continuation)
    if list.size <= 1
      (list[0] == target) ? continuation.call(0) : XXXXX
    ...

This says return the value +0+ if the list[0] matches the target value. The continuation function will apply any adjusts specified by the calling context. (The "XXXXX" represents how we handle the -1 return value. We will come back to this in a bit.)

Now we just need to create the continuations at the right points.

If we are recursing on the first half of the array (line [1] above), then there is no need to add anything. Our contination will just return the input value directly.

  chop_cps(target, list[0...mid], proc{|x| continuation.call(x) })     # [1a]

Remember, continuation is the continuation of our current function call. In other words it is the code to execute when our current fuction returns. So, in order to properly return a value, we need to call continuation, passing in our result.

If we need to adjust the returned result by adding mid (line [2] above), then the continuation we pass needs to look like this …

  chop_cps(target, list[mid..-1], proc{|x| continuation.call(x+mid) }) # [2a]

One final optimization. We notice that in [1a] we are just passing the return value without changing it. We can shorten that to just …

  chop_cps(target, list[0...mid], continuation)                        # [1b]

Ok, we are ready to write the CPS style chop function … except for one thing! We don’t know how to handle the case where the target value is not found!

Handling Errors

The spec for the chop function says that we will return a negative one whenever the target value is not found. Unfortunately, if we return a negative one, the continuations from the calling methods clobber our error return by (possibly) adding the valud of mid to it (remember [2a] above?).

What we need is an alternative continuation where no adjustment is done. No problem! Since we are just using functions for continuations, we can pass in an "error reporting" continuation to handle failure. Our error return continuation would look like this:

    proc { -1 }

Code

Here’s the code to the recursive version using CPS. Since we are passing two continuations into our recursive function, we will call the continuation for the normal return found and the continuation for the error return not_found.

  def chop_cps(target, list)
    sub_chop_cps(target, list, proc{|x| x}, proc{-1})
  end

  def sub_chop_cps(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_cps(
          target,
          list[0...mid],
          found,
          not_found)
      else
        sub_chop_cps(
          target,
          list[mid..-1],
          proc{|x| found.call(x+mid)},
          not_found)
      end
    end
  end

  class TestChopCpsRecursive < Test::Unit::TestCase
    alias chop chop_cps
    include ChopTests
  end

Problems Encountered

This implementation turned out to be surprisingly easy. No problems were encountered during the implementation.

Notes

I find the introduction of the not_found continuation very interesting. Why does the chop function return a negative one as an error value? Why doesn’t it throw an exception?

With the not_found continuation, we can decide at runtime how errors are to be reported. For example, to switch to an exception throwing version of chop, all we have to do is …

  def chop_cps(target, list)
    sub_chop_cps(
       target,
       list,
       proc{|x| x},
       proc{ fail "Value #{target} not found." })
  end

This is cool!

Where to Next?

Some of you are no doubt surprised that this entire discussion of continuations never touched on Ruby’s callcc mechanism. We will save callcc for the next session, along with two or three more variations on the CPS variation introduced here.