Vidar Hokstad V2.0

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

Google Wave as infrastructure

Sat, 30 May 2009 21:44:40 -0400

It's new but not new

All of the things in the Wave demo are possible without Wave. The interesting thing about Wave is not so much the application, but the infrastructure, the protocol and the underlying concepts. Many limited collaboration apps have offered various subsets of the Wave functionality, for example, and the superficial functionality can be built using existing technology, without fancy new protocols and clients etc.

But that's missing the point. Wave is interesting because the infrastructure makes it extremely open-ended.

A lot of people have been comparing Wave to e-mail. That's missing the point too. Wave has the potential to be as important as the Web. I'm serious. Wave is taking the web and making it interactive, embeddable, recordable, and shareable on a whole different level than what we are used to. And like most great "revolutionary" ideas it doesn't actually add all that much new:

When the web arrived, hypertext systems were well known (and most of them were far more advanced than early web browsers), for example. What the web gave us was two simple innovations: A simple system for letting anyone create content, and an addressing scheme and protocol that allowed the content to be distributed world wide. But that existed - sort of - too before the web, in the form of Gopher. The web was a very tiny evolutionary step in many ways, but they were "just the right ones": The web was more chaotic and unstructured and open-ended than gopher (which was more of a distributed catalog of files), and with a number of ideas that spurred people on to extend it in all kinds of weird and wonderful ways.

Wave could be similar. We have IM. We have e-mail. We have document sharing over the web. We have the web. All of the functionality of Wave can be achieved with existing technology. You can chat with your friends. You can share content. You can run shared whiteboard apps that you could interface apps to.

But it's not all seamlessly integrated. That is the one deceptively small evolutionary step that Wave provides, that could very well be a big game changer. Especially since Wave does it in a very simple way.

It's built on XMPP

That means:

It leverages a huge amount of existing infrastructure
It's federated by default (see below).
A lot of the underlying protocol is well understood by a lot of people

It's federated

Jabber / Google Talk / XMPP is powerful because anyone can set up their own server, and Google has promised the same will be the case for Google Wave - it only makes sense anyway since XMPP is built ground up to be a federated protocol, with support for server-to-server connections etc.

Federation allows you to set up your own server, and so act as gatekeeper to information that is critical to you, and so makes Google Wave palatable as an intranet tool as much as an external tool - in fact, barring issues with how the clients are built there's no reason why an intranet user could not start a public wave (on a public server) for an open discussion and then break away a private sub-wave on the intranet wave server - all in the same session - to discuss with his/her co-workers.

This makes Wave a potentially pretty amazing collaboration tool for situations where you may have multiple parties with information of both public and private nature who wants to share different subsets with different parties. Systems like Basecamp allows this today (you can add other companies and users from those companies to your Basecamp setup, and control their access to your information) but it is fairly static and limited to the specific feature-set of Basecamp, while in Wave it is a feature of the infrastructure and completely orthogonal to the functionality the various users employ.

In fact, nothing stops users from granting access to their own, internal, Wave-enabled apps, on a user by user basis as part of collaboration (or as a general service):

It's extensible

Imagine a booking agent (at any type of business: restaurants, airlines etc.) that answers live questions. Lots of companies do that now. But instead of just talking to you, the agent shares a booking form with you, and help you fill it in, live, while answering questions.

Or someone at your bank walks you through mortgage deals, and shows you a mortgage calculator, fills in details to illustrate the deals they are presenting, and show you graphs of your repayment schedule in real-time.

Because the Wave protocol allows both sides to push relatively arbitrary content, and update it realtime, you can use it to run presentations; to edit documents together; to fill in forms together that is then updated live by automated remote services.

Consider it a sort of "remote terminal" you can run applications in. Only it's shared. And graphical. And has built in playback.

It's persistent

The Wave server is responsible for maintaining a persistent store of the waves. Depending on your wave server there may be different policies for how long they persist, but due to the openness of the protocol, there's plenty of opportunity for archiving waves in ways that provides a record the way e-mail does. Providing search and retrieval functionality for local waves is possible, and the architecture allows searching either at "point-in-time" or building search functionality that would let you search in past states of your waves.

I.e. your client or your local wave server could either snapshot waves at specific times, or maintain a complete record of the wave operations and then let you find that mention of doughnuts in the kitchen that some greedy co-worker deleted seconds later.

It can be "gatewayed"

