Only 20,000 Lines

A while back I posted a big ol' post titled A Growable Languge Manifesto which argued strongly for extensible languages.

Well, I just ran across the one-year progress report from Alan Kay's current research group, and it's some extremely exciting work that is all about extensible languages!

The group is the Viewpoints Research Institute, and the progress report lays out their plan to implement a complete software stack -- everything from the graphics driver, to the language interpreter / compiler, to the TCP/IP stack, to the windowing and rendering system, to the IDE and programming environment -- in 20,000 lines of code. Total.

As they point out, a TCP/IP stack alone in many conventional languages is more than 20,000 lines. So how can they possibly pull it off?

The answer, it turns out, is extensible languages. Specifically, they have an extensible parsing system -- OMeta, cited heavily in my manifesto -- which allows them to easily and quickly extend their languages. They also have a "meta-meta-language runtime and parametric compiler" named IS, which is how they actually get their languages and metalanguages into executable form.

One especially cool example is their TCP/IP stack. The TCP/IP specification has text diagrams of packet formats. So they wrote a grammar to parse those specifications directly as ASCII. And lo and behold, they could use the TCP/IP RFCs themselves to generate their source code. They also can use their parsing framework to analyze the structure of TCP/IP messages -- they basically define a grammar for parsing TCP/IP messages, and action rules for handling the various cases. (OMeta lets executable code be attached to matching productions in a grammar.)

They also wrote domain-specific languages for just about every area. One example is low-level pixel compositing, basically giving them the functionality, and most of the efficiency, of a generative 2D pixel processing library such as Adobe's Generic Image Library, cited in Bourdev and Jaaki's LCSD 2006 paper. Another example is polygon rendering (450 lines of code that implements anti-aliased rasterization, alpha compositing, line and Bezier curve rendering, coordinate transformations, culling, and clipping). Though evidently they have yet to fully define a custom language for polygon rendering, and they hope to cut those 450 lines by "an order of magnitude".

Basically, they take almost all parsing and optimization problems and express them directly in their extensible language, which gives them almost optimal flexibility for building every part of the system in the most "language-centric" way possible.

They have no static typing at all, which doesn't work for me (though their line counts make a compelling argument), but there's no reason in principle that these techniques couldn't also apply to static type system construction.

In fact, there is work right now on intuitive language environments for creating written formal definitions of programming languages. A system like Ott lets you write semantics declarations that look like they came straight out of a POPL paper, and convert them into TeX (for printing) or Coq/Isabelle/HOL (for automated verification). I don't know how far the implementation of Ott or Coq/Isabelle/HOL would change if Viewpoint's techniques were aggressively applied, but I look forward to finding out!

I think this kind of programming is the wave of the future. Reducing lines of code has always been an excellent way to improve your software, and the expressiveness of a language has always shaped how succinctly you can write your code. From that perspective, it seems obvious that an extensible language would provide maximum potential increase in expressiveness, since you can tune your language to the details of your specific problem. It's a force multiplier, or possibly a force exponentiator.

Object-oriented class hierarchies, query languages, XML schemas, document structures, network protocols, display lists, parse trees... they all share a common meta-structure that the "extensible languages" concept subsumes, and the Viewpoint project is the clearest evidence I've seen of that yet. It's going to be a dizzyingly exciting next few years in the programming language world, and programming might just get a lot more interesting soon -- for everybody.

There's more to say on that topic, but I'll save it for another post!

My New Job

Well, this post has been a long time in coming. Finally all the stars have aligned, and I can announce to the world (i.e. you!) that I have accepted a job at Microsoft. My family and I are moving up there in just a few more weeks -- we sold our house (in one week flat! amazing what price reductions can do), and are in escrow. Which also explains the loooong delay since last post.

What exactly will I be doing? I'll be working for a technical strategy incubation team, which kind of sits in between research and line development. We're working on a new operating system stack from boot loader all the way to applications. I can't really say much more, except that what we're doing is not entirely unrelated to the Singularity operating system.

Having spent the last twenty years in the bay area, hotbed of anti-Microsoft sentiment, I am pretty sure that I have quite a few readers (and friends!) who will be wondering why exactly I'm joining the Evil Empire. Especially when I interviewed with quite a few other places, including Amazon and Google. What's up with that?

There are a few answers to that question:

• I don't like how Microsoft has abused their monopoly power, but I also have been a Windows user for the last sixteen years, with quite reasonable satisfaction. So I personally have never quite swallowed the "Microsoft is Satan" kool-aid.


• The more blogs I read by Microsofties (especially the anonymous ones), the more I see that Microsoft's internal self-assessment is by no means all rosy. Microsoft engineers seem quite aware of when their stuff sucks. The existence of the team I'm joining is arguably proof of that exact fact.


