Vidar Hokstad V2.0

How to implement closures

Mon, 21 Dec 2009 11:45:15 -0500

This is a sort-of interlude to my regular compiler series.

The goal is to give a brief overview of some techniques for implementing closures in a programming language. I will use C for my examples, mostly because it's low level enough that a further translation to assembler etc. is straight forward, and many compilers target C directly anyway.

Before we start, most of the code examples in this post are available in this Gist so you don't need to cut and paste bits and pieces (which won't work anyway, as the text below will omit details such as header includes)

A closure) is in it's simplest form a block of code that can be passed around as a value, and that can reference variables in the scope it was created in even after exiting from that scope.

(For a more formal description look at the Wikipedia page linked above)

A Ruby block forms a closure, for example:


    def foo x
      printf "x is %d\n",x

      lambda do
        x += 1
        printf "block: x is %d\n",x

      end
    end
    
    c = foo(5)
    c.call

    c.call

Every time foo is called it will return a closure that has access to the x that was passed in to foo. In the example, x will start out at 5 and get incremented to 7.

The most important implication of this is that any variables used in the closure must be guaranteed to live as long as the closure does.

We'll get back to this example throughout this article.

There are a number of ways of handling this, for example:

Instead of a traditional stack, put activation frames (arguments and local variables) for function/method calls on the heap, as a linked list. When creating a closure, you just keep a reference to it. When returning from a function you unlink the frame from the ones below. Presto, the gc handles the remaining dirty details. Some variations of this is called a spaghetti stack
Rewriting. You can rewrite any function that may create a closure to create a separate heap allocated environment, and to copy/locate all arguments and variables that may be reused into it. The environment can safely be returned with the closure.
Copy. You can copy the current activation frame into a separate closure environment when returning the closure, ensure the closure refers to the variables via a reference, that is replaced with a references to the environment copy.
More? Probably...

Each of these have advantages and disadvantages.

We're going to look at the rewriting method mainly, though most of what you find below also apply to the copying method.

These methods are pretty similar - they both involve returning a pointer to the function implementing the code in the closure combined with a pointer to the data in the closure. The difference lies in how that data is accessed.

The rewriting approach creates the closure environment as early as possible, and changes the surrounding function to refer to that environment. It incures the closure creation cost whenever the closure generating function is created, but since local variables are initialized straight into the environment it avoids later copying.

The copy approach delays the creation of the closure environment as much as possible, and then copies the data. It can avoid unnecessary creation cost if there are paths that don't lead to creation of a closure, but when the creation happens, it needs to handle full copying of any objects or object references involved, which may be more expensive.

For both of these methods, care must be taken to create a single environment for any set of closures created during the same execution of the function that creates the closures.

"Fat pointers", objects and thunks

When returning a closure we also need to be able to pass along the environment.

As it turns out, there are a number of ways of handling this:

We can create a "fat pointer". I.e. instead of passing around only the address to the code, we also pass around a pointer to the environment, and it is the callers responsibility to load that address onto the stack or into a register so the code can get at it.
We can turn the closure into an object, like Ruby's Proc, and simply treat the variables used as instance variables of that object.
We can create our own half-assed almost object by storing the function pointer in the environment.
We can create a "thunk" on the fly - a small piece of code that will load the address of the environment and jump straight into the real code - and return that instead of a pointer to the real code of the closure. The major downside here is that it requires turning off protection against executing code from the heap.

The "fat pointer" approach is simple but involves more work at every call site, and doubles the size of the data that is passed around.

Turning it into an object is simple, and for my Ruby compiler it's even necessary a lot of the time since most of the time when you handle blocks in Ruby, you'll actually get a Proc object. But it has the full overhead of method dispatch.

The "half-assed object" approach still requires each call site to do a little bit more work, but less than the fat pointer approach. It also doesn't require additional data to be passed around (the function pointer is stored in the environment instead of copied around)

Creating a "thunk" also has overhead, but isn't as scary as it may sound - the code to create is very simple, and really it consists of copying a few bytes around.

We'll start with a "sort of" object, and then take a look at the thunk approach.

Simulating the rewriting method in C

closures-basic.c

C lacks pretty much everything that could make this convenient and easy, so it really lays the implementation bare, for better or worse.

First, let's create a structure to hold the function pointer and environment:



    struct closure {
      void (* call)(struct closure *);
      int x;
    };

If we had more local variables in foo, we'd add them to this structure.

Then we need to create a function with the code for the lambda block:


    void block(struct closure * env) {
      env->x += 1;
      printf ("block: x is %d\n", env->x);
    }

Finally we can implement foo:


    struct closure * foo(int x)
    {
      struct closure * closure = (struct closure *)malloc(sizeof(struct closure *));
      closure->x = x;
      printf ("x is %d\n",closure->x);
      closure->call = █
      return closure;
    }

Ewww..

A couple of observations: If we want to be able to return multiple closures (say, an array of them), the variables needs to be acessed via one more indirection, which makes this even more disgustingly convoluted.

It's also annoying, because it means lots of extra overhead in order to handle a situation that might very well never arise.

If the language requires supporting multiple closures (like Ruby), a compiler could support both approaches to optimize - adding the cost of the extra redirection only:

when more than one closure can potentially be returned at the same time.
when those closures need access to the same variables.

For an example of these restrictions, consider:


     def foo x
       a = 1

       b = 2
       if x
         return lambda { a += 1 }

       else
         return lambda { b+= 1 }

       end
     end

First of all, this function is guaranteed to only return one lambda at the time, so applying that rule, we can just assing the appropriate function pointer to the call member variable, and do away with the extra indirection.

