Use Ruby’s method_missing to see what happens to an object

Lately I’ve been generating MS Word .docs from text files, with RedCloth and Hpricot (thank you, why, for both of those), and win32ole. It’s been fun, except for the OLE parts: the ruby bridge is great, but the OLE API itself is strange, good documentation is sparse, and things get…flaky, sometimes.

In troubleshooting a bug that turns bold text on and off at the wrong times, I thought “it’d be nice if I could see all the calls that happen to this ‘selection’ object, in order they happen. Maybe I don’t realize I’m turning the ‘bold’ on at the wrong times.” Enter the Echoer:

class Echoer
    def initialize(name)
        @name = name
    end
    def method_missing(method_name, *args)
        puts "#{@name}.#{method_name}: #{args * ', '}"
        Echoer.new("#{@name}.#{method_name}")
    end
end

The Echoer is a stand-in for a regular object. Whenever a method is called on it, it prints its own name, the name of the method called, and the arguments.

def get_me_my_object
    # RealObject.new
    Echoer.new('obj')
end
obj = get_me_my_object
obj.puts 'Hello there'
obj.name = "Puddin'head Wilson"

# prints:
obj.puts: Hello there
obj.name=: Puddin'head Wilson

Each method call returns a new Echoer, whose name is based on its name, and the method name, so you can chain method calls.

obj.next.upcase.match /pattern/

# prints:
obj.next: 
obj.next.upcase: 
obj.next.upcase.match: (?-mix:pattern)

I should probably make Echoer a BlankSlate object, but I haven’t run into a need for it just yet. I could also inspect the method’s arguments with args.map { |arg| arg.inspect }, so you can tell strings and symbols apart.

Back in OLE-land, I replaced all instances of the selection object with Echoer.new('selection'), re-ran my code, and watched the output. I still haven’t found the source of the bug, but at least I know I’m not turning bold on or off when I don’t expect to.

Thanks to Michael Feathers for this idea. He wrote on the Beautiful Code blog about Spelunking Ruby Methods with Pebbles, but it seems O’Reilly took the blog down. All that’s left are the links from sites like reddit…does anyone know if the content is floating around somewhere out there?

Advertisements

Long-running averages, without the sum of preceding values

Here’s a little lunch-time diversionary math.  Suppose you want a function that takes a number, and returns the average of all the numbers it’s been called with so far.  Handy for continuously updated displays, that kind of thing. Here’s a method that will return this averaging function.

private static Func MakeAverager()
{
    float sum = 0;
    int count = 0;
    return delegate(float x)
    {
        sum += x;
        count += 1;
        return sum/count;
    };
}

It creates sum and count variables for the function to close over.  The function takes a number, x, and adds it to sum.  It increments count, and divides.  Pretty standard.

Now, let’s get crazy, and pretend this code is going on Voyager, and it’ll be running for ever.  sum will get pretty high, right?  We’ll blow through 231, the upper-bound for .Net 32-bit ints.  Sure, we could make it a long, and go up to 263, but that’s not the point.  The point is, it’ll eventually run out, because sum is too high.

I’ve been chewing on this brain-teaser for a while.  I knew there must be a way to calculate a long-running average without storing the sum and the count; it seems the average so far, and the count, should be enough, but I don’t want to resort to ((average * count) + x) / count++, because that’s the exact same problem. (Of course, count could still get so high it overflows, but that’s somewhat less likely. Hush, you.)

I finally sat down and figured it out.  The trick is, each successive x tugs your average up or down — first by a lot, but by less over time.  With each x, the average gets harder to move:  the effect each new x has on the average is inversely proportionate to the count.  We can put it like this:

average += (x - average) / count

We tug average by x - average, the distance between them, scaled down by count.  Then, add that on to average (of course, if x < average, then x – average is negative, so it’ll tug the average down).

Let’s make a new averager.

private static Func MakeNewAverager()
{
    float average = 0;
    int count = 0;
    return delegate(float x)
    {
        average += (x - average) / ++count;
        return average;
    };
}

It works the same, but it’ll take a lot longer for count to overflow than sum.

For the record, here’s the ruby I used to sketch this idea out.  Of course, in ruby, this problem is even more bogus, because ruby’s Bignum can handle any number that your machine has enough free RAM to store.  But still.

def make_averager
    sum, count = 0, 0
    lambda { |x|
        sum += x
        count += 1
        sum.to_f / count
    }
end

def make_sum_free_averager
    avg = 0.0
    count = 0
    lambda { |x|
        count += 1
        avg += (x - avg) / count
    }
end

Gregory Brown at the Hartford Ruby Brigade

This past Monday night, Gregory Brown, ruby mendicant, stopped by for the Hartford Ruby Brigade’s July meeting.

We started off with a Ruby Robots show-down, but since everyone still had work to do on their bots, we decided it’ll be a regular event.  Right now, my lame-ass Edger bot is, I believe, the champion, but I expect that to change next month.  Greg’s bot, the terminator, won the Matrix-version of the competition, where cheating hacking the system is allowed.  You can watch Greg talk about cheating Ruby Robots, how he hacked the enemy bots, and defended his bot against similar attacks.  It’s relevant to any ruby discussion, because he’s using basic ruby techniques, and ruby’s open and dynamic nature, to do it all.

Greg’s talks on Ruport, Prawn, and the finer points of designing a useful API in ruby were really good, too.  With luck, they’ll be up on Vimeo soon.

Constructor Inheritance in C# and Ruby

This morning: “Surprise!  Want to conduct a job interview?”  I’ve been here a little over 3 months, but um, sure!  “Great.  He’s in the conference room right now.”  Wow, we move quick.

So, without much time to gather my thoughts for good tech-y interview questions, I printed out the resume, and I winged it.  In the middle of the interview, I flipped over his resume, and scribbled out short-hand C# like this:

class A {
public A() {
Console.WriteLine(“in A”);
}
}
class B : A {
public B() {
Console.WriteLine(“in B”);
}
}
class C : B {
public C() {
Console.WriteLine(“in C”);
}
}
new C();

I asked, “What does this print out?” You know, see if he knows which order constructor inheritance goes in. I wanted to hear, “in A, in B, in C”, but not “in C, in B, in A”.

I forget exactly what the candidate’s answer was, but it stirred up a bit of discussion, because the three of us interviewing him disagreed on the answer: one of us said it would only print “in C,” because you need to stick : base() on the B and C constructors for the inheritance to work; I agreed with the third interviewer, who said it would print “in A, in B, in C”, because constructor inheritance is automatic (with no-arg constructors). We fudged around it, laughed a bit, and the interview moved on. (Update: here’s the answer.)

Back at my desk, I had to try it out. I didn’t want to bother with a whole Visual Studio .sln and all that nonsense, so I tried it in Ruby:

class A
def initialize
puts “in A”
end
end
class B < A def initialize puts "in B" end end class C < B def initialize puts "in C" end end C.new [/sourcecode] And the output is..."in C"! Huh? That can't be right...I was sure constructors were inherited automatically! Then I realized, of course! I’m working in Ruby, and you have to explicitly call superclass methods, constructors included:

class A
def initialize
super # <- call the superclass' constructor  puts "in A" end end class B < A def initialize super # <- call the superclass' constructor puts "in B" end end class C < B def initialize super # <- call the superclass' constructor puts "in C" end end C.new [/sourcecode] Stupid Ruby! Did I find a case where C# actually works nicer than Ruby? But then I realized, this also means Ruby lets you change the order of the constructor inheritance: you can go bottom-up, if you want, or even stranger: [sourcecode language='ruby'] class A def initialize super puts "in A" end end class B < A def initialize super puts "in B" end end class C < B def initialize puts "in C" super # <- call up the chain AFTER we're done end end C.new [/sourcecode] That one prints out "in C, in A, in B". The nice thing? No rule to memorize, and more control. The down-side? More to type. But given how compact Ruby already is, I think the added control is worth it here. What do you think?
(Update: I eventually did fire up Visual Studio, and the code above printed “in A, in B, in C”, without me typing out : base(). C# inherits constructors automatically, and the superclass constructors run before subclass constructors.)

My GoRuCo 2008 highlights

Aaron and I had a great time at GoRuCo 2008 last Saturday. Here are my highlights.

Bryan Helmkamp, Story-Driven Development

Bryan Helmkamp’s talk on SDD (slides, 1.6 MB PDF) reminded me of what Scott Hanselman calls “spec documents with teeth.” If I get it right, as you develop user stories, you use a standard format, and code parses your story file, and ties the text directly to functional tests you write. The stories aren’t executable themselves, but it brings them closer together.

Each story has a name, a description, and scenarios; the descriptions follow the format “As a …, I want to …, so that …”:

As a headhunter looking for Rails developers
I want to search for CVs with 8 years experience
So that I can make an exorbitant commission

The scenarios are different ways that story might play out. Each scenario has a description, which follows the format “Given … When … Then …”:

Scenario: Enough experience.
Given a CV with 9 years of Rails experience
When I search for qualified Rails candidates
Then I should find the CV
And I should realize the candidate is full of shit

Then code reads your story files, and uses the text following the keywords to connect to executable functional tests you write:

steps_for :cvs do
  Given "a CV with 3 years of Rails experience" do
    @cv = Developer.create!(:first_name => "Joe",
      :last_name => "Developer", :rails_exp => 3,
      :gender => "Male")
  end
end

steps_for :cvs do
  When "I search for qualified Rails candidates" do
    @results = Developer.find_qualified(8)
  end
end

The code that actually performs the test is just ActiveRecord. If you want to test the UI, there’s a DSL called Webrat that simulates the browser. It seems to live halfway between Watir and mechanize, and it doesn’t do javascript. It looks like this:

steps_for :cvs_with_ui do
  Given "a CV with 3 years of Rails experience" do
    visits new_developer_path
    fills_in "First name", :with => "Joe"
    fills_in "Last name", :with => "Developer"
    selects "4", :from => "Rails Experience"
    chooses "Male"
    clicks_button "Create"
  end
end

I’m curious about chooses "Male" — I don’t see how it connects that text with the drop-down it’s supposed to change, unless it looks at values for all drop-downs on the page. He gave a nice breakdown of the differences between Webrat and Selenium, and how SDD fits into an Agile team.

Giles Bowkett, Archaeopteryx

That’s ARK-ee-OP-ter-ix, or Arcx for short. Made by Giles (soft ‘g’) BOH-ket, or boh-KET, I wasn’t exactly sure which. It is, in his words, “a Ruby MIDI generator,” and “a system for auto-generating, self-modifying music.”

Giles had hands-down the most entertaining talk of the day. Instead of poring through each token of the code, he compared taking VC money (or “weasel-brained muppet fucker” money) to being an artist with a patron — as the programmer/artist, your job is to make stuff that makes your VC/patron look good. He showed some of Leonardo da Vinci’s designs that weren’t constructed until recently; that it took this long, he said, was a failure of da Vinci’s time. Similarly, staying within a VC’s idea of what’s possible is a failure of wasted passion and energy. Start-ups are so cheap now, you can ignore VCs — so follow your passion, create an open-source-enriched ecosystem around it, and make money by servicing the niche market you made. If your startup is great, you can say “my career is this thing”; if it’s mediocre, you can say “my career includes this thing”. Just remember that good artists ship.

Which brings us to Arcx, Giles’ idea for a crowd-interfacing, automatic music machine. Someone asked whether it was wise to name a new project after an extinct species, and Giles got all clever: archaeopteryx was either the last dinosaur or the first bird, and the project could be either the last DJ tool, or the first automatic music machine, played by the crowd. He played us some samples, and talked through the code just a bit, dropping hits about the CLOS-like structure of his code. As fun as his talk was, I would’ve liked to hear more music, and more about the lambda-passing and CLOS stuff.

He also pointed out the most interesting ruby book I’d never heard of, Practical Ruby Projects: Ideas for the Eclectic Programmer.

Chris Wanstrath, ParseTree

Out of all the talks, Chris’ was the one I’ll be using first. Lispers say “code is data,” and I can see why that’s so powerful — but I haven’t really tried it yet. ParseTree brings some of that coolness to ruby:

require 'ruby2ruby'

def to_ruby(&blk)
   blk.to_ruby
end

puts to_ruby { 1 + 1 }
puts to_ruby { |i| i == 42 }

def to_sexp(&blk)
   blk.to_sexp
end

puts to_sexp { 1 + 1 }
puts to_sexp { |i| i == 42 }

…which produces:

proc {
  (1 + 1)
}
proc { |i|
  (i == 42)
}
[:proc, nil, [:call,
   [:lit, 1], :+, [:array, [:lit, 1]]]]
[:proc, [:dasgn_curr, :i], [:call,
   [:dvar, :i], :==, [:array, [:lit, 42]]]]

Most of the examples he gave generated query syntax in a ruby-idiomatic way: say you have an ORM, and you want users to search for users like this:

old_cat_people = Users.select do |u|
   u.favorite_pet == "cat" && u.age > 100
end

How could you turn that into SQL? Call to_sexp on the query block (that’s “to S-expression“), and evaluate the abstract syntax tree it returns. Like this:

class Users
   def self.select(&query)
      query = query.to_sexp

      # Now, query looks like this:
      # [:proc,
      #    [:dasgn_curr, :u],
      #       [:and,
      #          [:call,
      #             [:call, [:dvar, :u], :favorite_pet],
      #             :==,
      #             [:array, [:str, "cat"]]],
      #          [:call,
      #             [:call, [:dvar, :u], :age],
      #             :>,
      #             [:array, [:lit, 100]]]]]

      # Time to evaluate the AST.
   end
end

Admittedly, it’s not that trivial, but that’s the gist of it — and I think the gem helps you with this. (Cue the smug Lispers: this stuff is natural in Lisp, the way passing anonymous functions blocks is in ruby.)

But here’s the interesting thing: we’re on our way to building .Net’s LINQ right into ruby. Remember, it stands for Language Integrated Query. LINQ is a big deal for .Net folks, because it’s handy. Microsoft put a lot of work into it, and it still needs its own new syntax. I think that’s a pretty clear example of the power of being able to see your own AST, and code off it.

Ryan Davis, Hurting Code for Fun and Profit

Ryan‘s talk was nominally about using tools like Heckle and Flog to beat the evil out of code, but my favorite part was his introspection-driven development. I know I’ll want to refer others to his slides and audio throughout my career.

Some of his tips for improving as a programmer:

  • Read. 1 technical book a month. Sites like c2.com — get close to the experts.
  • Focus. Only a few smart blogs: not zillions, not flame-prone. (Flame-retardant blogs?)
  • Grow. Learn 1 new language a year. Learn things outside of programming.
  • Learn from the pottery challenge story in Art & Fear: practice, a lot.

Ryan is also a fellow Dvorak typist, and pretty emphatic about it.

Johnson

Johnson is a ruby gem that executes JavaScript code. (It’s a successor to RKelly, which did the same thing.) I don’t know why I think this is so cool. Most people agreed the main use case for something like this is testing, but it seems to me there might be neater tricks to play. We’ll see how I feel after playing with it for a while.

GoRuCo 2009?

I’m definitely going next year — see you there.

Trading Space for Speed: Memoizing with Ruby Facets

Recently, I talked about a faster, cheaper way to calculate Fibonacci numbers. One of the optimizations I made was to remember the value of each Fibonacci number: since F(7) is always 13, instead of recalculating it each time N=7, we can stuff 7 -> 13 into a look-up table for future reference. The function builds up a cheat-sheet, to avoid doing the re-work. It remembers.

This is called memoization, and it’s a nice way to trade memory for performance. But it only works when the function always returns the same answer for a given set of arguments — otherwise it’s first-in wins, forever. This property of a function, returning the same answer for the same args, is called referential transparency.

A Sample Implementation

There are lots of ways you could memoize a function. Hash tables are a natural choice, since they map a key to a value, just like functions map arguments to a value. Even if you implement it differently, a hash table is a good working model for memoization.

Let’s briefly consider factorials. The regular version:

class Unmemoized
    def factorial(n)
        puts n
        if n < 1
            1
        else
            n * factorial(n-1)
        end
    end
end

unmemoized = Unmemoized.new

5.downto(1) { |i| puts "\t#{unmemoized.factorial(i)}" }&#91;/sourcecode&#93;


...and the memoized version:

&#91;sourcecode language='ruby'&#93;
class Memoized
    attr_reader :factorial_memo
    def initialize
        @factorial_memo = {}
    end

    def factorial(n)
        puts n
        unless @factorial_memo.has_key? n
            if n < 1
                @factorial_memo&#91;n&#93; = 1
            else
                @factorial_memo&#91;n&#93; = n * factorial(n-1)
            end
        end

        @factorial_memo&#91;n&#93;
    end
end

memoized = Memoized.new

5.downto(1) { |i| puts "\t#{memoized.factorial(i)}" }

puts memoized.factorial_memo.inspect&#91;/sourcecode&#93;


Printing the hashtable is especially telling:  <code>{5=&gt;120, 0=&gt;1, 1=&gt;1, 2=&gt;2, 3=&gt;6, 4=&gt;24}</code> It reads like a look-up table for factorials.
<h4>Memoization in Facets</h4>
As relatively easy as that example is, it has its drawbacks: we need to track our previous results in a separate variable, the memoization code is mixed up with the actual calculation (the part we care about), we can't easily use it with other functions, and the pattern only works for functions of one argument.  <a href="http://facets.rubyforge.org/">Facets</a> makes memoization trivial, and removes all these issues.


require 'facets/memoize'

class FacetsMemoized
    def factorial(n)
        puts n
        if n < 1
            1
        else
            n * factorial(n-1)
        end
    end

    memoize :factorial # <= HINT
end

facets_memoized = FacetsMemoized.new

5.downto(1) { |i| puts "\t#{facets_memoized.factorial(i)}" }&#91;/sourcecode&#93;


In case you missed it, this is just like <code>Unmemoized</code> above, except we added line 13, <code>memoize :factorial</code>...that's it.  Just like <code>attr_reader</code> and friends, you can pass a list of symbols to <code>memoize</code>, and it'll work on functions with any number of arguments:


require 'facets/memoize'

class MemoizedMath
    def add(n, m)
        n + m
    end
    def mult(n, m)
        n * m
    end
    memoize :add, :mult
end

When You Might Use Memoization, and What to Avoid

There are a number of places where this is useful: calculating a value by successive approximation, finding the path to the root node in an immutable tree structure, finding the Nth number in a recursively-defined series, even simple derived values (like ‘abc’.upcase). In general, a function is a good candidate if it only looks at its arguments (no global, class, or member variables, no files or databases) — especially if those arguments are immutable.

Relying on side-effects (printing to standard out, writing to a database or file, or updating a variable) in memoized methods is a bad idea: they’ll only happen the first time your method is called with those arguments, which is probably not what you intend. (Unless you’re printing the arguments to illustrate how memoizing works.) On the other hand, relying on side-effects is generally a bad idea anyway. Even if you don’t use a functional programming language, you can still benefit from minimizing state changes.

Further Reading

If memoization sounds interesting to you, you might like Oliver Steele’s article about memoizing JavaScript functions. If you’re curious about immutability, you might like this Joshua Bloch interview. If you’re interested in functional programming, there are worse places to start than the excellent Structure and Interpretation of Computer Programs. And of course, there’s more where that came from, in Ruby Facets.

Ruby Facets: Symbol.to_proc, Class.to_proc

One pretty well-know idiom in Ruby, and Facets, is Symbol.to_proc. It lets you turn these:

[1, 2, 3].map { |num| num.next }  #=> [2, 3, 4]

%w[alpha beta gamma].map { |word| word.upcase }
#=> ["ALPHA", "BETA", "GAMMA"]

…into these:

[1, 2, 3].map(&:next)
%w[alpha beta gamma].map(&:upcase)

It’s a nice little trick, though it’s not to everyone’s taste. If you’re already comfortable with Symbol.to_proc, you can skip down to the Class.to_proc section. But if you’re not, it’s worth a minute of your attention to learn it. Read on…

How it’s done

When a method takes a block, you can call yield, to run the block.

def with_a_block(a_param)
    yield
end
with_a_block('param') {
    puts 'in the block'
}

Or, you can name the block as the last parameter to the method, and put an ampersand in front of it. The ampersand makes ruby convert the block to a procedure, by calling to_proc on it. (So any object with a to_proc method can work this way, if you want.) This example works just like the last one:

def named_block(a_param, &blk)
    blk.call
end
named_block('my_param') {
    puts 'in the named block'
}

Symbol’s to_proc method creates a procedure that takes one argument, and sends the symbol to it. Sending a symbol to an object is the same as calling a method on it: object.send(:method) works the same as object.method. In the earlier upcase example, each word is passed to a procedure that calls upcase on it, giving us a list of uppercased strings.

&:upcase
# becomes...
lambda { |obj|
    obj.send(:upcase)
}
# or...
lambda { |obj|
    obj.upcase
}

Class.to_proc

So Symbol.to_proc creates a function that takes an argument, and calls that method on it. Class.to_proc creates a function that passes its argument to its constructor, yielding an instance of itself. This is a welcome addition to the to_proc family.

require 'facets'

class Person
    def initialize(name)
        @name = name
    end
end
names = %w[mickey minney goofy]
characters = names.map(&Person)

puts characters.inspect

&Person
# becomes...
lambda { |obj|
    Person.new(obj)
}

Why it’s nice

  • It’s fewer characters — it semantically compresses your code.
  • It lets you think, makes you think, on a higher level. You think about operations on your data, rather than handling one item at a time. It raises your level of thinking.
  • It works with first-class functions, which are worth understanding. They give you new ways to elegantly solve some problems (well, new to some audiences). They’re not fringe anymore — they’ve been in C# since v2.0.

A Faster, Cheaper Fibonacci Definition

The Fibonacci sequence is one of the best-known number sequences:

  1. 1
  2. 1
  3. 2
  4. 3
  5. 5
  6. 8
  7. 13
  8. 21…

Each Fibonacci number above 1 is defined as the sum of the previous two Fibonacci numbers:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Just for fun, here’s another way to specify the Fibonacci sequence. It takes fewer calculations, especially for large numbers. The math is basic algebra substitutions. This could be old news — if you’ve seen this before, I’d love to hear from you.

Deriving the new Fibonacci definition

Before we begin, let’s notate F(n) as Fn, and F(n-1) as Fn1 — it’ll make everything tidier.

That Fn1 + Fn2 part, to me, always begged for substitution. Fn1 should equal Fn2 + Fn3, right? What if we re-write Fn in terms of Fn1‘s definition? What might that lead to?

Fn = Fn1 + Fn2
Fn1 = Fn2 + Fn3
Fn = Fn2 + Fn2 + Fn3
Fn = 2Fn2 + Fn3, as long as n > 2.

Pretty basic: substitute the definition for Fn1 back into the definition for Fn, and simplify. We can keep going:

Fn2 = Fn3 + Fn4
Fn = 2Fn2 + Fn3, from above
Fn = (2Fn3 + 2Fn4) + Fn3
Fn = 3Fn3 + 2Fn4, for n > 3

…and then:

Fn3 = Fn4 + Fn5
Fn = (3Fn4 + 3Fn5) + 2Fn4
Fn = 5Fn4 + 3Fn5, for n > 4

…and again:

Fn4 = Fn5 + Fn6
Fn = (5Fn5 + 5Fn6) + 3Fn5
Fn = 8Fn5 + 5Fn6, for n > 5

…just one more time:

Fn5 = Fn6 + Fn7
Fn = 8Fn6 + 8Fn7 + 5Fn6
Fn = 13Fn6 + 8Fn7, for n > 6

See the pattern? Look at the coefficients:

Fn = 2Fn2 + 1Fn3, for n > 2
Fn = 3Fn3 + 2Fn4, for n > 3
Fn = 5Fn4 + 3Fn5, for n > 4
Fn = 8Fn5 + 5Fn6, for n > 5
Fn = 13Fn6 + 8Fn7, for n > 6

They’re the Fibonacci sequence starting up. Do the math, and you’ll see that the next few steps follow along. What if we replace the coefficients with their Fibonacci indexes? If F(6) = 8 and F(7) = 13, we can rewrite 13Fn6 + 8Fn7 as F(7) Fn6 + F(6) Fn7. Let’s carry that out:

Fn = F(3) Fn2 + F(2) Fn3, for n > 2
Fn = F(4) Fn3 + F(3) Fn4, for n > 3
Fn = F(5) Fn4 + F(4) Fn5, for n > 4
Fn = F(6) Fn5 + F(5) Fn6, for n > 5
Fn = F(7) Fn6 + F(6) Fn7, for n > 6

Let’s quickly verify this. We know from the original definition that F(10) = 55, so let’s see whether these new versions agree. (I’ll only test the first and last versions, to save space, but you can verify as many as you like.)

F(10) = 55 = F(3) Fn2 + F(2) Fn3
F(10) = 55 = F(3) F(8) + F(2) F(7)
F(10) = 55 = 2 * 21 + 1 * 13

F(10) = 55 = F(7) Fn6 + F(6) Fn7
F(10) = 55 = F(7) F(4) + F(6) F(3)
F(10) = 55 = 13 * 3 + 8 * 2

They both pass. More generally:

Fn = F(x) Fny + F(y) Fnx, for n > x, and y = x – 1

It’s not terribly wordier than the original definition, Fn = Fn1 + Fn2, for n > 2.

Putting this to use

A nice property of this new version is that it lets us skip some steps. If we’re calculating F(1000) with the traditional definition, we have to calculate each Fibonacci along the way; but now, we can set x = 500, and skip down to the neighborhood of F(500):

F(1000) = F(500) * F(501) + F(499) * F(500)

We can continue to skip down to about n/2, decreasing the amount of calculations we need to do.

Just for fun, I implemented both fib_orig and fib_new in ruby: here’s the file. I memoized the methods, for two reasons:

  1. It’s clearly much faster, and it’s simple to do.
  2. It lets us see exactly which Fibonacci numbers were calculated.

I put the two methods in a test case, with four test methods.

The first test ensures that the new equation matches the old. Unfortunately, I could only reach 6000 with the fib_orig, before I ran out of stack space.

The second test benchmarks the two versions. It reports the memo array size (6000 for fib_orig, as expected, and 40 for fib_new — 99.3% fewer calculations).

When fib_orig ran out of stack space so quickly, I wondered how far I could take the new version (which should recurse many fewer times). So in the third test, I benchmarked it with progressively bigger numbers. It starts to slow down around the millionth Fibonacci number: it completes in about 12 seconds on my machine. I suspect it’s spending the extra time array-seeking at that point, since the array gets pretty sparse — the last few non-null array indexes are: 125001 249999 250000 250001 499999 500000 500001 1000000. Maybe I’ll try a hash…

The fourth test is a bit of extra-credit, and a sanity check. Fn / F(n+1) approaches the golden ratio, 1.61803398874…, as N approaches infinity. So I calculated F(1401) / F(1400) with fib_new, and it’s accurate to 15 decimal points, rounding the last one, which seems to be the limit of precision on my WinXP machine. I tried using higher Fibonacci numbers, but was warned that I was exceeding the range of ruby’s floating point numbers. Here’s the output of that test:

 actual golden ratio: 1.6180339887498948482
approx. golden ratio: 1.618033988749895
precision-level test: 0.333333333333333

So it seems the new approach is correct, faster, uses less space, and is still pretty elegant. Who knows whether this will ever come in handy, but at least it was fun to do.

F(n) = F(x) F(n-y) + F(y) F(n-x), for n > x, and y = x – 1

Hartford Ruby Brigade starts with a tour of Ruby Facets

As Rob Bazinet has said, the Hartford Ruby Brigade is having its first meeting on March 24. You can get all the details from his post. Come join us! There’s even a book raffle.

I’ll be giving the first presentation, a tour of Ruby Facets. Facets is a pretty huge library (even after they moved some really neat parts into their own projects), and it’s crazy to think we could cover it all in one night. I’ll quickly touch on the simple features, just to let you know they’re there, and I’ll spend more time with some of the interesting parts. If you’re stuck, it’s a good chance Facets has what you need; the trick is knowing it’s there, and where to look — I want to point out enough of Facets to help you with that.

I’ll also start a Tour of Facets series here, starting with this post. I’m aiming for two to four posts a month, and will cover everything in the presentation, and then some. So, on with the tour…

compare_on and equate_on

Remember the first time you saw attr_reader and attr_writer? These tiny helpers got me excited about ruby, not just because they meant less typing and DRY-er code, but because they meant I could make helpers to generate methods, too, if only I could think of a reason to do it.

Facets has a great example of why you’d want to do that: compare_on and equate_on.

Most ruby programmers know you can make your objects sortable by defining <=>, the spaceship method, on them. Typically, you wind up delegating to some attribute:

class Person
   attr_reader :fname, :lname
   def initialize(fname, lname)
      @fname, @lname = fname, lname
   end
   def <=>(person)
      @lname.<=>(person.lname)
   end
end

Facets adds compare_on, which generates the spaceship method for you, based on that attribute. Not only that, but you can compare_on multiple fields, and it handles the hairy logic for you automatically:

require 'facets/compare_on'

class Person
   attr_reader :fname, :lname
   def initialize(fname, lname)
      @fname, @lname = fname, lname
   end
   compare_on :lname, :fname
end

people = []
people.push Person.new('Adam', 'Smith')
people.push Person.new('John', 'Adams')

people.sort #=> John Adams, Adam Smith

Correctly implementing the spaceship operator isn’t too hard, but object equality gets tricky in any language. Facets helps you here by implementing ruby’s main three equality methods for you: ==, eql?, and hash.

require 'facets/compare_on'

class Person
   attr_reader :fname, :lname
   def initialize(fname, lname)
      @fname, @lname = fname, lname
   end
   equate_on :lname, :fname
end

a_pres = Person.new('John', 'Adams')
another_pres = Person.new('John', 'Adams')
[a_pres].include?(another_pres) #=> true

Again, you can equate on multiple attributes (fname and lname), and it handles all the details for you. Hope to see you at the Hartford Ruby Brigade!

Continuations: a warm-up

Continuations and continuation-passing style (CPS) are introduced in The Little Schemer, chapter 8, using collectors: functions that collect values, through being repeatedly redefined. It was a tough chapter for me, but the idea is simple once you get it, so I’d like to leave some help for others. I’ll use Ruby for the examples, with some JavaScript and Scheme at the end.

In languages with first-class functions, you can assign functions to variables, and re-assign those variables. Consider this Ruby example:

func = lambda { |x| puts x }

['a', 'b', 'c'].each { |ch|
    old_func = func
    func = lambda { |x| old_func[x + ch] }
}

func['d']  #=> prints 'dcba'

By re-defining func in terms of old_func, we’re building up a recursive computation. It’s like normal recursion, but approached from the other side — without explicit definitions. Since a Ruby function is a closure, it remembers the value of the variables in scope when it was created; each layer of this recursion holds its own value for ch and old_func. When we call the last func, it sees ch = ‘c’ and x = ‘d’. It concatenates them, and calls its version of old_func…which sees x = ‘dc’ and ch = ‘b’, concatenates them, and passes it to its old_func, and so on.In fact, if we wrote it like this, the execution of all those lambdas would be exactly the same:

func_puts = lambda { |x| puts x }
func_add_a = lambda { |x| func_puts[x + 'a'] }
func_add_b = lambda { |x| func_add_a[x + 'b'] }
func_add_c = lambda { |x| func_add_b[x + 'c'] }
func_add_c['d']  #=> prints 'dcba'

We could calculate factorials this way:

def factorial(n, func)
    if n == 1
        func[1]
    else
        factorial(n - 1, lambda { |i| func[i * n] })
    end
end
factorial(3, lambda { |fact| puts fact })  #=> prints 6
  1. On the first call to factorial, n = 3, and func just prints its argument. But func isn’t called yet…since n isn’t 1, we recurse with n - 1 = 2, and a new function that calls func with its argument i times 3.
  2. On the recurse, n = 2, and func calls the original printer func with its argument i times 3. Since n still isn’t 1, we recurse again, with n - 1 = 1, and a new function that calls our func with its argument i times 2.
  3. On the final round, n = 1, so we (finally!) call func with 1, which…
  4. …calls the previous func with 1 * 2, which…
  5. …calls the original func with (1 * 2) * 3, which…
  6. prints 6.

As factorial recurses, it builds up a recursive tower of func calls. In factorial‘s base case, the last (and outermost) func is called, and we begin to climb down the func tower, to its bottom floor, the original func. It’s recursion in two directions.

In case Ruby isn’t your favorite language, here are versions in JavaScript and Scheme:

function factorial(n, func) {
    if (n == 1)
        func(1)
    else
        factorial(n - 1, function(i) {
            func(n * i)
        });
}

factorial(3, function(fact) { print(fact) })
; Too bad WordPress doesn't format Scheme or Lisp!
(define factorial
  (lambda (n func)
    (cond ((= n 1) (func 1))
          (else (factorial (- n 1)
                           (lambda (i) (func (* n i))))))))

; Here, the original func is just an identity function.
(factorial 4 (lambda (fact) fact))

Once this is clear, you can see many other applications:

  • You could find all the even numbers in a list: instead of passing a number to func, pass the list of even numbers, and add each even number in.
  • You could separate the numbers into evens and odds: instead of passing just one list to func, pass two lists, for evens and odds, and add each number to the correct list.
  • You could separate any list of items by any criteria: instead of hard-coding “is even?” into the function, pass a predicate function. (Maybe you want to extract all occurrences of ‘tuna’ from a list of words.)

That should be enough of a warm-up for chapter 8. See you in chapter 9, when they derive the Y-combinator!