• It's possible that working for Microsoft will circumscribe what I can blog about without making lawyers mad. However, that's just as true of Google, which is also notoriously secretive. Google also has had quite a few criticisms directed at its business practices. Basically, size, confidentiality, and ethical qualms seem unavoidably linked. (It's true that Google does more open source stuff than Microsoft, but that may be changing as well.)


• If our stuff is great and makes it into Microsoft products, it could potentially make life better for a whole lot of people. Operating system work at Microsoft can have a broad impact in a short time, if it's successful.

I'll also be working with some old friends from my Xanadu days, along with some relatively well-known other folks, including Pavel Curtis and Chris Brumme. I got to meet a good cross-section of the team and I'm very jazzed. My research paper addiction paid off handsomely, it turns out!

I spent the entire last week of February interviewing. I did get offers from other places, each of which I greatly appreciated.

I got a great offer from the Prime team at Amazon, also, which seems like an extremely sharp group; I will definitely be keeping a close eye on Amazon as they grow their distributed infrastructure business.

I also interviewed with a startup, which I expect to do very well (keep an eye on Apptio -- though they'll be rebranding themselves soon!). If I hadn't spent the last ten years in startups, none of which has (yet) had life-changing success, I would have probably jumped on them just for the raw upside potential; as it is, though, I'm ready to try a megacorp.

(To my Google friends: Google was very interested but ultimately turned me down. Might have partly been timing issues on my end. So, looks like it'll be a while (at least) before I'm working with you all. I'll also need to pull back from the GWT project. It's been a great few years in Java-land but it's time for a change, and I'm looking forward to C# generics :-)

All in all it was a very difficult choice across the board!

In general the whole week was the most fun I've ever had interviewing, despite the fact that I had a big bandage on my head for most of the week (beware of low pine branches after dark!!!). I sincerely thank everyone who took time to meet with me in person or by phone over the last few months.

Now to start walking the fine line between saying too little and too much. I don't plan to go dark on this blog, though I also won't (yet) be able to say much about my day job here. But that won't stop me from the general research paper talk to which you're already accustomed!

Simple Pieces, Dying Quickly

Late. Again. I assure you there are perfectly good reasons for this that, I further assure you, you do not want to know. Good news is things have radically improved in the last few days and the future is extremely bright. I'm squinting right now, in fact.

There are some architectural patterns that just Feel Right. That feeling of rightness isn't always reliable -- it can lead you pretty badly astray -- but still, it's there. And sometimes, what do you know, it even is right.

For years now I've been following research into microkernels, starting back in the early nineties when I was reading about Amoeba, an old-school distributed system structured as a set of small components. The idea of structuring an operating system as a set of isolated pieces, protected from each other and passing data only by well-defined messages, seems conceptually clean. It's started to gain traction lately with projects such as the L4 kernel, the Coyotos project, and Microsoft's Singularity, and IBM's K32.

Interestingly, one of the biggest obstacles to the wider use of microkernels is Linus Torvalds. In late 2006 he had an online spat with Alex Tanenbaum, developer of Amoeba (back in the day) and Minix3 (new hotness). Linus has been saying for years that microkernels are a crock, and that operating systems are best built with extensive use of shared memory, because -- in his view -- what operating systems do is provide coherent views of shared state to multiple processes, and without a single shared state available to the whole kernel, providing a coherent view becomes much, much harder. Linus draws a parallel between microkernels and distributed systems, pointing out that distributed protocols are really hard to implement, precisely because you don't have common state.

Personally, I agree strongly with Tanenbaum's (and Shapiro's) rebuttals. Tanenbaum points out that distributed protocols also have to deal with partial failure and reordering, which are not problems that microkernels have. Inter-component communication within a single machine's operating system can be radically simpler than communication over a network (even though multicore machines do start introducing some timing variability). Also, of course, shared state in a monolithic kernel still requires concurrency management, and the complexity of managing concurrent access to shared kernel state is by far the biggest single source of Linux kernel bugs. Just look at all the work on massaging the locking patterns in the Linux kernel (getting rid of the Big Kernel Lock, etc., etc.). For Linus to claim that micro-component kernel development is more complex than monolithic concurrent state management is... well... not as obvious as he seems to think.

Shapiro points out that all robust engineering practice has shown that high reliability requires high isolation between small, robust components. He claims, and I agree, that there are no large-scale highly reliable systems that are not built from small, modular, isolated pieces. Certainly Erlang provides another data point that high reliability comes from many small interacting components, rather than from large-scale shared state.

Small, modular components get you other benefits, such as upgradeability (if your microkernel tracks references between components and manages inter-component message passing, you can upgrade individual pieces of your system without shutting things down -- Erlang applications also work this way). Security is also enhanced if the compromise of a single component doesn't expose the entire state of your kernel.

There are also interesting parallels between building single-machine operating systems as sets of modular services, and building large-scale Internet systems as sets of modular services. In both cases, you want to build something big and reliable from individual pieces that communicate over explicit interfaces, and that can be individually quickly restarted when they fail. In an operating system, your drivers are the flakiest piece, and when they die you want to be able to reload them without the rest of the system batting an eye. In an Internet service, your individual servers are the flakiest piece, and when they die you want to be able to fail over to other (mostly identical) servers without batting an eye. Isolation between components is critical in both cases, and you want to build your whole system in a layered way with redundancy and restartability at all levels.

Linus is correct that distributed transactions (for example) are hard to build out of individual components. But it's also true that as you scale, distributed transactions are one of the biggest architectural system-breakers. Amazon, for instance, doesn't use them (see also here), instead relying on careful ordering of service updates to preserve consistency in the face of intermediate failures. And many microkernel operating systems are also structured to avoid multi-component consistency interactions wherever possible.

So I think this is a rare example of where Linus is squarely on the wrong side of history, and where Linux will likely fall behind other systems that push towards greater modularity and greater internal componentization. It's an interesting question whether large-scale Internet services will, over time, make individual-server operating systems less important -- in other words, whether most applications will migrate to a highly-managed cloud, in which case most computers will wind up being more like thin clients, with all the action happening on a virtualized pool of services. But even in that case, the companies building those services will still want to leverage multi-core technology to the max, which essentially means building their individual service instances using highly isolated component architectures. Having such an architecture at the base of the operating system can only help achieve that goal, and it's sad to think that Linus (on current evidence) will get in the way of that for Linux.

Inside Stories and Posted Mortems

Yikes, just missed my two-week window. Too much happening, too busy... get used to it, folks, it's here for the duration, e.g. until this summer, after we've sold our house. Enough of that! Onwards!

Research papers are one of my biggest Internet weaknesses. Another one is post-mortems. If we learn from others' mistakes, then post-mortems are solid education... they're experience reports in their most tangible form.

For some reason, it seems there have been a whole slew of interesting ones on the net recently. Here they are:

• Lambda the Ultimate cited this analysis of why Symbolics failed, as footnoted by Daniel Weinreb. Short story: too much technology, too little business focus. Still, interesting to get the inside view.


• Even better are Daniel Weinreb's posts about the history and impact of Object Design and Objectstore. Orthogonal persistence once seemed like a Really Good Idea to me, until we tried it at Electric Communities in the mid-nineties and couldn't make it work. Even so, it looks like there are some valid use cases that Objectstore exploited about as well as possible. Did you know Amazon evidently relies on Objectstore caching for their entire inventory database?


• Switching gears almost completely, from civilized discussion to rabid flaming, Zed's infamous rant on leaving the Ruby community deserves mention. (WARNING: SOME NOT-SAFE-FOR-STRAITLACED-WORKPLACES CONTENT!) I have to admit I have a weakness for, shall we say, colorful language. The BileBlog (WARNING: DITTO!) was entertaining for a long time, though recently it's gone dark... maybe Hani decided the career impact wasn't worth the flameful fun. I've been tempted to go balls out and get explicit here, but the more I consider it, the less necessary it seems. Wait, that was all a huge digression away from the facts, which are that Zed's rant is entertaining but I have no idea how accurate it is, and his comic self-promotion makes it hard to tell when he's being serious and when he's not, which hinders his message. He kind of wants to have his cake ("I'm so awesome, truly") and eat it too ("Can't you tell I'm mostly joking?"), which doesn't do him any favors.


• Meanwhile, the poor beleaguered Open Source Applications Foundation recently announced that Mitch Kapor is washing his hands of it all. No more funding on his nickel, almost two-thirds of staff laid off, and Katie Parlante left to try to turn it all into real revenue somehow. After six and a half years of Python hacking, they still barely have a usable application. Scott Rosenberg already told the whole epic story, but this seems like almost the last gasp. Open source projects can perish without clear architectural and requirements leadership, and OSAF will forever be the paradigmatic example. (I largely agree with, again, Dan Weinreb's take on it all. I wonder if a good dose of RPython would help out Chandler at all?)


• Finally, this isn't new news (totally the opposite!), but I've got my own personal post-mortem skeleton in the closet, namely my involvement with the legendary Xanadu project. I'm quoted in the Wired post-mortem article. Some of what I said there was classic "this kid is young and bitter" uncensored vitriol. I'm glad that the brilliant people I worked with there understood that, because I want to work with some of them again some day! But overall, there is a lot of truth in that article, and it's just a great read regardless. (Warning: that link is to the printer-friendly version, and Wired, under their new Conde Nast overlords, has lost their web-fu and has broken image links everywhere. Doesn't matter; the text is all that counts in this instance.)

I've made some whopper mistakes in my career -- some quite recently -- and it's too bad it will be a long time, if ever, before I get to tell the tales. (The downsides of modern tight-lipped corpocracy....) Still, we (hopefully) live and we (hopefully) learn. The more post-mortems, the better!

GWT2007 Video, Brain Teasers, and Semantic Metatheory

It's almost terrifying how busy things are right now in robjsoftwareland. Moving with two young kids is just not the best idea from any kind of sane logistical perspective. Trust me on this. PLEASE. My life is a continual rolling boil of domestic packing and repacking and remodeling and general chaos, and it will continue for months to come.

But I cannot and will not go dark on this blog. So, a quick update:

1) The video from GWT2007 got posted! If my previous posts about my RPC talk made you curious, you can now see for yourself. I'm amused at the Sartre reference that snuck into the video :-) I think it came out quite well overall (with the caveat, as before, that an unexpectedly large portion of the audience were newbies who didn't get the most out of it). The other talks are also online -- now I'll get to see the ones I missed! I'd also recommend Billy Hoffman's talk on security (warning: one short NSFW item in there!).

