Moserware

Building an Object-Oriented Parasitic Metalanguage

2008-07-31T07:34:00.001-04:00

It's all about pattern matching. The rest is just details.

My last post on OMeta# focused on what it is and the vision I have for its future. Briefly, OMeta is a new language that makes it easier to design programming languages in an object-oriented fashion using very few lines of quite readable code. OMeta# is my attempt to support OMeta on the .NET runtime. My main strategy has been to base its design off of Alessandro Warth's JavaScript implementation of OMeta/JS. This post gets into the specifics of how I've done this so far, but my hope is that you might see some places where the design could use improvement and that you might be encouraged to leave a comment so that it could get better.

High Level Design

At its core, OMeta has a very simple design. The highest level of abstraction is a grammar. Here is a calculator grammar in the current implementation of OMeta#:

ometa Calculator <: Parser {
  Digit    = Super((Digit)):d         -> { d.ToDigit() },
  Number   = Number:n Digit:d         -> { n.As<int>() * 10 + d.As<int>() }
            Digit,
  AddExpr  = AddExpr:x '+' MulExpr:y  -> { x.As<int>() + y.As<int>() }
            AddExpr:x '-' MulExpr:y  -> { x.As<int>() - y.As<int>() }
            MulExpr,
  MulExpr  = MulExpr:x '*' PrimExpr:y -> { x.As<int>() * y.As<int>() }
            MulExpr:x '/' PrimExpr:y -> { x.As<int>() / y.As<int>() }
            PrimExpr,
  PrimExpr = '(' Expr:x ')'           -> { x }
            Number,
  Expr     = AddExpr
}

A grammar is composed of rules (which are sometimes referred to as "productions"). Both the grammar itself and the rules have the same form:

Going into the rule is a list of things of the input type (here they're represented by red circles) and coming out on the right is a list of things of the destination type (represented by purple triangles). As you can see from the diagram, the output list can have lists inside of it. In the calculator grammar, the circles are individual characters and the output is a single integer.

My "Ad Hoc, Informally-Specified, Bug-Ridden, Slow Implementation of Half of Common Lisp"

As an implementer of OMeta, you have to make several design choices. One of the first is how to represent grammars. Since OMeta is object-oriented, I decided that it made sense to represent grammars as a .NET class (a.k.a. "Type"). Grammars contain rules; the obvious choice for implementing rules is to use a method. This especially makes sense because rules can refer to rules in their base grammar. For example, the above calculator grammar has a rule called "Digit" which captures a single numeric digit. The "Digit" rule applies the "Digit" rule in its base grammar (Parser) that simply captures a digit character. It does this by applying the special "Super" rule which will use the base grammar to apply the rule that is specified by an argument. Since rules are implemented as methods and rules can "override" their definition from their base grammar, it made sense to make rule methods "virtual."

Another important decision is how to represent data going into and out of a rule application. An easy choice is to represent the data in a List<T>. This works out well except for the small detail that lists can contain other lists. This nested list idea has been around for at least 50 years in LISP and languages derived from it (like Scheme). Since it has worked out fairly well in those languages, I stole the idea of a LISP-like list in my OMetaList<TInput> class which is a list of other lists with a special case that makes lists of length 1 equivalent to the element itself.

These decisions get us started, but a problem comes up if you try to implement the factorial function using recursion in an OMeta grammar:

ometa Factorial {
    Fact 0                                               -> { 1 },
    Fact :n ?(n.As<int>() > 0) Fact((n.As<int>() - 1)):m -> { n.As<int>() * m.As<int>() }
}

If you look carefully at this grammar, you'll see that it only says two things:

If the next element of input matches a 0, return 1
If the next element of input is something greater than zero, store its value to "n" and then apply the "Fact" rule supplying it with the value of "n - 1" and capture that result to "m". Finally, return "n * m".

What might not be obvious at first is that any time you store something to a variable using an expression like ":n", the value stored must be of the destination type (e.g. a triangle in the diagram). This makes us need to update our mental model for how OMeta works. We need a place to store rule "arguments" which are already in the destination type.

One way of doing this is to create an argument stack that is separate from the rest of the input. Additionally, we'll need a place to store grammar-local variables as well as a place to remember previous results of rule applications for performance reasons. This gives us a much more complete picture of what really occurs:

When a rule needs to consume input, it will first attempt to grab pop an item from the argument stack. If the stack is empty, then next element from the input list can be read.

I decided to store all of these details into a single class which I call an OMetaStream<TInput> which internally uses an OMetaList<TInput> for input data and an OMetaList<HostExpression> for storing the argument stack. The arguments are actually stored in an OMetaProxyStream<TInput> which inherits from OMetaStream<TInput>, but this is just an implementation detail.

With the major data structures out of the way, one important choice remaining is how to handle going down the wrong path. If you look at the calculator grammar, you'll see that the "AddExpr" rule can be of the form "x + y", or "x - y", or a "MulExpr".

How does OMeta know which one to take? It makes a prioritized choice by trying each of the alternatives in the order specified. If it discovers that it has gone down the wrong path (e.g. the next item from the input is a "-" instead of a "+"), it needs to backtrack and reset itself to the condition it was in before the bad choice and then try the next option.

There are two obvious ways of doing this. The first approach is to leverage runtime support by using exceptions. This is exactly what OMeta/JS does. Using exceptions has an advantage of making the generated code simpler because there is no explicit code to "unwind the stack" in case you go down a bad path.

Although it makes the code easier to read, I decided against using exceptions and instead chose to use methods that return a boolean value to indicate if they succeeded. I did this for two important reasons:

.NET does a bit of extra work when an exception is thrown (e.g. getting a stack trace). Therefore, throwing an exception has a non-trivial performance penalty.
Rules have prioritized choice. This means that failing a single choice doesn't imply that the whole rule fails. Failing can be a very common occurrence (it's not exceptional) and this makes it very performance sensitive.

