Tuesday, June 26, 2007

Rhino on Rails

What a day. Apparently getting John Lam'd is worse than getting Slashdotted. My team has been laughing at me all day; we have no idea how I get into messes like this.

Rather than reply individually to the crush of email, I guess I'll just do a bulk update.

But first: is anyone else as nonplussed as I am that of all the amazing things that were discussed in Foo Camp, my little improvised talk -- complete with a picture of me that for some reason looks as if I'd just crawled out of a tent 20 minutes prior, hung over and disoriented and wondering why I was in a field in the middle of Sebastopol, CA, only to find that the night before I'd apparently I'd signed up to give a 10am talk -- winds up being splashed all over everyone's blog, not to mention my inbox?

I mean, Foo Camp was truly amazing. There were just insanely brilliant people there, all presenting slick, well-prepared talks and roundtable discussions on vitally important topics such as improving democracy through technology, measuring the health of social networks, addictive collaboration in programming competitions, and the future of Open Source software. And here I was making the technological equivalent of armpit noises in an attempt to cover my complete lack of preparation, not to mention lack of a shower, and somehow that's all I hear about when I get back.


So here's the deal. I work at Google. No, let me put it a bit more accurately: I am privileged to work at Google. It's a privilege. It's something that I have no expectations about. If you were a slovenly teenager with a rich uncle who for some reason liked you and let you play golf at his $250k-per-year membership country club for free whenever you liked, you couldn't have lower expectations than I do about how long it might last. Not because my rich uncle won't last, mind you, but because teenagers just have a way of ruining situations like that. You just enjoy it while you can.

In addition to working at Google, I also happen (independently) to have this ridiculously over-subscribed blog with almost no actual content and far too many lowbrow booger jokes. Sometimes people seem to get a little confused, and think that maybe I (the teenager) have some sort of influence with my magnanimous uncle Google, or that I speak on his behalf, or some other such nonsense.

Let's get real for a sec, folks. I'm nobody at Google. I'm a very comfy, very small fish in a sea full of large, toothy sea creatures, if I may (*ahem*) be permitted to invest the metaphor with its most flattering possible meaning. And I certainly don't speak for anyone but myself.

With that said, I figured I'd give you the outline of my Foo Camp talk, which will hopefully answer most of the questions that have been flying around since I got back.

By way of background, I'm on a really cool project in Kirkland -- one that I can't talk about, alas, except to say that I think it's the veritable cat's meow. But I can't talk about it. So it goes.

Among other things, this meowing project requires a snazzy, Ajax-enabled web frontend. It's part of a larger herd of projects purring along on Java infrastructure, so our project also has to run on the JVM.

One of the (hundreds of) cool things about working for Google is that they let teams experiment, as long as it's done within certain broad and well-defined boundaries. One of the fences in this big playground is your choice of programming language. You have to play inside the fence defined by C++, Java, Python, and JavaScript.

My project's playground is actually a bit smaller than that, since it has to run on the JVM. But that's still a pretty big playground, and trying out (or creating) new web frameworks is totally fair game for experimentation, even if you're in a relatively high-profile domain.

Another boundary we have to play within is software engineering, including unit testing, documentation, code refactoring, security, scalability, internationalization, and a host of other non-negotiable criteria.

I hope you're beginning to see, at least faintly, why I love working at Google. It's because the code base is clean. And anything that takes more than a week of effort requires a design document, with specific sections that have to be filled out, and with feedback from primary and secondary reviewers of your choice. The net result is that for any significant piece of code at Google, you can find almost a whole book about it internally, and a well-written one at that.

I've never seen anything like it before, to be honest. I don't think you can get that kind of software-engineering discipline without doing it right from the start, and creating a culture that enforces and reinforces that discipline as the organization grows.

Whatever. I digress. My point is that as long as you play inside the fences, and you don't foolishly disregard the wealth of infrastructure for distributed computing that Google offers, then you have a great deal of leeway for experimenting with new approaches.

As it happens, I kinda like Rails. I like Ruby, too, independent of Rails. But for making web pages, Rails is the nicest thing I've used. And given the surprising number of titles available about our heroine Rails and her mute little woodland creature sidekicks Prototype and Scriptaculous, not to mention the vast number of Rails clones out there in other languages, I'd say DHH was really on to something unique and significant when he created it. Kudos.

Ruby is on the other side of the fence. We can see it over there, rolling around in the grass and pretending it's having fun, hoping we'll invite it in. Sometimes it even comes snuffling right up to the edge of our playground, and we have to throw a giant knife switch to engage the high-voltage coils, and there's a loud hum while Ruby's hair stands all the way up, and it backs away slowly. It tried digging a hole once, but... well, you get the idea.