2) I'm currently putting all research papers and language-y thinking on hold for a few months. Instead I'm getting back to basics. All my side reading/hacking time is going into plowing through these two books: Introduction to Algorithms and Artificial Intelligence: A Modern Approach. I've generally in the past spent most of my time reading current research, because books get out of date so quickly. Well, not these two! They come pretty darn close to being timeless.

One quick brain teaser from the algorithms book: Everyone knows how to write a recursive algorithm to print an inorder traversal of a binary tree. Almost everyone knows how to convert it to an iterative algorithm using an explicit stack, too. But the book mentions that -- if your binary tree contains parent links as well as child links, and if you can test pointers for equality -- you can actually write an iterative algorithm to do an inorder traversal without keeping an explicit stack... in other words, an iterative algorithm that uses constant space (rather than space proportional to the depth of the tree). It took me about twenty minutes to figure it out. How about you?

3) One of the more interesting posts recently on good old Lambda the Ultimate was this post by Paul Snively asking whether syntactic or semantic theory is the way of the future. Most approaches to programming language theory historically have been largely syntactic, but there are a number of recent papers that take a purely semantic view.

While I'm still learning this field myself (and haven't spent nearly enough time on the basics -- Pierce's syntactically-oriented Types and Programming Languages is on my reading list, but so far I've only dabbled), it seems to me that semantic approaches have an intentional stance that might make them fundamentally more general. For example, this paper on semantic verification of a simple compiler makes the point that a typed assembly language program can only go wrong if it tries to treat a given memory location as being of an unsafe type, but that there might be possible values in that memory location which can be safely interpreted as other types without inconsistency.

