Monday, December 29, 2008

The Five Stages of Programming

Programming is an interesting job, because it goes in continual cycles. Each part of the cycle has its own emotion that goes with it, too.

When starting off a new project, there's a learning curve that goes with it. You're spinning up, reading code, reading technical papers, trying to figure out what the hell you're going to do. The main emotion here is puzzlement -- how is this thing going to work? What's the interface? What's the feature set? What the heck is going ON?

After that comes early implementation. In this phase, the main emotion is nervousness. You think you know how it's going to work, but there's nothing really there yet. So you're hacking madly away, trying to get enough of a skeleton in place that you can start to make it dance. Forget about getting flesh on the bones, you're just trying to come up with something that can stand up! Since you don't really know what you're doing yet, it could all still fall apart on you.

Once you're out of those woods, you're into late implementation. Here, the main emotion is adrenalin. You're charging on all cylinders, driving at full throttle. The bones are rapidly becoming enfleshinated, and you're in the zone. This is in some ways the most satisfying part of the whole cycle, because now you start to see some real results from what you've been working on.

The last phase is debugging. Here, the emotion swings wildly between frustration and relief. You're almost done... except you're not! There's a bug! Fix it, fast! OK... and on to the next test... and WHAMO, another weird bug! Grrrr. OK, got that one done... YES! IT WORKS!!! Ship it!

And then the whole cycle starts over again.

So that's my job: puzzlement, nervousness, adrenalin, frustration, and relief. Of course sometimes you take a few steps back. For example, right now I made it all the way to relief, but I'm about to backslide into nervousness. The best-case scenario, though, is when you make it to relief and then you can keep building on the code you just finished... then you have a kind of secure happy foundation under you, reassuring you that even if your current layer falls to bits in a welter of recrimination, at least you know the relief -- that fantastic sense of accomplishment that comes with writing a software machine from thin air, that has real value and usefulness -- is still out there, in the future, waiting for you.

That's what software is, to me: the promise of progress, of building on what's come before, making it better. And this emotional cycle is what it takes to make that happen. So I'll close with a word that sums it all up for me:


Monday, November 24, 2008

Yow! MGrammar ahoy

I've ranted about grammarware here in the past, but now I'm actually using some, and it's rocking. I'm talking about MGrammar, part of the impending Oslo.

MGrammar is a toolset for writing grammars and working with them. The MGrammar grammar description language lets you write what is basically an LALR(1) grammar, which means it's about as powerful as YACC. Or it would be, if it wasn't also a GLR parser, which means that when your language is ambiguous you get all the possible alternatives. This is a nice way of avoiding the NP-completeness issues around ambiguity detection.

MGrammar also separates syntax (LALR(1)) from tokenizing (regular). This is a win, since sometimes tokenizing is all you need.

The coolest thing about MGrammar is the grammar development tool. It's a three-paned window, with sample text on the left, the grammar in the middle, and the parse tree on the right. You can change the sample or the grammar at will, and it reparses with every keystroke. When your grammar finds a parse error or ambiguity in the sample text, the sample text gets a red underline with Intellisense. When your grammar itself has an error in it, you also get a red underline with Intellisense, which is reasonable because there is in fact an MGrammar description of MGrammar itself, which drives the Intellisense.

It works very well in practice and makes grammar writing so much more productive it's not even funny. Using a lot of negation can make it go nonlinear, but it's manageable.

On a sad note, Gilad and his merry band have lost their funding. This really sucks, as Newspeak is one of the most interesting language efforts around. I very much hope a community takes root around it and drives it. (If it can happen to Factor, of all things, it can happen to Newspeak.)

And finally, yes, was broken for the last month or two. I had one email filtering rule for all of GoDaddy, and when we moved to Seattle this spring, the address change broke GoDaddy's monthly charging, but I didn't see the warning because it was in the same bucket with all of GoDaddy's spam^H^H^H^Hinformative emails. Which I never read. Sigh. I clearly need a fully redundant alerting and monitoring system for my blog.

Wednesday, October 8, 2008

Life, it is the greatest

Well, except for Blogger eating my profile picture, and GoDaddy eating my redirect from to -- why can't things just Keep On Working? Entropy, I hates it.

Shortly after I griped last month about a lack of working FLINQ samples in the latest F# CTP, Don Syme himself came through nicely with just what I asked for. So yay Don! And yay F#! And boo me, because I have not done thing one on the personal-hacking front in the last month. In fact, that aspect of this blog is going to go quite dark, if current evidence is anything to go by.

