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.

First of all, here's the biggest reason I've been so excrutiatingly slow with getting this part together (at least that's my story, I guess I've had other things on my plate too...):

Tristan is 13 months now, and a real menace to my laptop (pulling off keys and drooling on the screen) and anything else within reach, and a real attention seeker...

So, whenever I'm slow at posting a new part, I'll blame him. I have no part in the delays at all, of course. None. I'm completely faultless...

Towards define_method via closures

For starters, here's the commit that covers most of this

To support define_method we need to support blocks with arguments. Really, full closures.

If you haven't already, you should read my post on closures

We want this:

    define_method(:foo) do |a,b|
       # Do something with a,b
    end

to be mostly equivalent to:

    def foo a,b
       # Do something with a,b
    end

For our attr_* implementation we actually want more:

    def attr_reader sym
      define_method sym do
        %s(ivar self sym) # FIXME: Create the "ivar" s-exp directive.
      end
    end

(or, as it turns out, not really that, as I realize the above can be simplified - if we have a lookup function to lookup the symbol to instance var slot, we can just use our index primitive to get the address; we'll return to that, but the above is the current state of attr_reader)

What that calls for is actually proper closures. One step harder.

There's the other issue that the above will be really inefficient. As in, requiring a hashtable lookup on every call inefficient, when we can statically determine the offset for any instance variable we know about at compile time. We'll get back to that at some point too, but if you've been following this series you know I care about getting things working first, efficient second.

For now attr_reader and friends still serve as a useful test case for basic closure support.

Baby steps

The first step towards closures is actually easy (we've already done it). We have our :lambda primitive that creates an anonymous function (which isn't really anonymous, it's just that the name is quitely created in the compiler and not accessible to the programmer).

Adding an environment

But an anonymous function is only of relatively limited use if you can't bind variables to it - it's not much more than a function pointer in that case.

So how do we let "sym" hang around, and how do we take advantage of that for define_method?

First, let us consider how you can call a lambda in Ruby:

• yield
• Proc#call

We could implement Proc#call via yield by passing the block as an argument to a method, if we wanted to, but that would probably be more inefficient than implementing both in terms of a primitive.

But this means those are the only things that has to explicitly know how to deal with the environment.

That gives us an interesting option. We could turn:

    c,d = somevalues
    do |a,b|
       ... uses c,d 
    end

into

    class SomePrivateUniqueClassName
        def initialize c,d
           @c,@d = c,d
        end
        def call(a,b)
            ... code here with access to c,d rewritten
        end
    end

And we could have it inherit Proc. yield in that case is just rewritten to block.call

This does however have the troubling implication of messing with self, and as this irb session shows, we'd have to fix that:

>> lambda { p self }.call
main
=> nil
>> 

The other alternative is to create a lightweight environment binding of sorts. Oh wait, we already have that. It's called an object. The problem is not the class above as such, but creating a full class for each block. We could do something like this instead:

    class Proc
      def initialize & block
         # So Proc#initialize takes a block, but we're using this
         # to create blocks... Uh oh, I sense endless recursion.
         # We need to make it work so we can initialize a Proc
         # both from a block and from a raw function pointer
      end
      def call *args
         %s(call @block_func (res args))
      end
    end

Our code needs to be rewritten, so that blocks get wrapped in code to create the appropriate Proc object. Additionally, if the method uses variables from the surrounding scope, we need to alter the surrounding method and the block to refer to instance variables in this object, and if any of those variables are arguments to the surrounding scope, we need to copy them.

An example

Here's a simple example using a closure. Note the use of s-expressions here because we're now starting to get bitten by the changes we've done to turn Ruby code by default into method calls (the way it should be) without having put in the pre-requisite work to implement the number classes and Kernel methods (such as print to replace the libc printf). Ignore that for now.

    def mkcounter step
      cnt = 0
      lambda do
        %s(assign cnt (add cnt step))
        %s(printf "cnt: %d\n" cnt)
      end
    end
    cnt = mkcounter(5)
    cnt.call
    puts "Calling again..."
    cnt.call
    puts "Done"

And here's the expected output:

cnt: 5
Calling again...
cnt: 10
Done

And here's the syntax tree after we've done the required transformations (more about that in a second):

    [:do,
     [:defm,
      :mkcounter,
      [:step],
      [:let,
       [:__env__, :__tmp_proc],
       [:sexp, [:assign, :__env__, [:call, :malloc, [8]]]],
       [:assign, [:index, :__env__, 1], :step],
       [:assign, [:index, :__env__, 0], 0],
       [:do,
        [:assign,
         :__tmp_proc,
         [:defun,
          ".L2",
          [:self, :__closure__, :__env__],
          [:let,
           [],
           [:sexp,
            [:assign,
             [:index, :__env__, 0],
             [:add, [:index, :__env__, 0], [:index, :__env__, 1]]]],
           [:sexp, [:printf, "cnt: %d\n", [:index, :__env__, 0]]]]]],
        [:sexp, [:call, :__new_proc, [:__tmp_proc, :__env__]]]]]],
     [:assign, :cnt, [:call, :mkcounter, 5]],
     [:callm, :cnt, :call],
     [:call, :puts, [[:sexp, [:call, :__get_string, :".L0"]]]],
     [:callm, :cnt, :call],
     [:call, :puts, [[:sexp, [:call, :__get_string, :".L1"]]]]]

That's a bit of a mouthful, so lets go through it the new bits

    [:let,
       [:__env__, :__tmp_proc],

This is added to hold a pointer to the environment we create to hold cnt and step, and to hold a pointer to the function we use to create the Proc respectively.

       [:sexp, [:assign, :__env__, [:call, :malloc, [8]]]],
       [:assign, [:index, :__env__, 1], :step],
       [:assign, [:index, :__env__, 0], 0],

Then we allocate the environment. We copy the argument, and from now on we use (index env 1) to refer to step. We then carry out the cnt = 0 statement. cnt and step are both moved into the environment because they are used inside the closure.

(You may have already picked up that we currently won't handle nested closures - lets leave some fun for later)

        [:assign,
         :__tmp_proc,
         [:defun,
          ".L2",
          [:self, :__closure__, :__env__],

Then we create a function and assign the address of the function to __tmp_proc. As you can see there are tree synthetic arguments to it:

self,__closure__ and __env__. The first is, as you'd expect, the object the method is called on. The second is to be used when passing blocks to a method, and the third is used to refer to the environment when inside.

(Something I just realized: We're begging for a name clash, if there's a closure defined inside that needs a separate environment. Obnoxious details; later)

            [:assign,
             [:index, :__env__, 0],
             [:add, [:index, :__env__, 0], [:index, :__env__, 1]]]],

And this monstrosity is what cnt = cnt + step was turned into.

Now, to make this work, we obviously need this __new_proc function, and a Proc#call that's sensible. Here's our current Proc:

    class Proc
      # FIXME: Add support for handling arguments (and blocks...)
      def call
        %s(call (index self 1) (self 0 (index self 2)))
      end
    end
    # We can't create a Proc from a raw function directly, so we get
    # nasty. The advantage of this rather ugly method is that we
    # don't in any way expose a constructor that takes raw functions
    # to normal Ruby
    #
    %s(defun __new_proc (addr env)
    (let (p)
     # Assuming 3 pointers for the instance size. Need a better way for this
       (assign p (malloc 12))
       (assign (index p 0) Proc)
       (assign (index p 1) addr)
       (assign (index p 2) env)
       p
    ))

Very simplistic and rather ugly, but it does the work. As you can see, the environment pointer is stored in the Proc object, and Proc#call hides the ugliness.

You may notice that this is inefficient - an extra level of indirection. Indeed it is - we can in theory make the environment part of the Proc object and save an indexed lookup, and there's a bunch of other tricks waiting. But again, that's optimizations we wont deal with now.

For now, lets move on to how to do the appropriate changes to get the example output above.

Some refactoring, and a few rewrites

Almost all the changes for this is in the Compiler class, and the code in question is now in the transform.rb file. There are some other small changes, but I don't think they need to be covered in detail.

Specifically, transform.rb represents the start of a bit of refactoring.

Some constructs in the Compiler class can be built easily on top of more primitive operations. lambda was an example of that.

Overall, a lot of things can be done by rewriting the parse tree. Doing it that was has the distinct advantage that it's possible to switch the various rewrites on/off to debug their effects, and to see the result long before it ends up as machine code.

It also helps isolate the CPU architecture specific parts further.

As a first step, transform.rb contains methods that solely rewrite the syntax tree. They are still currently part of the Compiler class, and do make use of the Emitter (specifically Emitter.get_local to get a unique label), but this can be changed later.

Unfortunately not all of these rewrites are small and simple.

In this round, we're left with three:

• rewrite_strconst
• rewrite_let_env
• rewrite_lambda

rewrite_strconst used to be in compiler.rb and is mostly unchanged.

rewrite_lambda

rewrite_lambda replaces the lambda handling in compiler.rb with a rewriting step that looks like this:

    def rewrite_lambda(exp)
      exp.depth_first do |e|
        next :skip if e[0] == :sexp
        if e[0] == :lambda
          args = e[1] || []
          body = e[2] || nil
          e.clear
          e[0] = :do
          e[1] = [:assign, :__tmp_proc, 
            [:defun, @e.get_local,
              [:self,:__closure__,:__env__]+args,
              body]
          ]
          e[2] = [:sexp, [:call, :__new_proc, [:__tmp_proc, :__env__]]]
        end
      end
    end

What this rewrite does, is use our Array#depth_first method from extensions.rb to descend down the parse tree looking for :lambda nodes. It will skip any :sexp nodes, as they are used as "guards" to mark areas that should not be touched by rewrites.

When it finds a :lambda, it will replace the :lamda with this:

    %s(do
       (assign __tmp_proc
               (defun [result of @e.get_local
                 (self __closure__ __env__ [ + args])
                   [body]))
       (sexp call __new_proc (__tmp_proc __env__))
      )

Effectively defining the lambda (as we did before), but then calling __new_proc with the result. You'll note __tmp_proc is seemingly superfluous. It is in fact a workaround for a slight problem: The call needs to be within a sexp to not be rewritten to a callm (Ruby method call), but the defun can't be within a sexp, or other rewrites won't touch the body of the defun.

We'll clean that up later.

rewrite_let_env

Now for the hairy bit. Really hairy.

The goal of this one is to identify variables in the methods - this used to happen in the parser in a really simplistic way - combined with identifying :lambda nodes (and so this must run before rewrite_lambda) and lifting variables that are used inside the closure into an environment, and update the :let in the surrounding method definition to have a suitable environment.

It then also adds code to allocate the environment, as well as to shadow method arguments. Finally it rewrites accesses to variables that have been lifted into the environment, so that it uses %s(index __env__ offset) instead of the variable name.

Let's go through the code.

    def rewrite_let_env(exp)
      exp.depth_first(:defm) do |e|

We're hunting for :defm nodes only. Everything else will be ignored.

        vars,env= find_vars(e[3],[Set[*e[2]]],Set.new)

First step is to find a candidate set of variables. find_vars is another new method, and we'll go over that next. e[3] is the body of the method. find_vars is recursive, and we pass in the methods arguments (e[2]) as the starting "scope". Third we pass in an empty Set as the the starting point for the environment.

        vars -= Set[*e[2]].to_a

We remove the method arguments, as we'll use vars to create a :let node later on.

        if env.size > 0

If find_vars found any variables to make part of the environment, we need to:

           body = e[3]
           rewrite_env_vars(body, env.to_a)

Rewrite access to the members of the environment

           notargs = env - Set[*e[2]]
           aenv = env.to_a
           extra_assigns = (env - notargs).to_a.collect do |a|
             [:assign, [:index, :__env__, aenv.index(a)], a]
           end

Create assigns to copy all arguments that are used in the closures from the arguments on the stack into the environment

           e[3] = [[:sexp,[:assign, :__env__, [:call, :malloc,  [env.size * 4]]]]]

Allocate the environment

           e[3].concat(extra_assigns)
           e[3].concat(body)

Tack on the extra assigns and the body.

         end
         # Always adding __env__ here is a waste, but it saves us (for now)
         # to have to intelligently decide whether or not to reference __env__
         # in the rewrite_lambda method
         vars << :__env__
         vars << :__tmp_proc # Used in rewrite_lambda. Same caveats as for __env_
         e[3] = [:let, vars,*e[3]]

Then we create a :let node with the new variable set, including __env__ and __tmp_proc which we've seen elsewhere.

         :skip
       end
     end

Finally we skip any nodes below the :defm so the depth_first call does not waste time.

find_vars

The purpose of find_vars is to identify variables that should be put in a let node as well as that should be part of a closure environment. This one is hairy, and a clear candidate for looking for ways to clean up later

def find_vars(e, scopes, env, in_lambda = false, in_assign = false)

    return [],env, false if !e

First of all, if we've been called with a nil expression, there are now variables to return, and the same environment passed in.

    e = [e] if !e.is_a?(Array)
    e.each do |n|
      if n.is_a?(Array)

An expression?

        if n[0] == :assign
          vars1, env1 = find_vars(n[1],     scopes + [Set.new],env, in_lambda, true)
          vars2, env2 = find_vars(n[2..-1], scopes + [Set.new],env, in_lambda)
          env = env1 + env2
          vars = vars1+vars2
          vars.each {|v| push_var(scopes,env,v) }

If it's an assignment, then we want to process both the left hand and right hand, but we need to mark the left hand since variables on the left hand introduce a new variable in the scope.

        elsif n[0] == :lambda
          vars, env = find_vars(n[2], scopes + [Set.new],env, true)
          n[2] = [:let, vars, *n[2]]

Special casing on :lambda because if we're handling a closure, and variables found inside the closure that were defined outside means that those variables needs to be lifted into the closure environment we're creating so that they're not allocated on the stack.

        else
          if    n[0] == :callm then sub = n[3..-1]
          elsif n[0] == :call  then sub = n[2..-1]
          else sub = n[1..-1]
          end
          vars, env = find_vars(sub, scopes, env, in_lambda)
          vars.each {|v| push_var(scopes,env,v) }
        end

Finally we special case on :callm and :call when handling the remainder, because they have arguments that are not sub-expressions to be considered when creating the closure environment.

      elsif n.is_a?(Symbol)
        sc = in_scopes(scopes,n)
        if sc.size == 0
          push_var(scopes,env,n) if in_assign

If n is a variable that does not exist in any of the scopes we keep track of, and it is not part of the environment, and it's on the left hand of an assign, we add it to the top scope.

NOTE: This current version is buggy. Not every variable potentially occuring on the left hand side should be added, just the one assigned to.

        elsif in_lambda
          sc.first.delete(n)
          env << n
        end

If it is in a scope and we're in a lambda, then the variable needs to be moved (deleted) from that scope and added to the closure environment.

      end
    end
    return scopes[-1].to_a, env
  end

Finally we return the innermost scope from this level and the environment

rewrite_env_vars

Finally let's look at rewrite_env_vars. When we've gathered together all the variables for the closure environment, we have an array, and any accesses to those variables needs to be rewritten to (index __env__ num). That's done like this, and I hope this one is simple enough not to go through line for line:

    def rewrite_env_vars(exp, env)
      exp.depth_first do |e|
        STDERR.puts e.inspect
        e.each_with_index do |ex, i|
          num = env.index(ex)
          if num
            e[i] = [:index, :__env__, num]
          end
        end
      end
    end

Next steps

We still haven't actually added support for define_method, but we now finally have most of the plumbing. That's the next step.

Then I want to start alternating between something more practical: Making the compiler compile early/simple versions of itself, and let it "eat its own tail" so to speak, and secondly to start refactoring and cleaning it up.

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.

Apologies for the delay... This part was ready before christmas, but for various reasons I never got around to posting it. And to make matters worse I managed to post the wrong part yesterday. Sigh.

The Outer Scope

Stepping back from the attr_* debacle for a bit... I wanted to look at something else, mostly because it affects all my ad-hoc testing.

One of the downsides of starting this without a specific design in mind is that after I decided to go down the Ruby path we've been dragging along quite a bit of cruft.

But that is the cost of experimentation.

In particular, the compiler has a weird distinction between functions and methods: Define something with def outside of a class and it becomes a function, inside it becomes a method.

We need support for functions to make implementation reasonably easy: It makes bootstrapping the object model far easier, as well as integration with the outside C-based world.

But Ruby doesn't have functions.

So what to do?

Recently I wrote about hiding the "low level plumbing" and the change I'm about to show you gets us a bit closer to that while at the same time starting to clean up the function vs. method mess.

In Ruby, self outside of a class is the main object - an instance of Object. Logically then, for a def outside of a class, the method will be defined on `Object. So, we'll create that object.

What about function calls?

Defining and calling functions will still be possible, but only using the s-expression syntax. That reasonably cleanly "hides" the plumbing we use functions for (in fact, it means we could stop the annoying convention I started of prefixing the names with "__" since they effectively now live in their own namespace, though I haven't changed that yet).

Some preparations

First we must rewrite a few functions fully as s-expressions. This is straightforward. For example:

    -def __get_string(str)
    -  s = String.new
    -  %s(callm s __set_raw (str))
    +%s(defun __get_string (str) (let (s)
    +  (assign s (callm String new))
    +  (callm s __set_raw (str))
       s
    -end
    +))

Otherwise the upcoming changes will turn them into methods, which is not what we want.

I'm not going to present all of them. The biggest one is probably __new_class_object, but all of these are straight forward translations.

These changes were done on the master branch prior to starting this feature proper.

Splitting up "defun"

You can follow these remaining changes on the main-object branch

So far defun has been made up by two mostly different branches: If occurring inside a class, it's compiled as a method, if not it'd compile a function.

This is both messy and not very logical.

Going forward we'll separate it into defm that defines a Ruby style method, and defun, which, as before, defines a function. defun will be completely hidden from normal Ruby code - you'll have to dip down into the s-expression syntax to access it.

First our list of compile_* methods in compiler.rb:

    -                   :do, :class, :defun, :if, :lambda,
    +                   :do, :class, :defun, :defm, :if, :lambda,

The new, simplified compile_defun:

    # Compiles a function definition.
    # Takes the current scope, in which the function is defined,
    # the name of the function, its arguments as well as the body-expression
    # that holds the actual code for the function's body.
    #
    # Note that compile_defun is now only accessed via s-expressions
    def compile_defun(scope, name, args, body)
      f = Function.new(args, body,scope)
      name = clean_method_name(name)
      # add function to the global list of functions defined so far
      @global_functions[name] = f
       # a function is referenced by its name (in assembly this is a label).
       # wherever we encounter that name, we really need the adress of the label.
       # so we mark the function with an adress type.
       return [:addr, clean_method_name(name)]
    end

This is really more or less just tearing out the method part, and brings it roughly back to how it was before we added the method calling bit.

But compile_defm is also somewhat simpler than the old method part:

    # Compiles a method definition and updates the
    # class vtable.
    def compile_defm(scope, name, args, body)
      scope = scope.class_scope
      f = Function.new([:self]+args, body, scope) # "self" is "faked" as an argument to class methods.
      @e.comment("method #{name}")
      body.depth_first do |exp|
        exp.each do |n| 
          scope.add_ivar(n) if n.is_a?(Symbol) and n.to_s[0] == ?@ && n.to_s[1] != ?@
        end
      end
      cleaned = clean_method_name(name)
      fname = "__method_#{scope.name}_#{cleaned}"
      scope.set_vtable_entry(name, fname, f)
      # Save to the vtable.
      v = scope.vtable[name]
      compile_eval_arg(scope,[:sexp, [:call, :__set_vtable, [:self,v.offset, fname.to_sym]]])
      # add the method to the global list of functions defined so far
      # with its "munged" name.
      @global_functions[fname] = f
      # This is taken from compile_defun - it does not necessarily make sense for defm
      return [:addr, clean_method_name(fname)]
    end

The most important changes?

• The call to scope.class_scope at the top.
• The change to call __set_vtable near the bottom instead of hardcoding the asm to set the vtable entry.

So, why those changes?

If you look at GlobalScope, we've added a @class_scope instance variable that is initialized to this:

    @class_scope = ClassScope.new(self,"Object",@vtableoffsets)

This means that if you have a :defm occurring in the global scope (we'll get to that) it will be compiled in that class scope, as a method of class Object.

Poof and our functions are (almost) gone.

(In ClassScope we just return self from the new class_scope method.)

For the second change, adding __set_vtable is just the purist in me wanting to expel as much assembler as possible. Here it is (from lib/core/class.rb):

    # FIXME: This only works correctly for the initial
    # class definition. On subsequent re-opens of the class
    # it will fail to correctly propagate vtable changes 
    # downwards in the class hierarchy if the class has
    # since been overloaded.
    %s(defun __set_vtable (vtable off ptr)
      (assign (index vtable off) ptr)
    )

Ok, so not just the purist in me. In fact, this makes re-opening classes "cleaner" in that this function will actually get reasonably complex as we fix this issue, and also later handle define_method and otherwise deal with cases where no vtable slot is actually available.

Anything else? A few pieces of cleanups to deal with the scope changes, and this little gem / turd depending on your point of view, in lib/core/core.rb:

    +
    +# OK, so perhaps this is a bit ugly...
    +self = Object.new
    +

Ehm. We probably should put that in the compiler, or at least prevent arbitrary assigning to self in user code. But it works for now, and we've done worse in the past. To reiterate: Get things working first. Make them fast/pretty later.

The last vital change is this, in Parser#parse_def:

    -    return E[pos, :defun, name, args, exps]
    +    return E[pos, :defm, name, args, exps]
       end

It does what it looks like - make the parser for the Ruby code spit out only :defm nodes instead of :defun nodes. Our code is now free of functions anywhere outside of s-expressions.

What's the effect?

These changes make this work as expectd:

    class Foo
      def hello
        puts "hello"
      end
    end
    def hello_world
      puts "hello world!"
    end
    %s(puts "foo") # Calls the C function
    Foo.new.hello  # Calls Foo#hello which calls Object#puts
    puts "world"   # Calls Object#puts (via the "main" instance)
    hello_world    # Calls Object#hello_world (via the "main" instance)

Adding this on the end on the other hand still fails (but it works in MRI) because __set_vtable doesn't propagate the vtable update downwards to subclasses of Object:

    Foo.new.hello_world

When re-opening a class, new methods needs to be added "properly" by processing all child classes and updating their vtables.

The alternative (which moves the cost from the point of defining a method to the point of calling the method), is to implement a proper default method missing that ascends the class hierarchy to look for an implementation before giving an error.

We really should do both, since we eventually need to handle methods without vtable entries.

But that's for a future installment

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.

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

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.