This approach reminds me of the Logic of File Systems paper, in which file systems are modeled in terms of their beliefs about the contents of memory versus disk. It's a fascinating philosophical view, to think of programs as enacted, operational beliefs and to consistency check them on that basis. A program only goes wrong if its beliefs are inconsistent with the contents of the machine, as opposed to being inconsistent with its own source text (represented as base terms of the program). It's going to be fascinating to see how far the semantic approach can be pushed.

That's it for early January -- see you in about two weeks!

Me, Manifesto, GWT2007

Sigh, another two weeks gone by without a post. Still, that last post was a doozy, so cut me some slack, willya? Incidentally, my readership has increased by 50% in the last two weeks according to Feedburner. I am honored to have all of you paying attention to me, and I will try to be worthy of your eyeballs and neurons.

This post is going to be a bit of a catch-all: some about me, some about my last big-ass posting, and some about the GWT conference.

First, sorry I missed last week -- I got another cold (endemic in the wintertime with two young kids in the house), and my wife kicked into moving high gear. Yes, we're selling our house, for a wide variety of reasons I will discuss in personal email if you're interested enough to send me some. (Not in the comments, sorry!) We're shooting for having it on the market March 1, which means there is no time at all to waste. I'll be doing no hacking for the next two and a half months, that's an absolute given. I'll keep up the blogging, but weekly may be tough; bimonthly WILL happen if it kills me!

Which is all too bad, in a way, because there's plenty to do in hackland. My manifesto was rather well received. The comments on the post itself have a number of intriguing links. I also posted about it on Lambda the Ultimate, where it got a number of other fascinating responses. Thanks to all who engaged with it in either location. I am sorry I won't be able to touch it until March first at the earliest, but that's the nice thing about research -- interesting ideas don't go away!

I also wanted to give an update on the GWT conference. My talk was quite well received if the consensus speaker's feedback was anything to go by. I appreciate the appreciation, to say the least. I did hear that there was a significant fraction (over 50%?) of the audience that felt it was too technical. Evidently a substantial quorum of GWT2007 attendees were relatively unfamiliar with GWT at any level. I apologize to anyone who wasn't experienced enough to get the most out of my talk; I hope that you can find helpful material on the GWT site and/or any of the various GWT books. I've put my slides online for anyone interested. Evidently it'll be Youtubed sooner or later, but I've yet to get a date on that.

The last morning of the conference, we had a participatory breakfast session where Joel Webber and I led a discussion of declarative UI and declarative data binding in GWT. One thing that was clear from my talk is that there are a lot of people doing form-like web applications, and GWT underserves that population right now. Joel spent some time going over the declarative UI work he's doing; he specifically mentioned that various internal Google customers want him to ensure that you can write a GWT-XML document that lays out a GWT widget tree with HTML fragments mixed in almost arbitrarily. This seems like a win insofar as Joel's talk on performance specifically mentioned that innerHTML is your friend; the DOM is faster at inserting HTML fragments than it is at handling individual DOM element insertions. So everyone keep an eye on Joel's stuff as it hits the incubator.

I asked the table what kinds of form-data-binding approaches would be most useful to implement. The consensus seemed to be split. A number of people were familiar with the JSF-like structure of binding to backing beans and using expression language to specify the coupling from bean fields to the UI. I mentioned JSR 295 and various people expressed interst in that. There is a recent thread on the GWT contributors forum about some community work in this very area, which I look forward to investigating in depth (in early March! :-P ). Check that thread out if you want GWT to do this. I talk at more length there about a potential GWT EL parser.

