However, one thing I have noticed is that Rubyists and Pythonistas bring different assumptions to the table. What is intuitive to one group seems ad hoc and downright weird to the other.

Here’s one example that I noticed.

In Python, the construct "x.y" means lookup the name "y" in the dictionary of "x". (Ok, that’s simplified, but you get the picture). The result of that lookup may be a value (instance data), or may be a function that can be called (member functions). In other words, "." is basically a lookup operation.

In Ruby, the construct "x.y" means send a message named "y" to the object represented by "x". All operations on an object must be done through the sending of a message.

This leads to all kinds of non-intuitive behavior if you are expecting the wrong thing. For example, one Pythonista commenting on the fact that "x.y" and "x.y()" are equivalent asks the question: "How do you get access to the y function inside x?".

A Rubyist’s response to the question is "Huh?". You see, there are no "functions" in Ruby. At least not in the way the question assumes. Ruby’s unit of execution is a method, and methods are not first class objects in Ruby. If you wish to have a callable object that references a method on a particular object, then that is easily accomplished by asking the object for a Method object.

  o = Object.new
  m = o.method(:to_s)
  m.class              # => Method

Note the difference between a method (an internal Ruby construct) and a Method object (an object that represents the internal method bound to an instance). To "call" a method object (or any callable object in Ruby), you send the object the "call" message. So, the result of calling m should be identical to the result of sending to_s to o directly. And we see that it is.

  m.call               # => "#<Object:0x401c8618>"
  o.to_s               # => "#<Object:0x401c8618>"

Although Python and Ruby are similar in many ways, their basis for computation is quite different in some fundamental ways. Python follows C++ and Java in using "." as a structure selector operation, while Ruby is more closely attuned to Smalltalk’s message sending paradigm. Both approaches work and are interally consistent, but be prepared for surprises if you try to interpret one using the assumptions of the other.

I did something similar a while back. A Java programmer had taken a look at Ruby and declare that he didn’t like all that "line noise" in the language. He was refering to the "@" and "$" characters used to mark instance variables and globals. I pointed out that Ruby actually uses quite a bit less punctuation than Java, and wrote the following linenoise program do demonstrate.

    #!/usr/bin/env ruby
    ARGV.each { |fn|
      noise = open(fn) { |file| file.read }.gsub(/[A-Za-z0-9_ \t\n]/m, "")
      puts "#{fn} (#{noise.size}): #{noise}"
    }

Linenoise will strip out all alphanumeric characters and white space, leaving only the "line noise" behind. Running linenoise on a series of small programs written in different languages produces this (edited slightly for line breaks) …

  animal.cc   (83):  #<>{:()=;};:{:();};::(){::<<"\";}:{:();};::(){::
                     <<"\";}(){*[]={,};(=;<;++)[]->();;}
  Animal.java (67):  {{();}{(){..("");}}{(){..("");}}([]){[]=[]{(),()}
                     ;(=;<.;++)[].();}}
  animal.pl   (41):  ;{{};}{"\";};{{};}{"\";};$(->,->){$->();}
  animal.py   (23):  :():"":():""[(),()]:.()
  animal.rb   (10):  """"[.,.].

The number in the paranthesis is the number of line noise characters in the file.

What I find interesting is the amount of semantic information that still comes through the "line noise". For example, the "#<>" sequence in the C++ code is obviously an include statement for something in the standard library and the "<<" are output statements using "cout".

It would be interesting to see if you could determine the language given only the line noise. You could tell Java from C++ by the ";}" vs ";};" punctuation. Python is pretty clear from the ’:():"":():’ style patterns.

Before I go, here is the source code to the Animal programs I used in my examples…

Language: C++

  #include <iostream>

  class Animal {
  public:
      virtual void talk() = 0;
  };

  class Dog : public Animal {
  public:
      virtual void talk();
  };

  void Dog::talk() {
      std::cout << "WOOF\n";
  }

  class Cat : public Animal {
  public:
      virtual void talk();
  };

  void Cat::talk() {
      std::cout << "MEOW\n";
  }

  int main() {
      Animal * (a[]) = { new Dog, new Cat };
      for (int i=0; i<2; i++)
          a[i]->talk();
      return 0;
  }

Language: Java

  public class Animal {
      interface IAnimal {
          void talk();
      }

      static class Dog implements IAnimal {
          public void talk () {
              System.out.println("WOOF");
          }
      }

      static class Cat implements IAnimal {
          public void talk() {
              System.out.println ("MEOW");
          }
      }

      public static void main (String args[]) {
          IAnimal[] zoo = new IAnimal[] { new Dog(), new Cat() };
          for (int i=0; i<zoo.length; i++)
             zoo[i].talk();
      }
  }

Language: Perl

  package Dog;

  sub new {
      bless {};
  }

  sub talk {
      print "WOOF\n";
  }

  package Cat;

  sub new {
      bless {};
  }

  sub talk {
      print "MEOW\n";
  }

  package main;

  for $a (Dog->new, Cat->new) {
      $a->talk();
  }

Language: Python

  class Dog:
      def talk(self):
          print "WOOF"

  class Cat:
      def talk(self):
          print "MEOW"

  for a in [Dog(), Cat()]:
      a.talk()

Language: Ruby

  class Dog
    def talk
      puts "WOOF"
    end
  end

  class Cat
    def talk
      puts "MEOW"
    end
  end

  for a in [Dog.new, Cat.new]
    a.talk
  end

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.

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.