Here's a small glimpse of what the generated code looks like for attempting to apply the "AddExpr" rule:

OMetaList<HostExpression> x;
OMetaStream<char> addExprOut;

if(!MetaRules.Apply(AddExpr, inputStream2, out x, out addExprOut))
{
    return MetaRules.Fail(out result2, out modifiedStream2);
}

In this case, AddExpr is the name of the rule which is implemented as a method. Data is read from the "inputStream2" which is an OMetaStream (where the red circles are characters). The resulting list is saved to the "x" variable and the modified stream is stored in "addExprOut". In order to make back-tracking easier, OMetaStreams are mostly immutable, which means that they can't change. Instead of updating the stream itself, you get a fresh copy of the stream that contains what the result would be. If you need to back track, you can simply ignore the rule application output. As a side benefit, it makes it slightly easier to debug since you don't have to worry about the mutations that could otherwise occur.

Parasitic?

OMeta's creator likes to refer to OMeta as a "parasitic language" because it doesn't exist on its own. It always lives on top of a "host language." This makes an implementation usually defined in terms of its host language. That's why there is "OMeta/JS" which uses JavaScript as a host language. Although my ultimate goal for OMeta# is to have the host language be any .NET language, I decided to use C# as my first host language.

One of the first issues that came up was trying to recognize what exactly is C# code. As you can see from examples in my last post, my first attempt was to pick a really ugly pattern that wouldn't occur in normal use. I picked two consecutive @ signs as in:

@@/*This is C#*/@@

It worked out well, but it had the downside that it was, well... incredibly ugly. I have since written a rudimentary C# recognizer written in OMeta# itself that is aware of strings and comments. The upside is that the syntax looks a little nicer:

{ /*This is C#*/ }

Using C# as the host language had several implications. The most challenging was working with C#'s static type system. This was both a blessing and a curse. On the one hand, I had to constantly think about where the data came from and where it was going. This forced me to actually understand the overall design better. On the other hand, I had to spend so much time thinking about it. Late-bound systems with dynamic typing such as Smalltalk and JavaScript remove the need for people to spend so much time doing this.

I'm optimistic that over time a lot of the stronger annoyances will go away. For example, the current syntax forces type identification as in:

-> { n.As<int>() * 10 + d.As<int>() }

Where, OMeta/JS can just say:

-> { n * 10 + d }

I'm not exactly sure how to do this yet. My initial guess is that I might be able to write some sort of type inference algorithm (preferably written in OMeta#) that could do a reasonable job. My current ideas are tied too closely with the specific host language and would require a bit of work to port them to other host languages like Visual Basic. Another approach is to implement one or more helper classes that could enable duck typing (e.g. if it looks like a certain type, walks like that type, and quacks like the type, it's probably that type).