There was one gentleman (whose card I got, and subsequently lost; please contact me again, sir!) who was a forceful advocate of an XForms-like approach; evidently XForms lets you declaratively specify data dependencies within your model, and allows you to lay out interactions witihn your UI purely in your interface specification. This was pretty much news to everyone at the table. I will definitely have to look into XForms now. However, it seems to me that a JSF-like, JSR-295-like bean-binding approach covers many of the basic use cases people want, and should certainly be a near-term project.

OK, that's it for this week. Happy, happy holidays to you all!

A Growable Language Manifesto

Warning: this is by far the largest and most action-packed post I've ever made. Grab a cup of [insert favored beverage here], sit back, and enjoy. If you get headcramp from reading this in narrow-column blog format, there's another full-screen version here -- but please return to this post to leave your comments!

I've posted recently about the dynamic versus static flamewar and about recent research in extensible languages. The more I think about these ideas, the more compelling they get. It seems clear to me that these ideas are synergistic and point in the direction of a new kind of programming environment -- one which could potentially offer the ease of dynamic languages, the safety of static languages, and an altogether new level of extensibility (both for enhancing the type system and for allowing safe metaprogramming.)

So I want to lay out a manifesto here for a growable programming language. Or perhaps it's more like a toolbox for language construction. Or perhaps it's a framework for experimenting with extensible syntax and extensible analysis. In any case, here is the vision. At the end, I include extensive references to the research that's inspired these ideas.

• A growable language should be opt-in. It must support a graceful spectrum of usage styles. A growable language will necessarily be multi-paradigmatic, since it will be extensible with features from various fields of programming. The language should implement a dynamically-typed core on which all static analysis is built, to allow programmers a straightforward and lightweight syntax for prototyping.


• A growable language should be increasingly powerful. It should support a rich and expanding variety of static analyses and dynamic checking, to give maximal benefit to the programmer who wishes to leverage these features. over time, as more program analyses become possible, a growable language should gracefully integrate them. A growable language must continually increase the expressive power of the programmer, both in terms of what the programmer can say and in terms of what the environment can help the programmer prove about their program. A growable language should have a powerful analysis framework as a foundational component, such that other analyses can share that basic capability; wherever possible, additional analyses should require only incremental effort by leveraging infrastructure already created.


• A growable language needs a declarative metalanguage. Current languages do not define inherent mechanisms for syntax extension and for type extension. The syntax and the type system are both baked into the language's compiler. A growable language needs to lift the specification level of the language itself to be both declarative and modularly defined, so that syntax and type analytics can both be expressed and implemented as layered extensions.


• A growable language needs partial typing. Certain analyses are necessarily incomplete or even undecidable. A growable language should permit such type systems, and should be able to fall back on dynamic typing whenever analysis is inconclusive. This lets programmers work freely without having to continually meet the demands of the type system, yet supports graceful type annotation to enhance static safety at the programmer's discretion. (Without partial typing, the opt-in goal cannot be met.) The language should ideally provide clear feedback as to when its analyses are conclusive or inconclusive, and ideally should identify the sources of inconclusiveness so the programmer can either annotate them appropriately or deliberately ignore them.


• A growable language needs layered types. A growable language should be able to extend itself with primitive types, dependent types (e.g. data-dependent subrange types), traits or other parametric or abstraction-based genericity mechanisms, and multiple flavors of type qualifiers. Integers should be as much of a language extension as non-null types, tainted types, or range types. A growable language requires an extensible subtype lattice.


• A growable language needs inferrable types. To avoid drowning in explicit type declarations, the language should be able to infer types wherever possible, and the programming environment should support controllable visibility for the inferred type information. Without inferred types and environmental support for controlling analysis visibility, a growable language cannot scale for users; being able to selectively ignore some or all of the (many) analyses is critical.


• A growable language needs explicit, optional type annotations. An extensible analysis framework will be able to infer or deduce a great deal about the actual behavior of the program. But the actual behavior of the program may or may not correspond to the programmer's intent. The programmer's explicit annotations express the programmer's expectations. A programmer might look at the analyzed annotations and make some of them explicit -- perhaps they reflect properties of the code that the programmer considers important after the fact, and that the programmer now wants to enforce. Or a programmer might add explicit annotations during development, such that the system can confirm they are valid and warn when they are violated. Explicit annotations at module boundaries -- whether programmer-generated or system-generated -- are likely to aid in separate compilation and in module documentation.


• A growable language must be efficiently implementable. As more language features are added -- more qualifiers, more types, more syntax -- the language must still be efficient and usable. This applies both to programs written in the language (which should have performance competitive at least with Java or the CLR) and to programming environments for the language. The latter requires aggressive attention to analytical optimizations and to multi-threaded analysis frameworks. As the language's analysis structure grows, the language's programming environments must be able to leverage multicore architectures to ensure consistent responsiveness for users. Moreover, the language should be continuously analyzing in the background; incremental feedback as the user edits should be available for all language features and extensions.


