## Algorithm Proof Inference in Scala

1
Apr
2008

Anyone who’s written any sort of program or framework knows first-hand the traumas of testing.  The story always goes something like this.  First, you spend six months writing two hundred thousand lines of code which elegantly expresses your intent.  Next, you spend six years writing two hundred million lines of code which tests that your program actually does what you think it does.  Of course, even then you’re not entirely sure you’ve caught everything, so you throw in a few more years writing code which tests your tests.  Needless to say, this is a vicious cycle which usually ends badly for all involved (especially the folks in marketing who promised the client that you would have the app done in six hours).  The solution to this “test overload cycle” is remarkably simple and well-known, but certain problems have constrained its penetration into the enterprise world (that is, until now).  The solution is program proving.

### A More Civilized Age

Program proofs are basically a (usually large) set of mathematical expressions which rigorously prove that all accepted program outcomes are correct.  A program prover takes these expressions and performs the appropriate static analysis on your code, spitting out either a “yes” or a “no”.  It’s far more effective than boring old unit testing since you can be absolutely certain that all the bugs have been caught.  More than that, it doesn’t require you to write reams of test code.  All that is required is the series of expressions defining program intent:

$\Gamma_m \to \\left\{\Gamma_0 = \textit\left\{input\right\} | m \sub \Gamma_0\\right\} \cup \Sigma^\star$

$\epsilon = e^\left\{\epsilon \pm \delta\right\}$

$f \colon \\left\{ x \in \left[\epsilon, \infty\right) | x \to \Gamma_x \\right\}$

$\rho_\delta = f\left(\Gamma_\delta \bullet \Gamma_\alpha\right) \Rightarrow \alpha \in \Sigma^\star$

$\mbox\left\{prove\right\}\left(\Omega\right) = \Omega \in \Gamma_\Beta \Rightarrow \left(\Omega \times \epsilon\right) \vee \rho_\omega$

There, isn’t that elegant?  Much better than some nasty JUnit test suite.  In a happier world, all tests would be replaced by this simple, easy-to-read representation of intent.  Unfortunately, program provers have yet to overcome the one significant stumbling block that has barred them from general adoption: the limitations of the ASCII character set.

Sadly, the designers of ASCII never anticipated the widespread need to express a Greek delta, or to properly render an implication.  Of course, we could always fall back on Unicode, but support for that character set is somewhat lacking, even in modern programming languages.  And so program provers languish in the outer darkness, unable to see the wide-scale adoption they so richly deserve.

### An Elegant Weapon

Fortunately, Scala can be the salvation for the program prover.  It’s hybrid functional / object-oriented nature lends itself beautifully to the expression of highly mathematical concepts of intense precision.  Theoreticians have long suspected this, but the research simply has not been there to back it up.  After all, most PhDs write all their proofs on a blackboard, making use of a character set extension to ASCII.  Fortunately for the world, that is no longer an issue.

The answer is to to turn the problem on its ear (as it were) and eschew mathematical expressions altogether.  Instead of the developer expressing intent in terms of epsilon, delta and gamma-transitions, a simple framework in Scala will infer intent just based on the input code.  All of the rules will be built dynamically using an internal DSL, without any need to mess about in low-level character encodings.  Scala is the perfect language for this effort.  Not only does its flexible syntax allow for powerful expressiveness, but it even supports UTF-8 string literals!  (allowing us to fall back on plan B when necessary)

Note that while Ruby is used in the following sample, the proof inference is actually language agnostic.  This is because the parsed ASTs for any language are virtually identical (which is what allows so many languages to run on the JVM).

class MyTestClass def multiply(a, b) a * b end end   obj = MyTestClass.new puts obj.multiply(5, 6)

Such a simple example, but so many possible bugs.  For example, we could easily misspell the multiply method name, leading to a runtime error.  Also, we could add instead of multiply in the method definition.  There are truly hundreds of ways this can go wrong.  That’s where the program prover steps in.

We define a simple Scala driver which reads the input from stdin and drives the proof inference framework.  The framework then returns output which we print to stdout.

object Driver extends Application { val ast = Parser.parseAST(System.in)   val infer = new ProofInference(InferenceStyle.AGRESSIVE) val prover = new ProgramProver(infer.createInference(ast))   val output = prover.prove(ast) println(output) }

It’s as simple as that!  When we run this driver against our sample application, we get the following result:

Notice how the output is automatically formatted for easy reading?  This feature dramatically improves developer productivity by reducing the time devoted to understanding proof output.  One of the many criticisms leveled against program provers is that their output is too hard to read.  Not anymore!

Of course, anyone can write a program which outputs fancy ASCII art, the real trick is making the output actually mean something.  If there’s a bug in our program, we want the prover to find it and notify us.  To see how this works, let’s write a new Ruby sample with a minor bug:

class Person < AR::Base end   me = Person.find(1) me.ssn = '123-45-6789' me.save

It’s an extremely subtle flaw.  The problem here is that the ssn field does not exist in the database.  This Ruby snippet will parse correctly and the Ruby interpreter will blithely execute it until the critical point in code, when the entire runtime will crash.  This is exactly the sort of bug that Ruby on Rails adopters have had to deal with constantly.

No IDE in the world will be able to check this code for you, but fortunately our prover can.  We feed the test program into stdin and watch the prover do its thing:

Once again, clear and to the point.  Notice how the output is entirely uncluttered by useless debug traces or line numbers.  The only thing we need to know is that something is wrong, and the prover can tell us that.

### Conclusion

I can speak from experience when I say that this simple tool can work wonders on any project.  Catching bugs early in the development cycle is the Holy Grail of software engineering.  By learning there’s a problem early on, effort can be devoted to finding the bug and correcting it.  I strongly recommend that you take the time to check out this valuable aid.  By integrating this framework into your development process, you may save thousands of hours in QA and testing.

## Groovy’s Performance is Not Subjective

31
Mar
2008

Ah, the saga of misinterpreted micro-benchmarks!  Developers advocating one technology over another have long used micro-benchmarks and trivial examples to illustrate their point.  This is most often seen in the area of language implementation, where performance is a critical (and often emotional) consideration.  The Computer Language Benchmarks Game is a good example of this.

With the rise of the JVM as a platform for language development, we’ve been seeing a lot of benchmarks directly comparing some of these languages with each other and with Java itself.  Actually, it seems that the popular trio (as far as benchmarking goes) are Scala, JRuby and Groovy.  It’s been a bit of a favorite past-time of the blogosphere to create benchmarks for these languages and then spin up controversial posts about the results.  Back in September, Darek Young wrote a post illustrating a ray tracer benchmark which really caught my eye:

Results

ray.java
12.89s

ray.scala
11.224s

ray.groovy
2h 31m 42s

I was expecting the Groovy code to run longer than the Scala code but was shocked at the actual difference. All three versions of the code produce identical images: (fullsize here)

Wow!  I’ve seen these results dozens of times (looking back at the post), but they never cease to startle me.  How could Groovy be that much slower than everything else?  Granted it is very much a dynamic language, compared to Java and Scala which are peers in static-land.  But still, this is a ray tracer we’re talking about!  There’s no meta-programming involved to muddle the scene, so a halfway-decent optimizer should be able to at least squeeze that gradient down to maybe 5x as slow, rather than a factor of 830.

If this were an isolated incident, I would probably just blow it off as bad benchmarking, or perhaps an odd corner case that trips badness in the Groovy runtime.  Then a week later, I read this post by Pete Knego:

 Test Groovy Java Java vs Groovy (times faster) Simple counter 8.450 150 56x Binary tree building 19.500 2.580 7.6x Binary tree traversing 2.530 76 33x Prime numbers 43.270 1.170 37x

All [non-decimal] times are in milliseconds.

Well, this is really disappointing. I expected Groovy to be slower but not by that much. In order to understand where does such a performance hit come from we have to peek under the hood. The culprit of all this is of course Groovy’s dynamic nature, implemented as MOP. MOP is a way for Groovy to know which class elements (fields/properties, methods, interfaces, superclasses, etc..) are defined on an object and to have a way to alter that data or invoke it. The core of MOP are two methods defined on GroovyObject: get/setProperty() and invokeMethod(). This methods are called every time you access a field or call a method on a Groovy object and quite a lot of work is done behind the scenes. The internals of the MOP are listed in MetaClass interface and implemented in six different classes.

All of this is old news, so the question is: Why am I bringing this up now?  Well, I recently saw a post on Groovy Zone by none-other-than Rick Ross, talking about this very subject.  Rick’s post was in response to two posts (here and here), discussing ways to improve Groovy code performance by obfuscating code.  Final result?

This text is being written as I was changing and trying things, I gained 20s from
minor changes of which I lost track. I am currently at 1m30s (down from the
original 4m and comparing with Java’s 4s).

I’m sorry, this is acceptable performance?  This is someone who’s spent time trying to optimize Groovy, and by his own admission, Groovy is 23x slower than the equivalent Java code.  Certainly this is a far cry from the 830x slower in the ray tracer benchmark, but in this case it’s simple string manipulation, rather than a mathematically intensive test.

Coming back to Rick’s entry, he looks at the conclusion and has this to say about it:

Language performance is highly overrated

Much is often made of the theoretical “performance” of a language based on benchmarks and arcane tests. There have even been cases where vendors have built cheats into their products specifically so they would score well on benchmarks. In the end, runtime execution speed is not as important a factor as a lot of people would think it is if they only read about performance comparisons. Other factors such as maintainability, interoperability, developer productivity and tool and library support are all very significant, too.

Wait a minute, that sounds a lot like something else I’ve read recently!  Maybe something like this:

Is picking out the few performance weaknesses the right way to judge the
overall speed of Groovy?

To me the Groovy performance is absolutely sufficient because of the
easy integration with Java. If something’s too slow, I do it in Java.
And Java compared to Python is in most cases much faster.

I appreciate the efforts of the Groovy team to improve the performance,
but if they wouldn’t, this would be no real problem to me. Groovy is the
grooviest language with a development team always having the simplicity
and elegance of the language usage in mind – and that counts to me.

This is almost a mantra for the Groovy proponents: performance is irrelevant.  What’s worse, is that the few times where they’ve been pinned down on a particular performance issue that’s obviously a problem, the response seems to be along the lines of: this test doesn’t really show anything, since micro-benchmarks are useless.

I’m sorry, but that’s a cop-out.  Face up to it, Groovy’s performance is terrible.  Anyone who claims otherwise is simply not looking at the evidence.  Oh, and if you’re going to claim that this is just a function of shoe-horning a dynamic language onto the JVM, check out a direct comparison between JRuby and and Groovy.  Groovy comes out ahead in only four of the tests.

What really bothers me about the Groovy performance debates is that most “Groovyists” seem to believe that performance is in the eye of the beholder.  The thought is that it’s all just a subjective issue and so should be discounted almost completely from the language selection process.  People who say this have obviously forgotten what it means to try to write a scalable non-trivial application which performs decently under load.  When you start getting hundreds of thousands of hits an hour, you’ll be willing to sell your soul for every last millisecond.

The fact is that this is simply not the case.  Performance is important and it must be considered when choosing a language for your next project.  Now I’m not implying that it should be the sole consideration, after all, we don’t use Assembly much anymore.  But we can’t just discard performance altogether as a means of evaluation.  Developer productivity is important, but it means nothing if the end result doesn’t meet basic responsiveness standards.

It’s like the first time I tried Mingle (which is written using JRuby BTW) back when it was still in pre-beta.  The application was amazing, but it took literally minutes to render the most basic of pages.  The problem was closely related to the state of the JRuby interpreter at the time and its poor memory management with respect to Rails.  In the end, the application was completely unusable.  ThoughtWorks had produced an amazing piece of software in a remarkably short time span, but the cost was the use of a language and framework which (at the time) led to unredeemable performance.  They spared the developers at the expense of the end-users.

Both Mingle and JRuby have come a long way since those first tests.  Charles and the gang have put an intense amount of effort into optimizing the JRuby runtime and JIT compiler.  They’ve gone from an implementation which was 5-10x slower than MRI 1.8.6 to a fully compatible implementation that is usually faster than the original.  Obviously performance is achievable in a dynamic language on the JVM, so why is Groovy still so horrible?

