language parallax

I noticed yesterday that Github is using ACE to edit files. Apparently ACE is a descendant of the Bespin project.

In a previous post I described a script I had written that parses python into an AST represented using JSON. I’m looking for budding attempts at standardizing such representations. Does ACE have something appropriate?

As I mentioned in that previous post, this was just a small piece of a project on source code search algorithms. It’s a fun project, but when I think about why more progress hasn’t been made by others, the lack of a good standard for representing AST’s seem to be the biggest barrier.

As much as I respect the work of Xtext, MPS and Spoofax, it seems to me that the key to unlocking all this potential is creating AST interchange formats that Javascript can easily manipulate.

Five years ago the strategies with the most buzz were 1) ATerm and 2) MOF. I don’t imagine that projects like ACE will ever give the time of day to MOF. And I’m not aware of any plans to build a Javascript library for ATerm.

Ometa/JS was a cool attempt at creating language-oriented tools in a browser, but as far as I know, it never gained a big following.

The hardest part about the vast majority of software these days is not performance optimization or correctness or proving properties about some fancy type system. It’s decomposing the problem into components that the world is ready to digest.

Many of the existing attempts at multi-language IDE’s have just been too big. I’m thinking of the “libraries not frameworks” meme that has been making the rounds on Twitter lately. I’d like to be able to embed text-editing panes for language mash-ups and DSL’s in my web applications. The big GUI tools out there at the moment can’t be carved up to suit that purpose.

On the other hand, some attempts like the syntax highlighter I’m now using on this blog don’t seem ambitious enough. Will this project ever evolve into a more powerful tool, or will it be content to simply highlight text? The problem is that — as anyone who has used syntax highlighting in text editors like emacs knows — there are frequently edges cases that stymie anything other than a full description of the language.

Projects like ACE seem to be in the right position to take the lead. I’ll update this post if I find any answers.

I gave a talk at the 2011 Iowa Code Camp on Saturday, April 30th.

Given a lot of events like this in MongoDB:

db.events.insert({
    report: "file1",
    time: { dateHour: "2011042412",
            date: "20110424",
            month: "201104" },
    data: { product: "coffee",
            age: "young",
            height: "tall",
            gender: "m",
            mood: "happy" }
})

And “pivots” defined like this:

db.pivots.insert({
  company: "JavaCo",
  dimensions: ["age", "gender"]
})

And some scala that more or less does this:

val buffer = ... // local filesystem file buffer
val aggregator = ... // a wrapper for MongoDB
while( true ) {
  for( report <- buffer.unprocessedFiles ) {
    aggregator.loadFile(report)
    for( pivot <- pivots ) {
      events.???(pivot, report, "dateHour")
    }
    buffer.remove(report)
    aggregator.purge(report)
  }
  pause
}
aggregator.close

We’re left to define what “???” does.

My current thought is that something like this is appropriate:

m = function() {  emit( {
  { "pivot" : ObjectId("4dba..."),
    "time" : { "dateHour" : this.time.dateHour },
    "data" : { "age" : this.data.age,
               "gender" : this.data.gender } },
  1 ) };

r = function(key, values) {
    var total=0;
    for ( var i=0; i < values.length; i++ ) {
        total += values[i];
    }
    return total;
};

db.events.mapReduce(m, r, {
    out  : { reduce: "aggregates" },
    query: {
        "filename": "file1",
        "data.product": "coffee" }
})

My sample dataset is 2 million events spread across 114 files.

I’m using the SAFE WriteConcern.

Earlier today I turned off atime updates on the ebs volume that I had run the load test on. This was purely loads — no pivots were defined, ergo no mapreduce was performed. With atime on my dataset took 425 seconds. With atime off it took 414 seconds. I don’t have enough data to know if this 11 second speedup is real, but in any case it’s not a significant speedup. As expected. I can now check off that little optimization item.

The real way to speed up this phase is likely running 8-10 ebs volumes together as a raid 10 volume using lvm.

The other phase — mapreduce — is CPU bound. And due to the single-threadedness of mapreduce, I can only bring to bear the power of one core without sharding (or doing the computation in scala). This is the more serious bottleneck. I hope that MongoDB 2.0 addresses the concurrency problems with mapreduce or provides some new features that solve the aggregation problem.

Here are some of the resources I drew upon for the talk.

• EC2 pricing
• 10gen webinar on how to deploy MongoDB using EC2, EBS, and other AWS-specific issues
• 10gen blog post on distributed consistency (part 6 of 6)
• MongoSF 2011 schedule, including hint of 2.0′s new aggregation capabilities
• MongoDB mapreduce page (including note about its single-threadedness)
• MongoDB optimization page
• MongoDB replica set tutorial
• Martin Odersky’s post on Scala levels of mastery
• chart of $/bit over time

A friend asked me recently about parsing YAML with perl. He needed to impose some additional structure to a set of YAML documents. His initial approach was to define a new grammar for the language, but this was turning out to be non-trivial — due to significant whitespace and other complexities.

I told him about how I had used Moose types together with YAML.pm to achieve the effect of a “schema” for document types defined on top of YAML. But my solution relied on the “!!perl/hash:Bar” syntax to tell the deserializer how to bless the parsed perl data structure. That’s OK for a purely internal document that I was using, but not appropriate for anything that might be more public.

Stackoverflow led me to a cleaner solution that uses Moose’s type coercion. When passing a raw deserialized perl data structure to a Moose constructor, Moose will look for matching coercions when a type constraint is not initially met.

I’ve been looking for a schema language for YAML and JSON for a while. The wikipedia suggests that Kwalify, Rx, and Doctrine can all fulfill that role, but in the absence of consensus about a schema language, I’d prefer to use something that I have more control over.

Here’s an example. Let’s say we have the following yaml file:

---
name: Extreme Foo
id: 10
alias: FooX
bars:
  - id: 1
    name: bar1
  - id: 2
    name: bar2

The obviously implied Moose types that would define Foo and Bar are:

class Bar {
    has 'name' => (isa => 'Str', is => 'ro', required => 1);
    has 'id' => (isa => 'Int', is => 'ro', required => 1);
}

class Foo {
    has 'name' => (isa => 'Str', is => 'ro', required => 1);
    has 'id' => (isa => 'Int', is => 'ro', required => 1);
    has 'alias' => (isa => 'Str', is => 'ro', required => 0);

    has 'bars' => (isa => 'ArrayRef[Bar]',
		   is => 'ro',
		   required => 1,
		   default => sub { [] } );

    method print() {
	print $self->name . "\n"; # etc
    }
}

Unfortunately Moose will complain about the “bars” variable not being of the correct type. To fix this, we set the coerce flag on the “bars” field, so that Moose will know to go looking for coercion during object construction:

    has 'bars' => (isa => 'ArrayOfBars',
		   is => 'ro',
		   coerce => 1, # This tells Moose to look for matching type coercions
		   required => 1,
		   default => sub { [] } );

In this case — because the “Bar” is embedded in the parameterized ArrayRef type — we also need a new type called ArrayOfBars, and a coercion from ArrayRef[HashRef] to ArrayOfBars.

subtype 'ArrayOfBars'
    => as 'ArrayRef[Bar]';

coerce 'ArrayOfBars'
    => from 'ArrayRef[HashRef]'
    => via { [ map { Bar->new($_) } @{$_} ] };

Meaning that we can now do this with a yaml file that does not contain the “!!” syntax:

my $foo = Foo->new(LoadFile('example2.yaml'));
$foo->print();

The complete code is available on github

For my part, I’ve been working on a project that is tangentially related to language workbenches.

In short, it’s a language-parametric source code index and search algorithm. I put together a prototype in python early last year, and have been working on a port to scala in my free time since then. The scala version will begin to be demo-able in the next couple of weeks. This will be followed by several months of deeper research into scalability and performance.

Last night I stopped by a meeting of the Bay Area Categories and Types group at Noisebridge in the Mission District of San Francisco. They’re using a text from Barr and Wells (which will be arriving soon). It’s nice to have the ability to continue exploring abstract concepts with a group.

I’ve been bumping into category theory repeatedly for many years, and it seems like something I’m going to have to master eventually.

A few years ago I recognized that one thing missing from all the computer science education I had received was a mathematical tool that allowed me to treat languages as objects. It only occurred to me after taking several classes on the syntax of natural languages. I had seen deep mathematical treatment of various aspects of languages, but none that allowed me to refer to a language with a symbol (except maybe as a set, as was the case in my undergrad formal languages class).

After dancing around the subject for years, it’s pretty clear that Category Theory is the tool that I’ve been looking for. I’m looking forward to exploring its concepts.

A colleague of mine sent me a couple of related links: A series of youtube posts from the “Catsters”

And a paper on physics & topology

Just noticed via a Slashdot article that Bespin a web-based IDE from Mozilla Labs, and Heroku, which appears to be a Ruby on Rails web-based IDE, are generating a lot of interest. There’s also mention of an EclipseCon talk introducing a web-based Eclipse workbench.

It had to happen eventually. I’m still planning on playing a little in this space — starting with some web-based python tools — but it looks like it may be crowded soon.