• A growable language must have a unified internal representation. Concrete syntax, abstract syntax, type and name bindings, type qualifier propagation, type parameterization, dependent range type constraints, and logical queries over the program's alias structure should all leverage a single internal representation of the program. This maximizes the reusability of internal language implementation code and ensures consistency in analytical derivations. Where multiple representations are necessary, the derivation rules must be clear and consistent.


• A growable language must promote static metaprogramming. Fully dynamic metaprogramming -- runtime extension of classes and objects with arbitrary code, or even unrestricted dynamic reflective access to arbitrary methods -- is almost impossible to analyze effectively. To give a growable language's extended type systems maximum exposure to the actual behavior of the code, static metaprogramming techniques must be definable, extensible, and compatible with the rest of the language's structure. One would hope that the very extensibility techniques that implement the language itself would be usable for static metaprogramming.


• A growable language must support diverse analyses. Some analyses are most naturally expressed as systems of recursive equations over an abstract syntax tree. Others can best be expressed as logical queries over a program's alias graph. Ideally these could both be expressed naturally in the metalanguage.


• A growable language must be analytically composable. This is likely the single most technically ambitious goal. Traditional compiler development involves subtle and explicit scheduling tradeoffs, layering multiple analyses through manual interleavings that can be fragile or non-optimal. A growable language with a declarative metalanguage needs an analysis engine that can automatically schedule multiple, potentially interleaved analyses, leveraging parallelism where possible to optimize non-dependent analyses. Achieving this goal will be immensely difficult, but proportionately valuable. Interestingly, here is where the metalanguage itself will require many of the same extensibility properties as the language it describes; meta-level closure -- implementing the metalanguage using the language itself -- will be a holy grail for this language design.

Is the above language even possible? Is it too much of a stretch -- particularly the "unified internal representation" and "analytically composable" goals? Maybe so. I'm definitely not an expert at programming language implementation; the only compiler I ever wrote was back in high school. So this may be ridiculously unrealistic in whole or in part. I welcome feedback on which areas of this manifesto are more or less plausible.

Overall, consider this my stab at answering Paul Graham's challenge to ponder the hundred-year language. Given current trends in programming language development, it seems that languages of the future will transcend being "languages" as we know them and will become more like unified environments for language creation and extension. Arguably, this vision has a lot in common with intentional programming, which doesn't bode well, since the intentional guys have been in stealth mode for almost fifteen years and nothing has publicly come of it. But that doesn't mean the general direction isn't interesting, any more than the slow progress of Chandler means that a unified and flexible personal information manager isn't worth pursuing.

I promised references. Here they are:

• opt-in -- Gilad Bracha's pluggable type systems paper is the origin of this goal. Bracha forcefully posits that static type systems are all necessarily incomplete and that dynamically typed languages have necessary flexibility. Meijer makes a similar point in his static where possible, dynamic where necessary paper. I'm not clear that Bracha's extreme view -- that all static analysis must be kept out of the language kernel -- is the correct one, given the potential performance cost, but I suppose RPython provides an encouraging counterpoint.


• increasingly powerful -- There are increasingly many varieties of static analysis being developed primarily for Java. One recent paper on http://www.cs.umd.edu/~jfoster/papers/oopsla07-uno.pdf points out that its framework could straightforwardly be implemented on top of other analyses with similar intraprocedural resolution. The BDDBDDB framework has already been used for implementing taint analysis, and the JastAdd system for non-null Java type inference. In general it seems there is a lot of opportunity for shared infrastructure here. Also note that support for excellent error messages and great visibility into analysis results (and analysis failures) will be critical for usability. See Grimm's paper titled Systems Need Languages Need Systems for some forceful advocacy here.


• a defining metalanguage -- Some good examples of metalanguages for syntactic language description are the OMeta pattern-matching language for executable grammars, Gilad's executable grammars in NewSpeak, and the Rats! extensible parsing system. A good example of an extensible language for static analysis is the JastAdd extensible Java compiler with its support for defining rewritable circular reference-attributed grammars... they implemented Java 1.5 generics as a modular declarative compiler extension, which proves their point to me, anyway!


• partial typing -- The two best examples of this that I know of are the gradual typing work of Siek and Taha, and the hybrid typing for undecidable type systems work of Flanagan, Freund, et al. In both cases, a static type system is enhanced with a generalized type (named Dynamic or "?"), which is inferred to be a more specific static type where possible, and otherwise cast at runtime to preserve dynamic type safety.


• layered types -- The already-mentioned JastAdd system is perhaps the best example of a structure which permits layering additional analyses. The extensible Java compiler Polyglot is another.


• inferrable types -- My original thinking about this entire line of research originated in a blog post from a couple of months ago where I realized that some implementations of type qualifiers -- for example, a "tainted" type qualifier in C++ -- would ripple through the whole program due to mandatory explicit static typing everywhere. It's noteworthy that many type qualifier analyses for Java are not based on explicit syntax. For example, the taint analysis based on the BDDBDDB framework does not require explicit propagation of tainted or untainted declarations, yet it derives such information throughout the program's structure. An environment which made the results of that analysis visible -- and traceable -- at every program point would let the programmer see the flow of tainted values without having to explicitly declare them.


