Archive for March, 2008

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!


Say Hello

danbernier [at] gmail [dot] com
Twitter @danbernier
Hartford.rb
LinkedIn

Tweeting:

  • @rbazinet Dude, a Dell Latitude D820? That's my work laptop! I'm pretty "meh" about it. 34 minutes ago
  • @jpmccu "Clutter [is] a result of...excessive attachment." I think this relates to projects too. So many things out there to do! 2 days ago
  • @wigu If we say we LIKE the teeth, does that mean they'll go away sooner? 2 days ago
  • @dchec Invite them behind the counter, and move the event to a small town. You never know. 6 days ago
  • @kdaigle Where's the new digs again? Congrats on the move! 6 days ago

I’m a BackPack fan

Backpack

Categories