Not to say I'm not still deeply digging geeky things -- I'm currently reading my way through the extremely excellent Parsing Techniques, The Second Edition. My upcoming task at work is to do a whole lot of parsing stuff, and this is exactly the book I need. It's amazing. I've been reading scads of parsing papers (one-stop shop for me: Bryan Ford's Parsing Expression Grammars page), but I lacked the basic background -- what exactly is LALR? How do shift-reduce parsers work? How do you convert a left-recursive grammar to a non-left-recursive grammar, and what does it do to your attributes? Well, the Parsing Techniques book is absolutely the best imaginable text for me. It's the second edition, just published this year; the first edition was from 1990. How beautifully synchronistic that it should come out just when I absolutely vitally need it! I LOVE it when that happens.

And honestly, there are two other reasons I'm not getting much solo hacking done. One is that I'm climbing about 20 learning curves at once in my day job, and it's saturating my technical novelty bandwidth. There's not a lot of extra juice right now for doing yet further explorations in the evening. The other reason, and this is something I have yet to blog about here, is that it's the fall season, and that means GAMES.

Yes, the truth is out: I'm a fairly inveterate computer/video gamer. It's been a hobby of mine ever since I first laid eyes on a computer -- literally; the first computer I ever saw was a PLATO timesharing system at my best friend's doctor father's medical school in Connecticut. And what was it running? Spacewar. I still remember it vividly.

Ever since then I've been happily gaming away, and in many ways it's the perfect hobby for a compulsive hacker -- video games push technology in a lot of ways, and modern games use cutting-edge 3D graphics, physics simulation, distributed virtual space technology, and generally a whole lot of hardcore computer science in doing what they do. So not only do the games themselves get more immersive as games, but they also get more technically interesting and intriguing to learn about. Right now I'm playing Crysis, one of the most hardware-intensive games ever made (though people debate whether that's because it's not well optimized or just super ambitious). I finally got my self-built PC to run two graphics cards (through NVidia SLI), and man, this game is freaking stunning on my 1920x1200 26" monitor. (Which cost only $600! Damn, wasn't it just two years ago that this sort of thing was $2000+?)

So I'm giving myself permission to slack off, personal-hacking-wise, for the rest of the year. Unfortunately it looks like it will still be a good long time before I can post in depth about what I'm actually working on at Microsoft, but suffice to say that I really do look forward to that, and it will happen sooner or later, and the longer it takes the more I'll have to say when the veil finally drops. But rest assured, it's freaking cool and you will love it when you see it :-)

Wednesday, September 3, 2008

Best laid plans, mice, men, etc.

Well, not a lot of F# hacking got done last month. I did download the then-current F# build, and tried out some of the FLinq samples, and they didn't work. I posted about it on the F# mailing list (Microsoft, your mailing list server needs some serious kicks in the pants region), and there was no helpfulness forthcoming. So, onto the (cold, dark) back burner it went.

Which was fine, because ordinary life (summer vacation for the kids, my birthday, etc.) was plenty busy. And my work has exploded into a drinking-from-the-firehose geek frenzy -- I wrote a monadic push parser the other day, and got paid for it. Not clear whether it'll ever ship, but it was definitely relevant, which rocks. I can now say that I have lost my monadic virginity. Whether I should say it is another question. (My wife says not....)

However, on the bright side, the F# team did ship their CTP (Community Tech Preview, or something like that, for those outside the MAZ (Microsoft Acronym Zone)). So I'll take another run at it later this month. One cool thing is they have support for dimensional quantities now, a la Fortress. Only F# is basically here now, and usable for production software, whereas Fortress is still N years away from having any kind of realistic compiler. So IN YOUR FACE, Guy Steele! (Seriously, Fortress looks great. It's just that F# is here now, and is pretty great itself.)

OK, time to get back to watching a truly monster build crunch away. Work is creeping out of normal working hours -- getting assigned a fairly major team-wide task tends to have that effect. It's also cutting into my discretionary hacking and gaming time considerably. We'll see what the next month holds....

Sunday, August 3, 2008

Not Dark, Just Busy

It's amazing what a difference not commuting can make. Up until our move to Seattle in April, I'd been commuting an hour each way every day into San Francisco. That time on BART -- without net access -- was where all my blogging got done. Well, now I'm driving 15 minutes each way to work (modulo time to take my daughter to her school), and still coming down off the stress of moving, so I've been putting my energy elsewhere in the evenings. In any case, consider this a summer vacation for your RSS feed :-)