The only answer I can think of is that the Groovy core team just doesn’t value performance.  Why else would they consistently bury their heads in the sand, ignoring the issues even when the evidence is right in front of them?  It’s as if they have repeated their own “performance is irrelevant” mantra so many times that they are actually starting to believe it.  It’s unfortunate, because Groovy really is an interesting effort.  I may not see any value for my needs, but I can understand how a lot of people would.  It fills a nice syntactic niche that other languages (such as Ruby) just miss.  But all of its benefits are for naught if it can’t deliver when it counts.

## JRuby Interop DSL in Scala

24
Mar
2008

JRuby is an amazing bit of programming.  It has managed to rise from its humble beginnings as a hobby project on SourceForge to the most viable third-party Ruby implementation currently available.  As far as I am aware, JRuby is the only Ruby implementation other than MRI which is capable of running an unmodified Rails application.  But JRuby’s innovation is not just limited to a rock-solid Ruby interpreter, it also provides tight integration between Java and Ruby.

There’s a lot of material out there on how to replace Java with Ruby “glue code” in your application.  The so-called “polyglot programming” technique states that we should embrace multiplicity of language in our applications.  Java may be very suitable for the core business logic of the application, but for actually driving the frontend UI, we may want to use something more expressive (like Ruby).  JRuby provides some powerful constructs which allow access to Java classes from within any Ruby application.  For example:

require 'java'   JFrame = javax.swing.JFrame JButton = javax.swing.JButton JLabel = javax.swing.JLabel   BorderLayout = java.awt.BorderLayout   class MainWindow < JFrame def initialize super 'My Test Window'   setSize(300, 200) setDefaultCloseOperation EXIT_ON_CLOSE   label = JLabel.new('You pushed the button', JLabel::CENTER) label.visible = false add label   button = JButton.new 'Push Me' button.add_action_listener do label.visible = true end add(button, BorderLayout::SOUTH) end end   window = MainWindow.new window.visible = true

Not a terribly complex example, but it illustrates some of the major advantages of JRuby.  Notice how clean and concise this code is.  It wouldn’t have been much longer had I done this using Java, but it would certainly have been less readable.  Ruby is absolutely perfect for this sort of use case (driving a UI).

As I said though, there are a myriad of examples showing this sort of thing.  As such, it’s not a very interesting topic for a posting.  What the masses have failed to cover, however, is how to accomplish the opposite: calling from Java into Ruby.

Likely the reason this topic has received less attention is because Java is the language will the veritable zoo of libraries and frameworks.  The amount of effort and research that has been put into Java simply dwarfs the comparative immaturity of the Ruby offerings.  Given the disparity, why would you even want to call into Ruby from Java?  This conclusion seems logical until one remembers that almost any application which uses Ruby for the frontend must actually pass flow control to Ruby at some point.  This means calling some sort of Ruby code.

### The Java Way

There is some information available on the JRuby Wiki.  The wiki article really should include the caveat that “some experimentation may be required.”  Sufficient information is available, but it is neither intuitive nor convenient.  From Java, the syntax for executing an arbitrary Ruby statement looks like this:

ScriptEngineManager m = new ScriptEngineManager(); ScriptEngine rubyEngine = m.getEngineByName("jruby"); ScriptContext context = engine.getContext();   context.setAttribute("label", new Integer(4), ScriptContext.ENGINE_SCOPE);   try { rubyEngine.eval("puts 2 + $label", context); } catch (ScriptException e) { e.printStackTrace(); } It’s a typical Java API: over-bloated, over-designed and over-generic. What would be really nice is to have a syntax for accessing Ruby objects that is as seamless as accessing Java from Ruby. I want to be able to call Ruby methods and use Ruby classes with the same ease that I can use Java methods and classes. In short, I want an internal DSL for Ruby. Unfortunately, Java is a bit constrained in this regard. Java’s syntax is extremely rigid and does not lend itself well to DSL construction. It’s certainly possible, but the result is usually less than satisfactory. We could certainly construct an API around the the Java Scripting API (JSR-233) which provides more high-level access (such as direct method calls and object wrappers), but it would be clunky and only a marginal improvement over the original. The good news is there’s another language tightly integrated with Java that has a far more flexible syntax. Rather than building our JSR-233 wrapper in Java, we can avail ourselves of Scala’s power and flexibility, hopefully arriving at a DSL which approaches native “feel” in its syntax. ### The Scala Way Since we’re attempting to construct a tightly-integrated API for language calls, the most effective route would be to apply techniques already discussed in the context of DSL design. As always, we start with the syntax and allow it to drive the implementation: // syntax.scala import com.codecommit.scalaruby._ object Main extends Application with JRuby { require("test") associate('Person)(new Person("")) println("Received from multiply: " + 'multiply(123, 23)) println("Functional test: " + funcTest('test_string)) val me = new Person("Daniel Spiewak") println("Name1: " + me.name) println("Name2: " + (me->'name)()) me.name = "Daniel" println("New Name: " + me.name) println("Person#toString(): " + me) val otherPerson = 'create_person().asInstanceOf[AnyRef] println("create_person type: " + otherPerson.getClass()) println("create_person value: " + otherPerson.send[String]("name")()) eval("puts 'Ruby integration is amazing'") def funcTest(fun:(Any*)=>String) = fun() } class Person(name:String) extends RubyClass('Person, name) { def name = send[String]("name")() def name_=(n:String) = 'name = n } And the associated Ruby code: # test.rb class Person attr_reader :name attr_writer :name def initialize(name) @name = name end def to_s "Person: {name=#{name}}" end end def test_string 'Daniel Spiewak' end def multiply(a, b) a * b end def create_person Person.new 'Test Person' end Obviously we’re going to need some heavy implicit type conversions. The important thing to note is that we don’t see any residue of the Java Scripting API, it’s all been encapsulated by our DSL. We’ve taken an API which is oriented around single-call, low-level invocations and created a high-level wrapper framework which allows method calls, instantiation and even some form of type-checking. Starting from the top, we see a call which should be familiar to Rubyists, the require statement. In our framework, this method call is just a bit of syntactic sugar around a call to eval(String). This semantics are basically the same as within Ruby directly, with the exception of how Ruby source files are resolved. Any script file on the CLASSPATH is fair game, in addition to the normal Ruby locations. This allows us to easily embed Ruby scripts within application JARs, libraries and other Java distributables. Moving down a bit further, we find a somewhat mysterious call to the curried associate(Symbol)(RubyObject) method. The purpose of this invocation will become more apparent later on. Suffice it to say that this step is necessary to allow Scala class wrappers around existing Ruby classes. On the next line of interest, we see for the first time how the framework allows for seamless Ruby method invocation. Unlike Ruby, Scala doesn’t allow us to simply handle calls to non-existent methods. Because of this limitation, we have to be a bit more clever in how we structure the syntax. In this case, we use Scala symbols to represent the method. There doesn’t seem to be a terribly good explanation of symbols in Scala, but there’s plenty of information regarding how they work in Ruby. Since the concepts are virtually identical, techniques are cross-applicable. The key to the whole “symbols as methods” idea is implicit type conversion. The JRuby trait inherits a set of conversions which look something like this: implicit def sym2Method[R](sym:Symbol):(Any*)=>R = send[R](sym2string(sym)) implicit def sym2MethodAssign[R](sym:Symbol) = new SpecialMethodAssign[R](sym) private[scalaruby] class SpecialMethodAssign[R](sym:Symbol) { def intern_=(param:Any) = new RubyMethod[R](str2sym(sym2string(sym) + "="))(param) } Though we haven’t looked at it yet, it is possible to infer the purpose of the send(String) method. It’s function is to prepare a call to a Ruby method without actually invoking it. This distinction allows us to pass Ruby methods around as method parameters, just like standard Scala methods. The method returned is actually an instance of class RubyMethod[R] (where R is the return type). Scala allows classes to extend structural types like methods, allowing us to redefine the method invocation semantics for wrapped Ruby calls. class RubyMethod[R](method:Symbol) extends ((Any*)=>R) { import JRuby.engine override def apply(params:Any*) = call(params.toArray) private[scalaruby] def call(params:Array[Any]):R = { val context = engine.getContext() val plist = new Array[String](params.length) for (i <- 0 until params.length) { plist(i) = "res" + i context.setAttribute(plist(i), JRuby.resolveValue(params(i)), ScriptContext.ENGINE_SCOPE) plist(i) = "$" + plist(i) }   evaluate(() => if (plist.length > 0) { sym2string(method) + "(" + plist.reduceLeft[String](_ + ", " + _) + ")" } else { sym2string(method) + "()" }) }   protected def evaluate(invoke:()=>String):R = { val toRun = invoke() Logger.getLogger("com.codecommit.scalaruby").info(toRun)   JRuby.handleExcept(JRuby.wrapValue[R](engine, engine.eval(toRun, engine.getContext()))) } }