• explicit, optional type annotations -- Programmers must also be able to add explicit qualifiers, since the programmer's intent may or may not match the analysis; the analysis may be incomplete and the programmer needs to provide more information, or the analysis may be consistent and the programmer wants to declare that they confirm it and want it to be enforced at that location (e.g. if the program changes such that the property is no longer true there, the language would signal an error). The programmer's explicit intent and the analyser's implicit understanding should be able to be flexibly cross-checked. I'm not aware of any inference systems that support this fully; they seem to be either purely inference-based (e.g. JQual) or purely annotation-based (e.g. a C++-based type qualifier system discussed in the "Extending Type Systems in a Library" paper from LCSD '06).


• efficiently implementable -- This is obviously enormously difficult, insofar as analyses can in general be interdependent. There is a great tension between layering analyses (for separability) and weaving them (for mutual dependence and synergy). See the "analytically composable" goal below. In general, I wouldn't be surprised if aggressive parallelization of a language analysis / compilation framework required software transactions to support optimistic and incremental analysis by multiple threads.


• a unified internal representation -- I mean something along the lines of Grimm's declarative extensible syntax trees, a concept proven by his weaving of Java and C typechecking into a single system. The JastAdd framework is another example; there is no separate symbol table in JastAdd, since name bindings become reference links in the abstract syntax tree (which is really more of an abstract syntax graph). Note that JastAdd's own declarative language for extending the syntax tree is fundamentally similar to open classes, in that subsequent extensions can directly modify the structure of already-defined syntax node classes. This seems to inhibit modular development of language extensions, but modular language extension development is really hard anyway.


• promote static metaprogramming -- This goal is about ensuring the entire program text remains analyzable, and about permitting domain-specific languages to be implemented in the same structure used for extending the base language. See OMeta's SQL extensions or C# 2.0's language-integrated queries which reify some expressions as syntax trees visible to the runtime system. The Google Web Toolkit's support for extensible code generation is another example, as is the RapidMind system for creating parallel compute kernels from C++ code. Finally, there's the RPython system which creates a "metaprogramming startup phase" for Python programs, followed by a static compilation phase yielding 100x speedups. Interestingly, this whole goal contradicts Paul Graham's 2001-era view that "true macro systems aren't compatible with static type systems."


• support diverse analyses -- The best two already-cited examples here are the JastADD grammars formalism and the BDDBDDB Datalog-based analysis specification. These are radically different but potentially very synergistic. I'd be fascinated to see whether there's some deeper commonality between them....


• analytically composable -- The JastADD framework seems the best example of a declarative structure that supports automatic weaving of multiple analyses. For evidence to this effect, consider that the JastADD folks claim that the Polyglot team is reimplementing their framework in JastADD to avoid the difficulties of scheduling dozens of analysis passes.

I plan to start experimenting with some prototypes of an Eclipse plugin for an extensible language framework along these lines, likely starting with something much like OMeta and extending it with a JastADD-like rewritable grammar formalism. This will be open source all the way. I would enthusiastically welcome all pointers to similar projects, all interest in helping with such a framework, and all critical comments on all or part of this manifesto!

(Disclaimer: our family will also be moving out of our house in the next three months, so progress may well be slow :-)

GWT presentation tomorrow!

I've been working on a truly monster blog post, nothing short of a manifesto for a growable programming language. It's about four pages long now and roughly 90% complete. All I have to do is Google up the two dozen reference links.

But I can't quite get to it tonight, because tomorrow is my presentation at the GWT conference and I've been tweaking my slides semi-compulsively.

So, hopefully I'll see several of you tomorrow at the conference, and stay tuned later this week for my Big Fat Language Rant! Your patience is very deeply appreciated.

Gaming, Turkey, and Burnout

(Warning: relatively low technical content ahead!)

Rats, missed another blog-posting week here. A week ago I finally got my GWT conference presentation done. I was rather nervous about whether I was hitting the right technical level, so I mailed it to a few GWT team members, and Bruce Johnson (the team lead) wrote back and said, basically, "It's perfect." Thanks, Bruce! Eased my mind tremendously. The conference is coming up next week.

Then on Tuesday, Mass Effect shipped, and I was instantly lost in space. I've gone back and forth on whether to talk about gaming here, but this title pushed me over the edge. I've been a computer gamer ever since I've been a computer user -- my very first experience with a computer was playing Spacewar on a PLATO timesharing terminal at my friend's father's college. And gaming has become a true lifelong hobby. Mass Effect is a great example of why that is.

Programmers inherently love systems. A truly intrinsically motivated programmer will spend hours thinking about how something fits together, and more hours tinkering with it and seeing what happens. A great game also has a systemic internal structure that rewards tinkering and exploration. So it's natural that so many programmers are gamers.

Moreover, many programmers are thrilled by advances in technology. The more powerful our computers become, the more we can do with them. And computer games are definitely the most widely visible hardware-pushing applications. Just take a look at some of these screenshots. A $280 XBox 360 can now do real-time facial animation that looks a lot better than ANYTHING being done five years ago (real-time or pre-rendered). And it qualitatively changes the nature of the game, when your character and the zany aliens they're talking to both have facial emotions and lip-syncing that are so much closer to realistic that you can almost lose yourself in the illusion. I'm not claiming that Bioware's crossed the uncanny valley just yet, but they've definitely taken huge strides in that direction, and they've hooked me but good.

I expect to be a gamer for the rest of my life, since games just keep getting cooler and cooler as hardware gets more and more powerful and we learn more about what to do with it. It's a perfect hobby for a systems-oriented, game-addicted technophile.

So Mass Effect took over my after-the-family's-asleep life, and stole my blogging cycles last week. Thanksgiving was also pretty hectic -- we cooked an 18-pound turkey for our church get-together, which took me all day while my wife juggled our three-month-old and our (almost-)three-year-old. That left us pretty wrecked and we laid low the rest of the weekend.

Meanwhile, on the hacking front, I have continued to feel blocked by the whole Seam 2 broke my code issue. Actually, technically, it's that Seam 2 broke the G4JSF code. That code was originally written by the Ajax4JSF team, but they have abandoned it. So the question for me is, how motivated am I to fix it? (And, potentially, to continue fixing it as Seam, JSF, and GWT continue to evolve?)

I originally started on this whole Seam / GWT / JSF project because I had ambitions to create a peer-to-peer distributed blogging system. I made a lot of progress on that system (at least as far as creating a Seam-based model for representing version trees with Java persistence, a la Mercurial). Then I wanted to start on the UI. Which led me to GWT, and the realization that the existing G4JSF library didn't couple gracefully with GWT RPC. So I patched GWT, and then G4JSF, and that led me to presenting to the GWT team at JavaOne last year, which then got me the opportunity to speak at the GWT conference next week. All of that was quite unexpected and quite appreciated -- particularly the speaking opportunity!

BUT, going back to my original project, the peer-to-peer distributed object system lost its mojo somewhere over the last year. It led me down the GWT / Seam / JSF path, which was really interesting and connected me to the open source world like never before... but somehow the journey became the destination, and the original goal no longer feels as interesting. Frankly, I'm not feeling very enthusiastic about being the sole owner of the G4JSF code base, given the evident cost of keeping it current and given the lack of other support from the JSF community. Maybe having a second baby also cut my energy level.

In order to avoid burnout I need to work on the projects that are most interesting to me, which right now is looking like prototyping some extensible programming language ideas that have been burning a hole in my brain for the last two months.

So, I'm going to set aside the G4JSF work and I'm going to leave the Seam/GWT/JSF integration project in its current state. I am more than willing to work with anyone (at Red Hat or elsewhere) who wants to pick it up again and fix it up to work with Seam 2 (and JSF 2 when it comes along), but I can't drive it further on my own. Anyone who was using that integration library and who is interested in fixing it, feel free to email me (rjellinghaus at gmail dot com).

This blog will shift focus away from Seam/JSF and towards programming language research and the experiments I'm doing. Hopefully that'll still be interesting to my loyal readers -- I'll do my damnedest to make it so! Because I'll tell you one thing, it's pretty fascinating to me :-)

Android hits the fan

Unless you've been buried under a boulder, you've heard about Android. It's nice to know what my secretive Google mobile JVM guru friend has been working on all this time :-)

The Android forum is awash in C / C++ developers ranting about how lame Android is because it doesn't support raw access to the hardware. It's too bad, really. I feel for them, and I agree: Android apps are going to be slow and clunky compared to native apps.

But Google's making a play to build a whole new kind of mobile ecosystem here. Google's betting on increasing mobile CPU power (certainly an excellent bet), and Google knows that if Android develops a personal-computer-like reputation for flakiness, it will fail and fail bigtime. I would argue that a big reason no mobile platform has really taken off yet (besides crazy licensing costs) is that native apps are simply flaky, and the more of them you run, the flakier your hardware gets. Since Android is trying to greatly increase the hardware diversity of Android devices, allowing raw native access combined with open developer access would rapidly drive the stability of the system to zero.

Native developers hate to hear this, because they spend their lives tuning for performance and chasing crash bugs. I'm sure many of them do write good solid apps. But I'm also sure that making native code crash-proof, especially across a wide spectrum of hardware, is very, very hard to do. And if you want to throw your platform open to anyone who wants to ship an app for it, you're guaranteed that many if not most of those people will lack the uber native skillz to achieve that kind of cross-platform stability.

So HOORAY GOOGLE! for making Android a fully managed platform! Note also that Microsoft sees the writing on the wall; they're working on a fully managed operating system, for crying out loud.

End rant. The most interesting thing I've yet learned about Android is that it is fundamentally trying to end-run around Sun's IP restrictions on Java ME. Stefano Mazzocchi breaks it down in exemplary fashion. Super cool! It's going to be really strange to see Sun and Google at each other's throats, but given how close the two companies are, and given how heavily Android leverages Java-the-language while totally subverting Java-the-runtime, AND given how anti-patent-war Sun is trying to be, I hope for some kind of peaceful reconciliation there. Microsoft, on the other hand, will go apeshit. Let the fireworks begin!