Many of the more exciting uses of Wave allowed by the open architecture is that you can create two-way gateways for all sorts of content using it. Nothing is preventing you from building wave support into your new spreadsheet app, for example, so you can click a button to share the spreadsheet, or a graph from it, or whatever, with other people and have them help you edit it,and comment on it. Or you can share your word processor document in a phone conference and people can add their own comments. Or you could export your blog entries, and have people use Wave to add or read comments from your web page. Or Wikipedia could export every page as a wave so those obnoxiously formatted "talk" pages could instead consist of people adding comments "inline" to the actual text. Or you could turn it into an IRC client. Or Facebook could turn the walls into waves and let people read/post to their wall via wave (though given facebooks past behavior in banning people who post too many updates, perhaps not).

Google itself has a suite of apps that could be exported as waves: Docs/Spreadsheets, Gmail, Picasa, Calendar etc. - imagine starting a wave, pulling in a document, adding your pics from Picasa, dragging in the calendar and creating an event, and turning it all into a nicely formatted event invitation e-mail that is gatewayed out via normal e-mail to your friends and family (or made available as a wave to those who use it), complete with nice pictures from the place you're inviting them too, the price list from Docs, a calendar invite etc.

It's encrypted by default

Encryption by default makes it a lot easier sell as a collaboration tool also internally in businesses, or even in many cases as a replacement for e-mail or other channels that are insecure by default and takes conscious actions to secure.

It's client independent

While Google obviously has a head start, and while extensions may (or may not?) be client dependent, nothing stops other parties from building Wave clients that add new capabilities. The underlying protocol is really simple - it uses XMPP for federation and layers a thing layer of maintaining shared XML documents and serializing multi-party updates to that document to all participants. How the client (or the server) interprets that document is up to the client (or the server).

Some ways to use this: "Load" snapshots of waves into your word processor when you've finished collaboratively editing it, and finish cleaning it up (your word processor could be a wave client); open a wave in Finder / Explorer and drag images from the wave somewhere else (or open the wave in Photoshop and pick an image to edit). All of course assuming the various app gets wave support.

All my known ancestors

Thu, 28 May 2009 21:24:31 -0400

Toying with my script from the previous post... Not limiting the number of generations, and processing it with neato instead of dot (still from Graphviz) gives this cool diagram... I haven't tried removing overlaps. I also have some changes to allow including siblings (the diagram below includes only direct ancestors). Posting it mostly because it looks neat, and it illustrates pretty well how exponential growth quickly makes family trees unwieldly. Our family database contains thousands of people not in the diagram below - siblings of everyone there, as well as the spouses and descendants of siblings, and for the most part this stretches "only" back to the early 1700's, with a few spindly arms going back to about 1480:

(Click for a somewhat larger version -- I haven't posted a full size one as it's HUGE; maybe when I've cleaned it up a bit more)

When I've had time to do some more cleanups I'll probably post a more recent iteration of the script I'm using.

Family tree using Graphviz and Ruby

Sat, 23 May 2009 12:04:36 -0400

My dad spent a lot of time putting together a family database, currently containing about 12000 people covering both my parents ancestors as well as tracking forward to contain a lot of living descendants. Unfortunately, since he started this over 16-17 years ago it's been managed as a custom dBase III+ app, and the code grew by accretion over at least 7 years (until my father died). Spurred on by an e-mail from a possible distant relative (who it turns out I've even met) I finally dumped the dbf files into an Sqlite database and put together a few scripts to generate diagrams from it.

Here's an example (click to enlarge). The birth/death dates are in Norwegian format (day.month.year)

The full SVG diagram (which is zoomable in Safari and Firefox) is here.

This tree shows the known ancestors of Ole Martin Hokstad - the first person amongst my direct ancestors to be born to the Hokstad name (there are one or two other families where the name Hokstad was taken at different times). In our case the name stems from the Hogstad farms in Frosta, near Trondheim, Norway. The farms kept being divided as a result of children inheriting parts etc..
At one point the farm Lille-Hogstad was bought by Ola Viktil, and one of his grandsons, Peter Magnus Hokstad Johansen combined two smaller properties to Hogstad Lille Vestre in 1854, which was then renamed Hokstad (presumably he didn't like the thought of the name Peter Magnus Hogstad Lille Vestre Johansen). His children, including my great-grandfather Ole Martin Hokstad, got the name by birth.

The tree above doesn't show any siblings, and leaves out a few people we don't have any certain information about. I did render one of all my know ancestors as well, but it's too huge to be practical to reproduce here (about 20 times the size of the tree above).

To produce this I put together a very quick and dirty little Ruby script:

require 'model'
require 'set'

id = ARGV[0].to_i

# Prevent double inclusion of a node                                                                                                                       
$memo = Set.new

def filter_node(per)
  return nil if !per
  return nil if per.firstname.strip == "?" || 
         per.lastname.strip == "?" || 
         per.maidenname.strip == "?"
  return per
end

def node (per,color)
  return false if $memo.member?(per.pk)
  $memo << per.pk
  name = [per.firstname, per.middlename, 
                per.lastname, 
                per.maidenname]
  name = name.collect do |n| n && n != "" ? n : nil }.compact.join(" ")
  label = "#{name}\n#{per.birthdate} - #{per.deathdate}"
  puts "   p#{per.pk}  [ shape = box, style=\"filled\","+
          " fillcolor=\"#{color.to_s}\", label=\"#{label}\" ];"
  return true
