Memoization with Reflection in Ruby
Since my classes started, in Programação Avançada (Advanced Programming) we have been talking about Reflection, using Lisp and Java for the examples. Now, Ruby is well know for it’s Metaprogramming magic, so, being the geek I am, I was anxious to apply some of the things we discussed in class with Ruby.
Because this post is so long please feel free to jump around and view only the parts that interest you the most. Here’s a mini table of contents to help you out:
- Reflection
- Self-Modification
- Self-Modification and Memoization with Lisp
- Self-Modification and Memoization with Java
- Self-Modification and Memoization with Ruby
- Simple Ruby Code Benchmark
Reflection
Reflection, as per Wikipedia, is a particular kind of Metaprogramming. It is the process of reasoning about yourself and acting upon oneself. So basically it gives you the power to observe your own computer program during it’s execution and, in some cases, allow you to modify it.
Reflection can be divided into two categories:
- Introspection – the ability to examine the structures of the program in execution from within itself;
- Intercession – the ability to actually modify the behavior of the program in run-time.
Intercession can still be divided into another two sub-categories:
- Self-Modification – the ability to modify one’s own structure;
- Intercession – the ability to to modify the semantics of the language within the language itself.
Self-Modification
The teacher in class used the recursive Fibonacci function – fib(n) – as an example. Because of it’s recursive nature, it’s extremely inefficient to calculate fibonacci for big values of n. To speed up it’s execution, the teacher defined a memoization function and applied it to fib(n). So it turns the original fibonacci function from an exponential beast into a linear calculation. It’s pretty awesome to see how much time is saved by keeping the intermediate values and how that influences the execution time.
So now let me show you how it’s done in Lisp first, then in Java, and finally in Ruby.
I won’t spend too much time explaining the Lisp and Java code samples, they’re here more for illustrative purposes than anything else. But if you’re really interested in these samples and would like a detailed explanation, please drop me a comment as I’d be glad to explain them to you.
Please note that the following 2 code examples I’m going to show you weren’t programed by me; they were taken from my classes powerpoint slides which were created by my teacher, António Leitão. Only the Ruby code is 100% mine =)
Lisp
Let’s take a look at the Fibonacci function in Lisp:
(lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
The memoize function looks like this:
(defun memoize (lambda-form) (setcar (cddr lambda-form) `(let ((result ,(caddr lambda-form))) (setcar (cddr ',lambda-form) `(if (eql ,',(caadr lambda-form) ',,(caadr lambda-form)) ',result ,(caddr ',lambda-form))) result)))
Pretty scary right? I’m not going to explain it, it’s just here for me to scare you and show you how cool Ruby is.
But what this function does is it changes the fib(n) function so that every time it has to calculate the fibonacci of some n, it modifies itself. It does this by adding a new If condition to the beginning of the function body, checking if n is equal to some n that was previously calculated. If so, it returns the value straight away. If not, the function calculates the value recursively and modifies itself once again.
Java
Java doesn’t allow destructive modification of programs at run-time like Lisp does. But what it does allow you to do is modify the program before the class is loaded by the Java Virtual Machine – aka Load-Time. This is done by using an external library, in this case, Javassist.
The Fibonacci in Java looks something like:
public class Fib {
public static Long fib (Long n) {
if (n < 2) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
}
A bit verbose, I know. Now for the memoization function:
import javassist.*;
import java.io.*;
public class Memoize {
public static void main(String[] args)
throws NotFoundException, CannotCompileException, IOException {
if (args.length != 2) {
System.err.println("Usage: java Memoize <class> <method>");
System.exit(1);
} else {
ClassPool pool = ClassPool.getDefault();
CtClass ctClass = pool.get(args[0]);
memoize(ctClass, ctClass.getDeclaredMethod(args[1]));
ctClass.writeFile();
}
}
static void memoize(CtClass ctClass, CtMethod ctMethod)
throws NotFoundException, CannotCompileException {
CtField ctField =
CtField.make("static java.util.Hashtable cachedResults = " +
" new java.util.Hashtable();",
ctClass);
ctClass.addField(ctField);
String name = ctMethod.getName();
ctMethod.setName(name + "$original");
ctMethod = CtNewMethod.copy(ctMethod, name, ctClass, null);
ctMethod.setBody("{" +
" Object result = cachedResults.get($1);" +
" if (result == null) {" +
" result = " + name + "$original($$);" +
" cachedResults.put($1, result);" +
" }" +
" return ($r)result;" +
"}");
ctClass.addMethod(ctMethod);
}
}
Instead of adding an If statement to be beginning of the function every time it calculates n recursively, we’ll use a Hash Table to keep the intermediate values by using n as a key and the fibonacci value as the key’s value.
So this code renames the fib(n) function to original$fib which isn’t normally allowed, but because Javassist works at such a low-level, it’s allowed to do that. Plus, this way, it avoids any namespace collisions. After the rename, it redefines the original fib(n) method so that it:
1. Checks if n is in the hash table. If so, return the corresponding value. 2. If not, call the original$fib function, store the value in the hash table, and return it.Pretty simple right? That’s exactly what I did in Ruby.
Ruby
I saved the best for last. To be consistent, I’ll show you the Fibonacci method I defined in Ruby:
class Fib
def fib(n)
return n if n < 2
return fib(n-1) + fib(n-2)
end
end
And here’s my memoization function:
def memoize(className, methodName)
className.class_eval do
alias_method("original_memoize_#{methodName}", methodName)
define_method(methodName) do |*args|
hash = instance_variable_get("@memoize_#{methodName}_hash")
if hash.nil?
hash = Hash.new
instance_variable_set("@memoize_#{methodName}_hash", hash)
end
return hash[args] if hash.has_key?(args)
res = self.send("original_memoize_#{methodName}", *args)
hash[args] = res
return res
end
end
end
The function takes as arguments: the Class to be modified and the corresponding method name as a symbol. With that it modifies the method, giving it memoization super powers.
So, given fib(Fib, :fib), the function:
- Opens up the Fib class and changes the fib method’s name to original_memoize_fib
- Adds a new method to the Fib class, called fib, that:
- Tries to get the hash table from an instance variable called @memoize_fib_hash
- If that instance variable doesn’t exist, it defines and initializes it with an empty Hash
- Checks if the key n exists in the hash table, if it does, then return it straight away.
- If not
- Call the original fib function, original_memoize_fib and calculate the value recursively
- Add it to the hash table
- Finally, return the value.
Simple Benchmark
Here’s an sample execution with n = 30.
Running Fib with 30 Without Memoization: 1.530000 0.000000 1.530000 ( 1.565292) With Memoization: 0.000000 0.000000 0.000000 ( 0.000440)
And that’s pretty much it for the Ruby version. Out of all the examples, I prefer this one, and not because it was me that did it. I find the code is a bit more elegant than the Lisp version, and a lot more elegant and less verbose than the Java one.
If you want to play with the code, you can get the full version here.