Buu Nguyen's Blog

After the previous post, it came across me that member_missing can be used to implement something like Python’s defaultdict. So I thought it’s interesting to code up an example leveraging this ability.

You know the fibonacci calculating algorithm right? This is the fibonacci code (except written in Bike, not Java) that I use to teach my students about recursion in an entry Java programming course:

var fib = func(n) {
  n < 2 ? 1 : fib(n-1) + fib(n-2)
};

Clean and simple! A base case on the left expression of the ternary and a recursive case on the right. Probably among the best to introduce people to the concept of recursion. What I didn't tell my students is that this is extremely inefficient. Pick fib(30) for example. It will invoke fib(29) + fib(28). fib(29) in turn invokes fib(28) + fib(27). Notice something? No? Read again? Still no? fib(28) is executed twice. And this is just the top part of the call tree. As you go down further, this phenomena is phenomenal, i.e. fib(27) is invoked tree times, fib(26) four times and so on! Needless to say, your CPU won't be very happy. Enter memoization.

In a nutshell, we use memoization as a technique to cache result of previous invocations. Assume the function has no side effect (i.e. being idempotent), which should generally be the case in a functional language, we can later reuse the cached result should the function is invoked again with the same arguments. Here's the code to compute fibonacci making use of memoization technique (and member_missing, as defaultdict).

func memoize(f) {
  var cache = {
    member_missing: func() { null }
  };
  return func recur(n) {
    cache[n] || (cache[n] = f(recur, n));
  };
}

var fib = func(n) {
  n < 2 ? 1 : fib(n-1) + fib(n-2)
};

var m_fib = memoize(func(recur, n) {
  n < 2 ? 1 : recur(n-1) + recur(n-2);
});

load 'stopwatch.bk';
var watch = Bike.Stopwatch.create( ).start( );
println('fib(20) = {0} (elapsed: {1}ms)', fib(20), watch.stop());

watch.reset().start();
println('m_fib(20) = {0} (elapsed: {1}ms)', m_fib(20), watch.stop()); 

Run the code and you should notice a significant difference between the run time of the normal fibonacci and one with memoization.

I always like the ability of objects to dynamically respond to a message without having an explicit binding. Something like method_missing in Ruby or DynamicObject in .NET. It would be great for Bike to have that capability. Fortunately, adding this feature was much easier than I thought, thanks to how the interpreter code was already laid out. Please join me welcoming member_missing in Bike! Let’s examine this feature more closely, shall we?

var obj = {
  member_missing: func(name) {
    return "Member: {0}".with(name);
  }
};

println(obj.notExist); # Member: notExist
println(obj.has_member('notExist')); # False

The code above creates an object and defines the special member_missing method, which will be invoked by the runtime whenever it can’t resolve a member. Therefore, when trying to access notExist, methodMissing is invoked with the member name as its only argument and has a chance to decide what to return. In this case, it returns a string showing what member was being accessed.

This works for method invocation as well. When the interpreter attempts to invoke a method, the first thing it does is resolving the method object (Bike.Function) before invoking it. Therefore, member_missing can also do its magic here by returning a method that the runtime will instead invoke.

obj = {
  member_missing: func(name) {
    if (name == "add") {
      return func(a, b) { a + b };
    }
  }
};

println(obj.add(1, 2)); # 3

You see, Bike’s member_missing doesn’t behave exactly like Ruby’s method_missing. I could modify the runtime to instead of invoking the function returned by member_missing, it will invoke something like method_missing (Bike edition!) and pass in the call information (e.g. name, arguments). Maybe that what I should have done for efficiency sake (i.e. avoid creating a function every time!). Then again, maybe later, one thing at a time, eh. For now, those who care about a bit of efficiency here and there, you can cache the generated method, as follow.

obj = {
  member_missing: func(name) {
    if (name == "cache") {
      return this.cache = func() {};
    }
  }
};

obj.cache();
println(obj.has_member('cache')); # True

The next time obj.cache() is invoked, member_missing() isn’t invoke anymore because an explicit binding already exists.

Now, a more interesting example demonstrating the power of member_missing. If this somehow reminds you of Rails‘ ActiveRecord, you’re right.

var db = {
  member_missing: func(name) {
    if (name.starts('find')) {
      return db[name] #! cache it !# = func(obj) {
        var sql = 'SELECT * FROM {0}'.with(name.sub(4).upper());
        obj.members(false, true).each_with_index(func(name, index) {
          sql += (index == 0 ? ' WHERE ' : ' AND ') +
                 name.upper() +
                 (obj[name] is Bike.String ? '' : '=') +
                 obj[name]
        });
        println('Executing...{0}{1}', NL, sql);
        return [#! Suppose I'm a product array, yay! !#];
      };
    }
  }
};

# SELECT * FROM PRODUCTS WHERE CATEGORYID=1 AND PRICE>1000
var products = db.findProducts({categoryId: 1, price: '>1000'});

Interested? Have Bike up and running and start hacking. The examples above can be found in GitHub.