end

def ancestors per

  father = filter_node(per.father)
  mother = filter_node(per.mother)

  pk = per.pk
  arrowhead = "normal"
  if mother and father
    merge = "m#{mother.pk}and#{father.pk}"
    if !$memo.member?(merge)
      puts " p#{merge} [ shape = point ]"
      puts " p#{merge} -> p#{pk} [ arrowtail=none ]"
      arrowhead = "none"
    else
      $memo << merge
    end
    pk = merge
  end

  if father
    if node(father,:green)
      puts "   p#{father.pk} -> p#{pk} [ arrowhead=#{arrowhead} ]"
      ancestors(father)
    end
  end

  if mother
    if node(mother,:gold)
      puts "   p#{mother.pk} -> p#{pk} [ arrowhead=#{arrowhead} ]"
      ancestors(mother)
    end
  end
end


def graph per
  puts "digraph ancestors {"
  node(per,:red)
  ancestors(per)
  puts "}"
end

per = Person[:id => id]
if !per
  puts "Unable to find #{id}"
  exit
end

graph(per)

I'm not going to spend a lot of time going through the script, other than to point out the dependencies if you want to try this for yourself:

You need to create a class with the methods #pk that returns a unique key suitable to be part of a Graphviz dot-file node name, #father and #mother that returns an equivalent object for the father and mother respectively or nil if not known, and methods #firstname, #middlename, #lastname and #maidenname respectively that returns the names as strings. Whether it comes from a database or not is irrelevant - you can load it all into memory first if you like. In my case it's all from a Sequel model, as you can see I retrieve a Person object for the id provided as the root of the tree at the end of the script.
I don't think I'll put in much effort to make this a generic package, but it should be easy enough to adapt if you know some Ruby. I will probably post a couple of variations to add output of siblings and also to generate an equivalent one for descendants instead of ancestors though.

I then use this little bash script to generate the SVG file (requires xsltproc)

#!/bin/sh

ruby ancestors.rb $1 >/tmp/$1.dot
dot -Tsvg /tmp/$1.dot >/tmp/$1.svg
xsltproc /opt/diagram-tools/notugly.xsl /tmp/$1.svg >$2