The gist of this code is simply to assign every parameter value to an attribute in the Ruby runtime.  Attributes of ENGINE_SCOPE (as defined by JSR-233) are represented as global variables within Ruby.  These variables are named sequentially starting from zero.  (e.g. $res0, $res1, …)  As you can imagine, this technique tends to be a bit of a concurrency killer.  To keep things simple, I decided to completely ignore the issues associated with asynchronous execution.  It is certainly possible to adapt the framework to function in a multi-threaded environment, but I didn’t bother to do it.  (one of the perks of blogging is a license to extreme laziness)

Once these parameters are assigned, the method call is evaluated within the context of the runtime.  This is done by literally generating the corresponding Ruby code (done in the anonymous method) and then wrapping the return value in an instance of RubyObject (if necessary).  Note that the send(String) method does not actually kick-start this invocation process at all.  Rather, it creates an instance of RubyMethod[R] which corresponds to the method name.  This class extends (Any*)=>R, so it may be used in the normal “method fashion” – by appending parentheses which enclose parameters (if any).

### Supporting Cast

At this point, it’s worth taking a moment to examine the specifics of the framework class hierarchy.  A number of classes exist to wrap around Ruby objects and methods.  We’ve already seen a few of them (RubyMethod[R] and RubyObject), but it’s worth going into more detail as to their purpose and relation to one another.

Note that these class names often conflict with existing classes in the JRuby implementation.  This odd coincidence is precipitated by the fact that the framework seems to deal with a lot of the same concepts as the JRuby runtime (go figure).  Rather than obfuscating my class naming to avoid conflict, I just assume that you will either make use of the enhanced Scala import feature (as I have in the implementation), or just avoid using the JRuby internal classes.

• RubyObject – The root of the object hierarchy.  This abstract class is designed to encapsulate the core functionality of the generic object (roughly: send, -> and eval) as well as containing all of the implicit type conversions.  Most of the syntax-defining magic happens here (more on this later).
• JRuby – This is the primary type interface between the developer and the framework.  Classes which wish to make use of Ruby integration must inherit from this trait.  This is where the Logger (for executed statements) is initialized and deactivated.  Within the corresponding object, all of the backend resources are managed.  This is where the actual ScriptEngineManager instance lives, as well as a set of utility methods to handle wrapping and unwrapping of framework-specific objects.
• RubyWrapperObject – This implementation of RubyObject is designed to wrap around instances which already exist within the Ruby interpreter.  For example, if a Ruby method returns an instance of ActiveRecord::Base, it will be represented in Scala by a corresponding instance of RubyWrapperObject.  Note that objects which are equivalent in the Ruby interpreter are not guaranteed to be pointer-equivalent.  However, the equals(Object) method is well-defined within RubyObject, thus comparisons between RubyObject instances will return sane results.  The == method in Scala is defined in terms of equals(Object), so existing code will behave rationally.
• RubyClass - With the exception of the JRuby trait, this is likely the only class within the framework which the developer will have to reference explicitly.  This class allows developer-defined Scala classes to wrap around existing Ruby classes, providing type-safe method calls and even extended functionality.  More on this feature later.
• RubyMethod – We’ve already seen how this serves as a wrapper around calls to Ruby methods.  However, its default implementation assumes that the method is defined in the global namespace.  This is impractical for many method calls (such as dispatch on an object).
• RubyInstanceMethod – This class solves the problem of object dispatch with RubyMethod.  All of the core functionality is identical to its superclass with the exception of the generated Ruby code.  Instead of just generating a method call passing parameters, this class will generate a method call on a given Ruby object.  Thus, this class depends upon RubyWrapperObject which maintains a reference to a corresponding Ruby instance.

### Alternative Dispatch

Not every method call is made on the enclosing scope.  Sometimes it is necessary to call a method in an object to which you have a reference.  For example, a method may return an instance of a some Ruby class.  This instance will be automatically wrapped by a Scala instance of RubyWrappedObject.  Since this Scala class doesn’t actually define any methods which correspond to the Ruby class, it is necessary to once more utilize the “symbols as methods” trick in method dispatch.  There are two ways to call a method on an object like this: the send[R](String) method (where R is the return type), and the -> (arrow) operator.

Using the arrow operator is a lot like normal method calls, except with symbols instead of method names.  Just like dispatch on the enclosing scope, the call is converted into an instance of RubyMethod (actually, an instance of RubyInstanceMethod) which can then be used as a standard Scala method.  The difference between using arrow and dispatching on the enclosing scope is the syntax must be a little more contrived.

Parentheses have the second-highest priority of all the Scala operators (the dot operator (.) has the highest).  This means that if we simply “follow our nose” where the syntax is concerned, we will arrive at an order of invocation which leads to an undesirable result.  Consider the following sample:

val obj = 'create_person() obj->'name()

The first call is a standard dispatch on the enclosing scope.  The second call is what is interesting to us.  Reading this line naturally (at least to old C/C++ programmers) we would arrive at the following sequence of events:

1. Get a reference to the name method from the instance contained within obj
2. Invoke the method, passing no parameters

Unfortunately, this is not how the compiler sees things.  Because parentheses bind tighter than the arrow operator, it actually resolves the expression in the following way:

1. Get a reference to the name method contained within the enclosing scope
2. Invoke the method, passing no parameters
3. Invoke the -> method on the instance within obj, passing the result of name as a parameter

This is obviously not what we wanted.  Unfortunately, there’s no way to make the arrow operator bind tighter than parentheses.  This is a good thing from a language standpoint, but it causes problems for our syntax.

The solution is to enclose any “arrow dispatch” statement within parentheses so as to force the order of evaluation:

val obj = 'create_person() (obj->'name)()

It looks a bit weird, but it’s the only way Scala will allow this to work.  This call now evaluates properly, calling the name method on the obj instance, passing no parameters.

There’s actually another problem associated with arrow dispatch in our DSL: Scala already has an implicit meaning for the arrow operator.  The following sample should look familiar to those of you who have worked with Scala in other applications:

val numbers = Map(1 -> "one", 2 -> "two", 3 -> "three")

By default, Scala defines the arrow operator as an alternative syntax for defining 2-tuples.  This is good for most things, but bad for us.  What we want is to define a new implicit type conversion which converts Any into a corresponding instance of RubyWrappedObject.  This would allow us to satisfy the syntax given above.  However, Scala’s 2-tuple syntax already defines an implicit type conversion for the Any type which deals with the arrow operator.  Rather than examining the context to attempt to disambiguate, the Scala compiler simply gives up and prints an error stating that the implicit type conversions are ambiguous.  This poses a bit of a problem and nearly killed the arrow operator idea in design.

The solution is actually to override Scala’s built-in conversion by defining our own conversion with the same name and signature but which provides us with the option of using our own arrow operator definition.  The behavior we want is to allow normal use of the arrow operator when dealing with Any -> Any, but convert to RubyWrappedObject and dispatch when dealing with Any -> Symbol.  After a little digging through the Scala standard library, I arrived at the following solution (defined in RubyObject):

implicit def any2ArrowAssoc[A](a:A) = new SpecialArrowAssoc(a)   private[scalaruby] class SpecialArrowAssoc[A](a:A) extends ArrowAssoc(a) { def ->(sym:Symbol) = (a match { case obj:RubyObject => obj case other => new RubyWrapperObject(other) })->sym }

Notice that we extend Scala’s pre-existing ArrowAssoc[A] class (which handles the special 2-tuple syntax) and then overload the -> method to work differently with symbols.  This code now does precisely what we need.  By introducing this extra layer of indirection, as well as by overriding Scala’s existing conversion, we’re able to support the arrow syntax as shown in the above examples.

#### Sending Messages

There is one final form of dispatch which allows typed return values: send[R](String).  This is actually the method to which all the other dispatch forms delegate (as it is the most general).  This method is very similar to the Ruby send method which allows Smalltalk-style message passing on arbitrary objects.  The really important thing about this method though is that it will automatically cast the return value from the method to whatever type you specify, allowing you to define type-safe wrappers around existing Ruby methods in Scala:

def multiply(a:Int, b:Int) = send[Int]("multiply")(a, b)   val result:Int = multiply(123, 23)

send is effectively defined as a curried function since it takes a method name as a parameter and returns an instance of RubyMethod as a result.  This mimics the behavior of dispatch with symbol literals in that you can use send to generate type-safe partially-applied functions for corresponding Ruby methods.

Note that send could just as easily have taken a symbol as a parameter, rather than a string.  However, the metaphor throughout the DSL is “symbols as methods”, thus string was used to avoid logical conflict.  Scala itself was perfectly happy passing symbol literals around in addition to treating them as methods.

### Class Wrapping

The final bit of code in the example now so far above us serves as a sample of how one might wrap an existing Ruby class within Scala.  Person is actually a class defined in Ruby (as you can see from the Ruby sources).  It has a read/write attribute, name, as well as an overridden to_s method.  RubyObject already contains the logic for handling calls to toString() and proxying them to Ruby’s to_s, but the name attribute must be handled explicitly in code.

The goal is basically to provide a type-safe wrapper around the Person Ruby class.  We could just as easily dispatch on the automatically wrapped instance of RubyWrappedObject using either syntax described above, but an explicit wrapper is a bit nicer.  The compiler can check things for us, and we can even add methods to the class (at least, as far as Scala is concerned) in true Ruby “open class” style.  All that is necessary to accomplish this wrapper is to extend RubyClass and to define the delegating wrapper methods:

class Person(name:String) extends RubyClass('Person, name) { def name = send[String]("name")() def name_=(n:String) = 'name = n }

We specify which Ruby class we are wrapping as the first parameter in the constructor for RubyClass.  The parameters which follow are passed directly to the constructor of the corresponding Ruby class.  This Ruby constructor is invoked automatically, instantiating the corresponding wrapped Ruby object in the background.  Notice that we specify the name of the Ruby class using a symbol.  This is the one place in the framework that we break with the “symbols as methods” metaphor.  The consequence is a nice, clean syntax for Ruby class wrapping.  Unfortunately, it also means that wrapping a class within a non-included namespace (e.g. ActiveRecord::Base) can be a little clunky.  The only way to do it is to explicitly invoke the Symbol(String) constructor.  (this is required because Scala symbols can only contain alpha-numerics and underscores)

