The Artima Developer Community
Ruby Code & Style | Discuss | Print | Email | First Page | Previous | Next
Sponsored Link

Ruby Code & Style
If It's Not Nailed Down, Steal It
Pattern Matching, S-Expressions, and Domain Specific Languages in Ruby
by Topher Cyll
May 23, 2006

Page 1 of 5  >>

Advertisement

Raw HTML
Summary
There's a whole world of language features that we sometimes miss out on as Rubyists, such as pattern matching, S-expressions, and external domain-specific languages. But the good news is that we can have them, too, as long as we're not afraid to steal a few things first.

Theft #1: Pattern Matching

Pattern matching is a relatively rare language feature found in Standard ML, OCaml0, Haskell, Common Lisp (CLOS), and a handful of others. It’s a form of multiple dispatch, so pattern matching functions run different code when called with different arguments. Pattern Matching lets you do this dispatch based on type, value, and even internal structure of the function’s arguments.

If there was ever a time to steal Pattern Matching, it’s now. Long rumored but now visible in the distance, Perl6 will be making heavy use of Multiple Dispatch.

Casing the Joint

In Haskell (a pattern matching language), a function to return the nth Fibonacci number looks like this:

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

In this recursive function, the base cases (when the function argument is either 0 or 1) are explicitly given the value of 1. Meanwhile, the recursive case is written generically, so if the argument is not 0 or 1, it is named ‘n’, and ‘(fib n-1) + (fib n-2)’ is recursively evaluted.

The Heist

The good news for the heist is that we only need to run the goods the last mile. They’re waiting safely bundled in a Ruby gem on Rubyforge. Let’s make off with them now while no one’s looking.

  $ gem install -r multi

Phew. Okay, let’s see what we got.

Pattern Matching in Ruby

The Fibonacci function above looks like this in normal Ruby:

  def fib(n)
    return 1 if n == 0 || n == 1
    return fib(n-1) + fib(n-2)
  end

Which really isn’t so bad. But let’s rewrite the above function using multi.rb anyways:

  multi (:fib, 0)       { 1 }
  multi (:fib, 1)       { 1 }
  multi (:fib, Integer) { |n| fib(n-1) + fib(n-2) }

For better or worse there it is: Pattern matching in Ruby. We’ll inspect our acquisition in a moment, but first let’s look at the example above.

Dissection

There are three calls to the multi function above. The first parameter to each of them is the symbol :fib. We already know this is a Fibonacci function, so we appear to be calling the multi function with the first argument being the name of the function as a symbol.

Using the Haskell fib function as a template, the rest of the Ruby one is not hard to decipher. The parameters to multi after the method name are the pattern to match. The fib method does two kinds of matching. We see in the top two declarations that it is matching instance values like 0 or 1. But in the last declaration, we see a class instead of an instance.

Actually, it’s a little more complicated than that under the hood. In Ruby, the class Integer is actually an instance of class Class, but multi does some hand waving here. It assumes you probably weren’t really hoping somebody called your fib method with the parameter Integer, and were instead hoping to matching a parameters of type Integer.

The other interesting features of the declarations are the blocks following each multi. These blocks form the bodies of the multi-methods. When a multi-method call finds an implementation match, it passes in the matching parameters to the block. Of course, Ruby lets us ignore block parameters when we feel like it, so in the first two method bodies we don’t even give them names. But in the third implementation we match any Integer parameter and we probably want to hang onto that value. We name it n, like the Haskell example, and then we can use it directly in our method body.

Taking It Around the Block

Don’t forget to require the gem and it’s components before trying multi.

  #!/usr/bin/ruby -w
  require 'rubygems'
  require 'multi'
  require 'amulti'
  require 'smulti'

Now, let’s define our Fibonacci method and try calling it.

  fib(0) ===> 1
  fib(1) ===> 1
  fib(4) ===> 5
  fib(5) ===> 8

It works! So far we’ve been using multi to write what are essentially free functions. However, we’ll probably want to do methods that are part of objects as well.

Using Multi in Classes

A multi method is not entirely the same as a method defined using def. multi is a actually a method call, while def is a keyword. If multi and def were the same, we’d be able to write something like this:

  class Example
    def method1(x)
      return 0 if x == 0
      return @a + x
    end

    multi(:method2, 0) { 0 }
    multi(:method2, Integer) {|x| @a + x }
  end

Unfortunately, because of the difference, this doesn’t work. But why?

Here’s a hint: Ruby blocks are closures. Normally this is great, but here it means that @a captures a reference to the @a variable in the class Example. Not the instance, but the class itself. So calls to method2() on instances of the class will all use the same @a variable (located in the Example class), while calls to method1() will use the unique instance variable in each instance.

How can we get around this? Well, we need to perform the multi definition someplace where the context for a block is the instance, not the class. Someplace that gets run for each instance:

  class Example
    def initialize()
      multi(:method2, 0)       { 0 }
      multi(:method2, Integer) {|x| @a + x }
    end

    def method1(x)
      return 0 if x == 0
      return @a + x
    end
  end

By putting the code in the initialize method we get the proper block scope and make sure every instance gets the method. This slows us down a little, but dispatch with multi isn’t blazingly fast anyways, so this isn’t such a big deal. But this approach does have some drawbacks. One problem in particular is that if a subclass forgets to call super then the subclass’ instances will lack the multi-methods of the superclass. This also makes it difficult to add multi-methods at runtime to all instances of a class without using ObjectSpace.

Page 1 of 5  >>

Ruby Code & Style | Discuss | Print | Email | First Page | Previous | Next

Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us