Not that I've personally been vacationing -- not at all! I'm finally getting up to some kind of reasonable cruising speed at work. It's been a colossal re-education in .NET, C#, low-level Windows debugging, SQL data stack design, and about 50 different interesting research projects which I can't really discuss -- at least not yet. It's very educational being on the list for all the different talks that happen inside Microsoft Research; there are a lot of different pies that those folks have their fingers in. The internal Windows developer talks are also very intriguing.

Now, this isn't to say that everything is on the hush-hush. Some of the better publicly visible tidbits I've run across lately involve LINQ, the techniques for basically doing data-oriented metaprogramming in the .NET framework. I mentioned LINQ in my last post, but suffice to say that it's a combination of a set of data-oriented query operators (that form a composable, monadic algebra), some syntactic extensions to allow more idiomatic SQL-like query expressions, and an internal syntax-tree representation that can be transformed into native query languages (including but not limited to SQL) and partially evaluated into high-performance serializers. Overall it's a very well-thought-out structure with a lot of room for growth. To wit:
  • DryadLINQ extends the LINQ operators to support MapReduce-like distributed cluster computation at scale.

  • PLINQ and the ParallelFX framework are building up the .NET infrastructure for fine-grained parallelism and efficient use of multi-core for data-parallel problems.

  • Matt Warren's series on implementing a LINQ query provider is a great example of metaprogramming in practice -- taking a C# abstract syntax tree describing a query, and transforming it into efficient SQL. This is the technique that is at the heart of LINQ. I've heard tell of F# projects that are using LINQ-like expressions to describe linear programming constraints declaratively -- same metaprogramming paradigm, completely different domain.

All of this is exciting because you noble long-term readers (e.g. since December 2007) will know how interesting metaprogramming is to me. Microsoft really gets it on multiple levels, and has put it into production with LINQ. There's a lot more on the horizon, too, and I'm eagerly waiting for each bit of it to reach RTM in some form so I can happily blog away about it!

Not only that, but I have a personal hacking project again. Matt Warren's blogs (mentioned above) are a great example of how to implement metaprogramming with an imperative C# visitor-style API. But I find the code hard to read -- it's taking this lovely declarative representation and then transforming it with all of this intensely imperative, explicitly scheduled transformation code. It reminds me of the JastAdd project, which has evidently now reached public release. JastAdd creates a declarative framework for implementing language analyses and transformations. I want to hack on an F# implementation of the JastAdd paradigm, applied to LINQ to SQL transformations. It would be very interesting to see if it could lead to something significantly easier to maintain and reason about.

This is something that arguably is potentially relevant to work. So I am going to blog about it internally first, and then repost publicly a week or so later (on a per-post basis). If it gets to where it is interesting enough for Microsoft to want to privatize it, I'll just have to find something else to blog publicly about! In any case, it'll be fun to post about here for as long as it lasts :-)

Monday, June 23, 2008

There's Nothing Micro about Microsoft

Hello everyone. Ah me. We live in Washington now! (State, that is.) We're happily ensconced in a nice rental home in Kirkland, and so far just about everything we hoped for from the move has happened -- we have less commute, cooler weather, a better school for our daughter, and my wife no longer has to work. And my new job at Microsoft is going very well so far, though I've actually been there less than a month -- I took May off to help our family settle in, and THANK GOODNESS, because moving is a LOT OF WORK even once you actually arrive!

But so far so good up here... I'm sitting in our living room looking out at the evening sky and the pine trees across the street, through the full-length windows and French door that front our house. It's beautiful up here.