Once we have our wrapped class signature, it’s easy to define the delegate methods.  Scala encourages a blurring of field and method, similar to Ruby.  As such, it supports a very Ruby-esque syntax for accessor/mutator pairs.  This makes the wrapped syntax just a bit nicer.  For the accessor, we make a call to the send method, specifying the return type necessary for the wrapper.  The mutator allows us to be a bit more creative.

We don’t really need type-safe return values for a mutator.  We would normally just set the return type as Unit and ignore the result.  Thus we can once again use the symbol dispatch syntax.  Notice that this time we’re not directly treating a symbol as a method.  We’re apparently assigning a value to the symbol using the = operator (corresponds to the operator= assignment operator in C++).  This is possible through a separate implicit type conversion which generates a one-off utility instance:

private[scalaruby] class SpecialMethodAssign[R](sym:Symbol) { def intern_=(param:Any) = new RubyMethod[R](str2sym(sym2string(sym) + "="))(param) }

As you can see, all this method does is generate a new symbol which includes the ‘=’ character and returns the result of dispatching on the corresponding Ruby method.  Note that mutators in Ruby are defined as “=“, thus appending “=” to the method name is the appropriate behavior.

#### Return Value Wrapping

There’s actually a slight problem involved in allowing Scala wrappers around existing Ruby types.  Well, not so much a problem as an inconsistency.  The problem is simply this: if a Ruby method creates an instance of a Ruby class for which there is a Scala wrapper and returns this value through the framework into Scala, one would expect this value would be wrapped into an instance of the Scala wrapper.  If you look in the example far above, there is an example of this in the create_person method.  The method creates an instance of Ruby class Person and returns it as a result.

Somehow, the framework must identify that there is a corresponding Scala wrapper and then properly create an instance.  This actually poses something of a dilemma in two ways.  Number one, Scala has no equivalent to Ruby’s ObjectSpace, so there’s no way to get a comprehensive list of all classes which have been defined.  Even if we could get this list, the corresponding Ruby class is specified in the constructor parameters to RubyClass, so there’s no way to obtain the information statically from outside the class.  Number two, we have to somehow create an instance of the Scala wrapper class without creating a corresponding instance of the wrapped Ruby class (since we already have one).  This means we need some sort of override in the RubyClass constructor.

The best solution to all of these problems is to introduce the associate method.  The usage is demonstrated at the top of the example where we associate the Person Ruby class with the Person Scala wrapper class.  More specifically, we associate the Ruby class with a pass-by-name parameter which defines how to instantiate the Scala class.  This is an important distinction as it solves our second problem of instance creation.  The framework has no way of knowing what parameters must be passed to the Scala wrapper constructor, so the instantiation itself must be passed:

associate('Person)(new Person(""))

As I mentioned previously, this is a pass-by-name parameter which means that it will not be immediately evaluated, but rather on-demand somewhere in the body of associate.  The associate method actually takes this value and wraps it in an anonymous method which invokes the instantiation each time a value of Ruby type Person must be wrapped.  Just prior to invoking the constructor, an override is put in place within the RubyClass singleton object (not shown in the class hierarchy) to prevent the creation of a corresponding Ruby instance.  This is what allows the new instance of Scala class Person to correspond with an existing Ruby value.  Here again we’re sacrificing concurrency for a hacky work-around to a complex problem.  Any sort of “proper” implementation would have to solve this problem in a more elegant way.

### It Never Ends!

This post, that is.  There’s so much more I could ramble on about (I never even talked about how exceptions are handled), but this entry is already far too long.  Hopefully the material presented here only serves to whet your appetite for slicker JRuby-Scala integration and all the benefits it can bring.  I’ve packaged up the framework presented here as a downloadable archive.  The package includes the Ruby engine for the Java Scripting API as well as a jar-complete build made from the JRuby SVN.  The project may work with JRuby 1.0, but I doubt it.  Anyway, JRuby 1.1 is due shortly, so why bother.  Remember that this is extremely untested and very experimental.  (I did warn you about the concurrency issues, right?)  If this is interesting to people, I may do a proper release into an OSS project somewhere.  For right now, I just don’t have the time.

I hope this entry gives you an idea of what’s involved in Scala DSL implementation, as well as an idea of where such a technique may be useful in your own projects.  After all, what would be better than everyone being able to write their own Rails-killer and define highly fluid APIs!

## ActiveObjects 0.8 Released

22
Mar
2008

Happy Easter everyone, we’ve got a new release!  ActiveObjects 0.8 is simmering at low heat (and footprint) on the servers even as I type.  This is probably the most significant milestone we’ve released thus far in that the 1.0 stream is now basically feature-complete.  I won’t be adding any new features to this release, just polishing and testing the heck out of the old ones.  We’ve already got a suite of 91 tests and I’ve got lots of ideas for more.  Expect this framework to get very, very stable in the next few months.

### Features

Despite an annoyingly cramped schedule in the last couple months, I have managed to implement a few long-requested features.  The big ticket item for this release is pluggable cache implementations.  For those of you not “in the know”, ActiveObjects has a multi-tiered cache system composed of several layers and delegates.  This isn’t entirely unusual for an ORM, which is why I hadn’t mentioned it before.  The three basic layers:

• Entity Cache – A SoftReference map from id/type pairs to actual entity values.  This means that if you run a query which returns an entity for people {id=1} and then run a second query which returns an entity for the same row, the two instances will be identical.  This is what enables the additional cache layers to function properly (and it saves on memory).
• Value Cache – This is where all the field values for a given row are stored.  This will store both field values from the database as well as entity values (corresponding to foreign key fields).  Each entity has a separate instance of this cache.  Most of the memory required by ActiveObjects is taken up here.  With a long-running application, quite a bit of the database can actually get paged into memory.  This is a really good thing, since it drastically reduces round-trips to the database.  Thanks to the SoftReference(s) in the entity cache, running out of memory due to stale cache entries isn’t a problem.
• Relations Cache – This is probably the most complex of all of the cache layers.  This cache literally caches any one-to-one, one-to-many or many-to-many result sets and spits them out on demand.  This reduces round-trips still more to the point where certain applications can be running completely from memory, even querying on complex relations.  This in and of itself isn’t that complex; the hard part is knowing when to expire specific cache entries.  This cache layer is essentially three different indexes to the same data, allowing cache expiry for a number of different circumstances.  Naturally, these structures don’t represent well as a single map of key / value pairs.  (more on this in a bit)

As of the 0.8 release, the value cache and relations cache layers have been unified under a single controller.  They’re still separate caches, but this unification allows for something I’ve been wanting to implement since 0.2: Memcached support.

High-volume applications often run into the problem of limited memory across the various server nodes.  Solutions like Terracotta can help tremendously, but unfortunately this doesn’t solve everything.  One answer is to provide every node in the cluster with a shared, distributed, in-memory map of key / value pairs.  This allows the application to page data into cluster memory and retrieve it extremely quickly.  Memcached is effectively this.  Naturally, it would be very useful if an ORM could automatically make use of just such a distributed memory cache and thus share cached rows between nodes.  Hibernate has had this for a long time, and now ActiveObjects does as well.

By making use of the MemcachedCache class in the activeobjects-memcached module (separate from the main distribution), it is possible to point ActiveObjects at an existing Memcached cluster and cause it to store the value cache there, rather than in local memory.  Once the relevant call has been made to EntityManager (setting up the cache), all cached rows will be stored in Memcached and shared between every instance of ActiveObjects running in your cluster.

#### Caveats

Of course, nothing is perfect.  For the moment, the major issues is that the relations cache doesn’t work properly against Memcached.  I had originally planned to just release it running against the local RAM, but this causes issue with proper cache expiry.  As such, the relations cache is disabled when running ActiveObjects against Memcached.  This doesn’t really impair functionality other than forcing ActiveObjects to hit the database every time a relationship is queried.  Since this is what most ORMs do anyway, it’s not too horrible.

I plan to have this issue resolved in time for the 0.9 release.  The biggest problem is figuring out how to flatten the multi-index structure into a single map.  Once I can do that, rewriting things for Memcached should be a snap.  (btw, if anyone wants to help out with patches in this area, you’re more than welcome!)

### Databases Galore

One of the major focuses of this release was testing on different platforms.  This process uncovered an embarrassing number of bugs and glitches in some of the supposedly “supported” databases.  With the exception of Oracle, every bug I’ve been able to identify has been fixed.  So if you’ve tried ActiveObjects in the past and run into problems on non-MySQL platforms, now would be the time to give it another shot!

Speaking of Oracle, we’ve made some tremendous progress toward full support of this ornery database.  To be fair, I’m not the one responsible.  One of our community members has been tirelessly submitting patches and running tests.  We didn’t have time to get things fully sorted for this release (so don’t try AO 0.8 with Oracle unless you’re willing to risk server meltdown), but you can expect dramatic improvements in 0.9.  Once these fixes are in place, we should be able to safely claim that we support most of the database market (in terms of product adoption).

### Final Thoughts

This really is an amazing release, well worth the download.  Most of the core API has remained the same, so things should be basically plug-n-play for existing applications.  The user-facing API is now in freeze and (unless some serious bug arises) will experience no changes between now and 1.0.  If you’ve been considering trying ActiveObjects for your project, now would be an excellent time.  I can’t promise no bugs, but if you point out my idiocy, I’ll certainly work to fix it!

Oh, as an aside, ActiveObjects is now in a Maven2 repository.  (thanks to some POM reworking by Nathan Hamblen)  To make use of this somewhat dubious feature, add the java.net Maven2 repository to your POM and then insert the following dependency:

<dependency> <groupId>net.java.dev.activeobjects</groupId> <artifactId>activeobjects</artifactId> <version>0.8</version> </dependency>

After that, the magic of Maven will take over.  Of course, you’ll need to add the dependency for the appropriate database driver and (optionally) connection pool.  Those dependencies are left as an exercise to the reader.  Note, activeobjects-memcached isn’t in Maven yet, but it will be for the 0.9 release (either that or integrated into the core, I haven’t decided yet).

I certainly hope you enjoy this latest release.  As always, feel free to drop by the users list if you have any questions or (more likely) uncover any problems.

## Function Currying in Scala

17
Mar
2008

As a hybrid-functional language, Scala supports many of the same techniques as languages like Haskell and LISP.  One of the least used and most misunderstood of these is that of function currying.  Furthermore, there are many articles talking about the various ways to use currying within languages like Ruby, Groovy and similar, but very few which actually discuss why it’s useful.  To that end, I present a quick run-down on how to curry methods in Scala, along with some idea of why you would want to.

### Defining Curried Functions

Conceptually, currying is a fairly simple idea.  Wikipedia defines it as follows:

In computer science, currying, invented by Moses Schönfinkel and Gottlob Frege, is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the other arguments having been specified by the curry).

Mathematically,

$f \colon \left(X \times Y\right) \to Z$

$\mbox\left\{curry\right\}\left(f\right) \colon X \to \left(Y \to Z\right)$

What this is saying is that the currying process transforms a function of two parameters into a function of one parameter which returns a function of one parameter which itself returns the result.  In Scala, we can accomplish this like so:

def add(x:Int, y:Int) = x + y   add(1, 2) // 3 add(7, 3) // 10

And after currying:

def add(x:Int) = (y:Int) => x + y   add(1)(2) // 3 add(7)(3) // 10

In the first sample, the add method takes two parameters and returns the result of adding the two.  The second sample redefines the add method so that it takes only a single Int as a parameter and returns a functional (closure) as a result.  Our driver code then calls this functional, passing the second “parameter”.  This functional computes the value and returns the final result.

Of course, it’s not very apparent as to why this is a good idea.  All we’ve really accomplished is eliminate the second parameter and move it into another function.  This is a big deal in languages like Haskell which only allow a single parameter, but Scala doesn’t have this restriction.  For the moment, just assume with me that this is wonderful and profound as we move forward into a better implementation.

Our first example was nice, but it seems a little clumsy.  All we’ve done is add a ton of syntactic overhead to our add definition.  Fortunately, Scala has a nice syntax for defining curried functions which dates back to pure-functional languages like ML.  We can shorten our curried definition to something more like this:

def add(x:Int)(y:Int) = x + y   add(1)(2) // 3 add(7)(3) // 10