Secondly, even if we decide to return both of them at the same time, they are guaranteed to never access the same variables, so we could instead create two distinct closure environments, and still avoid the extra indirection.

But let's take a look at the complete example with the extra indirection anyway, as a worst case scenario:

Indirection hell

closures-indirection.c

First we create an environment for the free variables we wish to "capture":



    struct env {
      int x;
    };

Our modified closure structure holds a pointer to it, instead of holding the variables:


    struct closure {
      void (* call)(struct env *);
      struct env * env;
    };

The block takes a pointer to the environment:


    void block(struct env * env) {
      env->x += 1;
      printf ("block: x is %d\n", env->x);
    }

And the closure function itself needs to first allocate the environment, and then the closure:


    struct closure * foo(int x) {
      struct env * env = (struct env *)malloc(sizeof(struct env));
      env->x = x;
    
      printf ("x is %d\n",env->x);
      
      struct closure * closure = (struct closure *)malloc(sizeof(struct closure *));
      closure->env = env;
      closure->call = block;
    
      return closure;
    }

Finally we call it with the env:


    int main() {
      struct closure * c = foo(5);
    
      c->call(c->env);
      c->call(c->env);
   }

Fat pointers

The example above is actually really simple to use to illustrate the fat pointer approach. Instead of returning a pointer to the closure object, we simply return the object itself:

closures-fatptr.c


    struct closure foo(int x)
    {
      struct env * env = (struct env *)malloc(sizeof(struct env));
      env->x = x;
    
      printf ("x is %d\n",env->x);
      
      struct closure closure;
      closure.env = env;
      closure.call = block;
    
      return closure;
    }
    
    int main() {
      struct closure c = foo(5);
    
      c.call(c.env);
      c.call(c.env);
    }

As you can see it makes some things simpler (no need for the second memory allocation step).

Variable substitution

An optimization worth keeping in mind is variable substitution. In cases where it can be guaranteed that the variables in question keeps the same value, the need for a separate environment may go away if variables are substituted for their values in the closures body.

Furthermore, if the variables can be guaranteed not to change in any closure returned from the function, then whether or not the variable changes in the function outside the closures, the closures may keep separate environments (and hence do the optimization to avoid indirection) with copies of the variables in question.

Of course this would require the function to carry out any updates once for each generated closure.

(you might have spotted here one of the advantages for functional languages with little or no mutation of variables - they have a lot fewer issues to worry about with respect to sharing of viarable state)

Moving on to thunks

closures-thunks.c

Now that we have the basics down, how do we return just a "plain" function pointer, so we can simplify the call sites?

What we want to create is something like the code below.

Note that we take a shortcut and don't create a proper stack frame - this kind of thing can easily confuse gdb and other debuggers, which is not necessarily very nice.

The thunk below also does not directly allow passing any arguments to the block - if we wanted to do that it gets hairier, since we'd need to manipulate the parameters passed, while the caller doesn't know we've altered the size of the parameter space set aside. In a compiler this would likely be solved by making either the caller or callee aware that it's a closure call, and adjusting the stack accordingly separate from the thunk.

Of course, the downside of using asm here is that it's architecture specific, and the code to generate the thunk will need to be modified accordingly to port the code, but then if you do this in a compiler that is outputting native assembly, you have to do that anyway.


    my_closure_instance:
        pushl $my_environment ; Push the environment onto the stack as the first arg
        call  $the_block      ; Go to the real code
        addl  $4,%esp         ; Throw the environment pointer away
        ret                   ; Return to the caller

Putting some arbitrary values in there, and assembling it with gcc/gas, and then doing objdump -D to the resulting binary gives this (and other bits and pieces I've cut - use the -nostdlib option to avoid dealing with a bunch of initialization code):


    08048055 :
    8048055:       68 00 08 af 2f          push   $0x2faf0800
    804805a:       e8 00 00 00 00          call   804805f 
    804805f:       83 c4 04                add    $0x4,%esp
    8048062:       c3                      ret

This shows us the values to put in our thunk. Couple of observations: The push is just followed by the address itself, but the call uses an offset from the first byte of the following instruction.

This approach of using structs to generate the thunk, I've blatantly stolen from Joe Damato because I like how it makes the code that manipulates the thunk more readable:


    struct __attribute__((packed)) thunk {
      unsigned char push_op;
      void * env_addr;
      unsigned char call_op;
      signed long call_offset;
      unsigned char add_esp_ops[3];
      unsigned char ret_op;
    };
    
    struct thunk default_thunk = {0x68, 0, 0xe8, 0, {0x83, 0xc4, 0x04}, 0xc3};

(the __attribute__ stuff is the gcc specific way of avoiding padding for alignement)

We change the rest like this:


    typedef void (* cfunc)();
    
    cfunc foo (int x) {
      struct env * env = (struct env *)malloc(sizeof(struct env));
      env->x = x;
    
      printf ("x is %d\n",env->x);
    
      struct thunk * thunk = (struct thunk *)mmap(0,sizeof(struct thunk), PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
      *thunk = default_thunk;
      thunk->env_addr = env;
      thunk->call_offset = (void *)&block - (void *)&thunk->add_esp[0]; // Pretty!
      mprotect(thunk,sizeof(struct thunk), PROT_EXEC);
      return (cfunc)thunk;
    }

The typedef is a workaround for C's absolutely atrocious ptr-to-function declarations...

The interesting bit is at the end where we allocate the thunk, and fill in the addresses

Then we cast the thunk data structure to a function pointer. That ought to make you feel dirty, and a bit queasy. It's ok, though.

We use mmap to avoid problems on systems with executable heaps turned off (execshield etc. that wil cause a segmentation fault if you try to execute code in malloc()'d memory or on the stack), and the mprotect() turns off write access to the page after we're done. For a production approach you may want a dedicated allocation function to properly manage this and perhaps avoid doing a separate mmap for every thunk created.

All of this could really be wrapped up into a nice generic function. Something like this:


    struct thunk * make_thunk(struct env * env, void * code) {
      struct thunk * thunk = (struct thunk *)mmap(0,sizeof(struct thunk), PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
      *thunk = default_thunk;
      thunk->env_addr = env;
      thunk->call_offset = code - (void *)&thunk->add_esp[0]; // Pretty!
      mprotect(thunk,sizeof(struct thunk), PROT_EXEC);
      return thunk;
    }

Finally, this makes our main function look like this:


    int main() {
      cfunc c = foo(5);
      
      c();
      c();
    }

Now that's nicer...

Since this is already gcc/Linux/x86-32 specific, it can be made even nicer. gcc supports inner functions, and with a tiny bit of restructuring and a couple of macros I did this, mostly for fun to see how close to a "natural" syntax for closures I could get in C without changing the compiler:


    #define initenv(__vars__) struct env { __vars__ ; } * env = (struct env *)malloc(sizeof(struct env));
    #define new_closure(__block__) (closure)make_thunk(env,&__block__)
    
    closure foo (int x)
    {
      initenv(int x)
      env->x = x;
        
      printf ("x is %d\n",env->x);
    
      void block (struct env * env) {  
         env->x += 1;
         printf ("block: x is %d\n", env->x);
      } 
    
      return new_closure(block);
    }

I'll still stick to Ruby...

Some parting comments

I wrote this while exploring various approaches to add closure support to my Ruby compiler. I haven't quite made up my mind yet. The object approach is tempting because Ruby already has the Proc class, but I'll probably go for an environment + fat pointer approach that will be converted into a Proc object if assigned to anything (as opposed to just used for yield)

The thunk approach is somewhat appealing too, but if turned into a Proc object it may be as much or more overhead than the fat pointer approach (and there will only be one call site: In Proc#call) and this approach would mean the fat pointer wouldn't be passed around much - typical usage would be passing a block to a method, and then yield'ing to it, where the yield would be the only call site.

Writing a (Ruby) compiler in Ruby bottom up - step 23

Wed, 16 Dec 2009 13:26:46 -0500

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

Continuing down the rabbit hole: String

A couple of parts ago we established some of the problems with supporting even the seemingly simple attr_reader, attr_writer and attr_accessor. To reiterate, a naive implementation looks like this:

def attr_accessor sym
  attr_reader sym
  attr_writer sym
end

def attr_reader sym
  define_method sym do
     %s(ivar self sym)
  end
end

def attr_writer sym
  define_method "#{sym.to_s}=".to_sym do |val|
    %s(assign (ivar self sym) val)
  end
end

We resolved the issue of having a working sym.to_s, but that still leaves a number of things to address. For example, we need at least the start of a "proper" String class that we can add #to_sym to. That's what we'll look at this time.

The first bit is very similar to what we did for Symbol: We won't type tag, and we'll create String objects for literal strings by calling a low level function.

Quick sidebar: Hiding the low level implementation

MRI "hides" the gory details of String and other basic classes by not making them real Ruby objects per-se. There's data there that is simply not accessible without dipping into the C API. We may eventually want to take a similar tack - add a mechanism for allocating space for, setting and retrieving low level variables via the s-expression syntax that are completely invisible for the higher level API.

Currently we don't. The "raw" string used for Symbol and for String objects is a normal instance variable, and it's perfectly possible to expose it, and accessing it thinking it's a real object will trivially easily cause nasty crashes.

In general, we would eventually benefit from creating a mechanism to "hide" the low level plumbing from accidental access by normal Ruby. For now we'll retain the ability to shoot ourselves in the foot easily.

The basics

The String class will for now contain just a pointer to a C-style string. It will be immutable in it's first incarnation. This gets us a decent step further very easily - we can just keep the address to a C-style string constant.

As it turns out, this will be an easy foundation to build on:

MRI uses a number of flags for strings, for example to do "copy on write". Once we need to make strings mutable, we'll do the same. Strings created from constants will start out marked as "copy on write", and when doing an update, the string buffer will be copied into freshly allocated space first. The hope is that many string constants will never be updated.

We also need to implement String#to_sym. This is thankfully also reasonably easy: We need to access the low level function we added that will retrieve a symbol based on a "raw" c-style string.

The code

As the last couple of times, this was unfortunately committed a bit piecemeal, so the commits aren't easy to follow. But lets go through this step by step.

First of all, we're going to rewrite the tree, to alter a literal string into

%s(call __get_string ConstantReferringToTheRawString)

So, we alter compile to add a call to rewrite_strconst:

#
# Re-write string constants outside %s() t
# %s(call __get_string [original string constant])
def rewrite_strconst(exp)
  exp.depth_first do |e|
    next :skip if e[0] == :sexp
    is_call = e[0] == :call
    e.each_with_index do |s,i|
      if s.is_a?(String)
        lab = @string_constants[s]
        if !lab
          lab = @e.get_local
          @string_constants[s] = lab
        end
        e[i] = [:sexp, [:call, :__get_string, lab.to_sym]]
        # FIXME: This is a horrible workaround to deal
        # with a parser inconsistency that leaves calls
        # with a single argument with the argument "bare"
        # if it's not an array, which breaks with this rewrite.
        e[i] = [e[i]] if is_call && i > 1 
      end
    end
  end
end

Effectively this visits all nodes that are not s-expressions, and if it finds a string, it will add a string constant. It will then use the label that is allocated to rewrite the expression like this:

[:sexp, [:call, :__get_string, lab.to_sym]]

As the following line says, it's a nasty workaround, and it will be torn out as soon as I get a parser, so just ignore that... pretend it's not even there ;)

Now, the reason we wrap the call to __get_string is that otherwise it will be rewritten to a method call because there really is no such thing as function calls in Ruby, but for some of our low-level plumbing we need actual C-style function calls (such as for calling out to C code).

We're also changing strconst, the method used to get the "value" of a string constant as follows:

-  def strconst str
-    lab = @string_constants[str]
-    return lab if lab
-    lab = @e.get_local
-    @string_constants[str] = lab
-    return lab
+  def strconst(a)
+    lab = @string_constants[a]
+    if !lab # For any constants in s-expressions
+      lab = @e.get_local
+      @string_constants[a] = lab
+    end
+    return [:addr,lab]
   end

What's left? Not much, really. You can see the basi c String class

Here's the important bit:

class String
   def __set_raw(str)
     @buffer = str
   end
end

def __get_string(str)
   s = String.new
   %s(callm s __set_raw (str))
   s
end

It's worthwhile reading the comments in at the link above if you want to see more about where this is heading.

We'll flesh out the String class in coming parts, but this groundwork now means we're working on a "real" object instead of on a raw pointer to a c-style string, which means it's mostly a runtime library issue instead of requiring much in terms of compiler changes.

One of the things worth mentioning that is covered in one of the comments in lib/core/string.rb is that the whole __get_string and __get_symbol thing is a bit ugly. As I mentioned earlier in this part, hiding the low level implementation would be nice, and that includes preventing direct calls to __get_string and _get_symbol, and that can be done trivially by simply ensuring the Ruby code can't directly do function calls (as opposed to method calls). But that doesn't solve String#__set_raw. To fix that, I'll need to either remove the need for the method, or by making it possible to "hide" certain methods entirely from the Ruby code...

It's not a priority now, though - first we get things working, then we make it pretty.

What about String#to_sym? Well, this ought to do the trick:

class String
  def to_sym
    __get_symbol(@buffer)
  end
end

So, that leaves us with a working define_method and %s(lambda) with support for variables to get attr_reader,attr_writer and attr_accessor working... We're heading down that road soon.

Ruby gets a spec

Thu, 10 Dec 2009 13:53:39 -0500

A week or so ago, the Ruby Draft specification made the rounds

Yes... Ruby is finally getting a standard. While RubySpec has been around for a while, and is a great, it is an executable specification that tells you what, not why, and it aims to be "complete" while the new project aims to define a shared core suitable for implementation by all the different Ruby implementations that are springing up.

I think they're complementary enough that the Ruby Draft Specification could be very beneficial.

For my compiler project this means there's now a compelling reason to revisit some things (such as the parser) to look at conformance, and a clear roadmap for some others (classes) to ensure it at least meets the spec.

Of course, in many ways MRI will still be the benchmark, but the standard will provide a minimal level of conformance that will likely be easier to achieve.

In particular, the spec includes a formal grammar for Ruby that doesn't involve walking through thousands of lines of code written for another implementation to verify that you're doing things right. I'm particularly looking forward to going through my parser and aligning it more closely with the draft spec... (I'm sure I'll be swearing a lot while doing it, though)

It also includes descriptions of expected semantics for things like the object model that have previously been something a lot of people (including me) have spent time revers engineering to figure out.

Combined with all the Ruby implementations in progress, this is a clear indication that Ruby is growing up and becoming a contender in areas where it would previously not be acceptable.

Keep an eye on the Ruby standard project...

Virgin Media, or how to make your customers hate you

Sat, 05 Dec 2009 11:45:38 -0500

UPDATE: I e-mailed most of the below to Neil Berkett, CEO at Virgin Media, earlier today. Neil had a guy called Peter call me to apologise and to confirm that they will arrange to have my account cancelled right away, as I had requested. Thanks to both of you - it goes some way to improving my impression and shows that at least some of you do care about customer impression. Just get the message through to your front line staff as well. I've posted this elsewhere, but it really belongs on my own blog too. I've you follow me on Twitter you've probably seen me complain loudly about Virgin, and briefly about BT too. The difference being the BT listened (following me on Twitter, getting back to me and fixing my problem within hours of becoming aware of it) while Virgin's behaviour so far has just gotten worse and worse. Here's the background: A couple of weeks ago my internet, TV and phone (though we dont use the Virgin phone service, so the latter didnt matter) went down. Called Virgin, and after lots of waiting and extremely unhelpful people we were given two different times for two different people to come look at our broadband and TV, even though both failing at the same time pretty much guaranteed it was the cable. Whatever, I thought, I can understand they dont want frontline staff making judgements like that. Sure enough, the two people came at different times, both said it was the cable. They promised itd be fixed by 5pm same day. Nobody came or called or told us anything. So around 7pm we called. Was put through the same round of questions before anyone would even listen to the complaint about lack of follow up. Was then finally told that someone would fix it by 6pm the following night. 6pm next evening came and went. No word from Virgin. Called them again, and was told that oh? nobody told you? They need to schedule repair for December 8th. Two weeks away. After I'd already waited several days. At which point I lost it. It was bad enough that their estimate was so long, but I might have accepted that, had I not by then had to endure hours of waiting in call queues, and repeated broken promises about when the problem was supposed to be fixed or when I would be called back (fort that matter this is not the first time I've had to deal with Virgin's poor excuse for customer service) So I told them they had until the following morning to get someone to call me and try to find another slot. Needless to say nobody called. So I looked around, and Sky turned out to be half the price of what I was paying for my broadband and TV, with more channels. Downside (or so I thought)? Having to deal with BT over ADSL. Install date? December 3rd and 4th. Not great, but contrary to Virgin they had the excuse that they were signing up a new customer, not fixing a problem for someone who had already been a loyal paying customer (paying through the nose for their top of the line packages) for years. So a few days later I wait for 40 minutes on a call centre line to cancel Virgin. Get through to some very unhelpful woman that wants me to call back to the same number I've just waited 40 minutes to get through on, because she cant put me through to the same people. Despite the fact their menu system doesn't work. I say no. Not my problem. Ive had enough. Im notifying them that I am cancelling the service. It is not my responsibility to work around their broken calling centre system when they could take a message and pass it on later. (Newsflash, Virgin: Companies with decent customer service does this. When I deal with my bank, or my other utilities, if something takes to long, I ask to get called back or for someone to pass on a message, and surprise, surprise, they actually do.) After ten minutes of arguing, she finally just puts me through to a supervisor without asking me first. I explain to the supervisor, argue with him, points out Ill just cancel my direct debit and that since I've already notified them that I'm cancelling I'll sue if they try to keep charging me (threatening to sue has an amazing effect in most cases). I'm finally promised that someone will call the next morning to confirm my cancellation. Nobody calls. Yeah, I'm not surprised, because if they'd called back they'd have broken a pattern of excessively bad service. So I fill out a complaint form on their website. Later that same day, on the 3rd, a Virgin repair guy show up with no warning to dig up our front garden and carry out the repair that was impossible to do before December 8th Eh. If theyd treated me properly first time around instead of jerking me around for 3 days, and then had told me they could repair things by the 3rd, and called me back when they promised to, Id probably have still been a customer (and paid over the odds for the privilege but not particularly cared). So of course we told him no, were no longer Virgin customers. Same day BT enabled our Sky ADSL. Or so we thought. Line is broken (as in, our landline stops working). I file a fault, gets told December 7th, gets pissed off and figure this is the BT Ive learned to loathe. Complain on Twitter the following morning. @Btcare on Twitter gets involved. 4 hours later an engineer is at our house, and the line is fixed shortly thereafter. At the same time Sky installs our new TV service, and the installation guys laughs about the familiar story when my wife recounts our woes to them. Now were up to this morning. I receive two phone calls. First one: Virgin Media complaints department: A rude woman starts arguing with me over whether or not Ive cancelled and proceeds to talk over me and then turn around to repeatedly interrupt me to complain about me interrupting her, forcing me to gradually raise my voice to even be able to explain the situation without having her constantly talk me down. After minutes of that I'm finally given a chance to speak long enough to point out that after dealing with their dreadful call centre (and her!) theres just no way Im dealing with another one after Ive notified them both by phone and by e-mail, and had her confirm to me on the phone, that theyve received my cancellation. Its not as if they can claim in any shape or form not to have received it. Argument goes on and on, until she just hangs up on me. Way to deal with complaints, the Virgin Media way: Have your biggest asshole call up the customer and talk over them and repeatedly tell them they're wrong and practically taunt them into hating you and your company. Then BT calls: (pay attention to this Virgin) They call to apologise profusely over not dealing with our problem sooner (time from initial fault report to problem was fixed: 24 hours; time from complaint over handling to problem fixed: 6 hours; time from complaint over handling to engineer was at our door: 4 hours); wants to make sure the engineer fixed our line properly; wants to find out what might have gone wrong in the first place to make us upset. Truly the only problem was that I got a long-ish repair estimate (four days; still miniscule compared to Virgin), which was annoying but to be honest I probably wouldn't even have bothered to complain about it if the treatment Virgin have given me over the last few weeks hadn't made my fuse incredibly short to begin with. Overall, in BTs case their fault reporting on their website needs to improve a bit (indicate that the problem will be fixed "no later than"; inform of how to contact Btcare; make it clearer that you'll only get regular updates if you sign up for SMS, not e-mail too), but once someone got wind of me being dissatisfied the problem was fixed quickly. With Virgin, on the other hand? Insultingly rude and arrogant calls, and apparently they still think Im their customer. I never thought Id see the day when I did this: BT actually did well. Problems happen, I accept that - I work with technology all day. What matters to me it how a company responds when they do. BT responded properly, and while I was a bit angry initially Im very happy with how it turned out. The call this morning was a very nice touch. Virgin on the other hand managed to turn me from a devoted customer who wouldnt even consider looking around (I honestly had no idea how much over the odds we were paying for Virgin, because price didn't really matter to me as long as things worked), to detesting them beyond what words can convey in two short weeks..

Writing a (Ruby) compiler in Ruby bottom up - step 22

Tue, 10 Nov 2009 09:20:49 -0500

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

A diversion into Method missing

So far the method_missing implementation has just printed a notice and quit.

During the trip down the rabbit hole that is attr_accessor and friends that became a major annoyance.

The problem is that this notice has not included a stack backtrace or any way to figure out where it occurred. It's also been impossible to override it and actually figure out what method was being called because we currently get to method_missing by jumping straight into the vtable.

We get method_missing when we hit the pointer that's installed there as default when nothing has overridden it.

So how do we get better debug output? And how do we support users overriding method_missing and actually getting a symbol to use?

Thunks

A "thunk" in terms of a object oriented languages is generally a small piece of compiler generated code that gets inserted to "adjust" a function or method call.

In this specific case, we will generate a separate thunk for each vtable entry.

Instead of inserting a pointer to method_missing directly, we will insert the address of a small thunk. The thunk will not even create a full stack frame, but simply add the address of the Symbol corresponding to the vtable slot as the first argument on the stack, and then jump straight into method_missing, thereby simulating a "direct" call to method_missing with the symbol as the first argument.

It's actually very simple - we just need to pop the real return address off the stack, push the symbol onto the stack, and then push the real return address back on.

Ok, so we still cheat a bit. Eventually we need to make our method_missing into a real method, but for now it's a function. Here's the code I've added to create a "base" vtable that is used to initialize the vtable slots of Object:


    def output_vtable_thunks
      @vtableoffsets.vtable.each do |name,_|
        @e.label("__vtable_missing_thunk_#{clean_method_name(name)}")
        # FIXME: Call get_symbol for these during initalization 
        # and then load them from a table instead.  
        compile_eval_arg(GlobalScope.new, ":#{name.to_s}".to_sym)
        @e.popl(:edx) # The return address 
        @e.pushl(:eax)
        @e.pushl(:edx)
        @e.jmp("__method_missing")
      end
      @e.label("__base_vtable")
      # For ease of implementation of __new_class_object we
      # pad this with the number of class ivar slots so that the
      # vtable layout is identical as for a normal class 
      ClassScope::CLASS_IVAR_NUM.times { @e.long(0) }
      @vtableoffsets.vtable.to_a.sort_by {|e| e[1] }.each do |e|
        @e.long("__vtable_missing_thunk_#{clean_method_name(e[0])}")
      end
    end

I hope it's reasonably easy to follow. First it generates a number of functions that will look like this:


    __vtable_missing_thunk_to_yaml:
        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L110, (%esp)
        movl    $__get_symbol, %eax
        call    *%eax
        addl    $4, %esp
        popl    %edx
        pushl   %eax
        pushl   %edx
        jmp __method_missing

This can be optimized a lot, but if you've followed this series, you know getting something working is higher priority. In this case we generate a call to __get_symbol, which was introduced in the last part, and we pass the string corresponding to the name:


    .L110:
        .string "to_yaml"

Then we adjust the stack as mentioned above.

The next step is to create the __base_vtable. Here's an excerpt:


    __base_vtable:
        .long 0
        .long 0
        .long __vtable_missing_thunk_new
        .long __vtable_missing_thunk___send__
        .long __vtable_missing_thunk___get_symbol
        .long __vtable_missing_thunk___method_missing
        .long __vtable_missing_thunk_array
        .long __vtable_missing_thunk___new_class_object
        .long __vtable_missing_thunk_define_method
        ...

Then we need to modify __new_class_object to assign entries from __base_vtable instead of just blindly assigning a pointer to __method_missing:


    # size <= ssize *always* or something is severely wrong.                                                                                                                
    def __new_class_object(size,superclass,ssize)
      ob = 0
      %s(assign ob (malloc (mul size 4))) # Assumes 32 bit                                                                                                                  
      i = 1
      %s(while (lt i ssize) (do
          (assign (index ob i) (index superclass i))
          (assign i (add i 1))
      ))
      %s(while (lt i size) (do
           # Installing a pointer to a thunk to method_missing                                                                                                              
           # that adds a symbol matching the vtable entry as the                                                                                                            
           # first argument and then jumps straight into __method_missing                                                                                                   
           (assign (index ob i) (index __base_vtable i))
           (assign i (add i 1))
      ))
      %s(assign (index ob 0) Class)
      ob
    end

Finally we make __method_missing output the symbol, instead of just spitting out "Method missing":


    def __method_missing sym
      %s(printf "Method missing: %s\n" (callm sym to_s))
      %s(exit 1)
      0
    end

A pitfall of the Ruby Range class

Thu, 05 Nov 2009 08:05:14 -0500

I tweeted about this, but figured it deserve a more lasting treatment.

If you've ever used Range#min or Range#max you may have inadvertently slowed your code significantly.

Both of those ought to be O(1) - constant time. After all, a Range in Ruby consist of two values, and though you can't be assured whether or not the first one or the last one is the smallest/biggest one, the obvious implementation is this:


    def min
      first <= last ? first : last
    end

.. and the equivalent one for Range#max. Except that's not what happens, as you can easily convince yourself by doing:


    $ irb
    irb(main):001:0> (1..10000000).max
    => 10000000
    irb(main):002:0>

... and see how slow it is. Eww. The explanation is that min/max are only provided in generic versions that iterate over the full Range (so that the same implementation also works on other collections).

If your app, like mine, frequently needs the smallest or greatest value in a Range, it may be time to monkey patch:


    class Range
      def min
        first <= last ? first : last
      end
          
      def max
        first >= last ? first : last
      end
    end

For the app that made me notice this problem, adding the above monkey patch caused a 30% speedup. Of course, if most of your ranges are small, or you don't use Range#min or Range#max anywhere, you may not notice any difference at all.

Writing a (Ruby) compiler in Ruby bottom up - step 21

Sun, 01 Nov 2009 17:38:38 -0500

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

I've been lazy lately... Well, not really, I've been extremely busy, but I ought to have fit this in earlier. It's gotten harder and harder to get done too, since it's now more work since I had to go back and figure out a lot of the reasons for what I'd done.

Anyway, finally a new part, though short.

Down the rabbit hole: attr_(reader|writer|accessor)

Adding attr_reader / "attr_writer" / "attr_accessor" Should be easy, right? After all, all they do is allow read/write or both of member variables.

Trouble is you can't know that in advance.

    class Class
      def attr_reader foo
        puts "Hah!"
      end
    end

    class Foo
      attr_reader :bar
    end

    foo = Foo.new
    p foo.bar

Ouch. This is part of what makes Ruby exceptionally painful to compile.

It doesn't mean we can't make some assumptions, though, as long as we can handle the worst case where someone does something stupid (later we may want to add an option to make it assume you're not being stupid, and enable additional optimizations).

So how do we do this then?

Well, the obvious answer is to implement it in Ruby. Here are naive initial implementations (that only handle a single symbol, not an array like the real thing):

    def attr_accessor sym
      attr_reader sym
      attr_writer sym
    end

    def attr_reader sym
      define_method sym do
         %s(ivar self sym)
      end
    end

    def attr_writer sym
      define_method "#{sym.to_s}=".to_sym do |val|
        %s(assign (ivar self sym) val)
      end
    end

Note the s-expressions that rely on a new "ivar" primitive (that's not been added yet). That part is simple enough to add, but what else does the above require to be added to the compiler?

That's the ugly part. Here's a (possibly incomplete) list:

define_method
Real Symbol class
Symbol#to_s
Real String class
String.to_sym
Indirectly the :lambda s-expression construct needs to have support for variables

This is part of the reason I picked attr_* as the next thing to implement: It's an important, frequently used piece of functionality that snowballs and help drive implementation of functionality that is actually likely to be used.

Baby steps

First take a look at this commit

This is one of our assumptions (in between some other cruft): If you use attr_accessor etc., you are likely to need a vtable entry for that method.

Remember, we still don't implement a proper "fallback" in the form of a hash table for cases where the vtable gets "too big" (whatever we decide too big is) so for now we need this, but even later it'll be a useful optimization for many cases.

Worst case? We waste a vtable slot.

Next is where we actually add the basic implementations shown above, plus some debug statements, and stub for "define_method".

The comments bring us to an important question:

To type-tag or not to type-tag?

In MRI Symbol objects are "type tagged" integers. That is, they are not real objects at all, rather each symbol is represented by a specific 32 bit value, and those values can be identified as symbols by looking for a specific bit-pattern in the least significant byte.

This has the advantage of saving space - no actual instances need to be constructed. In this instance, however, it creates a lot of complication, by requiring the type tags to be checked on each and every method call.

For this reason we will, at least for now, avoid it.

(For Fixnum we will run into this problem again, and it will be even more tricky - for Symbol the number of objects can be expected to be reasonably small, but what about Fixnum? Ugh... Lets think about that later)

Instead we will keep a hash table of allocated symbols, which we will use to return the same object for the same symbol literal

I'm going to skip over most of the commits here, and show you the current state of the Symbol class and its associated compiler changes, since I must admit my commits have been quite messy and all over the place while putting in place these changes, and it's not very condusive to explaining the actual changes.

    class Symbol
      # Using class instance var instead of class var
      # because the latter is not properly implemented yet,
      # though in this case it may not make a difference
      #  @symbols = {} # FIXME: Adding values to a class ivar like this is broken
      
      # FIXME: Should be private, but we don't support that yet
      def initialize(name)
        @name = name
      end
    
      def to_s
        @name
      end

      # FIXME
      # The compiler should turn ":foo" into Symbol.__get_symbol("foo").
      # Alternatively, the compiler can do this _once_ at the start for 
      # any symbol encountered in the source text, and store the result.
    #  def self.__get_symbol(name)
    #    Symbol.new(name)       
    #    sym = @symbols[name]  
    #    if !sym               
    #      sym = Symbol.new(name)
    #    end
    #    sym
    #  end
    end

    def __get_symbol(name)
      Symbol.new(name)
    end

Uh, yes. I started out with actually having it turn symbols from text into an object at runtime, but I quickly realized this makes no sense for the case where a literal symbol is present in the program.

Note that we still need a proper Symbol#__get_symbol as commented out here later, because it is necessary to handle things like String#to_sym. However for now I've skipped it for a simple reason:

It requires implementing a hash table. It's not that hash tables are hard. But currently implementing Hash in pure Ruby likely will require features that are not in place yet... So, lets sort out the literal Symbols first, and then work our way up.

The trivial version above is well and good, but we need to make the compiler call __get_symbol..

So we replace Compiler#intern with this:

    # Allocate a symbol
    def intern(scope,sym)
      # FIXME: Do this once, and add an :assign to a global var, and use that for any
      # later static occurrences of symbols.
      args = get_arg(scope,sym.to_s.rest)
      get_arg(scope,[:sexp,[:call,:__get_symbol, sym.to_s]])
    end

As you can see from my comment, it really makes no sense to call __get_symbol over and over - it's inefficient. But it works for now. We'll go back and fix that later.

Also note that this doesn't exactly match the above commit, but also incorporate a change from a later commit: We do [:sexp ..] there because :sexp nodes don't get rewritten to a :callm, and __get_symbol here is indeed a function not a method (this distinction doesn't really exist in Ruby, but it exist at the implementation level in our compiler, because it eases interoperability with C - this may change whenever I get to the point where it makes sense to implement FFI support)

The other changes are simply there to reflect the fact that intern now returns the result of a get_arg instead of some arbitrary integer:

    -      return [:int,intern(name.rest)] if name[0] == ?:
    +      return intern(scope,name.rest) if name[0] == ?:

That's it for now, folks

I promise it won't be nearly as long to the next part. I need to untangle my changes for splat operator support, method_missing debug improvements, and work on the Array and String classes. I'll likely give each one of them a short part each before I get fully "back on track" - I intend to write the future parts in parallel with actually making the code changes.

Vacation over

Wed, 19 Aug 2009 20:03:19 -0400

Just got back from a short vacation on the Isle of Wight and New Forest on Sunday night... Since then we've been relaxing at home, apart from a two hour detour to the office.

Tristan and me on the Esplanade in Ventnor:

The trip was nice - we had some trepidation in advance about bringing Tristan on another vacation at just a bit over 3 months. He was very good in Norway earlier this summer, but then we were around family and my mom and her partner used the opportunity to take him off our hands a lot of the time. Especially since we don't drive, and so took a cab to the station, train from Croydon to Portsmouth, ferry from Portsmouth to Ryde, train from Ryde Pier Head (the station - below - lies half a mile off the shore, as the ferries can't safely get closer) to Shanklin and cab from Shanklin to Ventnor just to get to our hotel. But he was calm the whole time.

After a few days on Isle of Wight we went to Lyndhurst, New Forest and spent the weekend there, with visits to Lymington, Beaulieu (compulsory complaint: Why, oh why must the English pronounce everything inconsistently - the "English" pronunciation of Beaulieu just refuses to stick in my head; I guess that's what I get from actually knowing how the French "beau lieu" which the name comes from is pronounced; also: Lynd-hurst, but Ash-urst) and Exbury gardens.

Next time we'll probably spend a bit longer in one place - dragging all the extra stuff required for a baby with us made it a bit stressful, and scheduling everything around his feeding and nap times and diaper changes made things a bit frantic.

Last three days we haven't even left the house apart from my little office trip. "Recovering" from the trip I guess... Besides, it's been far too hot out today.

... otherwise

... I've finally been hacking a bit on my Ruby compiler project again today (and I did a few bits and pieces whenever I could find a spare minute in the last week or so before I went off on vacation), and just got a couple more things I want to wrap up before posting another part in my series. I hope to post another part in a week or two.

Specifically I'm working towards making #attr_reader/writer/accessor work, which seems simple, but it led me down a rabbit hole to implement basics of Symbol, #define_method, as well as fix a number of bugs. On the upside getting this in place also means adding better debug output to #method_missing becomes simpler, and I have reasons to think that execution of the compiled version of the compiler itself will get a massive step closer.

Best way of keeping an eye on what's going on in the meantime is to follow my Github commits, or my Twitter feed.

Proof of concept SVG editor gadget for Google Wave

Fri, 05 Jun 2009 07:14:17 -0400

A couple of days ago I presented a "emulator" of sorts to run Google Wave gadgets without sandbox access because Google hadn't started giving out access yet. They have now, to Google IO attendees at least but not to the rest of us (or have they?) so I still don't have mine (hint, hint)

Anyway, what good would it do to write that gadget emulator without using it, so I've put together a very rough proof of concept for a shared graphics editor gadget using SVG. I didn't write all of it myself, mind you. Jayesh Salvi started a discussion about SVG in Wave, and during that discussion he pointed us to an existing open source browser based SVG editor by Narendra Sisodiya and Pavol Rusnak.

That made my job reasonably easy. I chopped their editor to pieces and stripped out a lot of stuff, partially to reduce the amount of work to make it work with Wave, partially to remove features that aren't quite finished yet.

The result is still buggy (clearing the canvas doesn't work; deletion is shaky), not as efficient as it could be (at the moment it re-sends all attributes of modified elements instead of just the changed ones, but that's easily fixed), lacks lots of features (like moving objects, saving, loading external SVG's etc.).

More importantly, since I don't have sandbox access it has not been tested with the actually Google Wave client (hint, hint; any Google people reading this?) It is possible or even likely that it won't work in the real client, but any issues should be reasonable simple to fix.

It's been tested - somewhat - on Firefox and Safari. It is highly unlikely to work on Internet Explorer (it's possible it could work if you have an SVG plugin installed, but I doubt it). It could be made to work on IE via a shim layer to use VML instead of SVG, but that's not very high on my priority list at the moment - especially as Google looks set to introduce a suitable shim layer.

You can test it now by going to my gadget emulator, and entering the filename "svg-edit.xml".

If you want to experiment with the code on your own, get the latest version of my gadget emulator from the Github repository and the SVG editor gadget also from Github.

Not that while I welcome patches / suggestions, this is a proof of concept and I'm not sure how far I'll take it - I also have not talked to Narendra or Pavol about whether it's possible or desirable to fold any of the (fairly extensive) changes I made back into the original editor. If you'd like to see this turn into something more, let me hear about it in the comments.
UPDATE: I will be working with the SVG Edit guys to combined the two projects. Also see this post at The Next Web

(And if you're with the Google Wave team and want to give me sandbox access, e-mail me at vidar@hokstad.com or vidar.hokstad@gmail.com - I promise I'll use it to make sure this gadget runs properly in the actual client ;) )

Google Wave Gadget Emulator

Mon, 01 Jun 2009 19:31:18 -0400

The Google Wave demo contained a variety of "gadgets" - small little apps written in Javascript that interacts with Wave.

It's one of the more interesting parts of the frontend, allowing you to customize the experience, and make the interaction with other users more structured (the pic to the right, borrowed from the Google Wave gadget API guide for example, shows an event attendance gadget, a chess gadget and a maps gadget.

Cool. But since I don't have sandbox access, and even with sandbox access might like to be able to instrument and debug things in different ways than Google has prepared for, and since it seemed like a good educational exercise in figuring out the gadget API's, I decided to take matters in my own hands.

So I wrote a Google Wave Gadget API emulation layer. Just a tiny little bit of javascript to reimplement just barely enough of the gadget API to allow some of the demo gadgets to run side by side in two iframes. It's very rough around the edge, not very cleanly written, probably full of bugs, and only tested on Safari and Firefox, but here's an example:

But it's more intesting to play with it yourself here.

If you find bugs, have comments, or want to add features to it, post in the comments here, or go over to Github where I've put the files you need. On top of the files in the Github repository you can find Gadget examples from the Gadget API guide posted above - you need to drop them somewhere on the same domain for jQuery to get hold of it.

The Github repository is here: http://github.com/vidarh/wave-gadget-emulator/tree/master