I can't say too much in detail about what I'm working on, because Microsoft (like Google) is mighty touchy about confidential projects. But I can make some general observations after being back on the inside of the Borg for a few weeks. (I was amused to discover that they remembered me! I interned at Microsoft in 1988 and 1989, and I guess they gave me employee number 40775, because when I signed back up they gave me the same number back again. People were like, why are you 40775 rather than 263484? Microsoft's gotten BIG over the years....)

It's very curious how deep the not-invented-here goes at Microsoft. It seems to be partly historical -- Microsoft was such a winner-take-all company for all of the eighties and nineties, it sank deep into the marrow of the company. And it is partly reactionary -- the rest of the industry reacted so negatively to that aggressive attitude (antitrust suits, pitched legal battles with Apple and Sun, etc.) that it drove Microsoft even further into its own corner. I've got kids now, and I think a fair bit about sibling rivalry, and how kids (and adults, and nations) tend to define themselves in opposition to one another... sometimes your identity emerges through your interactions with your peers. That's definitely happened to Microsoft, and as a more than thirty-year-old company, it's going to change only slowly if at all.

Regardless, Microsoft really is its own technological world now. And this has its good points and bad points. Coming from the Java world, and from California where lots of my friends are vehemently anti-Microsoft, it's a bit bemusing to see it all with an outsider's eyes... plenty of my new colleagues have been here for decades, which is almost unimaginable to me. It's certainly part of my value here, that I've got recent experience with how things are on the Outside.

I can't be too specific, but there are quite a few areas where I feel like Microsoft's internal technical isolation is hindering them... particular tools that seem like a step backwards, or particular design problems where it seems like there just aren't quite enough people providing fresh ideas. The relative isolation of the Microsoft software stack can seem a bit... I don't know... lonely? The "us vs. them" thinking is hard to escape in the blogosphere, and it's such a polar choice -- either you're on Windows / .NET, or you're not. And if you are, you've got to pay to play -- at my last startup, we were a Linux and Java shop, partly because it got the job done and partly because it was free. (Though as one of my new cronies says, the people who won't pay aren't customers anyway, because how can you make a business out of non-paying customers? That's a very deep-seated belief in Microsoft-land, and you know, there's some truth to it.)

But on the flip side, there are some real advantages to owning all the code you could possibly need to run an entire industry of PCs. I've spent the last two months spinning up on LINQ, one of the coolest new features in C# 3.0. It stands for Language Integrated Query, and on the face of it it seems like syntactic sugar to let you write SQL-like code in C#. But it turns out that under the hood there's a lot more to it -- it's implemented via compiling language statements into expression data structures, that can then be rewritten, reparsed, and used to generate entirely different kinds of language output. It is very cool technology, very useful for creating domain-specific languages -- in fact, it's rather along the lines of my extensible language rant from a few months ago.

And it would not have been possible if Microsoft didn't completely own the C# and Visual Basic languages, and have the resources to come out with a new iteration of the language spec, and all the compilers and tools to support it, simply because they thought it was a good idea. Compared to the slowness of Java's evolution (how long has the closure spec been rattling around?), Microsoft's ownership is yielding real benefits to .NET programmers. (OK, so the closure spec is deeper and wider-reaching than C#'s lambda expressions, but nonetheless there are several intersecting features in C# 3.0 that are all needed to make LINQ work, and I don't see Java catching up very quickly.)

It's also pretty amazing to see the breadth of the expertise here -- my team happens to be pretty closely connected to Microsoft Research, which is teeming with world-class experts. If you look at the roster (Simon Peyton Jones, Don Syme, Erik Meijer, Galen Hunt, Nick Benton, Martin Abadi, Luca Cardelli... heck, search 'em yourself!), you'll see a whole lot of people who've driven the world of software forwards. Microsoft has a deep commitment to that goal, even if their not-invented-here, no-open-source mentality gets in the way sometimes. So it's exhilarating to be part of that mission.

Microsoft is a colossal company, and I'm fortunate that I've landed in a very ambitious and solidly supported team -- in fact, I can't think of any job I'd rather have in the industry. I'm feeling very lucky indeed, and I'm doing my best to get productive quickly -- this opportunity isn't going to come along again anytime soon!

And, that said, I'm obviously not doing very well on keeping to my blog schedule. Realistically this blog is going to slow down a bit, probably to more like once per month. Eventually -- once our team's incubation project goes public (knock on wood!) -- I'll hopefully have another blog on where I'll blog semi-officially about our technology. But this blog will be my personal property into the indefinite future. Stay tuned!

Monday, April 14, 2008

Only 20,000 Lines

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

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

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

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

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

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

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

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

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

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

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

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

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

Sunday, March 23, 2008

My New Job

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Monday, February 18, 2008

Simple Pieces, Dying Quickly

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

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

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

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

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

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

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

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

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

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

Tuesday, January 22, 2008

Inside Stories and Posted Mortems

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

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

For some reason, it seems there have been a whole slew of interesting ones on the net recently. Here they are:
  • Lambda the Ultimate cited this analysis of why Symbolics failed, as footnoted by Daniel Weinreb. Short story: too much technology, too little business focus. Still, interesting to get the inside view.

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

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

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

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

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

Friday, January 4, 2008

GWT2007 Video, Brain Teasers, and Semantic Metatheory

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

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

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

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

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

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

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

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

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