Being able to have strong static typing internally while having a very clean syntax would be ideal (e.g. sort of like the C# 3.0 "var" keyword). Static typing is usually harder to achieve, but if you can do it well, you get many benefits. C# designer Anders Hejlsberg said it well in a recent interview:

"I don't see a lot of downsides to static typing other than the fact that it may not be practical to put in place, and it is harder to put in place and therefore takes longer for us to get there with static typing, but once you do have static typing. I mean, gosh, you know, like hey -- the compiler is going to report the errors before the space shuttle flies instead of whilst it's flying, that's a good thing!"

Another issue that came up was properly handling inheritance. It makes sense to use "virtual" methods for rules, but this also requires you to emit the "override" directive to avoid warnings. Another warning cropped up from my use of the "base" keyword in the many delegates that makes it convenient from a code emission perspective, but frustrating from a verifiable security perspective. Both of these warning are being left for a latter phase.

Compiler issues were only one factor. The other significant piece was aesthetics. A notable number of rules yield specific lists as their result. C# doesn't quite have a good, clean way of expressing an OMetaList (that is, a list of lists). In order to get around this, I created the "Sugar" helper class which makes it slightly easier to write these lists. It's still far from perfect. Instead of having a nice way for expressing lists like that OMeta/JS:

-> ['add', x, y]

You have to do this instead:

-> { Sugar.Cons("add", x, y) }

This annoyance can probably be fixed by tricking the C# recognizer to act as if C# had a nice implicit way of expressing an OMetaList and then re-writing the expression to use the Sugar class.

Beyond C#, there is the "meta" "host language" which is the .NET common language runtime itself. For code to play nice on it, it should abide by the .NET framework design guidelines which dictate naming conventions and general practices. This had a parasitic effect in that it led me to name my rules after the naming guidelines for methods (e.g. they must be PascalCased). Thus, in OMeta# there is the "Digit" rule instead of the "digit" rule. OMeta/JS opts to prefix metarule method names with an underscore to make them not collide with other rules. I also wanted to hide metarules so that people would have to try harder to do the wrong thing; the best I could come up with to convey this idea was to implement them using an explicit interface exposed via a property (e.g. instead of "_apply", I have "MetaRules.Apply").

Being a Contextual Packrat

The last intriguing thing about OMeta is exactly how it implements parsing. It uses a technique called a Parsing Expression Grammar (PEG) that Bryan Ford introduced in 2004. It's just a fancy way to say you support the following features: (The table comes from the OMeta paper. I've also included how OMeta# implements them to prove its legitimacy):

expression	meaning	OMeta# Function
e₁ e₂	sequencing	Seq
e₁ e₂	prioritized choice	MetaRules.Or
e^*	zero or more repetitions	MetaRules.Many
e⁺	one or more repetitions (not essential)	MetaRules.Many1
~e	negation	MetaRules.Not
<p>	production application	MetaRules.Apply
'x'	matches the character x	Exactly

The most interesting aspect to me is the prioritized choice. This is in contrast to "Context-Free Grammars" (CFGs) which are the traditional way of defining parsers. To highlight the difference, consider parsing this line of C/C++ code:

if (condition1) if (condition2) Statement1(); else Statement2();

Is it the same as:

if (condition1)
{
    if (condition2)
    {
         Statement1();
    }
    else
    {
         Statement2();
    }
}

... or is it:

if (condition1)
{
    if (condition2)
    {
        Statement1();
    }       
}
else
{
    Statement2();
}

This is the classic "dangling else" problem. Context Free Grammars usually have this problem because they are free of any context when they are parsing (surprise!). In these situations, you often have to rely on something besides the grammar itself to resolve these ambiguities. Parsing Expression Grammars don't have this type of problem because you specify explicitly which one to try first. The prioritized choice therefore avoids ambiguity.

In order to make the performance relatively in line with the size of the input, a technique of "memoization" is used. This means the parser remembers what it has done previously; it does this as a space-time tradeoff. Keeping all those previous values have given them the reputation of being a "packrat" parser.

Let's say you have

  AddExpr  = AddExpr:x '+' MulExpr:y  -> { x.As<int>() + y.As<int>() }
            AddExpr:x '-' MulExpr:y  -> { x.As<int>() - y.As<int>() }
            MulExpr

and you try the first choice (AddExpr:x '+' MulExpr:y), but you get to where you're expecting a "+" and it isn't there. You'll notice that the second choice (AddExpr:x '-' MulExpr:y) repeats the first part (namely AddExpr:x). Instead of re-evaluating it, you can just retrieve the stored value that you remembered, or rather memoized.

Well, it's almost that simple. Note that the definition of an add expression (AddExpr) is left-recursive. This means that the left side is defined in terms of itself. A naïve implementation of the parser would try to evaluate "AddExpr" by applying the first choice which started with a AddExpr which would then cause it to try to apply AddExpr again and eventually cause a stack overflow.

It's not a trivial problem to fix. In fact, the paper that introduced Parsing Expression Grammars said that left-recursion should be avoided since you can rewrite the rule to avoid left-recursion. This is unfortunate guidance because the rewritten rule sometimes loses the clarity that the left-recursive version of the rule had.

At the start of this year, a paper came out showing a very clever trick that makes left recursion possible.

Say that we're parsing the expression "1+2+3" using the "AddExpr." At the start of the expression we look at our memoization table to see if we have a precomputed value for "AddExpr". Since it is our first time, we won't find anything. The first part of the trick is to immediately store the result of "Fail" as the memoized result for AddExpr when starting at offset 0. We do this before we attempt to apply the rule.

When the parser uses recursion and finds itself again asking for the value of "AddExpr" at position 0, it will find a result of "fail" and thus fail that choice. It will then continue down to "MulExpr" where it will eventually match "1". The second part of the trick is to treat this value of "1" for "AddExpr" at position 0 as a "seed parse." The parser will then attempt to "grow the seed" by starting over at the beginning of the input stream, but this time it will remember its previous successful match. This will cause it to match "1+2" for AddExpr and then start over again by growing the seed to finally match "1+2+3."

In hindsight, it's a very simple idea. However, I say that only after some serious debugging time where I kept finding problems in my poor implementation. Alas, the entire algorithm is implemented in only a few lines of code in the "MetaRules.Apply" function in OMetaBase.cs.

So there you have it, you now know all of the interesting ideas in OMeta#.

Where is This Going?

OMeta# is a hobby project that's been a labor of love for me. You might have already guessed that if you noticed that most check-ins occur late at night or on the weekends. It's been slow, but it's coming together. Probably the most exciting highlight in the development came when I got enough of OMeta# working that I could rewrite parts of itself in OMeta#. This has the benefit of being cool from a meta self-reproducing level, but it's also a bonus because the code becomes much more readable and introspective. For example, compare the C# recognizer that I wrote by hand to the OMeta# grammar version that implements the same idea.

This approach of writing more of OMeta# in OMeta# will continue. It's my hope that as much as possible will be written in itself. A significant next step would be to rewrite the code generator as an OMeta# grammar. This isn't a new design idea. Each subsequent version of Smalltalk has been bootstrapped by its previous version.

I'll be the first to point out that there are a lot of rough edges to my current implementation. If you look around the source code, you'll see several comments labeled "// HACK" where I admit a hacked version of an idea. One of the most glaring problems is that debugging is annoyingly difficult. I haven't yet implemented an optimizer for the generated code which causes a lot of unnecessary metarule applications. The second annoyance is that just stepping into so many methods that fail often takes a long time. Over time, I hope to add better hints to get more traditional error messages that you get from good compilers so that you don't have to step through the generated code to debug a grammar.

As mentioned earlier, the language recognizer could use some work to make the syntax cleaner as well inferring types so that grammar writers don't have to explicitly declare them. I have confidence that the work that would go into a good C# host language implementation would directly port to other languages such as Visual Basic.

There's also a great need cross pollination with other projects such as the Dynamic Language Runtime (DLR) which has already tackled some of the issues that OMeta# will face. Additionally, languages such as F# have similar data structures already built-in that OMeta uses. Boo and Nemerle have interesting extensibility points which could provide some good ideas. The problem for me is that there is so many different places to look. It'd be great if you know these languages (or others) and could tell me via a comment or better yet, by sending code of how they could help OMeta#.

As of right now, I plan on keeping the core functionality in C# rather than rewriting everything in another language or by using the DLR. The main reason is that C# is wide-spread in availability, both on .NET as well as on Mono. A second reason is that I would like to keep the outside dependencies on OMeta# as small as possible.

OMeta is a beautiful in the same sense that mathematics can have a simple beauty. LISP has been referred to by some as "The Most Important Idea in Computer Science" largely because its core ideas could be expressed on a half page of the LISP 1.5 manual (page 13 to be exact). This elegance is similar to mathematics of Maxwell's Equations describing electromagnetism.

It's my hope that I won't mess up the implementation to the point where this elegant beauty is lost. Currently it's way too ugly. I see some of the rough edges, but I'm sure you can help me discover others along with how to fix them. If this post sounds too complicated, it's not you, it's me. Let me know if something doesn't make sense and I'll try to provide clarification.

If you're interested in OMeta#, I highly encourage you to download the latest version of the source code from CodePlex and step through the unit test runner to see things get built up.

If you can, keep notes of all the places where you see me doing something and let me know about them either through comments or via email. In addition, I also highly recommend experimenting Alessandro Warth's great OMeta/JS implementation via your web browser.

Happy OMeta-ing!

OMeta#: Who? What? When? Where? Why?

2008-06-24T00:36:00.003-04:00

What if programming language implementations were object-oriented? What if you wanted to change one itty-bitty part of your favorite language? Say you wanted to add an exponentiation operator (^^). How hard would it be?

Wouldn't it be nice if you could "subclass" a language like C# and then add 5 lines of code to make it work and then use it? What if you could add Ruby-like method_missing support in 20 lines?

What if you could conceive of a new language and start experimenting with it in production code in an hour? What if it leveraged your knowledge of existing frameworks like .NET?

Let's imagine that it were possible. Let's say someone else created a basic calculator-like "language":

Even without knowing the syntax, you can probably figure out how it works since it's written very close to the standard way of describing a language. If you give this language "3*4", it will respond with 12. If you give it "2^(3*4)", it'd respond with a nice syntax error message like "I don't know how to deal with the '^' symbol. Sorry!"

But you could make it work by writing this object-oriented-like "subclass" of the language:

Now, giving this language "2^(3*4)" happily gives you 4096.

This worked using simple inheritance. What if you wanted to compose your language from several other languages? That is, something like "multiple inheritance" but without its problems? What if we took a simpler approach and allowed a language to attempt to match elements of any other language?

Let's say we want to build a scientific calculator that leverages some of the work we've already done. Instead of inheriting from it, we'll call out to it:

Now you can calculate expressions like "sqrt (1+2^3)!"

What if such a meta language (e.g. a language for describing other languages) existed? What would you do with it? How might it help you get things done while producing extremely small, but very readable code? What if creating a new language that perfectly fit a problem your software was trying to solve was as easy as writing a simple regular expression?

What if you could get all the whiz-bang, gotta-have tool support like syntax highlighting, interactive debugging, and a compiler for it came at almost no extra cost? What if the barrier to entry for a new language was so low, that almost anyone could do it quickly?

This is what I've been thinking about for the past month or so.

Who? & What?

When I was doing some research for my "Towards Moore's Law Software" series, I came across a very interesting language called OMeta which was created by Alessandro Warth and Ian Piumarta with some inspiration from Alan Kay. In their 2007 Dynamic Languages Symposium paper, the authors described OMeta as

".. a new object-oriented language for pattern matching. OMeta is based on a variant of Parsing Expression Grammars (PEGs) —a recognition based foundation for describing syntax—which we have extended to handle arbitrary kinds of data. We show that OMeta’s general-purpose pattern matching provides a natural and convenient way for programmers to implement tokenizers, parsers, visitors, and tree transformers, all of which can be extended in interesting ways using familiar object-oriented mechanisms. This makes OMeta particularly well-suited as a medium for experimenting with new designs for programming languages and extensions to existing languages."

To be honest, I didn't really understand the paper when I first read it. It sounded cool, but it used a few new terms I hadn't heard of before. However, I couldn't help but be fascinated by OMeta's readable syntax. OMeta doesn't try to solve every problem involved with writing a complete program. It makes no claims about being a good general purpose programming language. But it positions itself by doing just one thing really well:

Pattern matching.

If you look at modern programming languages that are good for developing other languages, you'll notice that they usually have good pattern matching capabilities. For example, in ML (which stands for meta-language), you can specify functions in terms of patterns. Here's how you can reverse a list:

This defines the function named "reverse." When it sees the "pattern" where the function is called with an empty list (nil), it just returns nil. However, when the function is passed in a list whose first element is "x" and the rest of the list is "xs", it will return the reverse of the rest of the list and then append the head of the list to the end.

If you think about it for a second, it's a really compact way of expressing how to reverse a list.

Streams of Anything

What I find interesting about OMeta is how it matches patterns. OMeta can operate on a stream of anything. This is useful because modern language implementations have several phases that work on different types of "things." Here's a simplified view of what a compiler does:

At the start of the process, you're working with individual characters from source code. The list of characters is converted to tokens by use of a scanner. This is how the characters 'i', 'n', and 't' become the "INT" token. The next phase combines tokens together to form a higher level view of the program, typically using a tree data structure. From that phase, several intermediate steps occur on the program (almost always in tree form), until it's finally pulled apart to make an executable program.

Often, you have to use different tools at each phase. You might use lex for the scanner (aka "lexer"), Yacc for the parser, and some sort of visitor pattern in your implementation language (e.g. C#) for many of the intermediate phases. With all of these different tools to learn, it's no wonder why most people don't even bother trying to create their own language.

OMeta is different in that lets you use the same syntax for all phases. The only thing that is different is what the input stream contains. At the start, the input stream is characters. In subsequent phases, it tokens, then trees, and then finally you produce your intended result. At each pass, your OMeta code has similar syntax.

Passing the Match Around

Another interesting bit about OMeta is how it goes about finding rules. Rules are defined in grammars which behave like classes in an object-oriented language. A grammar can "inherit" from another grammar. An added twist is that a grammar can call out to a "foreign" grammar. This makes it easier to build a language from many different reusable parts and allows for trivial "mashups" of several languages.

Additionally, if a rule has multiple "choices," then OMeta always tries to match the first choice, then the second, and so on until it achieves success. Although this seems obvious in hindsight, most parsers don't have prioritized choices and thus they make it easy to define ambiguous rules. For example, is "1-2-3" equal to "(1-2)-3" = -4 or "1-(2-3)" = 2? With prioritized choice, you make this explicit. If it successfully parses, then it has exactly one choice and therefore no ambiguities.

The last really interesting aspect of OMeta's design is what it does when it matches a pattern. A pattern might consist of several sub-components. Each of these components (e.g. rules) can be captured into a variable. OMeta then feeds these variables into a "host" language.

OMeta doesn't care what the host language is. It can be just about any language (e.g. JavaScript, LISP, C++, etc.). Typically, the host language is what the OMeta implementation itself was written in. The host language is free to do whatever it likes with the variables. OMeta is only responsible for getting them there. The OMeta paper describes an implementation where the host language is cola. Other early versions were written in Squeak and use that as the host language.

Alessandro has recently created a JavaScript version where you experiment with OMeta/JS (e.g. JavaScript is the host language) in your browser. It's a very interesting playground. Some of the demonstrations range from the basic calculator language, to a type checker, to LISP, to even the OMeta compiler and code generator itself and all of them are written in OMeta/JS. The playground website is neat to use because it shows the translated (generated) JavaScript code for the grammar (although the generated code needs to be put through a pretty printer to make any sense of it).

Why the "#" in OMeta#?

After understanding the basics of OMeta/JS, I thought it would be interesting to have the host language be any .NET language. I started to sketch out what this might look like by using my limited JavaScript ability and translating Alessandro's code to an equivalent functionality in C#. The result was the start of a project that needed a name. "OMeta#" seemed to fit the bill.

Besides, it just sounded better than other .NET-ism alternatives like "NOMeta", "OMeta.net", or "IronOMeta."

Some might ask, "Why .NET?" A subtle reason is that OMeta is useful for code generation. Code generation is a normal part of the .NET ecosystem even if people don't realize it. When people use the graphical designer in Windows Forms, there is a code generator working behind the scenes writing code for their host language (typically C# or Visual Basic). When people write ASP.NET ".aspx" files, there is a hidden process that takes that HTML-like "language" and compiles it to a real DLL.

For example, ASP.NET transforms this:

Into this generated code:

I wanted to bring a similar "it just works" illusion to the .NET world with OMeta#.

With the encouragement of Alessandro, I started working on some of the supporting "goo" that would be required to get OMeta working on the .NET's Common Language Runtime (CLR). This isn't trivial because the CLR has stricter type system than languages like JavaScript. Also, since I chose C# as the implementation language, I had to make sure that the code passed all of the static type checking it performs at compile time. It's been a slow start, but I have been able to make a few steps towards making it work.

One pragmatic question is why even bother adding another language, or rather, meta-language to the .NET world? Why not just get proficient at another toolset that is decent at creating language like ANTLR, Irony, NParsec, or IronRuby? What about using Parsing Expression Grammars in F# or writing Domain Specific Languages in Boo with its extensible compiler pipeline?

Ultimately, all of those tools are pretty good, but none of them did exactly what I was looking for. Some came close, but none of them seem capable of matching OMeta's power and simplicity.

Another reason was that I knew that writing an implementation of OMeta from the ground up would really help me "know" how it works.

More importantly, I thought it would be fun to work on. I'm not a language expert. I'll never reach the level of someone like Anders, but I was one of those odd kids that actually liked my compilers and programming languages classes. I also enjoyed the talks from this year's Lang.NET symposium (even if I didn't understand a lot of things).

The Grand OMeta# Vision

The grand vision for OMeta# is to make it really simple to create languages that "just work." It probably won't have the world's best performance, but it should be decent enough for almost all practical applications. It would be neat to have OMeta# (or something like it) be used to do the following:

Serve as a common, unified way for developing languages on the .NET platform — There are many helpful, yet often different "tools" out there for various stages of language design. I mentioned a few earlier, but some of the more advanced ones include the new Dynamic Language Runtime (DLR) and Phoenix compiler framework. It would be neat to have a language that abstracted away some of these tools into a clean syntax like OMeta. That way, you'd get the benefit of these tools without having to constantly learn different ways of manipulating the concepts that can be expressed simply.

Factor out the "goo" of language development — For a language to be taken seriously, it has to have things like syntax highlighting, interactive debugging, and a decent compiler. Each of these takes time to implement and often involves a high learning curve. It would be great if you could just make some minor annotations to your OMeta grammar and then these features would "just work."

Useful for teaching — One of my favorite textbooks in college was "Programming Languages: An Interpreter-Based Approach" by Ramsey (et. al.). Our class used a "draft" version of it (and it still hasn't been published yet). It took a very interesting approach towards teaching programming languages. In order to understand a language like Scheme, you had to implement an interpreter for it in C or ML. I really liked this approach because getting your hands dirty with implementing the language typically leads to a better understanding of it. I would love to have the ability to implement this type of approach in something like OMeta. You could understand the essence of a language by only having to understand a page or two of code. It would also let you learn by experimenting with adding small features to existing languages.

Practical for production use — For anything to really succeed at moving towards a Moore's Law increase in expressiveness, it has to have reasonable quality. I can imagine OMeta# being introduced into real production projects by first integrating a small amount of OMeta's "generated" a project and then over time implementing more and more parts of the application in this highly specific language. For this to occur, it has to be reliable and simple to use.

When? Where?

All of the parts of the vision are still in the future. To make them a reality will require more than just a single person or even a couple of people. I'm ~~naïve~~ crazy enough to think that it's actually possible. In an effort not to "go dark," I've decided to be fairly open about the design and implementation of OMeta#. The current state of the code isn't even alpha quality yet. Despite all of these shortcomings, I've posted what I have so far on CodePlex and will continue to make updates to it.

Keeping in the tradition of other OMeta implementations, I've licensed it under the MIT License so that you can use, experiment, play, and modify it without any licensing concerns.

The first interesting result is that I've been able to get a complete end to end demo working for an extremely simple grammar that matches numbers. I fed this input grammar written in OMeta/C#:

into my OMeta compiler/translator and successfully had it generate this output C# file.

There is still a ton of work left. It's quite possible that some of the design decisions I've made so far need to be challenged and redesigned. I'd love to get feedback from anyone that's interested.

What do you think? Do you think OMeta fills a unique niche? Do you think it would be useful to have as a tool in .NET? Would you want to help out making "The Grand OMeta# Vision" happen? If so, what parts can you help out with?

I'm curious to hear your thoughts. In my next post, I hope to cover some of the technical details for how my current implementation works "under the covers."

P.S. Many thanks to Alessandro Warth for creating this beautiful language and helping me get started!

Who Is This "Licklider" Guy?

2008-05-21T22:00:00.001-04:00

Who are they talking about? Why haven't I ever heard of him?

I was at SRI, a research institute by the Stanford campus. Around me was a lively group of some of the best minds in Computer Science, some of them has had their PhDs in the field for 40 years. I had the honor of being the least credentialed person in the room. As I listened to some of the discussions, I noticed that they seemed to keep bringing up the name "Licklider." Sometimes they'd just call him "Lick." Other times they'd mention projects along with his name that I hadn't heard about before like "Project MAC." Since the guys talked so much about him, I knew I had to find out more about who this "Lick" guy was. One of them suggested that I read the book "The Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal" by M. Mitchell Waldrop.

My local library had the book. I was a bit worried when I saw that it hadn't been checked out for three years. "Hmm... maybe it's not that good?" I thought.

I was pleasantly surprised.

At about 500 pages, it's not a small book. Fortunately, I was able to finish it just before the library forced me to return it since I hit the maximum amount of renewals on it.

The book put me on a journey that filled in a lot of details about computing history that I didn't even know I was clueless about while weaving a story about a man from Missouri. Although his full name was Joseph Carl Robnett Licklider, just about everyone called him "Lick," a name he acquired in his fraternity days.

Lick's story is bigger than just one guy. It's a story that goes back to the dawn of computing right up to the personal computer. While reading the book, I had a lot of "Aha!" moments that helped fill me into the colorful history of computing. For example, I had heard a lot about DEC's PDP system, but it was interesting to know that they were specifically called "Programmed Data Processors" instead of "computers" because congress was pressured not to spend any more money on computers at the time. By itself, facts like these seem to be obscure trivia, but when you read about the politics of funding at the time, you can really understand that DEC had few alternatives.

I can't recall ever hearing Licklider's name before that meeting at SRI, but that's probably because I didn't try too hard. As a kid interested in computers growing up in the 1990's, I really focused my attention on learning about one person - Bill Gates. I read several books about him and had a reasonably good idea of his background and the history of Traf-O-Data, Microsoft and some of its products like BASIC, DOS, OS/2, Windows, and NT. Perhaps in the back of my mind I thought that learning about him would me emulate his success and make me ~~millions~~billions. Too bad that didn't work out.

In addition to the books, my other major source of information was when I watched Bob Cringely's Triumph of the Nerds on PBS in the summer before I started high school. In hindsight, after reading this book I really wish I would have watched the 1998 follow-on to the series called "Nerds 2.01: A Brief History of the Internet." I would have at least heard about Licklider and the computing days before Microsoft and Apple and not been so clueless back at that room in SRI.

What a story it is! It's not really just about Lick; it's about how he helped build a community that fostered the explosive computing growth in the 1960's right through the 70's and 80's.

Since I like to ask others what stuck out in books that they've read, I thought I'd share some things I found interesting:

22 Days of Beeps Can Change a Nation

Chapter 6 opens on a rocket launch pad in the early morning of October 1957 at a top secret Soviet Union location. When the rocket took off and deployed its payload, the world came to know Sputnik by its incessant beep beep beep transmissions.

Waldrop quotes this account:

"[Sputnik's] two transmitters would fail twenty-three days after launch - but their arrogant beeping would continue to sound in the American memory for years to come... Gone forever in this country was the myth of American superiority in all things technical and scientific." (p. 197)

Although the U.S. had rockets under development that were more sophisticated than the Soviet ones, it was a huge blow to American pride and there was a large public outcry. Everyone made the connection: if the Soviets could launch a satellite into space, they could probably launch a missile into any major U.S. city.

One famous result of this perceived threat was President Eisenhower's endorsement of "a plan to consolidate all the Pentagon's space research under a new civilian agency reporting directly to the secretary of defense. It would be called the Advanced Research Projects Agency, or ARPA."

Well it didn't quite work out exactly as planned.

Before ARPA opened for business, it had already been split up. The National Aeronautics and Space Administration (NASA) would handle all the non-military space projects and the services would get a large amount their funding back to handle most of their development projects. This left ARPA with "the kind of beyond-the-cutting-edge stuff that the services were willing to do without." (p. 198)

ARPA wasn't initially interested in computers. To them, they were really only helpful for things like accounting and payroll. This changed when ARPA was tasked to research new command and control ideas that would require a lot of data processing. This seemed like an ideal fit for computers. Licklider was asked to come over to ARPA and lead the new project.

He didn't want to take the job at first. He was already doing interesting things with computers and was so busy working on fleshing out his ideas of computer assisted "libraries of the future" to even think about burying himself in "the bureaucratic limbo of Washington." (p. 201)

Once he warmed up to the idea of going to ARPA, he began thinking that the command and control concept was ultimately a man-machine symbiosis, something he had been thinking about for years.

In March of 1960, he published his famous "Man-Computer Symbiosis" which began:

"The fig tree is pollinated only by the insect Blastophaga grossorun. The larva of the insect lives in the ovary of the fig tree, and there it gets its food. The tree and the insect are thus heavily interdependent: the tree cannot reproduce without the insect; the insect cannot eat without the tree; together, they constitute not only a viable but a productive and thriving partnership. This cooperative 'living together in intimate association, or even close union, of two dissimilar organisms' is called symbiosis.
'Man-computer symbiosis' is a subclass of man-machine systems. There are many man-machine systems. At present, however, there are no man-computer symbioses. The purposes of this paper are to present the concept and, hopefully, to foster the development of man-computer symbiosis by analyzing some problems of interaction between men and computing machines, calling attention to applicable principles of man-machine engineering, and pointing out a few questions to which research answers are needed. The hope is that, in not too many years, human brains and computing machines will be coupled together very tightly, and that the resulting partnership will think as no human brain has ever thought and process data in a way not approached by the information-handling machines we know today."

This might not seem radical in 2008, but it was revolutionary back in the 1960's when most people could only think of computers as batch processing machines. Lick saw computers in a symbiosis where humans could do the thinking and the machines would do the "algorithmic chores they were so good at" (p.148). In order to find out how much of a benefit they'd be, he did an experiment on himself and found to his horror that he spent 85% of his time just "getting into a position to think, to make a decision, to learn something I needed to know." The rest of the time was just clerical or mechanical. Computers would be a perfect fit to handle all the dreary stuff that got in the way of real thinking.

Lick knew that he could start making the man-computer symbiosis concept real and get the government to pay for it through his association with ARPA. Lick's view was "that the problems of command and control were essentially problems of man-computer interaction. I thought it was just ridiculous having command-and-control systems based on batch processing. Who can direct a battle when he's got to write a program in the middle of a battle?" (p. 202)

On the next page we see:

"Improbably, miraculously, through some once-in-a-lifetime alignment of all the right planets, ARPA was offering him a chance to turn his vision into a reality. He could reinvent the whole field of computing. He could transform those giant calculating machines into full-fledged partners in a human creativity. He could create 'information utilities' that spanned the continent. He could democratize information by opening up vast libraries of material to instant access by anyone. And he could do it all with the Pentagon's money." (p. 203)

And boy did he ever:

"[The professional bureaucrats] had a history of giving grants to individual people in twenty-thousand-dollar chunks. But Lick was talking about millions of dollars and whole teams of people. It was as though these folks had encountered this alien creature: friendly, but strange." (p. 206)

In addition to funding research organizations like SDC, RAND, and SRI, Lick is remembered for helping fund the new computer science departments at Berkeley, Stanford, Carnegie Mellon, and perhaps most famously, MIT. Lick's funding at MIT went towards a system that would put together several foundational ideas needed for his man-computer symbiosis. The goal was "Machine-Aided-Cognition," but since computer time was hard to come by and they had to invent a lot of the concepts for time-sharing to allow multiple people to access a computer at once, the project also went by the name "Multiple Access Computer." Regardless of which one you chose, the acronym was the same.

"So that's the Project MAC the folks in the room were talking about," I thought as I read about it.

Project MAC would lay a lot of the foundations for modern operating systems. Examples include technologies like multitasking and file systems to policies such as regular backups to protect themselves from their mistakes. They had to introduce passwords to stop some people from stealing computer time as well as ideas from unpublished academic papers. Unix and the C language it was written in was an offshoot of this project as an attempt to write a simpler version than what the Project MAC team was trying to accomplish.

And yet, Project MAC was just one of the many projects that Lick was funding and tracking. To the outside observer, all of the projects seemed like an ad hoc mess rather than a carefully crafted plan. Lick knew that his man-computer symbiosis dream would need to be maintained by more than just him. Waldrop writes:

"Lick realized, if this vision was ever going to outlast his tenure at ARPA, he would somehow have to forge all these groups into a self-reinforcing, self-sustaining community." (p. 225)

One such example of how he did this was his famous 1963 memo which began: "[to the] Members and Affiliates of the Intergalactic Computer Network." In his mind, Lick was referring to a human network. He continued: "It is evident that we have among us a collection of individual (personal and/or organizational) aspirations, efforts, activities, and projects." The challenge now was to exploit "the possibilities for mutual advantage". He went on to describe a connected system that would keep all the research projects together, a network focused on human thoughts but connected by wires. In essence, the early signs of the Internet.

But it took some time to materialize and didn't happen during Lick's ARPA tenure.

He did make progress. Due to the computing focus that Lick had caused, his ARPA division was given the title "Information Processing Techniques Office" (IPTO). After his two year tenure at ARPA, Lick handed the reins over to a young Ivan Sutherland (creator of Sketchpad, which launched the field computer graphics and computer aided design). When Sutherland finished his tenure, Bob Taylor would take over and proceed to actually make Lick's "Intergalactic Network" of people a real physical thing by linking ARPA people together into ARPANET, the direct predecessor of the Internet.

The first message went across it at 10:30 PM on October 29, 1969.

Two interesting things from the book stand out right around this period of time. The first was that the height of the Vietnam War was taking a huge toll on the nation, both in terms of people and dollars. In a reported attempt to limit spending on the war, Montana senator Mike Mansfield proposed an amendment that would prevent the Defense Department from "[carrying] out any research project or study unless such project or study has a direct and apparent relationship to a specific military function."

The practical effect of the "Mansfield Amendment" was that it diverted a large percentage of people's time into writing how their project had a "direct and apparent" relevancy. It's also one of the largest reasons why ARPA is now known as DARPA:

"In retrospect, moreover, [the Mansfield Amendment] came to be seen as the symbolic watershed for ARPA, the point at which it started its downhill slide from being a cutting-edge agency that was blessedly free to take risks to being an ordinary agency that was cautious and risk-averse." (p. 395)

The second big thing was that in May of 1969, Xerox was making a lot of money selling copiers. But their management knew they had to be more than a one product company. In an attempt to branch out and "go digital," they purchased Scientific Data Systems (SDS). However, they had a problem: the company was largely computer illiterate. They needed to go out and recruit the best computer people the world had. One of their first hires was none other than former ARPA IPTO director Bob Taylor. Taylor would go on to attract many from Lick's "Intergalactic Network" ARPA community who had been distressed by the Mansfield Amendment and its research cutting implications.

The resulting Xerox Palo Alto Research Center (PARC) was the place to be in the 1970's. It fostered freedom to explore ideas just like the early ARPA days since its backers were willing to invest in long-term innovation. Its anti-corporate culture included meetings filled with beanbag chairs which prevented people from leaping out of their chair to argue with someone. This 'helped' you hear them out. PARC would go on to create the foundations of personal computing as we know it with their Alto personal computer which was named after the city they were in. The Alto had new ideas like bitmapped displays, windows, an Ethernet network, WYSIWYG word processing, laser printing, and roots of modern object oriented programming. Unfortunately, Xerox's management didn't quite understand the business value of what their PARC guys were creating. Additionally, the guys inside PARC had a hard time creating a clear path and business model for getting their ideas to market. There was one notable exception. Waldrop writes:

"If [Jack Goldman] hadn't thrown a tantrum [in order to get the business guys to listen], they might just have rejected the laser printer itself - the one PARC-bred product that would eventually earn billions for Xerox and repay its investment in PARC many times over." (p. 392)

Steve Jobs, along with some other engineers, would visit PARC in December of 1979 for a demonstration of the Alto system. Jobs was so enamored by the graphical interface that he saw that he didn't even explore the object oriented programming and networking ideas. During the visit, Jobs reportedly exclaimed "Why hasn't this company brought this to market?" (p. 443) He didn't wait around for Xerox. Apple's first graphical computer, "Lisa," 'borrowed' several ideas from the Alto. When the Lisa and IBM PC hit the market in the early 80's, the guys inside PARC realized that Xerox had blown a huge opportunity. Many jumped ship. One example was Charles Simonyi, who took his ideas Bravo word processing ideas north to a relatively new company in Washington named Microsoft. It was a huge difference in culture. Simonyi's commented on the contrast:

"It was like going into the graveyard or retirement home before going into the maternity ward. You could see that Microsoft could do things one hundred times faster, literally, I'm not kidding. Six years from that point, we overtook Xerox in market valuation." (p. 449)

And that brought me full circle back to the pop culture history I was more familiar with. Throughout the years Lick would stay involved in some part with the research community, sometimes getting bogged down with management tasks which he despised. He would teach at MIT through the 80s with students that would only later realize all that he had done. Failing health caused him to pass away at the age of 75 on June 26, 1990: just before the world at large would come to use the "Intergalactic Network."

Lick was known for being quite modest about his contributions, often minimizing his role. When asked about what he did, he said:

"I think that I found a lot of bright people and got them working in this area. I got it moving. [And it was] a fantastic community. I guess that's the word. It was more than just a collection of bright people. It was a thing that organized itself into a community, so that there was some competition and some cooperation, and it resulted in the emergence of a field." (p. 258)

So that's why they kept talking about him. Now I get it.

Lick organized a community that would change the computing world. He realized that it's ultimately the people that matter. I think that our industry puts too much emphasis on technology and tends to marginalize people. I think that one of the first steps to reverse this trend is to understand the contributions of its founders like Lick.

"The Dream Machine" was a good book. I recommend it to anyone who might be curious about what happened in computing before the Microsoft, Apple, and especially Google days. From the early days of Von Neumann and Turing, right up to the 90's, Waldrop's detailed research helped the story come alive. The book appears to be out of print, but it is well worth a visit to your library or getting a used copy.

If you made it this far, I'd really love to hear your comments on a few related questions:

Had you heard of Licklider before? If so, where? What sticks out in your mind about Lick?
What do you think about Lick's funding and management strategy in the early days of ARPA's IPTO?
What do you think of Lick's comparison of the Fig Wasp and Fig Tree to a man-computer relationship? Do you think we've obtained the man-computer symbiosis he was referring to?
What about PARC? It could still be considered success since the laser printer paid for Xerox's investment in it. However, as Steve Jobs points out, they could have been the IBM of the 90's but blew their chance. What do you think?
What do you think about the Mansfield Amendment of the 1970 fiscal year? It's easy to criticize things in hindsight. If it was 1969 and you didn't know the future, which side would you have honestly taken? How would you have defended your position?
If you read this book or similar books, what is most memorable to you about the period from the 1930's through the late 80's that you think most people don't know about?