This assumes my diagram-tools GIT repository has been cloned into /opt/diagram-tools (git clone git://github.com/vidarh/diagram-tools.git /opt/diagram-tools), to pretty up the Graphviz output.

Making Graphviz output pretty with XSL - Updated

Mon, 18 May 2009 18:54:22 -0400

Over a year ago I posted an XSL file for prettying up Graphviz diagrams.

I got lots of feedback, and recently I've been fixing various bugs, and I finally got around to adding support for more of the Graphviz node shapes etc.

Here's an example of various node types and colors with the new version. Note that while rounder corners are "sort of" working, I haven't found a good way of making the gradient fill work nicely with it. The current version has been tested with Graphviz 2.20.2.

(Scaled down a bit to fit my layout; if you can't see it you need a browser that can embed SVG's, such as any recent Firefox or Safari)

The XSL file can be found with various other Graphviz related tools at my diagram tools repository on GitHub

This is a fairly substantial set of changes, so please do let me know if you find any bugs (if so, I appreciate an example dot-file as well as the Graphviz XSL output and the "cleaned" XSL output, and the version number of the Graphviz version you're using - please try to upgrade to at least 2.20.2, though).

Thanks to Jonas Tingeborn, Earl Cummings and Kevin Keraudren for various bug fixes and help debugging. Thanks to Michael Kennedy for posting a variation with lots of gradients (I've pilfered a smallish subset for my updated version - but you can copy the rest from his version if you prefer)

I love throwing out code

Thu, 14 May 2009 20:24:50 -0400

... it usually means putting something cleaner and smaller back in. I'm much happier when I've cut code from an app than when I've added it - adding code is easy; removing code is like a game of Jenga, trying to see how much I can remove without making everything tumbling down (not that I aim to go to the brink, mind you).

Just started thinking about that because I just ripped out lots of CSS (thanks to Blueprint) and a good chunk of code from my blog - hopefully it looks nicer at least. I've also replaced my homegrown comment system with Disqus. I've kept the old comment system for now. If (when) I decide Disqus works well enough I'll migrate the old comments and tear that out too.

If you come across something that is broken (this was a quick and dirty spur of the moment thing, sans unit tests...) please let me know.

Is it wrong to try to make the Imperial March your babys first memory?

Thu, 14 May 2009 07:32:24 -0400

So, paternity leave is over, and things are returning somewhat to normal, apart from lack of sleep.
Meanwhile I've taken to humming the Imperial March from Star Wars whenever taking him for a diaper change....

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

Tue, 05 May 2009 15:16:30 -0400

You may or may not have seen my recent post where I admitted to more or less having decided to make my compiler project a Ruby compiler. On the downside this means a lot of complexity that may make it harder to follow. On the upside... Well, you get to read about a compiler for a "real" language as opposed to a toy, and hopefully the result will be usable and I'll manage to contain myself and not go off on wild tangents (I have a long list of experiments I want to do)

Since the last part things have moved quite far, and I'm not going to do a "patch by patch" overview of what's happened since. Instead I will this time give a rough overview of the state of the compiler as of starting to write this - April 25th (slightly derailed by having a child). Parts of the compiler with more extensive changes will get more "coverage".

Let me again point out that all of the code is on Github. Specifically the state of the code when writing this can be found at tag "step-20c".

Furthermore, I'd like to extend an invitation to anyone who's interested in contributing. Go check out the project from Github, fork it if you like, and send me pull requests when you have something you'd like me to consider for the main tree, or just let me know if it's ok for me to pull things in whenever I see something interesting. There's now two of us - Christopher Bertels started contributing a while back, and have added lots of rdoc documentation and a range of other improvements, such as part of the instance variable support.

We've so far decided to go with the same license as Matz' version of Ruby, but I'm open to discussion about that. Specifically I would prefer the core library to be licensed under terms sufficiently loose to allow closed source apps to be compiled as well.

Anyway, lets see what things look like now.

The Parser

If you've followed my blog, you'll probably have seen the announcement that the compiler can now parse itself. I'm sure it still has bugs (it certainly did when I posted the announcement, as I've found out since), and it most certainly can't compile the AST it generates, but it's still a fairly big milestone. It also means that it can parse a small but relatively central subset of Ruby (there are many, many gaps).

The parser is split in three components:

The low level s-expression style parser. This part has hardly changed.
The operator precedence parser used for expressions. This has changed a lot, and needs a cleanup, but I'll attempt a description of the current state
The "high level" parser used for control structures etc.. This is a simple recursive descent parser. It also would benefit from a cleanup, but it's not hard to understand (I think).

First of all, let us take a look at something else: Test cases. Parsing Ruby is nasty. As much as I love to program in Ruby, the grammar makes me feel downright dirty. It is full of context sensitive parts, exceptions and weird rules that make it painful to write a small and readable parser for it. All the more reason to write extensive sets of test cases.

Testing the parser components

I've been using Cucumber to add test cases, mainly because so far for the parser the test cases are very repetitive "here's the input, it's meant to generate this tree" kind of tests, and Cucumber makes that look nice and readable:

Feature: Shunting Yard
    In order to parse expressions, the compiler uses a parser component that uses the shunting yard
    algorithm to parse expressions based on a table.

    Scenario Outline: Basic expressions
        Given the expression expr
        When I parse it with the shunting yard parser
        Then the parse tree should become tree

    Examples:
      | expr                 | tree                                 |
      | "__FILE__"           | :__FILE__                            |
      | "1 + 2"              | [:add,1,2]                           |
      | "1 - 2"              | [:sub,1,2]                           |
      | "1 + 2 * 3"          | [:add,1,[:mul,2,3]]                  |
      | "1 * 2 + 3"          | [:add,[:mul,1,2],3]                  |
      | "(1+2)*3"            | [:mul,[:add,1,2],3]                  |
      | "1 , 2"              | [:comma,1,2]                         |
      | "a << b"             | [:shiftleft,:a,:b]                   |
      | "1 .. 2"             | [:range,1,2]                         |
      | "a = 1 or foo + bar" | [:or,[:assign,:a,1],[:add,:foo,:bar]]|
      | "foo and !bar"       | [:and,:foo,[:not,:bar]]              |
      | "return 1"           | [:return,1]                          |
      | "return"             | [:return]                            |
      | "5"                  | 5                                    |
      | "?A"                 | 65                                   |
      | "foo +\nbar"         | [:add,:foo,:bar]                     |
      | ":sym"               | :":sym"                              |
      | ":[]"                | :":[]"                               |

As of writing, the parser components have 106 scenarios (each entry in the example tables counts as one scenario) including a few failing ones. Whenever we find anything broken, a new test case goes in. 106 scenarios is nowhere near complete, but it helps tremendously with debugging, particularly with the operator precedence parser, as it's been fairly tedious to adjust and adapt it to handle the peculiarities of Ruby. It also serves as documentation of sorts of what the parser is expected to deliver

The operator precedence parser

We've covered this component before of sorts (go revisit it if you're unsure about it), but it's grown significantly in complexity since, mostly to account for weirdness in the Ruby grammar, some to account for missing functionality. A word of warning before we start: It's gotten messy, and it needs to be cleaned up and re-factored. But it's not that hard to figure out.

I'm going to assume you're familiar with the previous parts, and have a rough idea of Dijkstra's Shunting Yard algorithm which this parser component is based on. We'll examine it top-down the way it's being used:

  def self.parser(scanner, parser)
     ShuntingYard.new(TreeOutput.new,Tokens::Tokenizer.new(scanner), parser)
  end

We start by instatiating the parser and passing the most frequently used components to it. By passing an alternative to TreeOutput you an turn the output into reverse polish notation or anything you like. But we want a parse tree. Tokens::Tokenizer is used to retrieve a stream of tokens instead of working on individual characters. Last but not least we're passing it a reference to the recursive descent parser. Yuck. We do this because of Ruby's block syntax, which because of the way blocks can look like literal hashes and/or can be chained and used as part of an expression means we need to be able to call bak out of the shunting yard parser.
It might be that it'd be just as well to combine the two, but I don't like tight coupling and I'm still living in hope of getting the time to figure out a way to reduce the coupling between these two components, and make the shunting yard parser generic enough to be reusable. One of the promises of an operator precedence parser is to be configured with a simple table of operators, and it's possible more of the exceptions in this current model can be handled by adding a few flags.

On to the next bit:

    def parse(inhibit=[])
      out = @out.dup
      out.reset
      tmp = self.class.new(out, @tokenizer,@parser)
      res = tmp.shunt(@tokenizer,[],inhibit)
      res ? res.result : nil
    end

A couple of oddities here. I've introduced an argument to allow specifying a set of tokens to inhibit and terminate the expression. This is needed because of peculiarities in how Ruby handle commas. Some places it's ok as it separates function arguments or array elements, but you also need to be able to put expressions IN argument lists as default assignments, and there commas are not allowed without parantheses, as they're needed to separate arguments, and the argument list itself is parsed by the recursive descent parser. It would be possible to change this, but I'm not sure I want to try to make the argument list be parsed by the same component until I'm more sure of the consequences. Besides the current arrangement works.
You can also see we do some annoying initialization - copying and resetting the tree output object. This is done because the parser recursively calls itself, and the state of the output tree builder need to be clean when it gets called for a subtree in parantheses for example.

The next bit is in a fairly shameful state at the moment, but rather than wait until it's cleaned up I'd rather show you the intermediate state, and we'll revisit again later once I have it all figured out - the shunting parser probably deserve it's own follow up article as it can get a bit hard to follow.

Leading up to the main loop, which I'll break up in several chunks:

    def shunt(src, ostack = [], inhibit = [])
      possible_func = false     # was the last token a possible function name?
      opstate = :prefix         # IF we get a single arity operator right now, it is a prefix operator
                                # "opstate" is used to handle things like pre-increment and post-increment that
                                # share the same token.
      lp_on_entry = ostack.first && ostack.first.type == :lp
      opcall  = Operators["#call#"]
      opcallm = Operators["."]
      lastlp = true

The commented local vars are hopefully reasonably understandable. "lp_on_entry" is set to true if the method is passed an :lp operator in - that means '(','[', '{' etc.. We'll see how that's used later. opcall and opcallm are just convenience shortcuts, though the hardcoded references to Operators[] are ugly (we'll meet more of them, and they'll go as soon as I find a clean way of decoupling the logic in this method). "lastlp" is set to indicate whether or not the last token was an :lp type operator.

      src.each do |token,op|
        if inhibit.include?(token)
          src.unget(token)
          break
        end

Ok, so this is the start of the main loop. We get the token as a string in in "token", and if it's an operator we get the operator object in "op". We check if the token is member of a set of "inhibited" tokens that we don't allow to be part of an expression. This is used to handle cases where the recursive descent parser wants an expression that stops on encountering something that is normally a legal part of the operator. We'll see it used when we look at the recursive descent parser.

        if op
          op = op[opstate] if op.is_a?(Hash)

We then start handling operator tokens - most of the loop is split between handling operators and handling non-operator tokens, with very little shared logic. In some cases there will be two operators that share the same token. Currently we handle :infix_or_postfix vs. :prefix operators, and the only case it's currently used for is "*" as multiplication operator vs. as the "splat" operator (which expands arrays).

          # This makes me feel dirty, but it reflects the grammar:
          # - Inside a literal hash, or function call arguments "," outside of any type of parentheses binds looser than a function call,
          #   while outside of it, it binds tighter... Yay for context sensitive precedence rules.
          # This whole module needs a cleanup
          op = Operators["#,#"] if op == Operators[","] and lp_on_entry

The comment above speaks for itself, no? And we see a use for lp_on_entry to help decide the precedence rule to use for the comma, by switching objects around (Note that this also shows an anti-pattern that needs to be fixed: When you have hashes, try to avoid string keys. Strings are expensive objects where symbols get mapped to an integer - for things like this using symbols as keys tends to be more efficient).

          if op.sym == :hash_or_block || op.sym == :block
            if possible_func || ostack.last == opcall || ostack.last == opcallm
              @out.value([]) if ostack.last != opcall
              @out.value(parse_block(token))
              @out.oper(Operators["#flatten#"])
              ostack << opcall if ostack.last != opcall
            elsif op.sym == :hash_or_block
              op = Operators["#hash#"]
              shunt(src, [op])
              opstate = :infix_or_postfix
            else
              raise "Block not allowed here"
            end

The whole block above gets executed if the current operator is a '{' (:hash_or_block) or :block ("do"), and it's one of the hairy bits... If we've seen what is possibly the start of a block (possibly, because '{' could also start a hash, hence the symbol), we first check if we're possibly looking at a function call (a pre-requisite for a block) based on the previous token, OR if the last operator to have been pushed on the operator stack is the function or method call operators (note: We currently still differentiate between function and method calls, though that is not a distinction Ruby makes; it is helpful for some aspects of the parser, and it is helpful for the low level s-expression syntax, but this distinction will normally become hidden from the "end-user").

If there's a function call being handled, then we know we're dealing with a block. We output an empty argument array if needed, and then call back up into the recursive descent parser via "parse_block" (token is passed so that the parser can determine what symbol the block should end on - '}' vs. 'end'). The "fake" operator "#flatten#" is output to aid in the tree building as the tree builder doesn't directly handle cases where a node has more than two children/arguments. This is a bit of a hack, and there is actually no real reason why a shunting yard parser can't be adapted to directly handle operators that are prefixes to multiple operands, so that may be part of the cleanup later.

If we're NOT dealing with a function call, we check if we're looking at the :hash_or_block ('{') operator, and if so we know we're now dealing with a Hash, and we recursively call shunt to handle the interior of the Hash.

          else
            if op.type == :rp
              @out.value(nil) if lastlp
              @out.value(nil) if src.lasttoken and src.lasttoken[1] == Operators[","]
              src.unget(token) if !lp_on_entry
            end

If we are not dealing with a potential block, we move on. First, above, we check for a :rp (right parenthesis, bracket or brace) operator. We "fake" a value if we've just seen an empty pair of parentheses, so we don't have to deal with operand-less operators elsewhere. We also fake value if the last token was a comma operator. This is to handle the convenience case in Ruby where arrays or hashes can have a "dangling" comma at the end like so: [1,2,3,] (useful for symmetry and machine generating Ruby source.

            reduce(ostack, op)

We call reduce in order to fore output of any tighter binding operators. In the case of, say, 1 * 2 + 3, (* 1 2) will get output when encountering '+'.

            if op.type == :lp
              shunt(src, [op])
              opstate = :infix_or_postfix
              # Handling function calls and a[1] vs [1]
              ostack << (op.sym == :array ? Operators["#index#"] : opcall) if possible_func

If it's an lp type operator, we do as we did for Hash ('{'), except we also want to selectively output "#index#" or the "#call#" operators if we're dealing with a function call. This occurs when we have an expression like "foo(1)", in which case "possible_func" will be true after "foo" has been encountered, and we then parse "(1)" and pass the result onto the output handler, and then output the "#call#" operator to tie "foo" and it's arguments together. As the slightly misleading comment says, "#index#" is used if we see '[...]' after something that might indicate a function call, as we need to differentiate a[1] (a call to the method "[]" on the object reference held in "a") vs [1] (constructing an Array object).

            elsif op.type == :rp
              break

If we dealt with an :rp we want to exit from the loop.

            else
              opstate = :prefix
              ostack << op
            end
          end

... if not we just push the operator on the operator stack.

        else
          if possible_func
            reduce(ostack)
            ostack << opcall
          end
          @out.value(token)
          opstate = :infix_or_postfix # After a non-operator value, any single arity operator would be either postfix,
                                      # so when seeing the next operator we will assume it is either infix or postfix.
        end
        possible_func = op ? op.type == :lp :  !token.is_a?(Numeric)
        lastlp = false
        src.ws if lp_on_entry
      end

Ok, time to handle non-operator values. Not much to say about this - it's hopefully reasonably understandable. The last line about will skip whitespace including line feeds if we're inside a parenthesized sub-expression, while normally (inside the tokenizer) we only skip whitespace excluding linefeeds. This is because the general rule in Ruby is to allow linefeeds anywhere where it doesn't create an ambiguity. I'm sure there are more special cases we'll need to handle, but for now this approximates the rule closely enough.

      if opstate == :prefix && ostack.size && ostack.last && ostack.last.type == :prefix
        # This is an error unless the top of the @ostack has minarity == 0,
        # which means it's ok for it to be provided with no argument
        if ostack.last.minarity == 0
          @out.value(nil)
        else
          raise "Missing value for prefix operator #{ostack[-1].sym.to_s}"
        end
      end

      reduce(ostack)
      return @out if ostack.empty?
      raise "Syntax error. #{ostack.inspect}"
    end

This is the last part we'll look at (for the "reduce" method, see the earlier post), and it's outside the look. It's down to handling errors and optional operands, and then reducing the operator stack completely before returning the output handler (which should at this point hopefully contain a complete expression).

The recursive descent parser

The operator precedence parser was the hard part of parsing. There's not really all that much to say about the changes to the recursive descent parser - it's all really formulaic, so I'll pick one of the larger functions and walk through that:

  def parse_block(start = nil)
    pos = position
    return nil if start == nil and !(start = expect("{")  || expect("do"))
    close = (start.to_s == "{") ? "}" : "end"
    ws
    args = []
    if expect("|")
       ws
      begin
        ws
        if name = parse_name
          args << name
          ws
        end
      end while name and expect(",")
      ws
      expect("|")
    end
    exps = parse_block_exps
    ws
    expect(close) or expected("'#{close.to_s}' for '#{start.to_s}'-block")
    return E[pos,:block] if args.size == 0 and !exps[1] || exps[1].size == 0
    E[pos,:block, args, exps[1]]
  end

This is what the shunting yard parser calls back into. Most of this should be fairly understandable assuming you remember that "expect" tries to match a string, and "ws" skips past whitespace.
The major new thing here is "position" and that "E[]" stuff. "position" is a method that returns what the scanner thinks is the current position. It isn't guaranteed to be 100% accurate all the time as the scanner doesn't itself keep track of the length of lines it has scanned past, so it depends on the token being "unget" to contain a postition for that (see scanner.rb - not going in depth into that).

In reality it works well enough to give reasonable error reporting during parsing. But what about errors identified in later stages? That's where E[] comes in. It's a shortcut to create an instance of a subclass of Array: AST::Expr. We'll be using this class to carry additional annotation of the nodes in the parse tree in later stages. For now the additional element is the position, which it takes from the first argument that either is a position or has one. See ast.rb for the details.

Compiling the syntax tree

The compiler class itself hasn't changed all that much since last time apart from much better error reporting (see error()). The most significant worthwhile change to look at is the implementation of basic support for instance variables in objects. As for vtables for classes we're taking major shortcuts to start with.

The magic starts in "scope.rb". Specifically we now keep an array of instance variables we've seen for this current class. This chunk in Scope#get_arg will return [:ivar, offset] where "offset" is the number of the "slot" of PTR_SIZE values starting from the beginning of an instance object that this instance variable belongs to.

    # instance variables.
    # if it starts with a single "@", it's a instance variable.
    if a.to_s[0] == ?@ or @instance_vars.include?(a)
      offset = @instance_vars.index(a)
      add_ivar(a) if !offset
      offset = @instance_vars.index(a)
      return [:ivar, offset]
    end

At the moment the above contains a bug, as the instance variables will actually get added too late for the "new" method to correctly allocate the object of the right size. So in the next batch of changes will be one to "visit" the nodes of a class definition to pre-allocate the instance variable offsets.
This current approach also has another problem: In Ruby you can dynamically add instance variables to an object. There's no guarantee that all (or any) of the instance variables identified will actually be added to any specific instance. Here the compiler will need to make a trade-off:

We can allocate space for all the instance variables we see (we still need a way to handle dynamically allocated ones) or we can pick a subset that is likely to be present on most objects (if it's set in "initialiaze" for example). For dynamically allocated ones we can set aside space for pointers to a hash table to hold them. We can also use a level of indirection to "pack" the instance variables more to avoid having to resort to the hash tables as often as we otherwise might do. There's no guarantee any specific one of these strategies will be best for exactly your app, so there's room for switches here, or have the system dynamically optimize the choices at runtime (at the cost of more complexity). For now, though, we'll just allocate sufficient space for everything we see, and ignore dynamically allocated ones. Then later, we'll add support for handling dynamically allocated ones, and then we can start looking at optimizations. As usual we take the shortcut that bring us functionality first.

The compilation of the instance variables is pretty trivial - load and saves happens in compiler.rb, in compile_assign and compile_eval_arg respectively. Here's what we do in compile_assign:

    if atype == :ivar
      ret = compile_eval_arg(scope,:self)
      @e.save_to_instance_var(source, ret, aparam)
      return [:subexpr]
    end

Emitter#save_to_instance_var just stores the value to the appropriate offset into the object.

The support libraries

We've barely started on the support libraries, so this will be short, but it's worth taking a brief look at what's in the main tree so far, not least because it demonstrates how I intend to proceed - even core elements of the object model, such as the Object and Class classes will largely be written in Ruby, and make use of only very limited bootstrapping help from the compiler. Only a small number of elements will require us to "dip out" of pure Ruby, and in those cases we'll as much as possible rely on the s-expression syntax that allow direct access to the AST. Doing C etc. is a last resort or temporary workaround only - a goal of this project is minimal dependencies.

Here's what we use to bootstrap Class:

def __new_class_object(size)
  ob = malloc(size)
  %s(assign (index ob 0) Class)
  ob
end

class Class
  def new
    # @instance_size is generated by the compiler. YES, it is meant to be                                              
    # an instance var, not a class var                                                                                 
    ob = malloc(@instance_size*4)
    %s(assign (index ob 0) self)
    ob
  end
end

Calls to __new_class_object is called by the bootstrap code generated by the compiler (in compile_class). It just uses the C-library's malloc() for now, and assigns a pointer to the class Class in the first slot.
Class#new is implemented so that it will take the instance size from each subclass (that's why we use an instance variable of the class instead of a class variable - class variables are shared across subtrees of the inheritance tree in Ruby), and then does more or less what __new_class_object does.

It's worth noting that we make this raw class reference available as the instance variable @__class__ in the objects. Why not as "class"? Well, the Ruby object model is finicky. Modules and meta-classes are inserted into the inheritance chain (for good reason - it makes things a lot easier), but the are "hidden" from you when you access self.class. So @__class__ is an implementation detail that should not be dependent on other than to help us implement the core classes. The same is true for "@instance_size" in class Class.

Final words (for now)

As usual, if you have questions or comments, they are welcome. Get all of the code from Github. The state of the code when writing this can be found at tag "step-20c".

And feel free to get in touch to contribute, or just fork the code and hack away.

There's already a ton of changes since I started writing this part. The next milestone is to get the compiler to compile itself - that's probably 2-3 articles away. The first step will be to get it to generate code that will link, but I fully expect it to have plenty of problems that will prevent it from running... An article on debugging the code generation is likely to be forthcoming at that stage...
Once it can compile itself, my next goal is to work on getting it to compile mspec, in order to get a measure of what is missing from Ruby. It will require quite a few fixes to the parser.

Tristan Ikemefuna Hokstad

Sun, 03 May 2009 15:49:49 -0400

Not much sleep the last few days, and plenty of diapers... He's our first child, and was born 22:49 on April 30th, 2009. Boy, 3.8kg, 49cm long... Programming with a child on one arm is "interesting".

Here he is at two days old: