Integrating Scala into JRuby

29
Sep
2008

More and more projects (especially startups) have been choosing to build their software in multiple languages. Rather than using SQL for the database, XML for the RPC and Java for the everything else, companies have learned that sometimes a different language can serve best in a specific area. Ola Bini provides some guidance with regards to methodology in this area in the form of what he calls “language layers”. He suggests that an application can be divided logically into separate layers, and for each of these layers there exists a class of language - be it dynamic, static, compiled or otherwise - which can best accomplish the task at hand. All of that aside, there is one problem which is absolutely assured when dealing with polyglot programming: integration between the languages.

I’m told that this issue came up at the JVM languages conference this past week. The problem of integrating very separate languages in a natural way is not an easy one, even when all languages in question are on the JVM. So far, the only solution that anyone has been able to come up with is just to use Java as an intermediary. After all, JRuby integrates with Java, as does Clojure, therefore JRuby has at least some path of integration with Clojure and vice versa.

The problem is that such integration is not really idiomatic. As the title of this post implies, we’re going to consider the example of Scala and JRuby. I’ve already written about how to create a Scala DSL for calling JRuby directly, so let’s look at the other side of the problem: it’s certainly possible to use Scala classes from within JRuby, but it isn’t exactly a pleasant proposition. Let’s imagine that I want to make use of my Scala port of Rich Hickey’s excellent immutable persistent vector data structure:

import com.codecommit.collection.Vector
 
vec = Vector.new
vec = vec.send('$plus'.to_sym, 1)
vec = vec.update(0, 2)
 
puts vec.apply 0       # 2

Straightforward, but ugly. Let’s break this down a little bit… The import and instantiation are both self-explanatory, so we come to the rather cryptic invocation of send. In case you don’t know, this is a Ruby method which makes it possible to invoke arbitrary methods on a given object, including those with illegal characters. I happen to know that Scala will compile the + operator to a method named $plus within class Vector. JRuby is perfectly happy to handle and forward this call as necessary, despite the fact that you could never actually declare this method in pure Ruby ($ has special meaning). Thus, this invocation is the same as the following Scala snippet:

vec = vec + 1

In other words, append 1 to the vector and assign the resulting new vector back into vec.

Moving on, we come to the invocations of update and apply. These should be a bit more comprehensible to those familiar with Scala’s intricacies. In short, these methods are how you overload the parentheses and parentheses/assignment operators. Thus, our last two lines correspond as follows:

vec = (vec(0) = 2)
println(vec(0))

This was just a trivial example, you can imagine how a more complicated Scala API could be neigh unusable in JRuby. Intuitively though, it shouldn’t have to be this way. After all, JRuby supports many of the same syntactic power as Scala: it has some operator overloading, closures and even more complicated features like mixins. With all of this common ground, surely there is a way to make the two coexist more naturally? I mean, optimally we could have something like this:

import com.codecommit.collection.Vector
 
vec = Vector.new
vec = vec + 1
vec = (vec[0] = 2)       # problematic
 
puts vec[0]              # 2

What we have just done is informally define a desired syntax for a domain-specific problem. Does that sound like an internal DSL to anyone else?

Our goal is to create a simple Ruby API that can be required into any JRuby application to improve the integration with Scala. To do this, we will need to find a way to convert Ruby features into their corresponding Scala features by going through Java. Once we find this translation, we can use meta-programming and dangerously-cool Monkey Patching to augment JRuby’s existing Java integration. In this way, we don’t have to start our integration layer from scratch, we can just “pretty up” JRuby’s existing features, taking advantage of the fact that Scala classes are Java classes.

Step One: Operators

From our example above, converting the invocation of a $plus method into a Ruby + operator seems to be the easiest challenge to tackle. Ruby does support operator overloading; unfortunately, this support is incredibly limited when compared with Scala’s awesome power. For example, in Scala it is possible to invent arbitrary operators, a feature which is heavily used in the Scala standard library. Ruby has no such capability, operators are implemented using conventional techniques and hard-coded rules in the parser.

In order to avoid blowing this experiment completely out of proportion, we’re only going to implement translations for the set of conventional Ruby operators. It would be possible to also implement Scala operators which are made by combining existing Ruby operators (e.g. the ++ operator) using techniques developed for the Superators gem, but to do so would be extremely difficult.

We saw in our original example that the Scala + operator is translated into an invocation of the $plus method. It stands to reason that we could make use of this fact in our translation from Ruby to Scala. The trick is finding a comprehensive list of Scala’s operators and what methods they compile to. Fortunately, I had already investigated these translations for a different project:

Scala Operator	Compiles To
`=`	`$eq`
`>`	`$greater`
`<`	`$less`
`+`	`$plus`
`-`	`$minus`
`*`	`$times`
`/`	`div`
`!`	`$bang`
`@`	`$at`
`#`	`$hash`
`%`	`$percent`
`^`	`$up`
`&`	`$amp`
`~`	`$tilde`
`?`	`$qmark`
`\|`	`$bar`
`\`	`$bslash`

Repeated iterations of an operator become corresponding repetitions of the equivalent character sequence. Thus, ++ becomes $plus$plus. This suggests a very natural strategy for converting Ruby operator invocations into Scala: string substitution. We can easily Ruby operator calls using method_missing, substitute the appropriate character sequences and then attempt the modified call against the same object. This idea, when translated into Ruby, is almost as simple as that:

OPERATORS = {"=" => "$eq", ">" => "$greater", "<" => "$less", \
        "+" => "$plus", "-" => "$minus", "*" => "$times", "/" => "div", \
        "!" => "$bang", "@" => "$at", "#" => "$hash", "%" => "$percent", \
        "^" => "$up", "&" => "$amp", "~" => "$tilde", "?" => "$qmark", \
        "|" => "$bar", "\\" => "$bslash"}
 
alias_method :__old_method_missing_in_scala_rb__, :method_missing
def method_missing(sym, *args)
  str = sym.to_s
 
  str = $&[1] + '_=' if str =~ /^(.*[^\]=])=$/
 
  OPERATORS.each do |from, to|
    str.gsub!(from, to)
  end
 
  if methods.include? str
    send(str.to_sym, args)
  else
    __old_method_missing_in_scala_rb__(sym, args)
  end
end

Right at the end, after we have transformed the method name to convert any Ruby operators into their Scala equivalents, we actually check to see if the method exists instead of blindly sending the invocation. The reason for this is to avoid creating an infinite loop in cases where a method really doesn’t exist. We can rely on the presence of bona fide methods due to the way that JRuby proxies Java objects into Scala.

Astute readers will notice the extra bit of regular expression checking right at the head of the method. We didn’t cover this in our target example, but this transformation is none-the-less quite important. Both Scala and Ruby provide mechanisms to simulate assignment to class members through method calls. In Ruby, you just suffix the method name with =, whereas in Scala the correct suffix is _=. This extra transformation looks for those situations and converts to the appropriate result. Thus, Scala var fields are now accessible within JRuby using the same syntax as standard attr_reader/attr_writer methods in Ruby.

Two other operators which might be useful to enable are the [] and []= operators, generally used for collections access. Scala doesn’t actually support these operators, reserving square brackets for declaring type parameters. However, it does provide a very similar syntax with parentheses. As a refresher, here is how we might use an array within Scala:

val arr = new Array(5)
arr(0) = 5
arr(1) = 4
arr(2) = 3
arr(3) = 2
arr(4) = 1
 
println(arr(1))        // 4

At compile-time, this translates into corresponding invocations of the apply and update methods of class Array. Specifically, apply is used to retrieve data, while update is used to assign it. These are the direct corollaries to Ruby’s [] and []=. It would only be natural to translate invocations of these operators into corresponding calls to apply and update, and we can do this simply by extending our method_missing just a little bit:

  # ...
 
  gen_with_args = proc do |name, args|
    code = "#{name}("
 
    unless args.empty?
      for i in 0..(args.size - 2)
        code += "args[#{i}], "
      end
      code += "args[#{args.size - 1}]"
    end
 
    code += ')'
  end
 
  if str == '[]'
    eval(gen_with_args.call('apply', args))
  elsif sym.to_s == '[]='
    eval gen_with_args.call('update', args)            # doesn't work right
  elsif methods.include? str
    send(str.to_sym, args)
  else
    __old_method_missing_in_scala_rb__(sym, args)
  end
end

The gen_with_args proc is merely a nifty little utility closure used to cut down on redundancy without creating an entire method. It actually generates a String of Ruby code which invokes the specified method with the given arguments. This is required because JRuby’s Java integration is only so smart. It will try to properly convert invocations of n-arity Java methods when Ruby arrays are passed as arguments, but it can only do so well. The safest route is to just call the method, passing each element of the array as a successive argument.

All of this looks quite nice, and it seems to satisfy our requirements, but there is just one problem: Ruby doesn’t behave itself with respect to the []= operator. Rather than taking the sensible approach and allowing the receiving class to define its return value, it actually ignores whatever value is returned from the []= method and forces it to be the final argument. In other words, the above code will work, but it might not integrate with Scala in quite the way we would expect. Consider our original motivating example:

import com.codecommit.collection.Vector
 
vec = Vector.new
vec = vec + 1
vec = (vec[0] = 2)       # problematic
 
puts vec[0]              # 2

Well, I said that this would be problematic. The issue is the value of the expression vec[0] = 2 is not a new Vector instance as returned by the Vector#update method, but actually the Fixnum value 2. Thus, the snippet above can never work. In what is probably the most bone-headed feature of the entire language, Ruby forces every invocation of []= to return the assigned value. This works fine (sort-of) for mutable, side-effecting implementations like Array and Scala’s ListBuffer, but it completely falls apart for immutable, functional collections like Vector. So much for a language that “makes me smile”…

The solution of course is to always be aware of these cases where the update method does not return Unit and just use update directly rather than []=. Thus, a working version of the given snippet would be as follows:

import com.codecommit.collection.Vector
 
vec = Vector.new
vec = vec + 1
vec = vec.update(0, 2)
 
puts vec[0]              # 2

By calling update directly, we ensure that its return value is captured and assigned back into vec. Kind of ugly, but unavoidable.

Step Two: Mixins

Mixins are probably the most useful and code-saving feature in the entire Scala language. Like interfaces, they provide the flexibility of multiple inheritance, but they also bring with that the DRYness of shared definitions between subtypes. In fact, it may even be safe to say that the overwhelming power of the Scala collections library is owed primarily to traits. After all, without the inherited method definitions from Iterable, each collection would have to re-implement foldLeft, map, flatMap and each of the myriad of common methods defined by collections.

It just so happens that Ruby also has mixins of a very similar variety. It seems natural then that we should be able to use Scala mixins within JRuby just as if they were standard Ruby modules. Unfortunately, Java does not have mixins, meaning that unlike operator overloading, there isn’t a nice and easy technique we can use to convert between the two worlds. The good news is that JRuby does give us a bit of a head start in making this integration work: it’s interface implementation syntax.

Ruby doesn’t support interfaces directly, but JRuby allows us to use the standard include syntax on a Java interface. Once we have included the interface and implemented its methods, we can pass an instance of our Ruby class into Java methods expecting instances of that interface. JRuby takes care of all of the magic required to proxy the method calls. Syntactically, it looks something like this

class DoSomething
  include java.lang.Runnable
 
  def run
    puts 'Running!'
  end
end

This is how we want our mixin integration to work. We should be able to include a Scala trait into a Ruby class, implement any abstract methods and then expect everything to work per-normal. In order to accomplish this, we’re going to need to override the include method to check to see if its target is a Scala trait. If that is the case, then include should create proxies for all of the defined methods within the trait. Basically, we have to do the same thing for Scala traits that Ruby does automatically for its modules.

Fortunately, this too is an area where Ruby’s notion of “open classes” will come to our rescue. Not only does Ruby allow us to add methods to classes at runtime, it also allows us to redefine core methods within the standard library; in this case, Module#include.

class Module
  alias_method :__old_include_in_scala_rb__, :include
  def include(*modules)
    modules.each do |m|
      clazz = nil
      begin
        if m.java_class.interface?
          cl = m.java_class.class_loader
          mixin_methods_for_trait(cl, cl.loadClass(m.java_class.to_s))
        end
      rescue
      end
 
      # ...
    end
 
    modules.each {|m| __old_include_in_scala_rb__ m }
  end
end

The most important thing to see here is regardless of whether or not the module in question is a trait, we still forward the inclusion onto the old definition. This is critical, because it means that JRuby is still able to create an interface proxy for that class, allowing us to pass instances of the including class into Scala and have them treated as instances of the trait in question.

The key to our actual inclusion of the defined methods is the way in which Scala compiles traits. Consider the following:

trait Test {
  def method1(): Unit
 
  def method2() {
    println("In method2()")
  }
}
 
class Usage extends Test {    // mixin
  def method1() {
    println("In method1()")
  }
}

Scala will compile this into the bytecode equivalent of the following Java code:

public interface Test {
    public void method1();
 
    public void method2();
}
 
public class Test$class {     // actually an inner-class of Test
    public static void method2(Test t) {
        System.out.println("In method2()");
    }
}
 
public class Usage implements Test {
    public void method1() {
        System.out.println("In method1()");
    }
 
    public void method2() {
        Test$class.method2(this);
    }
}

It’s very clever if you think about it. Through a bit of compile-time magic, Scala is able to keep the method definitions within traits centralized (rather than inlining everything) as well as maintain full interface-level interop with Java. It is actually possible to define a Java method which accepts as a parameter an instance of a particular trait. Since traits are interfaces, javac knows how to deal with this definition and the JVM has no problems in actually dispatching the call.

We can use this implementation detail to enable our mixin of traits into JRuby classes. We’re already testing within include to see whether or not the “module” at hand is in fact an interface, it would be a simple matter to also check for the existence of a class of the form “TraitName$class“. If such a class exists, we could loop through all of its public static members and create corresponding proxy methods within the including class. All of this is done within the mixin_methods_for_trait method:

def mixin_methods_for_trait(cl, trait_class, done=Set.new)
  return if done.include? trait_class
  done << trait_class
 
  clazz = cl.loadClass "#{trait_class.name}$class"
 
  trait_class.interfaces.each do |i| 
    begin
      mixin_methods_for_trait(cl, i, done)
    rescue
    end
  end
 
  clazz.declared_methods.each do |meth|
    mod = meth.modifiers
 
    if java.lang.reflect.Modifier.isStatic mod and \
	    java.lang.reflect.Modifier.isPublic mod
      @@trait_methods ||= []
 
      unless meth.name.include? '$'
        module_eval "\
def #{meth.name}(*args, &block)
  args.insert(0, self)
  args << block unless block.nil?
 
  args.map! do |a|
    if defined? a.java_object
      a.java_object
    else
      a
    end
  end
 
  begin
    scala_reflective_trait_methods[#{@@trait_methods.size}].invoke(nil, args.to_java)
  rescue java.lang.reflect.InvocationTargetException => e
    raise e.cause.message.to_s      # TODO  change over for 1.1.4
  end
end
"
 
        @@trait_methods << meth
      else
        define_method meth.name do |*args|    # fallback for methods with special names
          args.insert(0, self)
 
          begin
            meth.invoke(nil, args.to_java)
          rescue java.lang.reflectInvocationTargetException => e
            raise e.cause.message.to_s
          end
        end
      end
    end
  end
end

I know, the amount of code here is a little daunting, but it’s really not that bad. Essentially, this just implements our intuition about how mixins should work in Ruby. The only thing about the algorithm that we haven’t already considered is how to deal with the super-traits of traits. Since the inheriting of method definitions is only done through static proxying, there would be no reason for Scala to compile an inherited relationship between the definition class of a sub-trait and its super-trait. To get around this problem, we explicitly check for super-interfaces and then mixin their methods first. This is to allow for methods which are inherited by sub-traits and then overridden.

The final little tidbit here is the way in which the proxy methods are created. Ruby does allow us to add methods to classes at runtime, but it is unfortunately rather restrictive in how those methods can be added. In a nutshell, there are two main techniques: module_eval and define_method. By using define_method, we are able to avoid String evaluation and keep our editor’s syntax-highlighting happy with our sources. Unfortunately, methods created using define_method have a very critical limitation: they cannot accept blocks. Thus, any mixed-in trait methods which took function values as parameters would be unusable from within Ruby.

This inconsistency is fixed in Ruby 1.9, but until then we still need a way of proxying higher-order Scala methods. Thus, we default to using module_eval. Unfortunately, this technique also comes with its own set of issues; specifically: illegal characters. As we saw previously, any Scala method with a non-alphanumeric name will have to use the $ character to denote certain symbols. However, Ruby assigns special significance to symbols like $ and @, making it impossible to use them within method names. The only way around this restriction on method names is to create such special methods using define_method, which brings us right back to our first set of problems.

The only solution I could come up with for Ruby 1.8 was to use module_eval by default, unless the method name contained a $ character, in which case define_method would be used. With this technique, almost every case is covered. The only remaining issue would be if a method with a non-alphanumeric name took a function as a parameter. In this case, the method would be unusable from Ruby. However, even a cursory glance over the Scala standard library shows that this is an extremely rare case, one which can be safely made “difficult” if it means improving the integration in other areas (trait mixins).

One final unfortunate note on this method: it doesn’t work with JRuby 1.1.3 and later (the current release is 1.1.4). As reported by JRUBY-2999, including two separate Java interfaces with conflicting methods will actually cause the interpreter to crash. At the time of the writing, this bug has not been resolved, either in 1.1.4 or in the latest SVN sources. Since traits quite often have methods which overlap with inherited methods, there is really no way to get around this bug. Thus, the library described in this article was developed with JRuby 1.1.2 and will only work with that release or any upcoming releases which fix the regression. Interestingly, this means that the library must deal with a different, less critical JRuby bug which makes it impossible to raise Java exceptions. As this exception bug does not entirely prevent the use of Scala mixins, it is preferable to the more serious interpreter-crash regression.

Now that we have mixins at our disposal, it is possible to further improve our Scala integration by implementing a scala_object method for Array and Hash, one which converts these objects into a form which can be passed to Scala methods expecting Seq and Map, respectively.

class BoxedRubyArray
  include Scala::RandomAccessSeq
 
  def initialize(delegate)
    @delegate = delegate
  end
 
  def apply(i)
    @delegate[i]
  end
 
  def length
    @delegate.size
  end
end
 
class Array
  def scala_object
    BoxedRubyArray.new self
  end
end

The Hash proxy is analogous, but much more verbose. The key to this entire implementation here is the enabling of Scala mixins within JRuby. All we have to do is mixin the RandomAccessSeq trait, implement apply and length, and suddenly we have a first-class Scala collection backed by a Ruby Array. Not only does this allow us to use some of Scala’s higher-order magic on Ruby arrays, it also enables previously impossible usages like the following:

import com.codecommit.collection.Vector
 
vec = Vector.new
vec = vec + 1 + 2 + 3 + 4 + 5
 
arr = [6, 7, 8, 9, 0]
cat = vec.concat arr.scala_object

At the end of this snippet, cat is a Scala Iterable with contents [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]. Remember that concat is actually a method within Vector which itself expects an instance of Iterable. Fortunately, we now have a method to convert a Ruby array into just such an Iterable, which we then pass to concat achieving our final result.

Step Three: Closures

Both Ruby and Scala have this notion of closures, which are assignable, anonymous functions with access to their enclosing scope. Closures are most often used as a syntactic device for passing and/or storing a bit of code for later invocation. A common example that even Java has to deal with would be event handling, where a specific code block must be executed every time a button is pressed. Scala and Ruby take this concept a little further, providing higher-order functions like map and implementing conventional iteration using foreach and each (respectively).

Optimally, we should be able to call Scala methods passing Ruby blocks where Scala function values are required. As it happens, even without special Scala integration magic, we can already get very close to this:

vec = Vector.new
# ...
 
vec.foreach do |e|
  puts e
end

This will print every element in the vec instance. This works because JRuby allows blocks to be passed to methods accepting interfaces. Since Scala’s function values are in fact subtypes of traits Function0, Function1 and so on (according to arity), JRuby is able to recognize the method signatures appropriately and proxy the values.

Unfortunately, JRuby doesn’t innately understand Scala traits, so it doesn’t know that the compose method should be proxied to an implementation within the trait. I assume that JRuby will proxy every method in the target interface to the block in question (I haven’t actually tested that). Assuming this is the case, the moment that foreach (or any other method) attempts to invoke compose on a proxied JRuby block, the result will be a ClassCastException. It just so happens that foreach behaves itself and there is nothing to worry about, but we cannot make that guarantee in general.

The solution of course is to do for Ruby’s Proc what we already did for Array and Hash: provide a wrapper which uses the Functionn mixin and delegates to the Proc in question. However, unlike Array, there is no single “Function” mixin that we can use. Instead, we must create a separate wrapper for each function arity supported by Scala…all 22 of them. Fortunately, Ruby’s meta-programming capabilities help us out here, allowing us to define classes within a loop and then dynamically select the correct wrapper class name based on the Proc arity:

module ScalaProc
  class ScalaFunction
    def initialize(delegate)
      @delegate = delegate
    end
 
    def apply(*args)
      @delegate.call args
    end
  end
 
  for n in 0..22    # sneaky, but much more concise
    eval "\
class Function#{n} < ScalaFunction
  include Scala::Function#{n}
end
"
  end
end
 
class Proc
  def to_function
    eval "ScalaProc::Function#{arity}.new self"
  end
 
  def java_object
    to_function
  end
 
  def scala_object
    to_function
  end
end

The only abstract method within any of the Functionn traits is apply, taking the same number of arguments as the function arity. It’s easy enough to implement this function once within the ScalaFunction superclass, which means that all we have to do within each of the arity-specific wrappers is mixin the relevant Function.

Now that we have this conversion between Ruby Proc(s) and Scala function values, we can make use of it in situations where it becomes necessary. For example, let’s say that I have a Scala method like the following:

def doAndMultiply(by: Int)(f: (Int)=>Int) = {
  f compose { (_:Int) * by }
}

Simply put, this method takes two curried parameters, an Int along with a function value taking another Int and returning an Int. This method then returns a new function which itself takes an Int, first multiplies it by the original first Int parameter, then applies the given function to the result. Got all that?

We can call this function from Scala in the following way:

val comp = doAndMultiply(3) { _ + 2 }
comp(5)      // => 17

Now that we have our super-fancy Proc conversion, we are able to use an almost identical call syntax from within Ruby. Notice how we are able to take advantage of the way in which Scala compiles curried methods to achieve a JRuby syntax which looks almost exactly like block-standard Ruby:

add = proc {|x| x + 2 }
comp = doAndMultiply(3, add.scala_object)
 
comp.call 5        # => 17

And if doAndMultiply is a method brought in via a mixin, we can do even better:

comp = doAndMultiply 3 do |x| 
  x + 2
end
 
comp.call 5        # => 17

This works because of the way in which we coerce parameters within the proxies for the mixed-in methods. Recall from earlier:

args.map! do |a|
  if defined? a.java_object
    a.java_object
  else
    a
  end
end

The very reason we have to explicitly map over the method arguments is to satisfy this particular case. JRuby’s Ruby-to-Java coercion is pretty smart, but it doesn’t seem to be up to this particular challenge (believe me, I tried). Thankfully, a little bit of benign check-and-coerce later, our arguments are none the worse for wear and in a form that Scala can chew on.

Conclusion

As you may have guessed, I have already taken the liberty of implementing the framework described in this article. It even has a few features I didn’t discuss, like auto-detecting the default Scala installation and the ability to use Scala function values as if they were Ruby Proc(s). All in all, it makes for a very slick way of working with Scala libraries from within JRuby scripts in an intuitive, idiomatic fashion. Hopefully, this should help to encourage the use of these two fascinating technologies together in future projects.

Download scala.rb (does not work with JRuby 1.1.3 or 1.1.4)

Filed in Scala, Ruby | Comments (11)

Implicit Conversions: More Powerful than Dynamic Typing?

15
Sep
2008

One of the most surprising things I’ve ever read about Scala came in the form of a (mostly positive) review article. This article went to some lengths comparing Scala to Java, JRuby on Groovy, discussing many of its advantages and disadvantages relative to those languages. Everyone seems to be writing articles to this effect these days, so the comparison in and of itself was not surprising. What was interesting was an off-hand comment discussing Scala’s “dynamic typing” and how it aids in the development of domain specific languages.

Now this article had just finished a long-winded presentation of type inference and compilation steps, so I’m quite certain that the author was aware of Scala’s type system. The more likely target of the “dynamic typing” remark would be Scala’s implicit conversions mechanism. I have heard this language feature described many times as being a way of “dynamically” adding members to an existing class. While it would be incorrect to say that this feature constitutes a dynamic type system, it is true that it may be used to satisfy many of the same design patterns. Consider the facetious example of a string “reduction” method, one which produces an acronym based on the upper-case characters within the string:

val acronym = "Microsoft Certified Systems Engineer".reduce
println(acronym)            // MCSE

The immediate problem with this snippet is the fact that string literals are of type java.lang.String, a class which comes pre-defined by the language. The only way to ensure that the above syntax works properly is to “add” the reduce method to the String class separate from its definition. In a language such as Ruby or Groovy which have dynamic type systems, we could simply open the class definition and add a new method at runtime. However, in Scala we have to be a bit more tricky. We can’t actually add methods to an existing class, but we can define a new class which contains the desired method. Once we have that, we can define an implicit conversion from our target class to our new class. The Scala compiler sees this and performs the appropriate magic behind the scenes. In code, it looks like this:

class MyRichString(str: String) {
  def reduce = str.toCharArray.foldLeft("") { (t, c) =>
    t + (if (c.isUpperCase) c.toString else "")
  }
}
 
implicit def str2MyRichString(str: String) = new MyRichString(str)

This contrasts quite dramatically with the Ruby implementation of the same concept via open classes (somewhat less-graciously known as “Monkey Patching”):

class String
  def reduce
    arr = unpack('c*').select { |c| (65..90).include? c }
    arr.pack 'c*'
  end
end
 
puts 'HyperText Transfer Protocol'.reduce       # HTTP

No visible type conversion is taking place here, all we did is add a method to an existing class and trust that the runtime can figure out the rest. Indeed, for this application, we don’t really need anything else. However, as anyone with experience implementing internal domain-specific languages will tell you, seldom is life as simple as adding a few methods to an existing class. Consider a more complicated scenario where we need to overload the < operator on integers to operate on String values, returning true if the length of the string is less than the integer value, otherwise false. In Scala, we would once again make use of the implicit conversion mechanism, this time with an even more concise syntax:

implicit def lessThanOverload(i: Int) = new {
  def <(str: String) = str.length < i
}

In fact, we don’t even need to go this far. It is possible to create an implicit conversion from String to Int defined on the length of the String. This would allow existing method implementations within the Int class to operate upon String values:

implicit def str2Int(str: String) = str.length

As a matter of interest, this particular situation can be managed by one of the most convoluted and verbose languages on the market, C++:

bool operator<(const int &i, const std::string &str)
{
    return str.length() < i;
}

Despite the seemingly-dynamic nature of the problem, the statically typed language camp seems well represented in terms of solutions. Ironically, this sort of problem is one which will be exceedingly difficult to solve in a language like Ruby. This is primarily because method overloading is an innately static device. That’s not to say that overloading is impossible in a dynamically typed language (Groovy), but it’s not easy. To see why, let’s consider the most natural implementation of our operator problem in Ruby:

class Fixnum
  def <(str)
    str.size < self
  end
end

Intuitively, this may seem like the right way to approach the problem, but the results of such an implementation would be disastrous. At the very least, the first time anyone attempted to perform a < comparison targeting an integer, the interpreter will overflow the call stack. In fact, any time any code uses the less-than operator on an instance of Fixnum, the interpreter will crash. The reason for this is the invocation of < upon str.size within our “overloaded” definition. This call creates a very tight recursive loop which will very quickly eat through all available stack frames. We can avoid this problem by reversing the comparison like so:

class Fixnum
  def <(str)
    self >= str.size
  end
end

Now we don’t have to worry about stack overflow, but in the process we have accidentally redefined integer-to-integer comparison in a very strange way:

irb(main):006:0> 123 < 'test'
=> true
irb(main):007:0> 123 < 123
=> true

Clearly, more effort is going to be required if we are to put to rest our little dilemma. As it turns out, the final solution is surprisingly ugly and verbose:

class Fixnum
  alias_method :__old_less_than__, '<'.to_sym
  def <(target)
    if target.kind_of? String
      __old_less_than__ target.size
    else
      __old_less_than__ target
    end
  end
end

Whatever happened to Ruby as a “more elegant” language? The unfortunate truth is that in order to emulate method overloading based on input type, we must hold onto the old method implementation while we implement a type-sensitive facade in its place. The alias_method invocation literally copies the old less-than operator implementation and provides us with a way of referencing it within our later redefinition. And what happens if someone else happens to monkey patch Fixnum and (for whatever reason) uses the identifier “__old_less_than__“? Well, then we have problems. It’s like the old days of Lisp macros and endless identifier collisions.

It is true that this was an example specifically contrived to make Ruby look bad. I could have implemented the overload using Groovy’s meta-classes and been reasonably certain that everything would work out fine, but that’s not the point. The point is that there are a surprising number of situations where static typing serves not only to check for errors but also to allow extension patterns which would be otherwise impossible (or very, very difficult). Dynamic typing isn’t the panacea of extensibility that its proponents make it out to be, sometimes it isn’t quite up to the task.

In fact (and this is where we come to my Digg-friendly point), I would submit that Scala (and to a lesser extent, C++) have created a mechanism for controlled extensibility which is more powerful than Ruby’s open classes design. That’s not to say that there aren’t situations which are easily solved using open classes and entirely intractable using only implicit conversions, but in my experience these scenarios are very rare. In fact, I believe that it is far more common to run against a problem like my contrived overload which is greatly simplified through the use of static typing.

Ironically enough, some of Ruby’s greatest pundits are starting to come around to the belief that a more controlled and well-defined model of class extension is required. ParseTree is a Ruby framework which provides mechanisms for dynamically manipulating the AST of an expression prior to evaluation. Conceptually, it is very similar to Lisp’s macros and peripherally related to .NET’s expression trees (used in LINQ). ParseTree is used by a number of complex Ruby domain-specific languages, including Ambition, a fact which is extremely telling of how great the need is for just such a tool. Having myself attempted a domain-specific language for constructing queries, I can state categorically that to do such a thing solely on the basis of open classes would be nearly impossible. Even if successful, such a framework would be extremely volatile, sensitive to the slightest change in the Ruby core library, either caused by update or by other packages injecting their own meddlesome implementations into runtime classes.

Lex Spoon (co-author of Programming in Scala) once said that any language which seriously targeted domain-specific languages would have to create some sort of implicit conversion mechanism. At the time, I was skeptical, convinced that Ruby (and similar) would always have the upper-hand in the area of class extension due to their dynamic treatment of modules and classes. However, after some serious dabbling in the field of internal domain-specific languages, I’m beginning to come ’round to his point of view. Implicit conversions are far from a weak imitation of Scala’s dynamically typed “betters”, they are a powerful and controlled way of extending types far beyond anything which can be easily accomplished through open classes.

Filed in Scala, Ruby | Comments (15)

Implementing Persistent Vectors in Scala

26
Aug
2008

Oh yeah, we’re really getting into Digg-friendly titles now, aren’t we?

The topic of persistent vectors is one of those odd backwaters of functional programming that few dare to approach. The basic idea behind it all is to try to devise an immutable data structure which has the performance characteristics of a mutable vector. What this means for practical application is that you shouldn’t have to deal with O(n) efficiency on random access like you do with List(s). Instead, accessing arbitrary indexes should be constant time (O(1)), as should computing its length. Additionally, modifying an arbitrary index should be reasonably efficient - as close to constant-time as possible.

Of course, the word “modifying” is a trifle inaccurate as it implies a mutable data structure. One of the primary qualifications for a purely functional vector is that it is completely immutable. Any changes to the vector result in the creation of a new vector, rather than modifying the old. Basically, it’s an immutable data structure just like any other, but one which retains the brutal efficiency of its mutable counterpart.

Unfortunately, this turns out to be a very tough nut to crack. A number of researchers have attempted different strategies for solving the problem, none of which have been entirely successful. Rich Hickey, the creator of Clojure, has a brilliant presentation that essentially describes the solution I have chosen. For the impatient, the good stuff starts at about 36:00 and lasts for about ten minutes. I’ll elaborate on the problems with functional vectors a bit more in a second, but first a bit of motivational propaganda…

Thou Shalt Not Mutate

There is a single principle which should be drilled into skulls of all programmers everywhere: mutable data structures are bad news. Don’t get me wrong, I love ArrayList as much as the Java addict, but such structures cause serious problems, particularly where concurrency is concerned. We can consider the trivial example where two threads are attempting to populate an array simultaneously:

private String[] names = new String[6];
private int index = 0;
 
public static void main(String[] args) {
    Thread thread1 = new Thread() {
        public void run() {
            names[index++] = "Daniel";
            names[index++] = "Chris";
            names[index++] = "Joseph";
        }
    };
 
    Thread thread2 = new Thread() {
        public void run() {
            names[index++] = "Renee";
            names[index++] = "Bethany";
            names[index++] = "Grace";
        }
    };
 
    thread1.start();
    thread2.start();
 
    thread1.join();
    thread2.join();
 
    for (String name : names) {
        System.out.println(name);
    }
}

What does this snippet print? I don’t know. It’s actually indeterminate. Now we can guess that on most machines the result will be essentially interleaved between the two threads, but there is no way to guarantee this. Part of the reason for this is the fact that arrays are mutable. As such, they enable (and indeed, encourage) certain patterns which are highly destructive when employed asynchronously.

However, concurrency is not even the only motivation for immutable data structures. Consider the following example:

List<String> names = ...
for (String name : names) {
    names.add(name.toUpperCase());
}

I’m sure all of us have done something like this, most likely by accident. The result is (of course) a ConcurrentModificationException caused by the fact that we are attempting to add to a List while we are iterating over its contents. I know that the first time I was faced with this error message I became extremely confused. After all, no threads are being employed, so why is this a problem?

Iterators are extremely dependent on the internal state of their data structure. Anyone who has ever implemented an iterator for a linked list or (even better) a tree will attest to this fact. This means that generally speaking, there is no way for an iterator to guarantee correctness if that structure is changing out from underneath it (so to speak). Things may be fine in a linear structure like a list, but as soon as you get into anything non-linear like a tree or a hash table it becomes difficult to even define what the “correct” behavior should be. Think about it; should the iterator backtrack to hit the missing elements? Should this backtracking include elements which have already been consumed? What if the order changes dramatically and pre-consumed elements are now ahead of the current index? There are a whole host of problems associated with iterating over mutable data structures, and so rather than vainly attempt to solve these issues in a sane and consistent manner, JDK collections simply throw an exception.

All of this becomes moot once you start using immutable data structures. There is no way to modify a structure while iterating over it because there is no way to modify the structure at all! Concurrency is not an issue because without any mutable state to require locking, every thread can operate simultaneously on the structure. Not only is it thread safe, but it is unsynchronized and thread safe. Immutable data structures retain all of the asynchronous throughput of non-locking implementations without any of the race conditions and non-determinacy which usually results.

A Brief Note on Idioms

At this point, the question you must be asking yourself is: “So if the data structure is immutable, what good is it?” The answer is “for reading”. Data structures spend most of their lives being read and traversed by other code. Immutable data structures can be read in exactly the same fashion as mutable ones. The trick of course is constructing that data structure in the first place. After all, if the data structure is completely immutable, where does it come from? A simple example from a prior article is sufficient to demonstrate both aspects:

def toSet[T](list: List[T]): Set[T] = list match {
  case hd :: tail => hd + toSet(tail)
  case Nil => Set[T]()
}

This is neither the most concise nor the most efficient way to accomplish this task. The only purpose served by this example is to illustrate that it is very possible to build up immutable data structures without undue syntactic overhead. You’ll notice that every time we want to “change” a data structure - either removing from the list or adding to the set - we use a function call and either pass or return the modified structure. In essence, the state is kept entirely on the stack, with each new version of the data structure in question becoming the “changed” version from the previous operation.

This idiom is actually quite powerful and can be applied to even more esoteric (and less uniformly iterative) operations. As long as you are willing to let execution jump from one function to the next, it becomes extremely natural to deal with such immutability. In fact, you start to think of immutable data structures as if they were in fact mutable, simply due to the fact that you are idiomatically “modifying” them at each step. Note that this pattern of modifying data between functions is critical to actor-based programming and any seriously concurrent application design.

Problems Abound

For the sake of argument, let’s assume that my pitiful arguments have convinced you to lay aside your heathen mutating ways and follow the path of functional enlightenment. Let’s also assume that you’re consumed with the desire to create an application which tracks the status of an arbitrary number of buttons. These buttons may be pressed in any order regardless of what other buttons are already pressed. Following the path of immutability and making use of the patron saint of persistent data structures (List), you might come up with the following solution:

class ButtonStrip private (buttons: List[Boolean]) {
  def this(num: Int) = {
    this((0 until num).foldLeft(List[Boolean]()) { (list, i) =>
      false :: list
    })
  }
 
  def status(index: Int) = buttons(index)
 
  def push(index: Int) = modify(index, true)
 
  def unpush(index: Int) = modify(index, false)
 
  /**
   * Modify buttons list and return a new ButtonStrip with the results.
   */
  private def modify(index: Int, status: Boolean) = {
    val (_, back) = (buttons :\ (buttons.length - 1, List[Boolean]())) { (tuple, button) =>
      val (i, total) = tuple
      (if (i == index) status else button) :: total
    }
    new ButtonStrip(back)
  }
}

This is a horrible mess of barely-idiomatic functional code. It’s difficult to read and nearly impossible to maintain; but it’s purely immutable! This is not how you want your code to look. In fact, this is an excellent example of what David MacIver would call “bad functional code“.

Perhaps even worse than the readability (or lack thereof) is the inefficiency of this code. It’s terribly slow for just about any sort of operation. Granted, we can imagine this only being used with a list of buttons of limited length, but it’s the principle of the thing. The fact is that we are relying on a number of operations which are extremely inefficient with lists, most prominently length and apply() (accessing an arbitrary index). Not only that, but we’re recreating the entire list every time we change the status of a single button, something which is bad for any number of reasons.

What we really need here is a random-access structure, something which allows us to access and “change” any index with some degree of efficiency. Likely the most intuitive thing to do here would be to just use a good ol’ array of Boolean(s) and make a new copy of this array any time we need to change something. Unfortunately, this is almost as bad as our copying the list every time. Normally, when you use an immutable data structure, modifications do not require copying large amounts of data. Our toSet example from above uses almost zero data copying under the surface, due to the way that Set and List are implemented.

Specifically, Set and List are persistent data structures. This doesn’t mean that they live on a filesystem. Rather, the term “persistent” refers to the fact that each instance of the collection may share significant structure with another instance. For example, prepending an element onto an immutable list yields a new list which consists of the new element and a tail which is precisely the original list. Thus, each list contains its predecessor (if you will) within itself. List is an example of a fully persistent data structure; not everything can be so efficient. Set and Map for example are usually implemented as some sort of tree structure, and so insertions require some data copying (specifically, the parent nodes). However, this copying is minimized by the nature of the structure. This notion of persistence in the data structure works precisely because these structures are immutable. If you could change an element in a persistent data structure it would likely result in the modification of that same element in totally disparate instances of that structure across the entire runtime (not a pleasant outcome).

So List is persistent, arrays are not. Even if we treat arrays as being completely immutable, the overhead of copying a potentially huge array on each write operation is rather daunting. What we need is some sort of data structure with the properties of an array (random access, arbitrary modification) with the persistent properties of a list. As I said before, this turns out to be a very difficult problem.

Partitioned Tries

One solution to this problem which provides a compromise between these two worlds is that of a partitioned trie (pronounced “try” by all that is sane and holy). In essence, a partitioned trie is a tree of vectors with a very high branching factor (the number of children per node). Each vector is itself a tree of vectors and so on. Note that these are not not like the binary search trees that every had to create back in college, partitioned tries can potentially have dozens of branches per node. As it turns out, it is this unusual property which makes these structures so efficient.

To get a handle on this concept, let’s imagine that we have a trie with a branching factor of 3 (much smaller than it should be, but it’s easier to draw). Into this vector we will insert the following data:

Index	Data
`0`	Daniel
`7`	Chris
`2`	Joseph
`4`	Renee
`1`	Bethany
`3`	Grace
`9`	Karen
`13`	Larry
`5`	Moya

After all the jumbling necessary to make this structure work, the result will look like the following:

It’s hard to see where the “trie” part of this comes into play, so bear with me. The important thing to notice here is the access times for indexes 0-2: it’s O(1). This is of course a tree, so not all nodes will be one step away from the root, but the point is that we have achieved constant-time access for at least some of the nodes. Mathematically speaking, the worst-case access time for any index n is O( log₃(n) ). Not too horrible, but we can do better.

First though, we have to lay some groundwork. I said that the structures we were working with are tries rather than normal trees. A trie implies that the key for each element is encoded in the path from the root to that node. So far, it just appears that we have built a fancy tree with numeric keys and a higher branching factor than “normal”. This would be true if all we were given is the above diagram, but consider the slightly modified version below:

Structurally, nothing has changed, but most of the edges have been renumbered. It is now a bit more apparent that each node has three branches numbered from 0 to 2. Also, with a little more thought, we can put the rest of the pieces together.

Consider the “Moya” node. In our input table, this bit of data has an index of 5. To find its “index” in our renumbered trie, we follow the edges from the root down to the destination node, arriving at a value of 12. However, remember that each node has only 3 branches. Intuitively, we should be thinking about base-3 math somewhere about now. And indeed, converting 12 into base-3 yields a final value of 5, indicating that the index of the node is indeed encoded in the path from the root based on column. By the way, this works on any node (try it yourself). The path to “Karen” is 100, which converted into base-3 becomes 9, the input index of the element.

This is all fine and dandy, but we haven’t really solved our original problem yet: how to achieve constant-time access to arbitrary indexes in a persistent structure. To really approach a solution to our problem, we must increase the branching factor substantially. Rather than working with a branching factor of 3 (and thus, O( log₃(n) ) efficiency), let’s dial the branching factor up to 32 and see what happens.

The result is completely undiagramable; but it does actually provide constant time access for indexes between 0 and 31. If we were to take our example data set and input it into our revised trie, the result would be a single layer of nodes, numbered at exactly their logical index value. In the worst case, the efficiency of our more complicated trie is O( log₃₂(n) ). Generally speaking, we can infer (correctly) that for any branching factor b and any index n, the lookup efficiency will be precisely log_b(n). As we increase the branching factor, the read-efficiency of our trie increases exponentially. To put a branching factor of 32 into perspective, this means that the algorithmic complexity of accessing index 1,000,000 would only be 3.986! That’s incredibly small, especially given the sheer magnitude of the index in question. It’s not technically constant time, but it’s so incredibly small for all conceivable indexes that we can just pretend that it is. As Rich Hickey says:

…when it’s a small enough value, I really don’t care about it.

So that takes care of the reading end of life, but what about writing? After all, if all we needed was constant time lookups, we could just use an array. What we really need to take care to do is ensure that modifications are also as fast as we can make them, and that’s where the tricky part comes in.

We can think of an array as a partitioned trie with a branching factor of . When we modify an array immutably, we must copy every element from the original array into a new one which will contain the modification. This contrasts with List - effectively, a partitioned trie with a branching factor of 1 - which in the best case (prepending) requires none of the elements to be copied. Our 32-trie is obviously somewhere in between. As I said previously, the partitioned trie doesn’t really solve the problem of copying, it just compromises on efficiency somewhat (the difference between 1 and 3.986).

The truth is that to modify a partitioned trie, every node in the target sub-trie must be copied into a new subtrie, which then forces the copying of its level and so-on recursively until the root is reached. Note that the contents of the nodes are not being copied, just the nodes themselves (a shallow copy). Thus, if we return to our example 3-trie from above and attempt to insert a value at index 12, we will have to copy the “Larry” node along with our new node to form the children of a copy of the “Renee” node. Once this is done, the “Grace” and “Moya” nodes must also be copied along with the new “Renee” to form the children of a new “Bethany”. Finally, the “Daniel” and “Joseph” nodes are copied along with the new “Bethany” to form the children of a new root, which is returned as the modified trie. That sounds like a lot of copying, but consider how much went untouched. We never copied the “Karen” or the “Chris” nodes, they just came over with their parent’s copies. Instead of copying 100% of the nodes (as we would have had it been an array), we have only copied 80%. Considering that this was an example contrived to force the maximum copying possible, that’s pretty good!

Actually, we can do even better than this by storing the children of each node within an array (we would have to do this anyway for constant-time access). Thus, only the array and the modified nodes need be copied, the other nodes can remain untouched. Using this strategy, we further reduce the copying from 80% to 30%. Suddenly, the advantages of this approach are becoming apparent.

Now of course, the higher the branching factor, the larger the arrays in question and so the less efficient the inserts. However, insertion is always going to be more efficient than straight-up arrays so long as the inserted index is greater than the branching factor. Considering that most vectors have more than 32 elements, I think that’s a pretty safe bet.

Implementation

I bet you thought I was going to get to this section first. Foolish reader…

Once we have all this theoretical ground-work, the implementation just falls into place. We start out with a Vector class parameterized covariantly on its element type. Covariant type parameterization just means that a vector with type Vector[B] is a subtype of Vector[A] whenever B is a subtype of A. List works this way as well, as do most immutable collections, but as it turns out, this sort of parameterization is unsafe (meaning it could lead to a breakdown in the type system) when used with mutable collections. This is part of why generics in Java are strictly invariant.

Coming back down to Earth (sort of), we consider for our design that the Vector class will represent the partitioned trie. Since each child node in the trie is a trie unto itself, it is only logical to have each of the nodes also represented by Vector. Thus, a Vector must have three things:

data
length
branches

Put into code, this looks like the following:

class Vector[+T] private (private val data: Option[T], 
      val length: Int, private val branches: Seq[Vector[T]]) extends RandomAccessSeq[T] {
  def this() = this(None, 0, new Array[Vector[T]](BRANCHING_FACTOR))
 
  // ...
}

RandomAccessSeq is a parent class in the Scala collections API which allows our vector to be treated just like any other collection in the library. You’ll notice that we’re hiding the default constructor and providing a no-args public constructor which instantiates the default. This only makes sense as all of those fields are implementation-specific and should not be exposed in the public API. It’s also worth noting that the branches field is typed as Seq[Vector[T]] rather than Array[Vector[T]]. This is a bit of a type-system hack to get around the fact that Array is parameterized invariantly (as a mutable sequence) whereas Seq is not.

With this initial design decision, the rest of the implementation follows quite naturally. The only trick is the ability to convert an index given in base-10 to the relevant base-32 (where 32 is the branching factor) values to be handled at each level. After far more pen-and-paper experimentation than I would like to admit, I finally arrived at the following solution to this problem:

def computePath(total: Int, base: Int): List[Int] = {
  if (total < 0) {
    throw new IndexOutOfBoundsException(total.toString)
  } else if (total < base) List(total) else {
    var num = total
    var digits = 0
    while (num >= base) {
      num /= base
      digits += 1
    }
 
    val rem = total % (Math.pow(base, digits)).toInt
 
    val subPath = computePath(rem, base)
    num :: (0 until (digits - subPath.length)).foldRight(subPath) { (i, path) => 0 :: path }
  }
}

As a brief explanation, if our branching factor is 10 and the input index (total) is 20017, the result of this recursive function will be List(2, 0, 0, 1, 7). The final step in the method (dealing with ranges and folding and such) is required to solve the problem of leading zeroes dropping off of subsequent path values and thus corrupting the final coordinates in the trie.

The final step in our implementation (assuming that we’ve got the rest correct) is to implement some of the utility methods common to all collections. Just for demonstration, this is the implementation of the map function. It also happens to be a nice, convenient example of good functional code.

override def map[A](f: (T)=>A): Vector[A] = {
  val newBranches = branches map { vec =>
    if (vec == null) null else vec map f
  }
 
  new Vector(data map f, length, newBranches)
}

Properties

Before moving on from this section, it’s worth noting that that our implementation of the vector concept has some rather bizarre properties not held by conventional, mutable vectors. For one thing, it has a logically infinite size. What I mean by this is it is possible to address any positive integral index within the vector without being concerned about resize penalties. In fact, the only addresses which throw an IndexOutOfBoundsException are negative. The length of the vector is defined to be the maximum index which contains a valid element. This actually mirrors the semantics of Ruby’s Array class, which also allows placement at any positive index. Interestingly enough, the efficiency of addressing arbitrary indexes is actually worst-case much better in the persistent trie than it is in a conventional amortized array-based vector.

Vectored Buttons

Since we now have an immutable data structure with efficient random-access, we may as well rewrite our previous example of the button strip using this structure. Not only is the result far more efficient, but it is also intensely cleaner and easier to read:

class ButtonStrip private (buttons: Vector[Boolean]) {
  def this(num: Int) = this(new Vector[Boolean])     // no worries about length
 
  def status(index: Int) = buttons(index)
 
  def push(index: Int) = new ButtonStrip(buttons(index) = true)
 
  def unpush(index: Int) = new ButtonStrip(buttons(index) = false)
}

You’ll notice that the update method is in fact defined for Vector, but rather than returning Unit it returns the modified Vector. Interestingly enough, we don’t need to worry about length allocation or anything bizarre like that due to the properties of the persistent vector (infinite length). Just like arrays, a Vector is pre-populated with the default values for its type. In the case of most types, this is null. However, for Int, the default value is 0; for Boolean, the default is false. We exploit this property when we simply return the value of dereferencing the vector based on any index. Thus, our ButtonStrip class actually manages a strip of infinite length.

Conclusion

The truth is that we didn’t even go as far as we could have in terms of optimization. Clojure has an implementation of a bit-partitioned hash trie which is basically the same thing (conceptually) as the persistent vector implemented in this article. However, there are some important differences.

Rather than jumping through strange mathematical hoops and hacky iteration to develop a “path” to the final node placement, Clojure’s partitioned trie uses bit masking to simply choose the trailing five bits of the index. If this node is taken, then the index is right-shifted and the next five bits are masked off. This is far more efficient in path calculation, but it has a number of interesting consequences on the final shape of the trie. Firstly, the average depth of the tree for random input is less, usually by around 1 level (on average). This means that the array copying on insert must occur less frequently, but must copy more references at each step. Literally, the trie is more dense. This probably leads to superior performance. Unfortunately, it also requires that the index for each value be stored along with the node, requiring more memory. Also, this sort of “bucket trie” (to coin a phrase) is a little less efficient in lookups in the average case. Not significantly so, but the difference is there. Finally, this masking technique requires that the branching factor be a multiple of 2. This isn’t such a bad thing, but it does impose a minor restriction on the flexibility of the trie.

Most importantly though, Clojure’s trie uses two arrays to contain the children: one for the head and one for the tail. This is a phenomenally clever optimization which reduces the amount of array copying by 50% across the board. Rather than having a single array of length 32, it has two arrays of length 16 maintained logically “end to end”. The correct array is chosen based on the index and recursively from there on down the line. Naturally, this is substantially more efficient in terms of runtime and heap cost on write.

At the end of the day though, these differences are all fairly academic. Just having an idiomatic partitioned trie for Scala is a fairly significant step toward functional programming relevance in the modern industry. With this structure it is possible to still maintain lightning-fast lookup times and decent insertion times without sacrificing the critical benefits of immutable data structures. Hopefully structures like this one (hopefully, even better implementations) will eventually find their way into the standard Scala library so that all may benefit from their stream-lined efficiency.

Vector.scala
VectorSpecs.scala (ScalaCheck rocks)

Update

The implementation of Vector which I present in this article is inherently much less efficient than the one Rich Hickey created for Clojure. I finally broke down and created a line-for-line port from Clojure’s Java implementation of PersistentVector into a Scala class. I strongly suggest that you use this (much faster) implementation, rather than my own flawed efforts. :-) You can download the improved Vector here: Vector.scala.

Filed in Scala | Comments (31)

How Do You Apply Polyglotism?

18
Aug
2008

For the past two years or so, there has been an increasing meme across the developer blogosphere encouraging the application of the polyglot methodology. For those of you who have been living under a rock, the idea behind polyglot programming is that each section of a given project should use whatever language happens to be most applicable to the problem in question. This makes for a great topic for arm-chair bloggers, leading to endless pontification and flame-wars on forum after forum, but it seems to be a bit more difficult to apply in the real world.

The fact is that very few companies are open to the idea of diversity in language selection. Just look at Google, one of the most open-minded and developer-friendly companies around. They employ some of the smartest people I know, programmers who have actually invented languages with wide-scale adoption. However, this same company mandates the use of a very small set of languages including Python, Java, C++ and JavaScript. If a company like Google can’t even bring itself to dabble in language diversity, what hope do we have for the Apples of the world?

A few months ago, I received an internal email from the startup company where I work. This email was putting forth a new policy which would restrict all future developments to one of two languages: PHP or Java. In fact, this policy went on to push for the eventual rewrite of all legacy projects which had been written in other languages including Objective-C, Ruby, Python and a fair number of shell scripts. I was utterly flabbergasted (to say the least). A few swift emails later, we were able to come to a more moderate position, but the prevailing attitude remains extremely focused on minimizing the choice of languages.

To my knowledge, this sort of policy is fairly common in the industry. Companies (particularly those employing consultants) seem to prefer to keep the technologies employed to a minimum, focusing on the least-common denominator so as to reduce the requirements for incoming developer skill sets. This is rather distressing to me, because I get a great deal of pleasure out of solving problems differently using alternative languages. For example, I would have loved to build the clustering system at my company using the highly-scalable actor model with Scala, but the idea was shot down right out of the gate because it involved a non-mainstream language. To be fair to my colleagues, the overall design involved was given more serious consideration, but it was always within the confines of Java, rather than the original actor-driven concept.

There is actually another aspect to this question: assuming you are allowed to use a variety of languages to "get the job done", how do you apply them? Ola Bini has talked about the various layers of a system, but this is harder to see in practice than it would seem. How do you define where to "draw the line" between using Java and Scala, or even the more dramatic differences between Java and JRuby or Groovy? Of course, we can base our decision strictly on lines of code, but in that case, Scala would trump Java every time. For that matter, Ruby would probably beat out the two of them, and I’m certainly not writing my next large-scale enterprise app exclusively in a dynamic language.

I realize this is somewhat of a cop-out post, just asking a question and never arriving at a satisfactory conclusion, but I would really like to know how other developers approach this issue. What criteria do you weigh in making the decision to go with a particular language? What sorts of languages work well for which tasks? And above all, how do you convince your boss that this is the right way to go? The floor is open, please enlighten me!

Filed in Java | Comments (19)

Scala Collections for the Easily Bored Part 2: One at a Time

28
Jul
2008

As I hinted previously, this series is intended to delve into Scala’s extensive collections API and the many ways in which it can make your life easier. Probably the most important operations you could ever perform on collections are those which examine each element, one at a time. After all, what’s a more common array idiom than looping over all values?

In that vein, this article starts by looking at foreach, the imperative programmer’s bread-and-butter when it comes to types like Array and List. But rather than just stopping there, we also will look at more powerful, higher-order operations like fold, map and the ever-mysterious: flatMap.

Iterating

As I said above, looping over every item in a collection is probably the most heavily used operation in a programmer’s repertoire. In fact, this pattern is so common in imperative languages that Java 5 saw the introduction of a special construct at the language level, just to make things a little easier. For example:

String[] names = { "Daniel", "Chris", "Joseph" };
for (String name : names) {
    System.out.println(name);
}

This code should be old hat to anyone coming from a Java background. Under the surface, this code is compiled into a while-loop with an iterator and an increment operation. The code steps through the array, assigning each successive element to name. Most statically typed languages have a construct similar to this. For example, C# offers the foreach statement, which is almost precisely similar to Java’s enhanced for-loop, but with a slightly different syntax. However, some languages (like Ruby) idiomatically eschew loops and rely instead on higher-order methods. Translating the above into Ruby yields the following:

names = ['Daniel', 'Chris', 'Joseph']
names.each do |name|
  puts name
end

In this case, we aren’t using a loop of any kind, but rather creating a block (Ruby’s name for a closure) which takes a single parameter and passes it to the built-in puts method. This block is then passed as an object to the each method of class Array, which calls the block once for each element in series. Certainly, there is a language construct which encapsulates this, but using the each method directly is considered more “Ruby”.

The same approach is taken in Scala. Rather than define a special construct for iteration, Scala simply provides the syntactic tools needed to construct higher-order methods like Ruby’s each. Every collection in Scala’s library defines (or inherits) a foreach method (taking after its C# ancestry) which behaves precisely like Ruby’s each. To show how, we will translate our example once more, this time into Scala:

val names = Array("Daniel", "Chris", "Joseph")
names.foreach { name =>
  println(name)
}

Here we define an anonymous method (Scala’s name for a closure) which takes a single parameter. As in Ruby, this closure is passed to foreach and invoked for each array element. In this way, foreach is a a so-called “higher-order” method, due to the fact that it accepts a parameter which is itself another method. Scala’s implementation of this concept is actually a bit more general than Ruby’s, allowing us to shorten our example into the following:

val names = Array("Daniel", "Chris", "Joseph")
names.foreach(println)

This time, instead of creating an anonymous method to pass to foreach, we simply pass the println method itself. The only criterion that foreach imposes on its parameter is that it is a method which accepts a single parameter of type String (the element type of the array). Since we already have just such a method (println), there is no need to define another simply for encapsulation.

Unfortunately, despite its flexibility, foreach is not always the most syntactically concise way to iterate over a collection. There are times that we just want to use a syntax which is similar to the for-loops available in other languages. Well, fear not! Scala’s for-comprehensions are more than capable of providing just such a syntax. Consider the example of imperatively summing the values of a list:

val nums = List(1, 2, 3, 4, 5)
 
var sum = 0
for (n <- nums) {
  sum += n
}

At compile-time, the above is actually translated into an equivalent call to foreach, passing the body of the loop as the anonymous method. This means that any class which correctly declares a foreach method may be used in a for-comprehension in this way, greatly reducing the syntactic overhead.

Folding

Looping is nice, but sometimes there are situations where it is necessary to somehow combine or examine every element in a collection, producing a single value as a result. An example of this could be our previous example of summing a list. Using foreach, we had to make use of a mutable variable (sum) and produce the result as a side effect. This is fine for hybrid languages like Scala, but some languages actually lack mutable variables altogether. In the previous post, I mentioned ML, which is a pure-functional language (almost). Since pure-functional languages lack mutable state, the gods of computing needed to come up with some other way to accommodate this particular case. The solution is called “folding”.

Folding a collection is literally the process of looking at each element in addition to a current accumulator and returning some value. To make things more clear, let’s re-write our list summing example in a functional style:

val nums = List(1, 2, 3, 4, 5)
val sum = nums.foldLeft(0) { (total, n) =>
  total + n
}

It may seem a bit disguised, but this too is a loop, just like foreach. For each element in the list (starting from the left), the foldLeft method will call the anonymous method we passed to it, providing both the current element, as well as the total accumulated from the previous call. Since there was no previous call when the first element is processed, we must specify an initial value for total - in this case, 0. Literally, the above can be flattened into the following:

val sum = 0 + 1 + 2 + 3 + 4 + 5

Of course, we would never want to hard-code a list in this fashion, but it serves as a sufficient illustration of the functionality. I know from experience that when you first discover fold it’s difficult to see why anyone would want to use a construct so limited. After all, doesn’t it just serve to obscure the true meaning of the code? Well, take my word for it, fold is an almost indispensable tool…once you get to know it a little better. Try keeping an eye out for times in your own code where a fold might be useful instead of a conventional loop. You’ll be surprised how often it can be used to solve a problem, sometimes one not even intuitively related to accumulation.

There’s no special language-level syntax for fold, but Scala’s powerful operator overloading mechanism has allowed the designers of the collections API to create a special operator of rather dubious readability. To illustrate, here’s our “summing a list” example once more:

val nums = List(1, 2, 3, 4, 5)
(0 /: nums) {_+_}

Yeah, I can’t read it either. This example is semantically equivalent to the previous fold, but its meaning is a bit obfuscated by a) the bizarre right-associative operator, and b) a mysterious cameo by Scala’s ubiquitous underscore. While I don’t have a problem using the underscore syntax in my own code, I don’t think that the fold operator improves anything other than number of characters. I suppose it’s a matter of taste though.

Reduce

Fold has a closely related operation in Scala called “reduce” which can be extremely helpful in merging the elements of a sequence where leading or trailing values might be a problem. Consider the ever-popular example of transforming a list of String(s) into a single, comma-delimited value:

val names = List("Daniel", "Chris", "Joseph")
val str = names.foldLeft("") { (acc, n) =>
  acc + ", " + n
}
 
println(str)

If you compile and run this code, you will actually arrive at a result which looks like the following:

, Daniel, Chris, Joseph

This is because folding a list requires a leading value, but this means that we have an extra separator running wild. We could try a foldRight, but this would merely move the same problem to the tail of the string. Interestingly enough, this problem of leading/trailing separators is hardly specific to folding. I can’t tell you how many times I ran into this issue when constructing highly-imperative query synthesis algorithms for ActiveObjects.

The easiest way to solve this problem in Scala is to simply use a reduce, rather than a fold. As a rule, any collection which defines foldLeft will also define reduceLeft (and the corresponding right methods). Reduce distinguishes itself from fold in that it does not require an initial value to “prime the sequence” as it were. Rather, it starts with the very first element in the sequence and moves on to the end. Thus, the following code will produce the desired result for our names example:

val names = List("Daniel", "Chris", "Joseph")
val str = names.reduceLeft[String] { (acc, n) =>
  acc + ", " + n
}
 
println(str)

There are of course a few small problems with this approach. Firstly, it is not as general as a fold. Reduce is designed primarily for the iterate/accumulate pattern, whereas fold may be applied to many problems (such as searching a list). Also, the reduce method will throw an exception if the target collection is empty. Finally, Scala’s type inference isn’t quite clever enough to figure out what’s going on without the explicit [String] type parameter (since our result is of type String). Still, even with all these shortcomings, reduce can be a very powerful tool in the right hands.

Mapping

We’ve seen how fold can be an extremely useful tool for applying a computation to each element in a collection and arriving at a single result, but what if we want to apply a method to every element in a collection in-place (as it were), creating a new collection of the same type with the modified elements? Coming from an imperative background, this probably sounds a little abstract, but like fold, map can be extremely useful in many common scenarios. Consider the example of transforming a list of String(s) into a list of Int(s):

val strs = List("1", "2", "3", "4", "5")
val nums = strs.map { s =>
  s.toInt
}
 
nums == List(1, 2, 3, 4, 5)   // true

The final expression in this snippet is just to illustrate what really happens to the list elements when map is called. Literally, the map method walks through each element in the list, calls the provided method and then stores the result in the corresponding index of a new list. (list is immutable, remember?) If you think about it, this is very similar to looping with foreach except that at each iteration we produce a value which is saved for future use.

Another common application of this technique might be to cast an entire array from one type to another. I often make use of XMLRPC, which has the unfortunate property of stripping all type information from its composite types. Thus, I often find myself writing code like this:

public void rpcMethod(Object[] params) {
    String[] strParams = new String[params.length];
    for (int i = 0; i < params.length; i++) {
        strParams[i] = (String) params[i];
    }
}

It’s a lot of trouble to go through, but I really don’t know any better way. We can’t just cast the array to String[], since the array itself is not of type String[], only its elements match that type. Java doesn’t support higher-order operations such as map, but fortunately Scala does. We can translate the above into a functional style and gain tremendously in both readability and conciseness:

def rpcMethod(params: Array[Object]) {
  val strParams = params.map { _.asInstanceOf[String] }
}

For the sake of brevity, you’ll notice that I made use of the underscore syntax as a placeholder for the anonymous method parameter. This syntax works remarkably well for short operations like the above, where all we need to do is take the input value and cast it to a new type.

As it turns out, mapping over a collection is a phenomenally common operation, perhaps even more so than fold. For that reason, the creators of Scala decided that it was worth adding a special syntax sugar built into the powerful for-comprehension mechanism. With a little bit of tweaking, we can transform our casting example into an arguably more readable form:

def rpcMethod(params: Array[Object]) {
  val strParams = for (p <- params) yield p.asInstanceOf[String]
}

At compile-time, these two forms are literally equivalent. In some ways it is a matter of taste as to which is better. I personally tend to favor directly calling map for simple, non-combinatorial operations like this, but to each his own.

Binding

Actually, the name “bind” comes from Haskell. Scala’s term for this operation is “flatMap” because the operation may be viewed as a combination of the map and flatten methods. Of all of the techniques discussed so far, this one probably has the richest theoretical implications. Coming straight from the menacing jungles of category theory and the perplexing wasteland of monads, flatMap is both intriguing and apparently useless (at first glance anyway).

Like map, flatMap walks through every element in a collection and applies a given function, saving the value for later use. However, unlike map, flatMap expects the return type of the specified function to be the same as the enclosing collection with an optionally different type parameter. If we look at this in terms of our number-converting example from previously, this means that our anonymous method must not return a value of type Int, but rather of type List[Int]. Once flatMap has all of the resultant List[Int] values, it flattens them into a single list containing all of the elements from each of the inner lists.

Ok, that was utterly un-helpful. Maybe the method signature would be more illuminating:

class List[A] {   // don't try this at home
  def flatMap[B](f: (A)=>List[B]): List[B]
}

Other than forcing order of evaluation, I can’t personally think of too many common cases where this sort of operation is useful. However, one contrived example does spring to mind. Consider once more the example of converting a list of String(s) into a list of Int(s), but this time assume that some of the String elements might not nicely convert into integer values:

val strs = List("1", "two", "3", "four", "five")
val nums = strs.flatMap { s =>
  try {
    List(s.toInt)
  } catch {
    case _ => Nil
  }
}
 
nums == List(1, 3)    // true

Recall that in Scala, everything is an expression - including try/catch blocks - therefore, everything has a value. This code literally walks through the entire list and tries to convert each element into an integer and wrap the result in a List. If the conversion fails (for whatever reason), an empty list is returned (Nil). Because we return an empty list for those elements which cannot be converted, flatMap literally resolves those results out of existence, leading to a List which only contains two Int(s). For the monadically uninclined among us, this is precisely the reason why Nil is referred to as the “zero” of the List monad. However, that’s a topic for an entirely different series…

Conclusion

Ok, so this article was a bit longer than I really wanted to run, but there’s a lot of material to cover! Scala’s collections framework shows how even operations steeped in mountains of theory can still prove useful in solving common problems. Now, every time I use collections in Java (or even Ruby), I find myself reaching for many of these same methods, only to find them either unavailable or less powerful than I would like. Scala provides a welcome refuge for all those of us who desire more powerful collection types in our daily programming.

Be with us next time for filter, forall, exists and more!

Filed in Scala | Comments (14)