This is really just syntactic sugar, the compiler treats both definitions the same.

### Applied to Existing Methods

Currying isn’t just limited to methods which you define.  Thanks to the power of a language with inner methods and closures, it is possible to define a method which takes a function of n parameters and converts it to a curried function of order n.  In fact, this function is already defined within the Function singleton in the scala package.  We can use it to curry the first version of our add method:

def add(x:Int, y:Int) = x + y val addCurried = Function.curried(add _)   add(1, 2) // 3 addCurried(1)(2) // 3

That mysterious underscore within the curried method invocation is actually a bit of Scala syntax which tells the compiler to treat add as a function value, rather than a method to be invoked.  Scala refers to this as a “partially applied function”, though it doesn’t really meet the strictest definition.  More on this later.

It is interesting (and important) to note that the curried method is only overloaded for methods of up to arity (number of parameters) 5.  I suppose that only a maniac would want to define a curried version of a function of any higher arity, but it’s still odd to consider.

Function also provides utility methods which allow us to reverse the process.  For example, if we start with our second version of add, we may wish to generate a version which takes all parameters inline (in conventional fashion).  This can be done using the uncurried method:

def add(x:Int)(y:Int) = x + y val addUncurried = Function.uncurried(add _)   add(3)(4) // 7 addUncurried(3, 4) // 7

As you can see, the process does invert quite nicely.  Notice that while this may appear to be dynamic programming (note), it’s actually quite static and valid from a compiler’s standpoint.  Effectively, addUncurried is a closure defined within the uncurried method.  Because we assign it to a val, we can call it anywhere in scope (anywhere we can access the addUncurried variable).  The compiler will type-check everything here, including the uncurried functional and its parameter types.

### Partially Applied Functions

All of this is great, but it doesn’t answer the question: “why do we care?”  After all, when you look at the differences, it just seems that we’ve slightly altered the syntax for passing parameters.  This doesn’t even seem terribly mathematical (normally a trait of functional languages) since the notation for passing multiple variables is comma-delimited, not parentheses-separated.

It turns out that the best rationale for using currying has to do with general and specialized functions.  It would be nice to define a function for the general case, but allow users to specialize the function and then used the specialized version on different data sets.  Take the following code as an example:

def process[A](filter:A=>Boolean)(list:List[A]):List[A] = { lazy val recurse = process(filter) _   list match { case head::tail => if (filter(head)) { head::recurse(tail) } else { recurse(tail) }   case Nil => Nil } }   val even = (a:Int) => a % 2 == 0   val numbersAsc = 1::2::3::4::5::Nil val numbersDesc = 5::4::3::2::1::Nil   process(even)(numbersAsc) // [2, 4] process(even)(numbersDesc) // [4, 2]

Aside from being a fair example of how imperative and functional programming blend well, this little ditty provides a convenient example with repeated code.  Astute observers will see that I could have easily done this using the List#filter method, but I wanted a curried function for an example.  Besides, I hadn’t even used the cons operator once on this blog and I figured it was about time to start…

The bit of code which is redundant is on the last two lines: the repeated invocation of process(even).  Not only is this redundant, but it’s somewhat inefficient.  To see why, we have to partially apply the curried function to look at the result type:

scala> process(even) _
res0: (List[Int]) => List[Int] = 

There again is our old friend the underscore.  Remember that it just tells the compiler to treat the suffixed value as a functional, rather than a method to be evaluated.  Thus it seems that invoking process(even) is perfectly valid in isolation.  We don’t have to specify the second parameter since there is none.  If the process method where not curried, there would be no way to do this (no way in most languages, we’ll see a way in Scala a little farther down).  The result type of this invocation is the functional which would be invoked next in the series (with the second set of parentheses).  Remember that a curried function is one which takes a parameter and returns another function which takes a parameter and does more processing.  We’re just accessing that intermediate function.

So if process(even) generates a functional, invoking it multiple times probably has some overhead.  To do so would be to create the intermediary functional twice.  Of course, the second problem is this is code-repeat,  something all good programmers cringe to see.  It turns out that we can solve both of these problems in one fell swoop:

//...   val even = (a:Int) => a % 2 == 0 val processEvens = process(even) _   val numbersAsc = 1::2::3::4::5::Nil val numbersDesc = 5::4::3::2::1::Nil   processEvens(numbersAsc) // [2, 4] processEvens(numbersDesc) // [4, 2]

Now we have a function processEvens of order 1 which specifically processes through an “even” filter.  We have created a specialized version of process by taking advantage of the way currying works.  This turns out to be a very powerful technique, and while I don’t have any non-trivial examples to share, I’m sure you can use your imagination.

### Partials without Currying

It’s clear that partially applied functions can be very powerful, but they only seem to apply to a method which is already curried.  Of course, for a standard, arity n method we can use the curried method to convert, but this gets clumsy.  It would be nice if we could use the partially applied function technique on any method, even one which is not curried.  Enter underscore.

This little construct is probably the most powerful single character I’ve ever seen.  You can do so much with it in Scala, and yet it all seems to remain semantically consistent.  Scala allows us to use underscore within the invocation, partially applying the function by creating a new functional which takes the appropriate parameters.

def add(x:Int, y:Int, z:Int) = x + y + z   val addFive = add(5, _:Int, _:Int) addFive(3, 1) // 9

Here we have partially applied the add method, specializing on the value 5 for the first parameter.  addFive is actually a functional which takes two parameters of type Int and returns the result of passing the values of 5 and the two parameters in order to the add method.  This code is semantically equivalent to the following:

def add(x:Int, y:Int, z:Int) = x + y + z   val addFive = (a:Int, b:Int) => add(5, a, b) addFive(3, 1) // 9

The underscore just provides a convenient syntactic sugar for this.  The only unfortunate part is the fact that we must annotate the underscores with types.  If this were ML, Haskell or similar, the types of the underscores could easily be inferred and the annotations omitted.  It would be nice if Scala could do things like this, but I guess it can’t be entirely perfect.

### Conclusion

Hopefully this provides a fair introduction to the useful world of method currying.  As you can see, currying is not just an academic construct we were forced to demonstrate on college exams, it’s a powerful technique with real-world applications.  By blending the functional and the object-oriented, Scala has managed to bring all the power of currying to the imperative world, a feat well worth utilizing on your next project.