The thing is, Google's decision to limit the number of languages allowed for production work is actually pretty smart. It's one of those things that might sting for a few weeks after you start (and not to put too fine a point on it, but why aren't you sending me your resume?), and if you're a bumbling fool like me it might take you a little longer to figure it out. But programming languages have a core of standard functionality that everyone knows, followed by a long tail of murky semantics that become increasingly difficult to figure out, especially for dynamic languages with no actual spec like Perl, Python, Ruby and their ilk. Google very prudently keeps the number of languages as small as practical, so that we can build up large groups of experts on the semantics of the languages we've chosen.

It's also to cut down on the combinatorial explosion of components required for language interoperability -- a huge tax at other companies I've been at, a tax that Google has managed, by and large, to minimize.

Google has set up an environment that makes it pretty easy for people to transfer between groups, and even between sites. You have to be a grown-up about it, of course, and not ditch your team during some critical crunch time. But provided you exercise mature judgment in the matter, you can pretty much switch teams whenever you want, and it doesn't cause the company to grind to a halt, as such a policy would at other places I've worked or visited.

It's NOT easy to set up that kind of environment, and it's certainly not easy to make it scale. There are many ingredients to the full recipe, far beyond the scope of this little blog entry, but one of the keys is to make the code base homogeneous across projects, teams, sites, and even (to the maximum extent practical) languages. That helps minimize the learning curve, and thus the resistance, when people are moving between groups.

So now you have all the key factors that went into my decision to port Ruby on Rails. I like Rails, and wanted to use it on our fancy new project in Kirkland. I needed to be on the JVM for interoperability with the rest of our code base. (Take my word on this one -- it's not something I could have solved by RPC calls; I needed to be running on the JVM itself for this.) Being on the JVM rules out C++ and (native) Python.

My only choices, then, were Java, Jython and Mozilla Rhino, which is an implementation of server-side JavaScript on the JVM.

Looking at the Rails APIs, which typically pass around hash literals as parameters, it didn't seem like Java was going to be a particularly good match. Ruby has no method overloading, and both Ruby and Rails have all sorts of conventions for passing varargs or block (function) parameters. Java's different enough from Ruby that the impedance mismatch might have killed the effort, so I decided to stick with a dynamic language.

Jython seemed like the obvious choice at first, except that it hasn't had much momentum since around 2001. It used to be arguably the best non-Java JVM language around; Jim Hugunin did an amazing job with it. Unfortunately it's had almost no love in the past six years, and it's now lagging the Python spec by several major versions (2.2 vs. soon-to-be 2.6).

Rhino, in contrast, has a great deal of momentum. It's been around even longer than Jython; it began life as a port of the SpiderMonkey (Netscape/Mozilla) JavaScript C engine, and it was written with an eye for performance. The Rhino code base reads almost like C code: it avoids allocation and does as much as possible with jump tables to avoid the overhead of virtual method lookups. It has two code paths: a bytecode interpreter that runs in a tight loop, and an optimizing Java bytecode compiler that turns many expensive-ish JavaScript property lookups into Java local or instance-variable lookups. It's a pretty serious piece of software.

When you start digging into Rhino, you find unexpected depth. JavaScript (unlike Perl, Python and Ruby, at least today) actually has a real specification, and Rhino follows it rigorously, aiming for complete SpiderMonkey compatibility within the bounds allowed by the different language platforms. Rhino also offers rich configurability, has well-defined multi-threading semantics, has a full set of hooks for debugging and profiling, and much more besides. There's a lot under the hood.

Oh, and Sun is now bundling it with the JDK; it's javax.script in Java 6. With that kind of endorsement it would have been hard to justify using anything else, even if some language other than Jython or JavaScript had been up for consideration.

Of course, the downside is that it's JavaScript, right?

JavaScript is admittedly a bit quirky, but keep in mind that this is server-side JavaScript we're talking about, and on the JVM to boot. So libraries aren't an issue; there are plenty. And browser incompatibilities aren't an issue either - there's only one Rhino, and it works as advertised. But we've been able to go a step further and make some fundamental extensions that have made it almost Ruby-esque.

As just one example, in client-side JavaScript there's currently no way to define a property that's non-enumerable, which implies that you can't add new functions or properties to Object.prototype, since they'll suddenly start showing up in your object literals (which are JavaScript's hashes, more or less). But in Rhino you just create a Java method that calls into the Rhino runtime to define non-enumerable properties, and you can extend Object.prototype to your heart's content. So we went wild, and added pretty much every interesting Ruby (and Python) built-in method on the built-in classes (Object, String, Array and the like).

JavaScript has also begun evolving again after a long hiatus, and its 1.7 features in Firefox 2, mostly borrowed from Python, are really pretty snazzy.

Rhino doesn't have those features yet, so we started a 20% project to add them, and people all over the company are signing up to help.

Did I mention how cool it is to work for Google? Well, I mentioned it a few months back to Norris Boyd, the original author of Rhino, and he thought it sounded like a fine idea. Now that he works for Google too, the Rhino 20% work is charging along like a large, gray, scaly African land-beast, if I do say so myself.

And then there's JavaScript 2.0, but the Foo Camp crowd heckled me mercilessly when I brought that up, so we didn't get to talk about it much. That's what I get...

Last thing on the menu today: I'll address the Rails port briefly, since I know there are questions. There really isn't all that much to say, though. Ports are kinda boring when you get right down to it.

I ported essentially all of ActionView, ActionController and Railties, plus a teeny bit of ActiveRecord, although for the most part we were already constrained in how we talk to our backends. Long-term, I think the story is going to be Hibernate.

I didn't use a code generator, since I've never met one that I liked. I just used Good Ole Emacs and a whole lot of keyboard macros. Initially I started by trying to do my own implementations of the Rails "spec", as it were, based on the Pickaxe book, but I pretty quickly found that Rails is its own most succinct implementation, with very few exceptions. (I think the routing engine could be cleaner, and there are a few spots here and there where the metaprogramming was a bit gratuitous, but otherwise the Rails code base is very clean and remarkably well-tested.)

We did some extensions here and there for security, performance, and internationalization support, but I'm guessing I shouldn't talk too much about them just yet. We've also been building some nice tools support, including spiffy debuggers and other IDE functionality for Eclipse and Emacs. But we've also tried to stay as Rails-compatible as practical, so that new developers on our team (in case you were thinking of applying, hint hint) can get started just by picking up a Rails book.

We've talked about open-sourcing our "Rhino on Rails", but so far it's been no more than idle chit-chat. For one thing, work on the framework plays second fiddle to work on the actual application, so it's progressing slowly, mostly as 20% work. For another, we're dependent on various other Google infrastructure components that are themselves in the process of being open-sourced, although I don't know if any of them have been announced yet.

The real key, though, is watching to see what happens in the Rails-ish web framework space on the JVM. There are plenty of other Rails clones out there in varying stages of maturity, including JRuby on Rails, Grails, Phobos, TrimPath, and probably half a dozen others.

If one of them emerges over the next couple of years as the dominant player, and it meets Google's internal quality bar for security, performance, scalability, internationalization support, and so on, then we'd be fools not to consider the possibility of migrating to it.

But platforms (like languages and IDEs) take years to flesh out, and they evolve fairly glacially, whether as open-source or as home-grown internal projects. They need teams of users to build entire applications with them, and during each feedback cycle the framework (or IDE, or language) gets saddled with a few more years of work.

I have absolutely no idea how it's all going to play out. All I know is that Rhino on Rails is working out very nicely for our little team up in Kirkland, and that curious folks at other sites inside Google are keeping an eye on it to see whether it turns into something cool enough to try out.

And that's about it. Did I forget anything? If so, I'm sure someone will let me know, probably by tying a nice note to a nice red brick and hurling it through my window. You should see the email I get sometimes.

I promise to give you a status update in exactly one year, provided someone reminds me. I can almost guarantee that at our current rate of framework progress, nothing interesting or newsworthy will happen to our Rails clone between now and then.

I encourage you to check the Rhino site if you want to be looped in on (or participate in) the Rhino enhancements. It's fun work, and they'd love to have your help.

And with that, I'm signing off to spend a little time working on my super-secret home project that should be ready for release later this year. This one's a bona-fide magic trick, which of course means I can't give it away. Let's just call it "NBE" for now, shall we? Yes, I think NBE sums it up nicely.

Betcha can't wait.

Thursday, June 21, 2007

Rich Programmer Food

The Olive Garden: it's where poor people go to eat rich people food.
— Dave Yegge

This is another one of those blog topics I've been sitting on for way too long, trying to find a polite way of saying something fundamentally impolite. I don't see a way to do it. So: you stand a good chance of being offended by this blog entry. (Hey, just don't say I didn't warn ya.)

I've turned off blog comments, incidentally, because clever evil people have figured out how to beat captchas using non-algorithmic approaches, and I don't have the bandwidth to police spam myself. Sorry.

I don't want to give you a heart attack, so I'm going to give you the gentle-yet-insistent executive summary right up front. If you can make it through my executive summary without a significant increase in heart rate, then you're probably OK. Otherwise, you might consider drinking heavily before reading this, just like people did in the old movies when they needed their leg sawed off. That's what I'm doing, in any case (drinking, that is, not sawing my leg off).

Gentle, yet insistent executive summary: If you don't know how compilers work, then you don't know how computers work. If you're not 100% sure whether you know how compilers work, then you don't know how they work.

You have to know you know, you know.

In fact, Compiler Construction is, in my own humble and probably embarrassingly wrong opinion, the second most important CS class you can take in an undergraduate computer science program.

Because every deep-dive I've attempted on this topic over the past year or so has failed utterly at convincing me after I sobered up, I'm going to stage this production as a, erm, stage production, with N glorious, er, parts, separated by intermissions. So without further ado...

Actually, that sounds like way too much work. So I'll just rant. That's what you paid good money to hear anyway, right? I promise to make so much fun of other people that when I make fun of you, you'll hardly notice.

Cots and Beards

I took compilers in school. Yup. Sure did. From Professor David Notkin at the University of Washington, circa late 1991 or thereabouts.

Guess what grade I got? I got a zero. As in, 0.0. That was my final grade, on my transcript. That's what happens at the University of Washington when you get an Incomplete and don't take the necessary corrective actions (which I've never figured out, by the way.) After some time elapses, it turns into a zero.

You can get an Incomplete in various different legitimate ways, including my way, which was to be an ill-considered beef-witted mooncalf who takes the course past the drop-date and then decides not to finish it because he doesn't feel like it. I earned that Incomplete, I tell you.

I took Compilers again a few years later. I was in college for a long time, because I got hired on as a full-time employee by Geoworks about a year before I graduated (among other reasons), and it wound up extending my graduation for several years.

Don't do that, by the way. It's really hard to finish when you're working full-time. Get your degree, then go to work. All the more so if you're a Ph.D. candidate within any reach of finishing. You don't want to be just another ABD for the rest of your life. Even if you're not sad, per se, we'll be sad for you.

I got a decent grade in Compilers the second time around. I actually understood compilers at a reasonably superficial level the first time, and not too badly the second time. What I failed to grasp for many more years, and I'm telling you this to save you that pain, is why compilers actually matter in the first place.

Here's what I thought when I took it back in 1991. See if it sounds familiar. I thought: a compiler is a tool that takes my program, after whining about it a lot, and turns it into computer-speak. If you want to write programs, then a compiler is just one of those things you need. You need a computer, a keyboard, an account maybe, a compiler, an editor, optionally a debugger, and you're good to go. You know how to Program. You're a Programmer. Now you just need to learn APIs and stuff.

Whenever I gave even a moment's thought to whether I needed to learn compilers, I'd think: I would need to know how compilers work in one of two scenarios. The first scenario is that I go work at Microsoft and somehow wind up in the Visual C++ group. Then I'd need to know how compilers work. The second scenario is that the urge suddenly comes upon me to grow a long beard and stop showering and make a pilgrimage to MIT where I beg Richard Stallman to let me live in a cot in some hallway and work on GCC with him like some sort of Jesuit vagabond.

Both scenarios seemed pretty unlikely to me at the time, although if push came to shove, a cot and beard didn't seem all that bad compared to working at Microsoft.

By the way, my brother Dave was at a party once, long ago, that had more than its fair share of Microsoft people, and apparently there was some windbag there bragging loudly (this is a party, mind you) that he had 15 of the world's best compiler writers working for him in the Visual C++ group. I told Dave: "wow, I didn't realize Richard Stallman worked at Microsoft", and Dave was bummed that he hadn't thought of that particular riposte at the time. So it goes.

The sad part about that story is that I've found myself occasionally wanting to brag that I work with some of the best compiler writers in the world at Google. Please, I beg you: if you ever find me at a party bragging about the compiler writers I work with, have pity on us all and shoot me dead on the spot. Hell, bash me over the head with a lamp if you have to.

Anyway, now you know what I thought of compilers in 1991. Why I even took the class is beyond me. But I didn't finish. And the second time around -- which I only did because I felt bad about the first time around: not from the zero, but from having let David Notkin down -- I only took the time to understand the material well enough to finish the course with a decent grade.

I was by no means atypical. If you're a CS student and you love compilers (which, anecdotally, often means you're in the top 5% of computer science students in your class worldwide), then I salute you. I bet I'm way better at Nethack than you are. The reality is that most programmers are just like I was, and I can't really fault 'em for that.

Before I leave this sordid story forever, I feel obliged to point out that it's partly academia's fault. Except for type systems research, which is being treated with approximately the same scholarly caution and restraint as Arthur's Grail Quest, compilers have been out of favor in academia for a long time. So schools don't do a good job at marketing compilers, and giving them due credit as a critical topic in their own right. It's a sad fact that most schools don't require you to take compilers in order to graduate with a Computer Science degree.


How Would You Solve...

You're a programmer, right? OK, I'll propose some programming situations for you, and you tell me how you'd solve them.

Situation 1: you're doing a bunch of Java programming, and your company has explicit and non-negotiable guidelines as to how to format your Java code, down to every last imaginable detail. How do you configure your editor to auto-format your code according to the style guide?

Situation 2: your company does a lot of Ajax stuff, and your JavaScript code base is growing almost as fast as your other code. You decide to start using jsdoc, a javadoc pseudoclone for JavaScript, to document your functions in a way that permits automated doc extraction. You discover that jsdoc is a miserable sod of a Perl script that seg faults on about 50% of your code base, and -- bear with me here -- you've vowed never to write another line of Perl, because, well, it's Perl. Pick your favorite reason. How do you write your own jsdoc extractor, bearing in mind that it will need to do at least a cursory parse of the JavaScript code itself?

Situation 3: your company has a massive C++ code base, the result of many years of hard work by dozens, if not hundreds, of engineers. You discover that the code needs to be refactored in a nontrivial way, e.g. to upgrade from 32-bit to 64-bit, or to change the way you do your database transactions, or (God help you) because you're upgrading your C++ compiler and the syntax and semantics have all changed again. You're tasked with fixing it. What do you do?

Situation 4: someone at your company writes a bitchin' new web based code review tool. Everyone switches to it. You realize, after using it for a while, that you miss having it syntax-highlight the source code for you. You don't have much time, but you might be able to afford a week or so, part-time, to make it happen. How do you do it? (Let's say your company uses five to eight languages for 99% of their code.)

Situation 5: an unexpected and slightly bizarre new requirement arises on your current project: you need to be able to use a new kind of hardware router. Maybe all your Web 2.0 stuff is screwing up your border routers or network bandwidth monitors, who knows. All you know is the sysops and network engineers are telling you that you need to talk to these new routers directly. The routers have IP addresses, a telnet interface, and a proprietary command language. You send commands, and they send responses. Each command has its own syntax for its arguments, and you need to parse the responses (which have no documented format, but you can reverse-engineer it) to look for certain patterns, in order to set them in the right state for your wacky uploads or downloads. What tool do you use?

Situation 6: your company's projects are starting to slip. The engineers are all smart, and they are all using the latest and greatest state-of-the-art Agile Object-Oriented Software Engineering Principles and programming languages. They are utterly blameless. However, for some reason your code base is getting so complex that project estimates are going wildly awry. Simple tasks seem to take forever. The engineers begin talking about a redesign. This is the Nth such redesign they have gone through in the past five years, but this is going to be the big one that fixes everything. What color slips of paper do you give them? Woah, ahem, sorry, I mean how do you ensure their success this time around?

Situation 7: you have a small, lightweight startup company filled with cool young people with long blue-tinted hair and nose rings and tongue rivets and hip black clothes and iphones and whatever the hell else young people have these days. You use Ruby on Rails for your site, and it scales just fine for your number of visitors. (You've never bothered to measure whether your number of visitors is a function of your site's latency, because it's never occurred to you to wonder.) You read about the latest horrible godawful Rails security vulnerability, under which users can make arbitrary SEC filings on behalf of your company by sending properly formatted GET requests to your public site. You download the new version and read the unit test code to figure out what the actual vulnerability is, since they didn't say, and you determine that you need to make a set of nontrivial code changes to remove a particular (and mysteriously non-greppable) idiom from your code base, replacing it by mechanical transformation to a different idiom. How do you do it?

Situation 8: some drunken blogger presents you with seven weird situations and asks you to speculate about what they have in common. Do you already know the answer?

Here are the answers. What, you thought these were rhetorical?

Scenario #1: you lobby your company to change the style guide to match whatever Eclipse does by default.

Scenario #2: you post to the jsdoc mailing list and ask if anyone else has had this problem. Several people say they have, and the issue pretty much dies right then and there.

Scenario #3: You quit. Duh. You knew that was the answer before you reached the first comma.

Scenario #4: Tough it out. Colors are for weenies. Or maybe you wire up GNU Source Highlight, which covers languages all the way from Fortran to Ada, and you live with the broken highlighting it provides.

Scenario #5: Perl. It's a swiss army knife. You can use it to sidestep this problem with honor, by disemboweling yourself.

Scenario #6: Pink.

Scenario #7: Fix it by hand. Hell, you only have about 10k lines of code for your whole site. It's Rails, fer cryin' out loud. This was a trick question.

Scenario #8: Yes. You skim until the end of the blog, just to find out what the first-most-important CS class is. Stevey's well known for shaggy-dog jokes like this.

And there you have it. You're now equipped to deal with just about every programming situation you could come across. So you obviously don't need to know compilers.

How Compilers Work

Here are some real-life answers from real-life candidates, with real-life Ph.D.s in Computer Science, when asked how compilers work.

Real Candidate #1: "Oh! They, ah, um, scan your program one line at a time and convert each line to assembly language."

Real Candidate #2: "Compilers check errors in your program and, ah, tell you if you had bad syntax. That's all I remember."

Real Candidate #3: "I... <3-minute pause>... I don't know."

Real Candidate #4: "They preprocess your program and convert #DEFINE statements into code, and then, um, emit machine code."

That's pretty much all the detail you'll ever get out of 75% of all interview candidates, because, hey, they don't want to work in a hallway at MIT. Can you blame them?

Only about 3% to 5% of all interview candidates (and that's being optimistic) can tell you any details about how a compiler works. The rest will do some handwaving about lex and yacc and code generation, maybe.

I told you your heart rate would go up. Didn't I?

Take a deep breath.

Why Compilers Matter, Part 1

The first reason Compiler Construction is such an important CS course is that it brings together, in a very concrete way, almost everything you learned before you took the course.

You can't fully understand how compilers work without knowing machine architecture, because compilers emit machine code. It's more than just instructions; compilers need to understand how the underlying machine actually operates in order to translate your source code efficiently.

Incidentally, "machines" are just about anything that can do computations. Perl is a machine. Your OS is a machine. Emacs is a machine. If you could prove your washing machine is Turing complete, then you could write a compiler that executes C code on it.

But you knew that already.

You can't understand how modern compilers work without knowing how Operating Systems work, because no self-respecting machine these days runs without an operating system. The OS interface forms part of the target machine. Sure, you can find people working on five- to ten-year mainframe projects that ultimately run no faster than a PC from Costco, and they may dispense with the operating system due to time constraints, plus the fact that they have a worldwide market of one customer. But for most of us, the OS is part of the machine.

You won't understand how compilers work unless you've taken a theory of computation course. The theory of computation reads like part one of chapter 1 of a compilers book. You need all of it.

You'll have difficulty keeping the phases (and even the inputs and outputs) of a compiler straight in your head unless you've taken a programming languages course. You have to know what the capabilities of programming languages are, or at least have an inkling, before you can write a program that implements them. And unless you know more than one language well, it won't make much sense to write a program in language A that converts language B to language C.

You're actually surrounded by compilation problems. You run into them almost every day. The seven scenarios I outlined above are the tip of the iceberg. (The eighth one is the rest of the iceberg, but no skimming!)

Compilers take a stream of symbols, figure out their structure according to some domain-specific predefined rules, and transform them into another symbol stream.

Sounds pretty general, doesn't it? Well, yeah.

Could an image be considered a symbol stream? Sure. Stream each row of pixels. Each pixel is a number. A number is a symbol. You can transform images with compilers.

Could English be considered a symbol stream? Sure. The rules are pretty damn complex, but yes, natural language processing (at least the deterministic kind that doesn't work and has been supplanted by stochastic methods) can be considered a fancy kind of compilation.

What about ordinary code? I mean, we don't all deal with image processing, or natural language processing. What about the rest of us? We just write code, so do compilers really matter?

Well, do you ever, EVER need to write code that deals with your own code base? What if you need to write a syntax highlighter? What if your programming language adds some new features and your editor doesn't support them yet? Do you just sit around and wait for "someone" to fix your editor? What if it takes years? Doesn't it seem like you, as the perfectly good programmer that you are, ought to be able to fix it faster than that?

Do you ever need to process your code base looking for certain idioms? Do you ever need to write your own doc extractor?

Have you ever worked on code bases that have grown inexplicably huge, despite all your best efforts to make them modular and object-oriented? Of course you have. What's the solution?

You either learn compilers and start writing your own DSLs, or your get yourself a better language.

I recommend NBL, by the way. It's my personal favorite: the local maximum in a tensor-field of evil, the highest ground in the vicinity of Hell itself. I'm not going to tell you what NBL is, yet, though. Patience! I'm only half done with my Emacs-mode for it.

If you don't take compilers...

One reason many programmers don't take compilers is that they've heard it's really, really hard. It's often the "capstone" course of a CS program (OS often being the other one), which means it's a sort of "optional rite of passage" that makes you a Real Programmer and puts hair on your chest, regardless of gender or chest-hair preference.

If you're trying to plan out a schedule that gets you to graduation before the money runs out, and hopefully with a GPA that doesn't cause prospective employers to summon the guard dogs on you, then when you hear the phrase "optional rite of passage", who can blame you if you look for alternatives?

I'm not saying other CS courses aren't important, incidentally. Operating Systems, Machine Learning, Distributed Computing and Algorithm Design are all arguably just as important as Compiler Construction. Except that you can take them all and still not know how computers work, which to me means that Compilers really needs to be a mandatory 300-level course. But it has so many prerequisites that you can't realistically make that happen at most schools.

Designing an effective undergrad CS degree is hard. It's no wonder so many ivy-league schools have more or less given up and turned into Java Certification shops.

If you're a conscientious CS student, you'll at least take OS and AI. You may come out without knowing exactly how compilers work, which is unfortunate, but there will be many problem domains in which you can deliver at least as much value as all the other people just like you. That's something to feel good about, or at least as good as everyone else feels at any rate.

Go team.

Most programmers these days, sadly, just want the degree. They don't care what they learn. They want a degree so they can get a job so they can pay the bills.

Most programmers gravitate towards a set of courses that can best be described as the olive-garden of computer science: the places where dumb programmers go to learn smart programmer stuff.

I hesitate to name these courses explicitly. I wouldn't be agile enough to dodge the game of graphic bloodshed aimed at me by animated, project-managing, object-oriented engineers using Java and Web 2.0 technologies to roast me via user interfaces designed rationally through teamwork and modern software methodologies. I'd become a case study in the ethics of software and its impact on our culture.

But you can probably imagine what some of the courses are.

If you don't take compilers then you run the risk of forever being on the programmer B-list: the kind of eager young architect who becomes a saturnine old architect who spends a career building large systems and being damned proud of it.

Large Systems Suck

This rule is 100% transitive. If you build one, you suck.

Compiler Camps

It turns out that many compiler "experts" don't know compilers all that well, because compilers can logically be thought of as three separate phases -- so separate, in fact, that they constitute entirely different and mostly non-overlapping research domains.

The first big phase of the compilation pipeline is parsing. You need to take your input and turn it into a tree. So you go through preprocessing, lexical analysis (aka tokenization), and then syntax analysis and IR generation. Lexical analysis is usually done with regexps. Syntax analysis is usually done with grammars. You can use recursive descent (most common), or a parser generator (common for smaller languages), or with fancier algorithms that are correspondingly slower to execute. But the output of this pipeline stage is usually a parse tree of some sort.

You can get a hell of a lot farther as a professional programmer just by knowing that much. Even if you have no idea how the rest of the compilation works, you can make practical use of tools or algorithms that produce a parse tree. In fact, parsing alone can help you solve Situations #1 through #4 above.

If you don't know how parsing works, you'll do it badly with regular expressions, or if you don't know those, then with hand-rolled state machines that are thousands of lines of incomprehensible code that doesn't actually work.


In fact I used to ask candidates, as a standard interview question, how they'd find phone numbers in a tree of HTML files, and many of them (up to 30%) chose to write 2500-line C++ programs as their answer.

At some point, candidates started telling me they'd read that one in my blog, which was pretty weird, all things considered. Now I don't ask it anymore.

I ask variants of it occasionally, and it still gets them: you either recognize it as an easy problem or you get out the swiss army knife and start looking for a second to behead you before the pain causes you to dishonor your family.

C++ does that surprisingly often.

The next big phase is Type Checking. This is a group of zealous academics (and their groupies and/or grad students) who believe that they can write programs that are smart enough to figure out what your program is trying to do, and tell you when you're wrong. They don't think of themselves as AI people, though, oddly enough, because AI has (wisely) moved beyond deterministic approaches.

This camp has figured out more or less the practical limit of what they can check deterministically, and they have declared that this is the boundary of computation itself, beyond the borders of which you are crossing the outskirts of civilization into kill-or-be-killed territory, also occasionally known as The Awful Place Where People Make Money With Software.

You should hear them when they're drunk at rave parties.

A good friend of mine with a Ph.D. in languages told me recently that it's "very painful" to experience the realization that all those years of slaving over beautiful mathematical purity have more or less zero bearing on the real world.

The problem -- well, one problem -- is the underlying premise, which is apparently that without the Hindley-Milner type system, or failing that, some crap-ass type system like Java's, you will never be able to write working code; it'll collapse under its own weight: a vast, typeless trap for the unwary adventurer.

They don't get out much, apparently.

Another problem is that they believe any type "error", no matter how insignificant it might be to the operation of your personal program at this particular moment, should be treated as a news item worthy of the Wall Street Journal front page. Everyone should throw down their ploughshares and stop working until it's fixed. The concept of a type "warning" never enters the discussion.

Remember when fuzzy logic came along? Oh, oh, wait -- remember when von Neumann and Stan Ulam introduced the Monte Carlo method? Oh, right, I keep forgetting: you were born in nineteen-ninety something, and you're nineteen, and I'm ninety-something.

Well, someday they will realize that strict determinism has always, always failed, in every dimensionality-cursed domain to which it's ever been applied, and it's always replaced by probablistic methods.

Call it "optional static types", as an embryonic version of the glorious future. NBL, anyone?

The third camp, who tends to be the most isolated, is the code generation camp. Code generation is pretty straightforward, assuming you know enough recursion to realize your grandparents weren't Adam and Eve. So I'm really talking about Optimization, which is the art of generating code that is just barely correct enough that most of your customers won't notice problems. Wait, sorry, that's Amazonization. Optimization is the art of producing correct code that is equivalent to the naive, expensive code written by your presumably naive, expensive programmers.

I'd call compiler optimization an endless chasm of eternal darkness, except that it's pretty fun. So it's an endless chasm of fun eternal darkness, I guess. But you can take it to extremes you'd never guess were possible, and it's a fertile, open research field, and when they "finish", they'll be in the same place the Type Checking camp wants to be, namely AI experts.

By which I mean Machine Learning, since the term "AI" smacks of not just determinism, but also a distinct lack of VC funding.

In any case, the three camps don't really mingle much, and all of them have a valid claim at calling themselves "compiler experts" at raves.

The Dark Side of Compilers

One of the reasons it took me so long to write this ridiculous blog entry is that I wanted to go write a compiler for myself before I spouted off about them.


Well, sort of. Actually, "not done" would be more accurate, since that, as I've found, is the steady state for compilers everywhere.

Without giving any details away, as that would be premature, I took a stab at writing an interpreter for a useful language, using another useful language, with the output being useful bytecode for a useful platform.

It was fun. It went pretty fast. I learned a lot, even though I'd taken compilers twice in school 15 years ago, and even though I've gradually taught myself about compilers and programming languages over the past 5 years or so.

I still learned a lot just by doing it.

Unfortunately, writing a compiler creates a living thing. I didn't realize this going into it. I wasn't asking for a baby. It was a complete surprise to me, after 20-odd years of industry experience, that even writing a simple interpreter would produce a lifetime of work.

Go figure.

I credit the phrase "a lifetime of work" to Bob Jervis, a friend of mine who happens to be the original author of Turbo C (with which I myself learned to program), and a damn good, even world-class compiler writer.

He gave a tech talk recently (Google does that a LOT) in which he pointed out that even just the set of features the audience had asked for was a lifetime of work.

This phrasing resonated deeply with me. It was similar to my realization about 18 months back that I only have a small finite number of 5-year projects left, and I have to start choosing them very carefully. After writing my own "production interpreter", I realized that the work remaining was unbounded.

I mean it. Unbounded.

So from one perspective, I suppose I should just release what I've got and start marketing it, so other people will jump on board and start helping out. On the other hand, I started this particular side-project not to create a lifetime of work for myself (far from it), but to make sure I knew enough about compilers to be able to rant semi-intelligently about them, after a few glasses of wine, to a quarter million readers.

So I'd at least better finish the byte compiler first.

I'll get there. It'll be neat. I've only described this crazy little side project to a handful of people, and they reacted pretty uniformly by yelling "WTF????" You know, the kind of shout you'd yell out if you discovered the most sane person you knew in the entire world trying to stuff a lit stick of dynamite into their mouth.

That's compilers for ya. You can hardly attempt one without trying to change the world in the process.

That's why you need to learn how they work. That's why you, yes you personally, need to write one.

It's not as hard as you think, except for the fact that it will turn into a lifetime of work. It's OK. You can walk away from it, if you want to. You probably won't want to. You may be forced to, due to time constraints, but you'll still be a far better programmer for the effort.

You'll be able to fix that dang syntax highlighting.

You'll be able to write that doc extractor.

You'll be able to fix the broken indentation in Eclipse.

You won't have to wait for your tools to catch up.

You might even stop bragging about how smart your tools are, how amazing it is that they can understand your code -- which, if I may say so, isn't something I'd go broadcasting quite so loudly, but maybe it's just me.

You'll be able to jump in and help fix all those problems with your favorite language. Don't even try to tell me your favorite language doesn't have problems.

You'll be able to vote with confidence against the tired majority when some of the smartest people in the world (like, oh, say, James Gosling and Guy Steele) try to introduce non-broken closures and real extensibility to the Java community. Those poor Java Community schmucks. I pity them all. Really I do.

Heck, you might even start eating rich programmer food. Writing compilers is only the beginning; I never claimed it was the end of the road. You'll finally be able to move past your little service APIs and JavaScript widgets, and start helping to write the program that cures cancer, or all viruses worldwide, or old age and dying. Or even (I'm really going out on a limb here) the delusion of Static Typing as a deterministic panacea.

If nothing else, you'll finally really learn whatever programming language you're writing a compiler for. There's no other way. Sorry!

And with that, I suppose I should wrap up. I'm heading to Foo Camp in the morning, and I have no idea what to expect, but I have a pretty good guess that there won't be much discussion of compilers, except hopefully from GVR vis a vis Python 3000. That might be cool.

If you don't know compilers, don't sweat it. I still think you're a good programmer. But it's good to have stretch goals!

But What's The Most Important CS Course?

Typing 101. Duh.

Hie thee hence.

Sunday, June 10, 2007

That Old Marshmallow Maze Spell

First thing I notice, walking into the familiar old Great Room, is that the crowd hasn't changed. There's one small difference that I can't put my finger on... it'll come to me, I'm sure.

More familiarity: mature fires are burning in the two great stone mantles at opposing ends of the room, each contributing warmth and a certain inevitable smoke. I make my way to the bar — where else? As I weave through the tables, old faces and new glance up from lively conversations, some smiling to greet me or wink at me. Oh, it's good to be back again. I've never been happier to walk into this room. Not so much because I've been away, but because of where I've been.

How could I have let it happen? I don't know how I'll explain to any of my old friends... better not to dwell on it for now. I arrive at the bar, settle onto one of the ancient teak stools. Before I've so much as glanced at the tap, a young, fashionably unkempt bartender I don't recognize sets down a half-yard of cool pilsner and declares: "On the house! Welcome back!" Before I can ask him his name he's off again, delivering a pair of frothing mugs to a pair of codgers laughing at some private joke near the far end of the bar from where I sit.

I study my pils. It's my regular fare, but I don't recognize the bartender. I must be getting old. The thought occurs to me that the only difference in the tavern crowd, in the six months I've been away, is that they seem to have aged backwards. Depressing? Maybe not. Life had its challenges when I was younger, too. Except for recent events, and surely they're anomalous, growing old hasn't been as bad as I've heard it would be. The past half year, sure, it's put years on my life... but that's quickly becoming so much bridgewater now that I'm back in town. Things already seem better.

I take my lager over to a table to enjoy it quietly. I want to be lost for a while in the noisy company around me. I choose an aged bench, an old favorite, its familiar knots worn smooth by countless drunken backsides, its gouges and furrows sealed with some unknown caulking the color of greasy smoke. I sip my pilsner and wonder again how it could have happened to me. Who would believe it? I resolve not to tell anyone. Instead I might tell the comfortable half-truths that people are expecting from me: I've been busy with personal affairs, all of which are now resolved satisfactorily, and now I'm back among the living. That's all anyone really needs to know.

My lager's gold deepens to sudden wheat as a shadow blots out the entire westward hearth from my vantage: an enormous blonde man, easily twice my size, is settling down directly across from me. My worries leave me on the instant.

"Rauser! What are the odds — how long has it been, friend?" I greet him with genuine cheer, and find I can't suppress a huge grin. I hadn't expected to see him here this afternoon.

"Too long, and then longer," Rauser booms back at me. He waves at the barkeep, pointing at the tap.

The funny thing about Rauser was that he always booms. His voice can't do anything but boom. I've known him for most of my life, and he's never been able to whisper. That trait got us into a lot of trouble as kids. But he also has the knack of talking his way out of trouble. Rauser and I, we go waaaay back. I'd trust him with my life.

Rauser's aged visibly since we last spoke, perhaps nine or ten months ago. His broad, almost ageless face has finally begun to sport lines, and his temples are half an inch higher. And he looks every bit as tired as I feel.

"What have you been up to, Raus old buddy? I heard you haven't been around here much lately. Although — admittedly — I haven't been around muchly myself to look for you." I'm genuinely curious. Rauser was once as much a regular here as I myself had been, not a year ago.

Rauser eyes my half-drained glass with unconcealed longing, grunts, turns to locate the barkeep. I push my glass over to him. "Have it. You look like you need a head start."

"Thanks, bud!" He drains it in a gulp, wipes his mouth, and shouts over the crowd to the pot-boy near the east fire, who seems to be taking his time serving a group of five or six young women who look like tourists. The pot-boy notices me and Rauser waving at him and bolts behind the bar.

Rauser looks me up and down appraisingly. I'm still grinning at how fast he demolished my beer. "You back for real now? Or just visiting?"

"I'm back," I announce, and as I say it I feel the truth of it. I really am back. I've been away from Story for far too long, and although I have a whopper of a tale, it's still too real to tell. Stories are best after they've settled a bit, not when they're still raw and confusing and don't seem quite dead enough to handle yet, not without risking getting your hand bitten by a side story or a vignette that hasn't played out yet, or simply hasn't realized that it's supposed to be over.

I'm back for real, but my story will have to wait. I need to rest and mull over it. When it's been mulled to sufficiency, I'll seal its gouges and furrows with a little smoke to make it comfortable to tell, which of course has to happen before it's comfortable to hear. All good stories should make you a little uncomfortable, and great stories can wound a person and leave scars for life. But if you're not careful, and you don't wait just a little before telling it, a fresh enough story can even do damage to itself.

So I want to hear someone else's story, and Rauser looks like he has a pretty good one to tell me. As we wait for our beer, I'm suffused with an odd mixture of nostalgia and relief. It has been a very long time since I've felt a pang this intense that wasn't guilt, or shame, or dread, and I suddenly feel nostalgic for the feeling of nostalgia, and relieved that I can once more feel relief. How did I let it happen to me? I wonder...

The pot-boy finally makes his way to us with a pair of oversized steins. We've switched to a dark malt, rich and subtle as fine chocolate, and I take a me-sized swig while Rauser takes a Rauser-sized swig. Our mugs thump to the table with different thump-pitches. I'd swear Rauser's mug sounds empty.

This place always has the best beer. Maybe that's part of why the stories are always so good.

Here's the story Rauser tells me. It's a little raw, but it's how he tells it to me. I'll try to keep my side-commentary to a minimum, at least after his story gets underway. I'll also try to remain true to Rauser's phrasing, which is as unique and personal as the man himself. Whatever. Here's what he booms out:

"My old friend, best of friends..."

He always starts that way. I'm not trying to disguise my name or anything. It's just how he starts his stories with me. We actually are pretty close to best friends, though. One or two heads turn, since it sounds like a story is starting up, but we pay them no attention.

"You know I've been gone a good while, and I've got a tale to tell all right. But I haven't spun it properly for a real Telling, not for an audience and all. So I'll just tell you, and I'll let the story take its real shape as I read your reactions. Got it?"

I nod knowingly. More beer, is what Rauser is saying. No secrets between friends, and Rauser's an old friend. It's the best kind of story introduction: just between you and me, for your ears only. That's always a call for more beer. I wave to the pot-boy, catching his attention; he nods from across the room and heads to the bar. Rauser continues...

"I've thought long and hard about how to tell this story, how to explain how I just disappeared for close to a year. I haven't decided yet. But you're getting the true version. And there's a hard bit to swallow right in the beginning, so let's get it out of the way."

Rauser eyes me with sudden intensity. I'm a little uncomfortable, even, and drop my eyes to my beer glass. I hope he hasn't murdered someone.

"Here it is, whether you believe me or not: I had a spell put on me by an evil wizard, and I've been laboring under that spell for the past ninemonth and some weeks. That's what happened to me. It was a modern-day, evil wizard, and you and I both know they don't exist. But that's the truth of it."

He pauses, not proceeding with his story, waiting for me to react. I try not to, but I think I may have winced involuntarily, just a little wince, when I heard him say "evil wizard". I take a deep breath and say nothing. At least he hasn't murdered anyone, unless that's supposed to be his alibi. But I think he saw me wince. Since that's my only reaction, he runs with it:

"Fine, fine, now that I hear myself saying it, I know it sounds unconvincing as all that. But hear me out, hear me out. I'm not talking about fireworks or so-called mystical rituals or any such nonsense. You know me well enough for that. What I'm telling you is much more subtle. I only know a few words that can adequately describe what happened to me. So when I tell you I was entrapped by a spell cast by an evil wizard, old friend, that's just me doing my best to explain something entirely outside my realm of experience. And you and I don't lack for experience."

The pot-boy arrives with two full yards of dark brown lager. Good boy. He can tell we're about to embark on a story, and gets out of our way quickly. I give Rauser's glass a solid clink with my own, wordlessly accepting his explanation and inviting him to tell me the whole story. I regret my little wince from before; it's just that... no matter, no matter. I put it out of my mind as Rauser begins his story in earnest:

"I'll tell you this much: I'll never eat another marshmallow again, not if I live to be a hundred.

"About nine months back, I landed a job with a local landowner. He had an old mansion on the property, and he'd forever been fiddling with it, adding extensions here and there, and it had never really, well, coalesced I guess is the word for it. It hadn't settled down and grown character the way a mansion should. It was just a mess, a big eyesore that he said was as uncomfortable to live in as to look at. So he wanted us to build him a brand-new mansion on another part of his property. That was the job.

"Normally you and I work with our own crews, hand-picked, but this landowner was in a hurry and had some of his own people in mind. He talked me into joining on, and it wasn't a hard sell, because I was looking for something big, and this job had real promise. It did, and it still does. I'm still on it, in fact.

"This landowner already has it made; he's got more cash than a reasonable person could ever need, enough to build himself a brand-new mansion while he's living out of his old one. And he has other properties, and such. You know the type. Rich entrepreneur. He wasn't happy with any of his other mansions, though, and he wants this one to be fit to house a king. He's set on it.

"I don't know if he's planning on inviting a king, or being one himself, but his plans for this mansion are immense. It's more palace than mansion. When it's done, and I've no doubt it'll be one of the finest mansions most folks will ever lay eyes on, assuming they ever go out there. It's quite a haul from here..."

Rauser squints at his beer, momentarily unsure of himself. He takes a huge gulp of it and continues, more confident. That's beer for you.

"You and I have done this kind of job plenty of times, and you know they take years. But there were two catches that made this job especially tricky. As if it weren't hard enough already!

"The first catch: this property we're building on is a lowland, with swamps and standing water, and you can't drain it. The water would just come right back. Traditionally the way the planner solves this is by bringing in earth, mounds and mountains of it, and building it up high above the water line.

"It can take a long time to build a foundation like that, and you know as well as I do they don't always work. You need to let the hill settle before building on it. But the purse strings are always drawn tight during those waits, and better than half the jobs wind up building on piles of fresh dirt. Things go well for a while, but when the dirt gets enough weight on it, the whole foundation can collapse. We've seen it happen. Oft as not the job will be over at that point — the landowner is out of coin, or someone on the crew is injured and they all leave superstitiously, or maybe the landowner blames the crew but can't find replacements who'll take the job. And sometimes everyone's lined up to keep working, but the thing is damaged beyond repair, and they grind away uselessly for a while before the effort just falls apart on its own.

"We've seen all those things happen before. Sure, we've seen successes with the build-a-hill approach, even done a few ourselves, but conditions have to be just right. You need proper time, proper planning, proper funding, fair weather, a strong crew, and a handy bit o' luck thrown in for a project like that to complete."

"The other catch to this dream job was the time: it had to be done on an impossible schedule. The landowner, a reasonable and respectable man in my judgment, had never undertaken this kind of job before, and didn't estimate the effort properly. The complexity and expense of a job like this are proportional to the physical size of the structure, so building a mansion just half again bigger than your last one can easily quadruple the effort required. It's deceptive. And it doesn't matter how you try to explain it, because from a distance it looks the same as the other jobs they've seen. They don't realize they're not just making it bigger; they're making it fancier while they're at it. Every new mansion has to be better than the neighboring mansions in every imaginable way, and it can wind up being ten or even a hundred times the work to build the last one.

"You can see now why I took the job. Building a palace fit for a king, on a swamp fit for a crocodile, with a schedule that wouldn't work for a midwife, let alone for building a normal-sized mansion. That's the kind of job that gets your attention, because if you do it right, and then you pull it off, some nobleman really will buy the thing, and your crew along with it. I've seen folks like us retire after one job like that."

Rauser pauses significantly for a deep draught of his lager. The mention of early retirement, or any retirement at all, always deserves a respectful drink in our profession, and I salute him with my glass. None of us would ever retire the way you'd think of it, of course; we're master builders, and in so-called retirement we'd likely continue puttering on our own homes and other projects forever. But doing your own thing on your own time is a damn sight better than doing it all for someone else. Well, that's what I've heard. Can't say myself, and neither can Rauser, but retirement is still one of our favorite toasts.

"So now you know the job, or as much about it as matters, and you know why I took it, and why he picked me. This landowner tracked me down at another site, where I was negotiating a new job. I'm surprised he didn't track you down too. We could have used you. Still could. He was going for top talent and paying top price, so I felt he was leaving starting gate with the right attitude and initial decisions. How many projects can we say that about?

"I laughed long and hard at his proposed schedule, and he took it well enough. He asked me how long I thought I needed, and when I told him, he didn't balk. That clinched it for me. This was going to be a dream job, after all: the kind where you build something that lasts for generations, the kind of job you can rest a career on.

"I told him I'd take the job on one condition: I alone get to make the decision about how to handle the swamp. I had an interesting idea in mind about how to build on the wetlands. It's not something we've seen done on this scale before, but I was convinced it would work. Even so, it took a bit of negotiation and some persuasion to get him to agree to my plan, because once you go this route you're committed from day one.

"My idea was to build a big floating platform, then build the mansion on the platform. I told him the platform would take three to five months, at which point it wouldn't be completely finished, but it would be strong and stable enough to let us start construction on the mansion. Then we'd continue to shore up the platform and refine it as needed while we built him his little palace.

"He was intrigued, just as you seem to be. But I'd been thinking about this approach and sketching out designs for, well, years if you want to know the truth. But in the past year I'd finally figured out the last technical obstacles.

"This platform was, and is, unlike anything you've seen before. You'd never guess it was floating by looking at it. It's actually partly supported by land, but during the rainy season it floats fully, and during a drought the land contacts can support its full weight and then some. Most of the floating platforms we've seen, leastaways the ones I've seen, maybe you know better than me, have been flimsy and skittish, built for cheap single-occupant homes. They only do it when there's no money for dirt. They're popular, sure, but I've never heard tell of a floatable platform strong enough to park a palace, and immobilized enough so none of the occupants gets seasick walking to the cupboard for a midnight swig."

We both take another swig, right on cue. A master storyteller like Rauser tailors his story on the fly to keep the beer flowing, which in turn keeps the story going.

"The technical challenge, both in design and construction, wasn't exactly risk-free, and both the landowner and I knew it. But we also knew that a fivemonth is a full year sooner than the time it would take to build a strong hill. He didn't seem to care if his mansion is elevated or not; he'd been to the East and seen water-level palaces fit for entertaining nobles, albeit not floating ones, at least as far as he could tell me. A hill would be nice, sure. But this job is a home, not a fortification, and if my floating platform were viable, it would save him a fortune in both time and money. More money for the palace! The better the palace, the better the crew's future career prospects; everyone comes away happy.

"So we signed the contract on the spot, and I went straight to work. He would provide the crew, although I was welcome to bring any of my own men as I could locate them. Our mini-crew would start work on the platform, and after three months we'd be fully staffed and ready to start on the mansion proper, with all of us transitioned full-time to the mansion work within half a year of our contract date.

"Here, my friend, is where my story departs from being just another bland job description, floaty platform or no floaty platform, and enters the realm of the bizarre, in a way most... unfortunate for all of us.

"Before I tell you what happened, just keep in mind the three Ms."

Rauser's been preparing his story for a mass audience rather more than I'd realized, if he's bringing an M into it already. Rauser busies himself waving down the barkeep, having finished his giant beer, but I'm certain he's doing it to give me time to think, and digest what he's told me so far.

Problem is, I can't concentrate. I've been listening to his story silently so far, trying to avoid making any faces other than rapt attention, because I know already that any faces I make will be the wrong ones at the wrong times, and Rauser, master storyteller and friend to me that he is, will notice. I don't want him to stop the narrative; the first telling can be make-or-break, and he may lose interest or change the focus of the story altogether if I push him off track inadvertently.

Raw stories are delicate to handle, even when apparently cooked with an M already, and I can tell this is Rauser's first telling of this thing, whatever it is that happened to him. I won't ruin his story by letting on that I know his entire story — at least so far — because it's the same as my own. The only appreciable difference is the platform; his floats, tailored to the wetland upon which he's building, and my platform, if that's the right word for it, is suspended in midair with ropes, cabling, wind-power and a fair bit of fingers-crossed hope, all tailored for a castle in the sky. Other than that irrelevant technical detail, Rauser could be telling my story, and it's scaring me, because if it ends up the same way, then it's not a happy one.

So I try to be stoic, almost holding my breath as his tale unfolds, told in his booming bass with big beer belches, Rauser-style.

The three Ms, by the way, are Metaphor, Misdirection, and Mashups. All are ways of covering your tracks, of hiding the puppet wires, of fictionalizing a story that began as nonfiction (or multiple stories, in the case of Mashups). Each M is an ingredient that enhances the flavor of a story when baked in, without changing the story's nature or intent. A romance is still romantic, a cautionary tale still cautions, and a shaggy-dog joke, one would hope, is still funny. The three Ms themselves are something of in-joke here in Story, because it's tacitly understood that there are more than three, and they don't all start with M. Whatever. That's writers for you.

Anyway, as soon as an M makes an appearance in a story, all bets are off. Rauser could be telling me an old joke he heard, or a synthesis of real events that happened to others, or he could be making it all up for practice; it's impossible to guess. Some storytellers have even been known to claim Ms are present when in fact there are none, in a paradoxical application of the second M.

But I have a hunch Rauser is telling me a story that's nearly raw, in part because I've known him so long, and in part because it jibes so closely with my own recent experiences. Unless, of course, I'm just making all this up for your enjoyment, which I just M-ight be.

The way these things are typically done, especially in the hands of a teller as practiced as Rauser, is each M is embodied by a character or story element that actually starts with M. Where does that leave us? Marshmallow is the obvious candidate, with Mansion being a solid runner-up. No matter. In the end, Rauser is simply telling me that this is just a story, and that any elements of real pain in it are entirely secondary to the fact that he's back among us, able once again to entertain and perhaps educate, and be entertained and educated himself. That's why we come here; that's all he's really saying.

Rauser's a beer ahead of me now. I'm not surprised; he's a big, thirsty man, and he's been away even longer than I have. I stop trying to pace him, and take a deep pull from my yard. The lager is almost as sweet as mead. I've missed this place.

"I guess it's time to tell you about the foreman. Well, heck, I'm not sure at this point who to tell you about. After three months of toiling through the rainy season, my floating platform was large and stable enough to hold thirty mounted riders, which is all we could muster for a stability check. It didn't budge, even though it was floating six inches above the anchor points from all the rain. We knew it was good enough to start construction of the mansion. We were still waiting on the final floor plan, though, and it wasn't due for a month... well, that's a detail.

"I'm trying to avoid too much detail here, since the technical and schedule details aren't what I'm about. You can imagine how they went. We had some delays, some setbacks, just like you'd expect, but we still managed to stay on the original schedule, or close enough to it so nobody could complain. Well — nobody rational, that is.

"About four months into the project, we started hearing... talk. Just bits of rumors, snippets here and there, about our crew and our project. This landowner's property is a good way from here, eight days' journey with strong horses and friendly weather. It wasn't exactly a secret, but we also knew the landowner didn't want to attract attention to the mansion until it was ready to show, for the usual reasons: bandits, pranksters, and even the chance that someone else would come along and build nearby, ruining the obvious potential for selling the place as a remote summer villa or even a fancy inn, should it come to that.

"The talk we heard was about our progress. The landlord rarely made appearances, what with it being the wet season and he needing to tend to his other affairs, abroad. But we heard he was unhappy, or that his potential buyers were unhappy, or that a neighboring baronial type was unhappy, all manner of unhappy-talk. The rumors were always different, and you know how they spread around, so nobody could place them. There was just enough traffic in and out to provide a constant supply of rumor. But we didn't pay much attention to any of it then, early on in the project, because we knew we were making great progress.

"Right around then, at least I think that's when it was, I started noticing the marshmallows. They were showing up in the provisions, little bags of them, and nobody thought anything of it at first. We started roasting them on nights when it was dry enough to light a fire. Sometimes we'd see little bowls of them appear on a workbench, or in a tool chest. Before long they seemed to be everywhere, and we didn't think much of it at the time. Maybe someone just liked marshmallows. Maybe one of our food suppliers was unloading them at a bulk discount. Nobody really cared that much, since any you didn't eat you could throw into the fire, or the swamp.

"Well, word came down from... somewhere... I never quite have figured out where it originated, I suppose, but I have a good guess now. In any event, we got word that we had to eat the marshmallows or there would be trouble of some unspecified sort.

"It was never made clear exactly why we had to eat them, as opposed to just throwing them away and not ordering so many. We heard that they were pushing back on the supplier, but talks were in progress; heck, we heard so many conflicting things, I doubt any two men on our crew have the same idea in their heads today as to what really happened. Maybe we heard that we couldn't throw them in the marsh or it would attract crocodiles, or maybe we just speculated as much, one night while we were roasting them. At the time, you know how it is, the project was really busy, we were building like crazy, and it seemed like a minor thing.

"You've heard about boiling frogs, of course, and I tell you: even if it's not true — never tried it myself — that wives tale about frog-boiling has the ring of truth because things like it happen all the time. There was never a clear time or event you could point at, where the rumors and the marshmallows became recognized as a problem, because we thought the problem was us.

"You're at a remote worksite like ours, you know how it is. Guys tell each other stories to keep from going stir-crazy, and we crave news from the outside world, even if it's just rumor. Some of our foremen wound up meeting with visitors or even going offsite way more often than the crew did, and we heard most of our news through them. And they were worried. You could see it.

"I didn't see why they should be worried; my floating platform was clearly going to work out just fine, and although one could fairly debate whether I'd created a repeatable process, well, as a one-off it was just what we needed. But I'd hear, usually via the foremen, that the folks with the money were questioning the entire approach, and were even saying that we should have built a hill, never mind that building a hill, which is already inherently risky, takes well over a year.

"You'd think we'd have spent more time questioning the foremen, but they assured us they were able to send accurate reports of our progress back upstream, and that as long as we could reel the schedule in just a little bit, it would reassure our patrons that we're a competent crew worth funding.

"'How much?' we asked, and we were told that maybe pulling it in a month or so, and fully transitioning work from the platform to the mansion (whose floor plans we'd just received) in five months instead of six would do the trick."

"You know how much day-to-day detail goes into our jobs, and you know pulling in a six-month schedule by a month requires a minor miracle at best, or a major one if you're unlucky. But the picture wouldn't be complete without telling you about the maze."

Another M. I'd known one was coming. Can't fool me, Rauser. The maze is a fake, a plot device, an allegory. Right? Right. Then why did my gut just do a flip? Can't fool myself, either. The maze — it's in my story, too. I'm not sure I'd have chosen the word "maze", but then my story didn't exactly have marshm... the word is sticking in my throat for some reason. MMmmmaaaaarsshhhmmm...

"This maze, old friend, was a real and oppressive thing. It came upon us gradually, just like the marshmallows did, just like the rumors about our progress. I can look back and see it growing. It was a combination of things. We were working out on this oddly-shaped platform, with its little docks and outcroppings and square holes to let a hillock of sandy mud jut through, all the sorts of oddments you'd expect of a floating platform in a swamp made for housing a mansion.

"So from the start, navigating it was always a little tricky. It helped if you had some seafaring experience, we found, and not because you needed your sea legs — the platform was immobilized from day one. It's because the ex-sailors on the crew knew how to dodge and weave through crates and equipment without losing their balance or slowing down. But everyone on crew got the hang of it eventually.

"Getting from our camp to the platform was, I will freely admit, pretty awful. We didn't have a lot of time to work on the ramps, so oft times it was just boards and homemade signs. The platform was maybe a quarter mile from our little lean-to village where we all slept and ate, on higher ground, and where deliveries and most visitors stopped. We had a lot of people ask to see the platform, but since it wasn't visible unless you went out there, and there was mud everywhere, most folks declined. I can't say I blame 'em. Wasn't my job to build the road. That could come later.

"Well, one of the downsides of the platform, given our three-month initial schedule, was that it was only maybe twice as big as the mansion itself. We didn't have room for all the crates, boxes, bags, lumber, piles of building material, paint, and all the other cruft that showed up ahead of schedule. Initially, I think we decided, without giving it much thought, that we should try to move deliveries as close to the platform as possible, while we had the extra hands of the delivery crews.

"So we wound up with dozens of makeshift trails leading to the platform. With all our comings and goings, one trail wasn't going to suffice, and the trails were lined with equipment, trees, bushes, anything that hadn't been trampled down by feet. It became kind of maze-like, and there were more than a few dead-ends. It finally got to where you needed a guide on your first trip out to the platform, and maybe your second or third too.

"And those damned marshmallow bags kept showing up on the trails, on the platform, everywhere. It was getting out of hand. We were tired of eating them, but there was always pressure when we tried to do anything other than eat them. We seemed to be running out of trail space — sometimes it felt as if trees would spring up overnight, I'd swear it. And we were forbidden from discarding the marshmallows or even moving them off-trail. We were told that we would offend our patrons if we didn't eat them, and we were told that everyone upstream was trying as hard as they could to shut off the supply, but evidently there was a miscommunication. We never did see where the marshmallows were coming from, but they kept showing up, each day more than the day before. And what with the rumors about our lack of progress, and the vague blame cloud surrounding my decision to build a floating platform rather than a mountain of dirt, we were in no position to push back.

"I'm telling you — this whole situation just crept up on us, and none of it seemed so unusual at the time that anyone would stop to question it all. Sure, we'd talk about the individual elements: our progress, or the rumors, or the increasing difficulty of getting to and from the platform, some of which was our fault, although our increasing schedule pressure gave us correspondingly less time to build better trails. And of course everyone was tired of marshmallows, to the point where people started hinting that some folks on the crew weren't doing their share of marshmallow-swallowing; some of us were eating huge bags of them every hour; why couldn't the rest keep up?

Rauser pauses, takes a deep breath. He's been talking faster, which is a bit worrisome if you know anything about storytelling. It can get away from you, can rip into the crowd before you can recover and beat it back into submission. Careful, Rauser...

"All right, you get the idea, I think. Permit me to skip ahead a few months and describe my condition after eight months on this job.

"I hadn't taken a vacation in months, not even a day-hike away from camp. I'd stopped exercising. I'd ceased whittling and reading and all the other little diversions I bring to remote jobs like this one. I'd stopped eating anything but marshmallows, because it was the only way to keep the maze clear. I slept on the platform and rarely visited the camp. I would work from before dawn, deep into the night, with only occasional breaks to stuff down a marshmallow as big as a picnic table that had gotten itself wedged in some important leg of the maze. The maze itself was navigable only by the crew and foremen, and nobody ever came to see the mansion anymore. This was just as well, since our hygiene had fallen somewhat into disrepair as well.

"I was exhausted all the time, and worried all the time, and the nature of our situation was such that the only solution I could think of was to work harder.

"The mansion was progressing steadily, and was still on the original schedule I'd envisioned with the landowner seven or eight months back. Not that I had access to the contract or, for that matter, the landowner, so my recollection was a bit hazy. But every few weeks we'd receive news from one foreman or another, all of whom by the way were looking as depressed, worried and overworked as I was, that the schedule had reverse-slipped again, and that we had apparently promised yet another key delivery well in advance of when the crew thought it was due. Every time this happened, we redoubled our efforts.

"You know the math on this approach. You cap out quickly. We've done it before, but the circumstances were different. In those rare times in our careers where we've sustained 100+ hour weeks for any length of time, it was a fixed schedule — a building for an upcoming wedding, maybe, or a holiday in need of an orphanage. We always knew what we were building, and we knew we were good at it. We'd work the extra hours to compensate for inevitable schedule slips, and afterwards we'd have a huge celebration.

"This, friend, was different. The mansion plans never really changed, but our progress was being measured daily, and we were made to commit to tasks, in front of the rest of the crew, and then held against those commitments regardless of what happened in the interim — a tree falling on the platform, a crocodile eating a crew member, a lumber delivery never arriving. It didn't matter. We were told to dodge, weave, cut corners, and do whatever it took to make up the slack, because every week we were in worse (yet always vague) trouble, and nearly every week the schedule was pulled in some more.

"You and I, we're strong guys; we've been through the fire and the gauntlet on countless projects together. I don't know how to tell you, but this was not normal. I was feeling guilty all the time, but I couldn't walk away because of the platform; it hadn't seen the dry season yet, and I didn't want it suddenly snapping in two and killing half the crew. I had to stay, but it was killing me. It was killing all of us. Except for the crocodile that ate that one guy, but I think some of the other crew members were actually envious of him; that's how bad it had gotten.

"We loved the mansion, and I had high hopes for the smile on the landowner's face when he next came to see it. We'd had to triage most of the niceties, saving them for later, but it was (and is) still going to be a functional giant mansion on a swamp in what has to be world record time.

"By month nine I was a disaster. I slept an hour or two per night. I took risks with construction that should have taken my hand off, even without the sleep deprivation. We'd been ordered to stop worrying about building codes or safety; all that mattered was the mansion, so much so that it could have been painted on cardboard and still met our new short-term requirements. Everyone felt so ashamed that we could barely speak to one other. Any time we might otherwise have spent on planning, or questioning the situation, or even sleeping, we spent trying to force passages through the now-clogged maze by swallowing more than our own weight in marshmallows each hour, which we were able to accomplish through some magic I still fail to comprehend."

Rauser has stopped quite suddenly, and he isn't taking a drink this time. He seems to have just noticed that I am not the only one listening to his story, which has finally acquired a grim life of its own, holding our attention effortlessly. We all gape at him. He looks around at the listeners, perhaps twenty in all, a few from every table nearby. Outside our circle, the tavern noise continues merrily, unabated.

Rauser's tone changes from a boom to something almost like a whisper. A booming whisper, I guess. It would be comical if he weren't so serious, and if his story hadn't turned us all into boiled frogs in just a few short minutes.

"Have you ever noticed that all our folklore about wolves has certain themes and patterns to it? I've never met a wolf, but I give them fair credit for being wily creatures. I'm a big man, not one to fear a big dog's bite, but I would give a wolf a wide berth, because they're reputed to be so crafty. And crafty, friends, I am not. A craftsman, yes, but I realize now that I am more sheep than wolf.

"The landowner in my tale is a good, affable fellow; I could see it within minutes of meeting him, and I stand by him today still. He's a man with a clear vision and a good heart, and he hired crew members who, for all our talents, know nothing of wolves or wizards.

"The problem with setting up an untended, untrained flock of sheep is that there are wolves aplenty, and as sheep are not adequately prepared to recognize or deal with wolves, they will all eventually be eaten. This seems obvious to us. Nearly as obvious is that this idea applies equally to government, with the minor change that the wolves are savvy politicians and the sheep are incompetent ones. Eventually the sheep are all eaten, so our assumption is generally that the government is filled entirely with wolves — an assumption that has proven to be essentially axiomatic, across time and nation.

"What's far less obvious is that the idea applies outside flocks and governments, with the same consequences. If you set up any organization of saintly do-gooders, with no politics anywhere in sight, then the presence of a single master politician can go unrecognized for long enough for every single sheep to be eaten and replaced with a wolf. At some point the shepherd looks down and perceives that he now has a flock of wolves, and he wonders how it happened. But a shepherd rarely witnesses the process while it's in motion, because the wolves are so sneaky.

"I was being eaten alive on my mansion project, and yet I was utterly oblivious to anything but the need to survive, which due to various odd circumstances required working without sleep and eating marshmallows without respite, apparently until either I was dead or forever happened, whichever came first.

"And before you fetch the blunderbuss from the mantle and go out a-hunting wolves, remember that they need to eat. That doesn't make them evil. And killing all the wolves may simply saddle you with a different predator. Although at this point I can't say I'd stop you, either.

"But you have to be careful. If you dispose of an un-subtle wolf, it will be replaced with a subtle one, and this process will repeat until you no longer know your wolves from your sheep until your flock is dying.

"That, I think, is how organizations die. Wolves, wizards, behind-the-throne court counselors, whatever you want to call them or whatever guise they take, they specialize in being invisible to sheep. But wolves need to eat, and when the organization's last sheep is gone, the entity has undergone a complete transformation that will either kill it or change its focus to devouring neighboring flocks."

"At least that's what I think, but perhaps my recent experience has biased me unduly."

Rauser has paused, for one final time I think, and this time he does take a drink. He's past the worst of it. I can see from the shocked and worried faces around me that his story is going to leave some marks, maybe even a scar or two. That's what you get, Rauser, handling a raw story like that in public. Remember your three Ms.

"The end of the story is simple enough. Our wolf finally became bold enough and ravenous enough to destroy two of our sheep, rending them and devouring them as I stood and watched. I'm a big man, so the wolf hasn't gone for me yet. But I'm also a dumb man, at least dumb to the ways of wolves and wizards, so it managed to convince me I was simply struggling for survival by virtue of my own incompetence. Hell, for a few minutes I thought those sheep were just marshmallows with ketchup. Anything to change the flavor.

"The wolf didn't huff, or puff, or blow my house down. It was the wolf from Red Riding Hood, the fabled wolf in sheep's clothing, and its craft was far beyond mine, since I have none.

"Once I realized they weren't ketchup marshmallows, but were in fact two members of my crew, the spell was broken. I had no idea what to do, and still have none, but at least I'm catching up on my sleep.

"Sheep can kick surprisingly hard, as many a wild wolf has found. They simply lack the will to do it. The wolf charms the sheep, lulls it with fear and promise of escape, with whatever whispers it needs to keep the sheep from fighting or fleeing. A flock of sheep can fend off a pack of wolves with few casualties, but it rarely happens, because the wolves have learned to avoid direct confrontation. They do their work invisibly.

"I don't know what I'll do next, but I suspect it will involve teaching some sheep a few basic fighting maneuvers, and also a fair amount of long-overdue repair to our floating platform and our in-progress mansion.

"The only thing I know for certain is that I haven't had a beer in nine months, and it was high time to set my priorities straight!"

Rauser drains his mug to applause. It was a pretty decent story, although he really needs to change it to third-person, set it a few hundred years ago, throw in a few anachronisms, and dial down the soapboxing at the end. I'm sure he'll figure it out.

I can never tell my own story now, of course. If you take out the mundane detail thrown in for color, it's essentially the same story. I'll have to catch Rauser after his newfound fans dissipate and he's sobered up a bit. I need to ask him... well, no, it just doesn't seem possible that his wolf is the same as my wolf. Our job sites are hundreds of miles apart, weeks of travel separating us.

Plus there was one critical detail — oh, how it turns my stomach. I can't think about it. But I know why his maze wasn't the same as my maze, why their wolf isn't the same as our wolf. It's another reason I can't tell my story, unless I make prodigious use of the three Ms.

You see, the same thing — well, almost the same — happened to me. The only important difference was... well...

Our maze was full of dog chow. I don't know what the hell Rauser's complaining about.


It's good to be back.