The Artima Developer Community
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 2 of 5  >>



Destructuring is a fairly common operation. For example, Ruby performs implicit Array destructuring on mulitple assignment:

  one, two, three = [1, 2, 3]

Ruby can also do explicit Array destructuring on method invocation.

  [].push(*[1, 2, 3])

produces [1, 2, 3] instead of [[1, 2, 3]].

You can start to see what’s going on here. Destructuring means taking apart a complex data structure, piece by piece. The Multiple Dispatch library contains two destructuring implementations, ‘amulti’ and ‘smulti’. amulti destructures arrays, smulti destructures strings.

Let’s have a look at amulti.

  amulti(:foo, Integer) {|i, rest| puts i; foo(rest) }
  amulti(:foo)          { puts "DONE" }
  foo([1, 2, 3])



Methods defined using amulti must take only a single list as a argument. The first elements of the list will be matched against the various patterns of the available dispatches, until one is found that fits. Then those elements are removed from the list and passed in as the first parameters while the rest of the list is passed in as the last parameter.

In the example above, the first rule matches if the first item in the list is an Integer. It then passes that Integer into the block with a list containing the rest of the list. When there are no more Integers to be removed, the final body is called. smulti works just the same except that it uses Regexp and String literals to tear chunks off the front of strings. It can be used to do simple parsing and other exercises.

Behind the Scenes

So how does multi work? Multi is built with two kinds of objects, Dispatches which represent a pattern along a method body, and a singleton Dispatcher that handles all calls to all multiply dispatched functions. The definition of the multi function itself is quite trivial.

  def multi(method_name, *patterns, &body)
    Multi::DISPATCHER.add(Multi::Dispatch, self, method_name, patterns, body)

This instructs the singleton dispatcher to create a new Dispatch of type Multi::Dispatch which is registered inside the dispatcher under that method name for that object. Multi defines methods on a per object basis to get around the scope problem described earlier. The registration process must therefore store the dispatch in a manner that it is associated with the object. Multi does something pretty sleazy here, and uses, along with the method name, the object’s object_id to store the dispatch in a hash table. Since there can be multiple dispatches per method, the dispatch is actually stored in a list in that particular location of the hash table, as seen below.

  key = [obj.object_id(), method_name]
  @map[key] ||= []
  @map[key].push(, body))

If this is the first time a multimethod pattern has been added, a stub method must also be installed that will ask the dispatcher to run the right dispatch if the method is ever called.

  if ! obj.methods.include?(method_name)
    obj.instance_eval <<-"DONE" 
      def #{method_name}(*params, &block), \"#{method_name}\", params, block)


Then if the method is ever called, it calls the dispatcher, which runs through the list of possible dispatches searching for the first match.

  dispatches = @map[[obj.object_id, method_name]]

  dispatch = dispatches.find{|dispatch| dispatch.match?(params) }, block)

Some languages that use multiple dispatch search for the “best” dispatch (for example, classes closest in the inheritence hierarchy to the actually method arguments). Multi is strictly in order. One nice you can do with Multi, though, is define new Dispatch classes. smulti is implemented using a class named StringDispatch and a wrapper ‘smulti’ that looks almost identical to the definition of regular ‘multi’.

  def smulti(method_name, *patterns, &body)
    Multi::DISPATCHER.add(Multi::StringDispatch, self, method_name, patterns, body)

We’ll look at smulti some more in a bit. But for now, having successfully nabbed pattern matching, let’s move on to the next heist.

<<  Page 2 of 5  >>

Sponsored Links
