The world's most popular functional language, and what it teaches us

I realized today, when I read the phrasing of this LtU post, that my last two posts were too pessimistic about functional programming languages. There is, of course, at least one very popular functional programming language, and that is Emacs Lisp. Emacs Lisp is even widely used, at least a little bit, by countless programmers who never use any other functional programming languages at all. But this just confirms my original hypothesis that language popularity is driven almost entirely by platform, not by characteristics of the language itself.

More on programming language adoption, from Meyerovich and Rabkin

A little bit of vindication from Meyerovich and Rabkin; a quote I found particularly interesting (emphasis added):

A given prior language only occasionally correlated with the choice of a specific different language for the next project. Most notably, developers have high propensities to switch between Windows scripting and application languages, such as VBScript and C#. These languages also correlate with Microsoft web-development languages such as ASP. Such correlations are also visible in the results of Karus and Gall [12], who found groupings such as WSDL and XML being used in conjunction with Java.

Notably, we do not see significant exploration within linguistic families. There is a relatively low probability of switching between Scheme and LISP, or between Ruby, Python, and Perl. We conclude that developer movement between languages is driven more by external factors such as the developer’s background or technical ecosystem than by similarity of the underlying languages. This implies that language advocates should focus on a domain and try to convince programmers in that domain, instead of trying to convince programmers who use languages with semantic similarities to the new language.

Note that this clearly weighs against the Chaudhuri/Hicks hypothesis that education or unfamiliarity with functional programming is the "real problem". If developers tended to choose languages based primarily on comfort and familiarity, then we would expect them to switch more frequently among languages within a family than across families. Instead we observe the converse pattern: developers switch quite freely between programming language families whenever they need to do so in order to get work done in their domain.

In fact I think Meyerovich and Rabkin are too tentative in their formulation (maybe appropriate in an academic paper, but here we don't need to be so tentative). I think it is quite unlikely that developer background is a major deterrent to new language adoption. To repeat something I said the other day, developers routinely learn all kinds of weird, complicated, and frequently frustrating technologies in the course of their work. New programming languages are not fundamentally harder than all these other technologies, and programmers will learn them when they need to in order to get work done. The problem most unpopular programming languages face is simply that nobody needs them to get work done.

Overall, people who wish to change the mix of programming languages currently in use should spend less time extolling the virtues of their language (and criticizing competing languages!), and much, much more time developing platforms and libraries to make their language of choice a stellar tool in some concrete domain.

Is education to blame for functional programming's minority status?

Rice University's Swarat Chaudhuri asks (and attempts to answer) the perennial question: why isn't functional programming more popular? I have my own long-running theory about why programming languages become popular (or don't), but first let me dispute a couple of specific things in the linked post. Chaudhuri writes:

The same survey also showed that the factor that correlates the most with preferring and using a language is the availability of libraries. This is certainly behind the meteoric rise of, say, Python. However, it seems implausible that this factor is the primary reason why functional programming is unpopular. If it were so, the F# language, which allows functional programmers to utilize the entire .NET infrastructure, would be a mainstream language by now. There’s no indication it will be any time soon.

I think Chaudhuri dismisses the hypothesis far too lightly. Here are three obvious reasons why F# is not a counterexample:

• I have never programmed in F# (although I've done a little OCaml, and I gather they're almost identical), but my long experience with cross-language interoperability makes me suspect strongly that accessing nontrivial C# libraries from F# is nothing like using libraries written idiomatically in F#. It probably feels much more like calling through a foreign function interface — for example, like accessing Java classes from Jython, except possibly worse, because C# is not only a different language but a different programming paradigm.
• There are a large variety of inevitable network effects that come from using a single language within a project. If you are going to use mostly C# libraries in the .NET ecosystem, then a sensible project manager is probably going to choose to implement the project itself in C# rather than F#. This is especially true if libraries would force you to write a lot of your code in a semi-OO style within F# anyway.
• The .NET ecosystem has never had great mindshare in the communities where most of the "hot" industrial software development is happening: open source, backend software running in the datacenter, web development, and mobile development. Spend a little time walking around Silicon Valley and San Francisco, and see how many hackers are using Windows. If, somewhere in the sea of Macbooks, you even glimpse someone using a Thinkpad, there's an excellent chance that it's running Ubuntu. Conversely, if you see someone using Windows, there's an excellent chance they're a business suit from a large corporation (at startups, even the businesspeople use Macbooks).

  In fact, this was almost as true, last I checked (years ago, admittedly), even within the programming language research community. It is startling to me that a programming language researcher would look around, observe almost nobody they know hacking on Windows, and still ask why F# on .NET has not taken off.

  (Mono notwithstanding, my understanding is that Microsoft has never made it a priority to make .NET development a really great experience on non-Windows platforms. C# may have a lot of libraries, but Mono has always been a second-class citizen and there is an excellent chance that large swaths of the C# ecosystem depend on APIs (or, worse, subtle implementation quirks) specific to Microsoft .NET. I suspect any prudent project manager looking at the .NET ecosystem is unlikely to bet the farm on Mono.)

Next, Chaudhuri goes on to argue that the lack of university education in functional programming is to blame. Well, I won't deny that this is a contributing factor, but: few CS schools these days teach Ruby or Perl or Objective-C, yet those languages seem reasonably popular; few CS programs teach more than rudimentary use of version control, but git (i.e. the most complex version control system known to humankind) seems popular; few CS programs teach web frontend development frameworks or MVC or template metaprogramming or MapReduce (at least, not until recently, and certainly not in intro level classes), yet all those things and many more have managed to achieve significant adoption in industry.

In short, professional developers routinely adopt all sorts of complex technologies that are not taught academically. As cool as functional programming is, I just don't believe it's fundamentally that much weirder or harder than all the things modern developers use every day. If I had told you a decade ago that in 2014, a nontrivial number of professional programmers would be writing server applications and developer tools in hand-rolled continuation-passing style, you would have looked at me funny; yet here we are!

So, then, how do I explain the relative unpopularity of functional programming languages?

First, I would observe that most programming languages are not popular, period. People have invented tens of thousands of programming languages, and nearly all of them languish in obscurity. Only a very select few manage to achieve popularity. Given that functional programming languages are a minority of all languages, we should naively expect a minority of popular languages to be functional, just from random selection. The null hypothesis does a lot of work here.

Second, I would observe that nearly all popular programming languages seem to be hybrids. Consider a different programming paradigm: Smalltalk-76 was purely "object-oriented" (everything is an object, every object has a class, every class has a superclass, objects communicate strictly by sending messages), but its most popular descendants seem to be hybrids. For example, C++, Java, and Python are not purely OO.

Therefore, we should expect that a popular functional programming language would also be a hybrid. And indeed when you view things in this light, many popular languages today have adopted bits and pieces that were once viewed as features of functional programming, such as automatic memory management, first-class lexical closures, and parametric polymorphism. Functional programming purists no doubt view this ad hoc borrowing as hopelessly inadequate cargo-cultism that misses the fundamental point of functional programming, but it is nevertheless exactly what we should expect from the gradual popularization of functional programming. In the essay Real Programming in Functional Languages (1982), J. H. Morris Jr. memorably wrote:

Functional languages as a minority doctrine in the field of programming languages bear a certain resemblance to socialism in its relation to conventional, capitalist economic doctrine. Their proponents are often brilliant intellectuals perceived to be radical and rather unrealistic by the mainstream, but little-by-little changes are made in conventional languages and economies to incorporate features of the radical proposals. Of course this never satisfies the radicals, but it represents progress of a sort.

I therefore claim that some small part of FP's "unpopularity" is apparent rather than real.

However, I admit that even the combination of the previous two explanations does not seem sufficient to explain why no primarily functional programming language has become the default way to program in a popular domain. But I don't think education is enough explanation either.

So I have to fall back on my primary theory: I maintain once again that languages reach popularity via platforms.

Thus, for example, Swift will probably be a big deal, independent of almost any qualities it has as a language. Apple is the dictator for the iOs platform. It seems likely that Apple will eventually make Swift the default way to program on iOs. Therefore, Swift will become popular, despite the fact that zero people graduating from university computer science programs in 2014 were taught Swift in school.

If functional programmers want FP to be a bigger deal, then my personal recommendation is:

• develop an industrial-quality platform for doing something that large numbers of developers really want to do, and
• evangelize the hell out of it, with a seriousness matching that of professional DevRel teams: videos, tutorials, books, portfolio-quality demo sites in GitHub, reliable turnkey commercial hosting infrastructure if need be, etc.

Web development is one good candidate domain, since (a) web development is a clusterfuck and thus ripe for improvement; (b) web developers are culturally eager to try the new hotness (in fact, arguably a little too eager); (c) you can reach a large audience without requiring any hard technology transitions of users since everyone has a web browser.

Look, for example, at how Rails lifted Ruby from relative obscurity to the default way (at least for a little while) that startups built websites in the Valley. The web framework space is more crowded today, but the field for new ones still seems fairly open, as long as you bring something new to the table. For example, focusing on realtime interaction seems to have bought Meteor a lot of buzz, despite the fact that its backend is currently built on a broken database.

Personally I think there is an opening for a "better PHP" — for all PHP's WTF/lol, if you study Keith Adams's talk "Taking PHP Seriously" (slides) it is clear that the PHP runtime does a few things right that no other platform currently does. Of course, at this point, you're probably laughing at the notion that a bunch of functional programming mandarins is going to successfully devise something for the median PHP programmer to pick up and use. But that is the type of work that might make functional programming the default way to do stuff.

---

EDIT: For more evidence that Chaudhuri and Hicks are wrong, see Meyerovich and Rabkin's study on language adoption.

---

p.s. Bizarrely, in a comment on Chaudhuri's post, Bob Harper (whom I have tremendous respect for) claims that Java doesn't have a conditional expression. What? Am I missing something?

  Object x =
    boolExpr1 ? valExpr1 :
    boolExpr2 ? valExpr2 :
    boolExpr3 ? valExpr3 :
    defaultexpr;

Is this not just cond with somewhat uglier syntax?

Tree structure and comment threads (a brief observation)

It has been claimed that flat, linear presentation of comments appears to work better for humans than tree-structured comment threads. Without getting too deeply into whether this is true (and if so, why), I would like to offer an observation.

Conversation is never a tree; it is a general directed acyclic graph. In reality, in the commenter's mind, every comment potentially implicitly responds to an arbitrary subset of preceding comments, not to a unique parent and its chain of unique transitive ancestors.

Tree-structured threading — sometimes (erroneously!) called "true threading" — artificially imposes a tree structure on this graph. Flat, linear comment systems do not: each comment appears after all those that precede it topologically in the DAG, and it is up to the reader to reassemble the DAG based on the comments' contents.

It is true, of course, that flat comment systems fail to reify all DAG edges as explicit metadata. However, the nature of these edges is quite subtle and capturing them all explicitly is intractable. Often a comment "responds" to previous comments in indirect ways — for example, simply by omitting some aspect of the argument that has been covered by a previous comment.

(Prompted by a TC article linked off HN.)

A simple handwave that makes The Matrix tolerable for the scientifically literate

Suppose that controlled fusion power requires real-time control computations which can be much more efficiently implemented in neurological hardware than in silicon.

(That Second Law of Thermodynamics thing was bothering the hell out of you, wasn't it?)

Note that neurological hardware really is exceptionally power-efficient for certain classes of computations. Common estimates of the human brain's power consumption are 20-25 watts; this is roughly the wattage of a Mobile Intel Core i5 processor, which (as far as we know) appears to be a much less powerful computer for many purposes. By contrast Watson runs on 90 IBM Power750 servers, filling ten racks, whose power draw is something like 80 kilowatts. In other words, Watson consumed about four thousand times more power than either of its meat-based competitors.

Here in reality, I think it's unlikely that any fixed class of computations can be efficiently implemented in neurons but not in silicon — see Carver Mead and his academic descendants' work on analog silicon circuits. But positing that such computations may exist seems within the realm of acceptable science-fictional handwaving.

---

UPDATE: Yes this is close to the standard handwave that the humans are being kept as computing devices, not power sources. But I think you need to draw the connection explicitly to power generation; otherwise there's just too much narrative in the film and animated shorts that makes no sense.

UPDATE': Never mind, I just remembered Morpheus's exact wording from the first film's voice over and I don't think it's salvageable. Oh well.

On the verbosity of Java generics and related type systems

So, recently T. B. Lee tweeted:

Java's generics syntax feels really clumsy. Are there other (strongly typed) languages that do it better?

I replied as best I could in 140 characters while riding a crowded Muni bus home after work, but I mangled the explanation, so I think I should rectify this.

First, it is worth comparing Java generics to other languages that have parametric polymorphism. For example, consider ML (and more generally the Hindley-Milner family of languages). In ML, you don't need to write down types most of the time, because of type inference. Whereas in Java you might write:

<K, V> LinkedList<K> keysAsList(HashMap<K, V> aMap) {
  LinkedList<K> result = new LinkedList<K>();
  for (K key : aMap.keySet()) {
    result.add(key);
  }
  return result;
}

in OCaml you can write:

let keysAsList aMap =
  Hashtbl.fold (fun key _ rest -> (k::rest)) aMap [];;

Notice that although we had to annotate all the Java variables with types, there's not a single type annotation in the OCaml code (Hashtbl.fold is the name of a function qualified by its module name; it is not a type annotation). But OCaml is statically typed nevertheless.

So, one might ask, what gives? Why can't you just add type inference to Java?

Well, the short answer is that typechecking Java generics is a fundamentally harder problem. ML has only parametric polymorphism; Java has both parametric polymorphism and subtype polymorphism (i.e. the object-oriented kind). It is perhaps not obvious why this makes things hard until you learn that B. C. Pierce proved in 1992 that bounded quantification in F_≤ (pronounced "F-sub") — a formalization of the most straightforward and general combination of subtyping and parametric polymorphism — is undecidable.

In other words, in F_≤ it is possible to write programs for which the type checker would not terminate. This is generally held to be a bad thing (n.b. I disagree with the prevailing opinion, but that's a discussion for another day), so over the next decade or so there followed several papers by Pierce and others attempting to isolate calculi weaker than F_≤ with type systems that were both usable and decidable. The most practically relevant outcome of this work was Featherweight Java, which provided the formal foundation for (most of) Java generics. C#, Scala, etc. build on this line of work, although in Scala's case fairly indirectly.

What does all this have to do with type inference? Well, nothing directly. But for any given level of type system expressiveness, full type inference is at least as hard as type checking. And the type checking problem for Java with generics already lives close to the undecidability ceiling (in fact, the decidability of Java generics with wildcards is, AFAIK, still an open problem; proving this sort of stuff used to be a hot research subject but I think everyone's gotten bored of object calculi and moved on). Oh, and I should mention that many of the best minds in academic language design have thrown themselves at the parametric polymorphism + subtyping + inference problem at one time or another, and come up empty. Now, none of this is hard proof that much richer type inference for object-oriented languages with generics is impossible, but it all hints strongly in this direction; at a minimum any such system is likely to be exceptionally intricate and difficult to prove sound.

So, basically, I believe that it is unlikely that anyone will come up with a fundamentally more concise type system for a programming style that combines (1) objects, (2) generics, and (3) static typing. At best, people will fiddle around on the margins — using different punctuation, for example, to denote type parameters, or making other parts of the language more terse to compensate.

That said, although general type inference seems hopeless, there are clearly some things that could make Java's generics more syntactically lightweight in certain common cases. For example, it would be trivial to infer the type of a variable at any declaration site with an initialization expression. C# and Scala appear to do some of this.

How to design a popular programming language

This has been kicking around in my brain for at least half a decade, and if you know me well then I've probably spoken it aloud in your presence; so it's high time to get it down in writing. Here is my Grand Unified Theory of Programming Language Adoption. There are three steps:

1. Find a new platform that will be a huge success in a few years.
2. Make your language the default way to program on that platform.
3. Wait.

That is all. Note that none of the above steps has anything to do with the language design itself. In fact, nearly all popular languages are terribly designed. Languages become popular by being the "native" way to program a certain kind of system. All of history's most widely used programming languages fit this model — Fortran (scientific programming), C (Unix), C++ (MS Windows), JavaScript (web pages), Objective-C (Mac OS X), . . .

Or, in fewer words: Languages ride platforms to popularity.

Why is this so? Well, to a first approximation, no piece of software ever gets rewritten in another language; and once a critical mass of software for a platform has been written in one language, nearly all the rest will follow, for two reasons:

• Nobody has figured out how to make cross-language interoperability work well.
• The network effects from language adoption are immense. Programming is, despite appearances, a deeply social profession. To write successful software quickly, you must exploit the skills of other programmers — either directly, by hiring them, or indirectly, by using library software they've written. And once a language becomes the most popular in a niche, the supply of both programmers and libraries for that language rapidly accumulates to the point where it becomes economically irrational to use any other language.

In fact, I claim that in all the history of programming languages, no language has ever successfully unseated the dominant language for programming on any platform. Instead, a new platform gets invented and a new language becomes the "founding language" for that platform.

Well, OK, there are exactly two exceptions: Java and Python. It took me a while to figure out what happened in those cases, and the answers I came up with were surprising (to me).

Java is anomalous because although it is widely used in its primary domain (Internet application servers), it is not predominant, the way that e.g. C++ is predominant in writing native Windows GUIs. My explanation is that the web architecture has a uniquely high-quality interoperability protocol in the form of HTTP and HTML(/XML/JSON/...). Hey, stop laughing. HTTP and HTML fail all kinds of subjective measures of elegance, but they succeed in isolating clients and servers so well that it is economically viable to write the server in any language. In other words, as unbelievable as it sounds, HTTP and HTML are the only example in history of cross-language interoperability working really well.

I'll abandon this explanation if I can find, in all the annals of computing, another protocol that connected diverse software components as successfully as HTTP and HTML. The only things I can think of that come close are (a) ASCII text over Unix pipes or (b) ODBC, and neither of these provide nearly the same richness or connect components of similar diversity.

Python is anomalous because rather than riding a new platform to success, it simply seems to be displacing Perl, PHP, etc. in the existing domains of shell scripting, text processing, and light web application servers. My explanation is that Python appears to be the only language in history whose design was so dramatically better than its competitors' that programmers willingly switched, en masse, primarily because of the language design itself. This says something, I think, both about Python and about its competitors.

Incidentally, this theory predicts that all the new(ish) programming languages attracting buzz these days — whether Ruby, or Scala, or Clojure, or Go, or whatever — will fail to attract large numbers of programmers.* (Unless, of course, those languages attach themselves to a popular new platform.)

---

UPDATE 2010-05-15: Reddit and HN weigh in.

---

*Which is fine. Very few languages become hugely popular, and in fact nearly all languages die without ever seeing more than a handful of users. Being either influential (so that later languages pick up your ideas), or even merely useful to a significant user population, are fine accomplishments.

Computer science and the iPhone developer agreement

Full disclosure: I work for Google. However, this blog reflects my personal opinions only.

Programming and computer science are not synonymous, but obviously the two are deeply intertwined. The fundamental activity of programming is the construction of abstractions. Programming language design and implementation is one of the fundamental forms of abstraction building. It is central to the field, and has been so nearly since its inception. One of the oldest and most important research conferences in computer science is named Programming Language Design and Implementation.

This suggests a particular understanding of what Section 3.3.1 means. Section 3.3.1 says: "Thou shalt not build abstractions other than those we prescribe." It bans one of the fundamental activities of programming.

This would be a mere curiosity, except for Apple's unusually influential position in the computing industry. All trends point towards mobile devices* becoming much more pervasive than all other general-purpose computing devices. Indeed, the combination of mobile and cloud computing may someday replace all other user-visible hardware except what's needed to support input and output (screens, cameras, etc.). And Apple has the credible goal of becoming the preeminent mobile device provider, setting standards for the industry and defining the entire computing experience for a huge swath of future computer users.

Section 3.3.1 therefore constitutes a direct attack on computer science, delivered by a powerful and well-funded organization that aims to transform laypeople's interface to the field. As long as 3.3.1 stands, for a computer scientist to purchase an iPhone or iPad is akin to a biologist purchasing a textbook that advocates against teaching evolution. Full stop. Go ahead and do it if you can't resist the shiny, but understand the moral weight of the decision you're making.

I can already hear people ready to trot out the standard roster of excuses. Hit the comment box if you want, but realize that I've anticipated the common objections and the only thing stopping me from preemptively rebutting them all is the fact that I'm moving soon and I have a huge number of boxes to pack. To pick just three examples:

Q: "The iPad isn't for people like you. Why do you care?"
A: "This post isn't for people who don't care. Why are you reading it?"

Q: "Apple has a right to do whatever it wants with its platform. If you don't like it, you shouldn't use it."
A: "Thank you for agreeing with me."

Q: "You can program whatever you want in HTML5 and access it through Safari."
A: "Yes, the web is an open platform, which Apple fortunately does not control.** I'm talking about Apple's rules for programming on the platform that it does control."

---

*A.k.a. "phones". Incidentally, I think the British slang "mobile" is more elegant and generalizes far better any of the {cell,smart,super,...}phone terms that are used on this side of the pond.

**Although I will remark that it's naive to imagine that a platform can be preeminent for very long without influencing the market of content and applications to which non-participants in the platform regime have access. There's a reason Hulu used to work on Flash only. But that's a post for another day.

J. Blow: Games as Instruments for Observing Our Universe

You might be dissuaded from listening to this talk by Jonathan Blow because it's distributed as a PowerPoint presentation and a couple of MP3s, or else because it's nominally about the much-maligned artifacts of human civilization commonly called "video games".

You would be making a mistake.

Jonathan Blow is a minor genius, and this talk is worthy of attention from anyone interested in science or art or really any creative activity. I have previously mocked video game apologists for viewing games as a failed (or at least not-quite-successful-yet) aspirant to "interactive cinema" — the teleological destiny of gaming, by this aesthetic, being the creation of an action movie in which You! Are! The! Hero! — and Blow is perhaps the most articulate proponent of the opposite view.

E. W. Dijkstra famously said that "Computer Science is no more about computers than astronomy is about telescopes." He was suggesting that there are properties of the universe — viz, certain mathematical truths — that can only be inspected by studying algorithms, which humans can only do through the construction of computing devices. Per Dijkstra, the devices are not the point, or at least not the only point.

In practice, most of computer science amounts to cleverly engineering around messes that humans have created; but sometimes you do glimpse something which appears to be a property of the broader universe. This is a point that is mostly unappreciated by non-computer-scientists, who assume that the essence of computer science is fiddling around with gadgets.

Similarly, the word "game" applies, in the broadest sense, to any system of rules with which one or more agents interact. Blow's basic point is that the generative systems of rules that we call games can be profound devices for exploring truth, just like the generative systems of rules we call algorithms. But that's a pretty inadequate summary of the talk. You should really listen to the talk itself.

(The Q&A is longer and somewhat more inside-baseball w.r.t. the Game Industry as it actually exists today, and therefore less interesting overall, although there are some good bits there too.)

Pro tip for ChromeOS punditry

Full disclosure: I work for Google, although this blog reflects my personal opinions only.

Please don't pontificate about ChromeOS until you grok the long-term implications of Web Storage, Native Client, Open3D/WebGL, Courgette, and a large local disk cache. Oh, and, of course, Moore's Law.

And if you can't work out the implications, at least talk to someone who can, before you hit the "Post" button. You might still think that ChromeOS is a bad idea, but at least you'll be critical in a more clueful way.

Dynamic dispatch is just higher-order programming

Wow, this is pretty terrible coming from a Haskell programmer (via HN):

Dynamic dispatch is a scary programming technique. When you call a virtual method, you never know what might happen. This makes is [sic.] difficult to reason about such code, and code that is hard to reason about is hard to maintain.

This is true in the exact same sense that when you implement a higher-order function, "you never know what might happen". Here is a naive implementation of map in Standard ML:

fun map f [] = []
  | map f (x::xs) = (f x) :: (map f xs)

f could be bound to anything! OMG WTF BBQ!

Likewise here is a Java implementation of printList:

void printList(List aList) {
    for (Object o : aList)
        System.out.println(o.toString());
}

o.toString() could dispatch to anything! OMG WTF BBQ!

Well hold up man, let's try that in ML:

fun printList _ [] = ()
  | printList toString (x :: xs) =
    (print ((toString x) ^ "\n");
     printList toString xs);

Oh that's so much better isn't it. Or not. Basically, you will note that we had to type toString three times instead of once to achieve roughly the same effect.* Note also that this function only works over homogeneous lists; if you want a heterogeneous list, you'll have to define a union type and pack/unpack it yourself.

Object-oriented programming is a form of higher-order programming wherein related data and operations are tightly bound to each other, thus freeing you from the pain of having to wrap them up yourself, thus making it exceptionally convenient to pass data and functions together. Or, in other words, OO programming is just a functional programming idiom with lots of very convenient syntactic and semantic sugar on top**.

Now, the OO community has plenty of bad code and bad guruism bouncing around. Maybe there's somewhat less of that in the functional world. But IMO that's largely explainable by the fact that there are vastly more working OO programmers and vastly more OO code modules than functional equivalents. If the Haskell or ML community were as big as the Java community, there would be just as much terrible higher-order function spaghetti as there is terrible inheritance spaghetti today.***

---

* Q: Wouldn't the version using Haskell and type classes be as compact as the OO version? A: Maybe, but you'll still have to restrict the function's domain to homogeneous sequences of StringConvertable instance values. Once I hand you a heterogeneous list, you're back in the land of passing toString and packing unions. The only way to do this right is to introduce existential pack/unpack into your language, which basically amounts to introducing a slightly crippled object system with additional syntactic overhead.

** In particular, making super sends and self sends work correctly without OO sugar gets messy. OTOH, conversely, the object-oriented programming languages in common use make certain other kinds of functional programming idioms somewhat baroque — for example, Java's lack of a compact syntax for anonymous functions is a huge pile of Lose — but that's a discussion for another day.

*** In fact, I strongly suspect that with a fair number of kids today thinking that Haskell is the new hotness, that community's in for a rude awakening as they realize that Haskell's going to require style guides and "Haskell annoyances" books and assorted baroque frameworks in order to allow programmers of average ability to assemble software of similar complexity to that commonly assembled in Java today.

Notes on [Hahn Litan 06]: Network Neutrality Part 1: Requests For Comments

[Full disclosure: I work for a large technology company that presently lobbies for network neutrality legislation. My personal views on network neutrality predate my employment, and are independent of it. Everything posted on this site reflects strictly my own thinking, and is not endorsed, sponsored, or approved by my employer in any way. Finally, this should go without saying, but nothing I write here reflects any confidential or proprietary information from my employer.]

The generally excellent Tim Lee @ TLF today writes two posts reacting to a recent white paper on network neutrality by R. W. Hahn and R. E. Litan of AEI/Brookings[0] (also to be published in the Milken Institute Review).

As I read it, Hahn and Litan's paper makes the following major claims. First, they claim that the Internet's not neutral, and never has been --- hence the title, "The Myth of Network Neutrality...". Second, they claim that existing proposed legislation to codify network neutrality into law would do more harm than good. Third, they claim that there are economic benefits to tiered pricing for network-layer "quality of service" (QoS).

The major weakness of the paper is that the authors do not understand Internet technology, and they seem to have consulted zero experts who do. As a result, they make many elementary errors of fact, rendering their argument unsound and their conclusions unsupportable. I am rather too tired tonight to go through all the errors at once, so I will delineate only a few in this post. Expect at least one follow-up post sometime in the next N days.

On Requests For Comment

Hahn and Litan cite several historical RFCs in support of the following conclusion:

. . . early writings on the Internet indicate that prioritization has always been considered an important design characteristic for TCP/IP --- sharp contrast to the romantic ideal of the end-to-end principle.

This post will examine how the authors attempt to support this claim, and how they fail.

As an aside, before I dive in, it is important to recognize that RFCs ("Requests For Comments") are not necessarily authoritative design documents for the Internet. RFCs have no binding force except insofar as many engineers independently decide to follow them --- a sort of community-based moral suasion, given economic force by network effects. Furthermore, RFCs vary widely in purpose: they may be arcane memos warning about one-time events, ideas of untested merit from the dustbin of history, cutting-edge research that may or may not ever be adopted, or even jokes.

Only a few RFCs describe protocols that have been widely implemented and deployed on the Internet, and even those are almost always provisional.

On to the meat. Hahn and Litan cite four RFCs. Tim seems to have missed read the short version of Hahn and Litan's paper, which lacks RFC citation numbers, but they're in the footnotes of the long version:

• RFC 675: Specification of Internet Transmission Control Program
• RFC 791: Internet Protocol
• RFC 1633: Integrated Services in the Internet Architecture: an Overview
• RFC 794: Pre-emption

The first two are (ancestors of) bona fide, widely-adopted standards. The third is a position paper by a group of highly respected networking researchers. So, those three RFCs are not jokes, although the first was superceded by RFC 793 before ARPANET even became the Internet, and the third has never, to date, been deployed on the Internet at all. Then there's the fourth, which does not even describe the Internet, but another network entirely; so it is not exactly a joke, but it's pretty funny to see it cited as evidence of the Internet's principles.

So, here are the mistakes the authors make w.r.t. each of these RFCs in turn. Note that I share Tim's frustration that the authors have not, in most cases, provided either page numbers or quotes, so in some cases I have had to interpolate the exact citation.

RFC 675

This RFC describes an early version of TCP, one of the two fundamental protocols of the Internet. The authors state that Vint Cerf "explained that outgoing packets should be given priority over other packets to prevent congestion on the ingoing and outgoing pipe" [HahnLitan06, p. 4]. I believe the authors are referring to section 4.4.1., as the word "incoming" only appears in a handful of places in this RFC, and only once in any context related to priority:

From the standpoint of controlling buffer congestion, it appears better to TREAT INCOMING PACKETS WITH HIGHER PRIORITY THAN OUTGOING PACKETS.

The all-caps are in the original. Hahn and Itan appear to have the capitalized part exactly backwards, which doesn't speak well of their conscientiousness, or that of the editors at the Milken Institute Review. However, that's not the deep problem. The deep problem is that Hahn and Litan do not understand what TCP is, and what is being described here.

First of all, TCP is an end-to-end protocol. Period. Every single normative sentence[1] in RFC 675 describes an operation that occurs on an end-host, not on a router internal to the network. The above sentence describes how an end-host should prioritize processing of packets in buffers inside its networking stack. It is, in other words, a hint to operating system implementors who want to write TCP/IP stacks. It has nothing whatsoever to do with "the network" prioritizing packets.

If this sounds like an abstruse distinction, imagine "the network" as the US Postal Service, and an end host as your home. The operating system's network buffer is your mailbox. What the above sentence is saying is that before you stuff outgoing mail into your mailbox, you should take your incoming mail out of your mailbox. It is saying nothing about whether the US Postal Service should pick up your mail in one order or another.

Does RFC 675 present a "sharp contrast to the romantic ideal of the end-to-end principle"?

It does not.

RFC 791

This RFC describes IP, the other fundamental protocol of the Internet. Again, the authors do not give exact quotes or specific citations, but they state:

A 1981 Request for Comments explained that precedence—a measure of importance of the data stream—could be used as a means of differentiating high priority traffic from low priority traffic.

Now, RFC 791 does contain some discussion of precedence. A "packet" is a little bundle of bits that a network shuffles around. Among other things, a network protocol must specify the form of its packets, just as the US Postal Service demands that envelopes be addressed and stamped in a particular manner. IP specifies a packet format with 8 bits reserved for the "Type of Service" field, which can technically be used to indicate the priority of a packet.

The motivation for this is as follows. Back in 1981, before the Internet emerged as the winner in the ecology of network designs, networking researchers were experimenting with different kinds of networks to run IP on. Some of those networks prioritized packets based on how the packets described themselves. It was believed that IP packets should reserve some space so that these networks could stash priority information in them. This reserved space is the "Type of Service" field.

RFC 791 does not describe how networks would use the "Type of Service" (TOS) field. That is specified in RFC 795, which describes how TOS is used by the AUTODIN II, ARPANET, PRNET, and SATNET networks.

None of those networks was the Internet. They were networks for military communications in the 1960s and '70's. None of them exists today. Now, as every geek knows, ARPANET was the ancestor of the Internet; but not all the features of ARPANET were carried over to the modern Internet. In particular, modern Internet routers do not use the TOS field, at least not as described in RFCs 791/795. Eliding many gory details, DiffServ (a.k.a. DSCP) supercedes TOS, and it is used for traffic shaping within individual subnets, not on the Internet as a whole.

In short, the section on precedence in RFC 791 describes a mechanism that is not, and has never been, used to prioritize packets on the Internet.

Does RFC 791 show that "prioritization has always been considered an important design characteristic for TCP/IP"?

It does not.

RFC 1633

RFC 1633 is, as noted above, a position paper by a group of distinguished networking researchers: R. Braden, D. Clark, and S. Shenker. In this RFC, Braden et al. argued (in 1994) that at some point in the future, a QoS mechanism should be adopted into the Internet's fabric.

Considered as a technical question, this is a controversial argument, but not a ludicrous one. I could discuss it at some length (and, if I ever get my act together, perhaps someday I will do so in this space), but for the moment I must focus on this RFC's relevance to Hahn and Litan's white paper. Hahn and Litan cite this as an "early writing on the Internet" that indicates that "prioritization has always been considered an important design characteristic of TCP/IP". There are at least two problems with this reading.

First, a document dated 1994 cannot be an early writing on the Internet. In June 1994, the Internet had not become a commercial mass phenomenon --- that had to wait for the spread of Netscape --- but it had existed for almost a decade. And, indeed, RFC 1633 sketches a speculative protocol extension to the existing Internet that has not, to date, been adopted by anybody.

Second, and more importantly, here are a few direct quotes from RFC 1633, Section 2:

The fundamental service model of the Internet, as embodied in the best-effort delivery service of IP, has been unchanged since the beginning of the Internet research project 20 years ago [CerfKahn74]. We are now proposing to alter that model . . .

. . . Internet architecture was [sic.] been founded on the concept that all flow-related state should be in the end systems [Clark88].

Designing the TCP/IP protocol suite on this concept led to a robustness that is one of the keys to its success.

In short, the authors state exactly the opposite of what Hahn and Litan would have us adduce. End-to-end flow control was part of the "fundamental service model of the Internet" and "one of the keys to its success".

Does RFC 1633 show that the Internet presents "a sharp contrast to the romantic ideal of the end-to-end principle"?

It does not.

RFC 794

Best for last. This one's particularly hilarious. Hahn and Litan quote this RFC at length --- one of the few times they do so:

In packet switching systems, there is little or no storage in the transport system so that precedence has little impact on delay for processing a packet. However, when a packet switching system reaches saturation, it rejects offered traffic. Precedence can be used in saturated packet switched systems to sort traffic queued for entry into the system. In general, precedence is a tool for deciding how to allocate resources when systems are saturated. In circuit switched systems, the resource is circuits; in message switched systems the resource is the message switch processor; and in packet switching the resource is the packet switching system itself.

That's a fine excerpt from RFC 794. The problem is that RFC 794 describes AUTODIN, not the Internet. Do you use AUTODIN? Me neither.

Vint Cerf was a networking researcher. He and Bob Kahn tried lots of things. The fact that some of his projects used packet prioritization has almost no relevance to the fact that the one project that succeeded wildly was a neutral network with end-to-end flow control.

Does RFC 794 give us an "early writing on the Internet"? Does it show that "prioritization has always been considered an important design characteristic for TCP/IP"? Does it demonstrate the Internet's "sharp contrast to the romantic ideal of the end-to-end principle"?

It. Does. Not.

Conclusion

The above points become apparent to anybody of moderate technical knowledge who attempts to read the RFCs carefully and understand them. RFCs were frequently written by Ph.D.'s, but they were not written for Ph.D.'s; they were written for hackers.

It is, perhaps, understandable that Hahn and Litan --- two economists --- could not understand these RFCs in detail. However, they have misread the RFCs so completely that it is almost inconceivable to me that they could have consulted someone with the necessary background.

They construe RFC 675 --- a description of an end-to-end transport protocol --- as a blow against the end-to-end principle. They construe (portions of) RFCs 791, 1633, and 794 --- documents which do not describe the Internet --- as documents describing the foundational principles of the Internet. In some cases, as with 1633, they cite these documents in support of a claim that is specifically refuted by plain text in the document.

How could this happen?

I would guess that Hahn and Litan's "research" process went something like this. First and foremost, they knew that they wanted to produce a paper arguing against network neutrality regulation. They had heard somewhere about these "RFC" things, and they knew that Vint Cerf, one of the current big pro-neutrality voices, had written a bunch of them. So, they decided to go search for the words "precedence", "priority", and "quality of service" in the old RFCs. To their great delight, these words appeared in some RFCs by Cerf himself, and by other prominent networking researchers. Alas, these technical documents turned out to be pretty tough to interpret if you've never written a line of networking code in your life. However, never mind meaning or context: knowing their "research" community --- economists predisposed to disliking regulation --- they figured they could get away with fudging the citations anyway, because none of their peers would understand the RFCs either. Most of them wouldn't even bother to try. So they went ahead and wrote their paper, and got it accepted to a little economics review.

Now, I understand that this is a pretty nasty thing to say. Given Hahn and Litan's long and distinguished careers in academia and public service, I would like to believe something else, but I'm having trouble doing it. I mean, look at the evidence above. They have clearly leaned upon the facts, as the proverb goes, as a drunkard leans upon a lamppost: for support, not illumination.

At best, I can understand this behavior as a combination of ignorance and arrogance: maybe the authors believed their vast experience in parsing documents in economics and law made it unnecessary to consult experts in computer science ("Not even a real science --- it has 'science' in the title!"). At worst, though, one could argue that it's a mixture of intellectual dishonesty and irresponsibility.

---

In Part 2 (if I ever manage to write it): Hahn and Litan's errors regarding VPNs and World of Warcraft.

---

[0] I normally ignore anything that comes out of AEI, as it tends to be 99% worthless on technology issues, and it's more work than it's worth to sort the wheat from the chaff. Based on Tim's decision to post about this paper, I waived my normal skepticism, and was pretty badly disappointed. Sigh. I have adjusted my priors, as the Bayesians say.

[1] By "normative sentence", I mean one stating a property that a TCP implementation must have in order to be rightfully called a TCP implementation. Now, like most RFCs, 675 is not an ultra-terse mathematical specification, but a document intended to be a useful and readable guide to practical implementors. So, it gives some background about routers and such to provide the reader with context. But as Cerf and Kahn state, TCP makes almost no requirements of the underlying network beyond its ability to carry bits, which is one reason why it works over substrates ranging from circuit-switched telephony (dial-up Internet) to the postal service.

Market share, market power, and network neutrality

J. Gattuso writes about a recent proposal by James DeMint (R-SC):

Submitted as an amendment to the telecom bill now being marked up by the Senate Commerce Commitee, DeMint’s proposal would make it unlawful to “prioritize or give preferential or discriminatory treatment in the methodology used to determine Internet-search results based on an advertising or other commercial agreement with a third party.” Any person found in violation would face a maximum fine of $5 million or imprisonment for up to one year.

...

For the record, this is a terrible idea. And, I’m willing to bet that Sen. DeMint thinks so too. Instead, the amendment seems intended to underscore Google’s uncomfortable position in the net neutrality debate. While the company has spearheaded the call to for net neutrality for telephone and cable firms, its own practices — and power — mirrors that of those companies.

...

Google’s business model to a large degree is based on tiering — providing preferred ad placement for those who can pay for it. Its clearly not a system where anybody “no matter how large or small” has equal access. Its based, like it or not, on money.

None of this matters, says Google. There’s a big difference, it says, between its actions and those of the "phone and cable monopolies." But is there? The phone companies and cable companies do have an overwhelming share of broadband connections. But market shares in the search engiine market aren’t dramatically different. Three firms — Google, Yahoo and Microsoft — account for 84 percent of all searches. Ninety-five percent of “toolbar” searches are by two firms, Google and Yahoo. Of course, this companies aren’t in lockstep — they compete among each other. And they may be challenged by newcomers, who now have small market shares. Yet, the same arguments, when raised regarding broadband networks, are rejected.

This certainly doesn’t mean that Google should be regulated. Or that it will be. Yet, there are some who have seriously proposed the idea. And once lawmakers start imposing mandates, its hard to predict where they will stop. Once network owners are regulated, it simply wouldn’t be that big a step to regulate other Internet players, starting with the biggest. Sen. DeMint’s proposal may not be meant to be taken seriously. And this week it won’t be. But someday, thanks in part to Google, it could.

First, let us dispose of the "universal slippery-slope argument" against regulation, which goes like this: "If you regulate X, what's to stop you from regulating Y?" This statement can apply to arbitrary X and Y, and is therefore not a serious argument against anything. Gattuso does not make exactly this argument (though he slides perilously close in the final paragraph), but stating the universal version illustrates the obligations that Gattuso must discharge in order to make his case.

A reasonable slippery slope argument must place a bound on X and Y, and then make the case that this bound is the necessary distinction. In other words, you need to say:

1. "If you admit that X is regulable because X satisfies the property P, then Y is also regulable because it also satisfies P."
2. "P is the only reasonable distinction in this case."

The second clause is necessary because otherwise, your opponent can simply propose a different (and better) bound P, which excludes Y while including X. In the course of his essay, Gattuso proposes the following two P in order to substantiate his slippery-slope argument:

• P(X) = "X is an 'Internet player'"
• P(X) = "X has sufficient market power that it is not subject to strong competitive pressures."

I think it is transparently obvious that the first of these is not a relevant distinction; "Internet players" is a category so broad and vague as to be analytically useless.

However, the second bullet point deserves some consideration, because it is also the distinction that network neutrality advocates propose. Distilled to its essence, Gattuso's argument is as follows:

1. The justification for regulating telecom companies is that their market power insulates them from competitive pressure.
2. Google, Yahoo, and Microsoft have large market share.
3. Therefore, Google, Yahoo, and Microsoft also have market power insulating them from competitive pressure.
4. Therefore, by the same reasoning, one should be able to regulate search engines.

Notice that between steps (2) and (3), the above argument jumps from market share to market power, effectively conflating the two. But market share is, at best, an indirect proxy for market power. Market power depends on a number of factors, but in the end two overarching factors dominate:

• Barriers to entry: How hard is it for competitors to get started in the market?
• Switching barriers: How hard is it for buyers to switch between sellers of the good in that market?

These are the two factors that determine how easily somebody can start competing with you, and how easily you can lose your customers to the competition. If anybody can start up a competitor and all your customers can flee overnight, then you're in a competitive market. If it takes many man-years of labor, political connections, and billions of dollars of capital to start a competitor, and it will cost your customers a lot of time and money to switch, then you're not in a competitive market.

High market share does not necessarily mean that a seller has market power. Google might be the most popular search engine because it has tremendous market power which insulates it from competition, or it might be the most popular because it simply provides a better product in an efficient and competitive market.

So, let's consider the barriers to entry and switching barriers in the search engine market, and in the telecom market.

Stop laughing.

OK, perhaps some of you are not already laughing, in which case I will have to explain it. If you want to start a new search engine, all you have to do is download Nutch, hire a programmer to customize it for your needs, and put it on the web. If you want to switch from one search engine to another, all you have to do is type a different URL into your location bar.¹

Of course, I'm being slightly disingenuous here. If you want people to use your search engine instead of the competition, it will have to be significantly better, in some way, than what people use today. And that will be pretty hard. But that's also a feature of competitive markets, so that does not, in itself, indicate market power.

Contrast this with broadband Internet access. Let's take barriers to entry first. How hard would it be for me to start a new broadband Internet provider that competes with cable and DSL? I don't know the details, but I'm pretty sure it would involve either (1) enormous capital outlays to dig trenches and lay down wire, and also possibly schmoozing with municipal officials to get permission to do these things, or (2) taking advantage of "common carrier" regulations that James Gattuso and other pro-telecom pundits despise.

Now let's take switching barriers. How hard is it to switch broadband providers? OK, in most U.S. jurisdictions you can do it, but it will take you a few weeks of waiting, several hours of your time, and on the order of a hundred dollars. And you won't be able to choose from any of dozens of providers, as you can with a search engine; you've probably got two choices (aside: if you're willing to assert that two choices provides "sufficient competitive pressure to produce an efficient outcome", then I will assume that you'd also be happy with a political system in which you are legally obligated to vote for a Democrat or a Republican. You've got two whole choices, after all!).

In case the foregoing has been too verbose, here's the ten-second recap:

• Search engine market: ten days to start a new search engine, ten seconds to switch search engines, dozens of search engines available to most consumers.²
• Broadband Internet market: years to start a new broadband provider, weeks to switch broadband providers, two providers available to most consumers.

Which looks more competitive to you? Do these two markets look even vaguely similar?

So, we see that Gattuso's slippery slope is not, in fact, slippery at all. Google, Yahoo, and Microsoft do not have the same kind of market power that broadband Internet access providers do. (Microsoft, however, does have a very different kind of power arising from its outsized market share in the operating system market, but I don't want to get into that in this post.) Given the property that he suggests, a strong distinction can still be made between search engine providers and network carriers.

Finally, as an aside, I'd like to note that a few weeks ago, shortly after my post on network neutrality, I received PR spam written by a telecom flunky named Scott Cleland and distributed by Peter Klaus of Fleishman-Hillard public relations, containing much the same argument as that espoused by Gattuso above. I am not suggesting that Gattuso is a mouthpiece for Fleishman, but I do want to suggest that this talking point --- conflating search engines' market share with anti-competitive market power --- is going to see wider circulation in the future.

---

[1] Oh, is everybody using Firefox with the default search engine? (And by "everybody", I assume you mean "roughly 10% of all Internet users", because that is the current number; and Google's definitely not the default search engine for Internet Explorer.) All you have to do is hire a programmer to download the Firefox source, change a couple of configuration files, and rebuild it, and now you've got a browser with the search box pointing to your search engine. Or, even better, it's easy enough to distribute a Firefox extension that people can install in their search box with a single click.

[2] I am pretending, here, that Google's users are its customers. Of course, most of Google's users are not customers; its real customers are advertisers, which suggests a somewhat different analysis (although not necessarily different conclusions). However, Gattuso and DeMint both initiated this "users are customers" fiction and I'm going along with it for now.

politics, public-policy, network-neutrality, economics

Notes on network neutrality

So, "network neutrality" has been getting lots of press lately. Briefly, network neutrality is the principle that Internet carriers should provide "dumb pipes" that carry all Internet traffic equally, rather than discriminating based on the type, content, or destination of the traffic that flows across their networks. A wide array of interests --- including MoveOn, Google, and a number of other groups and companies across the political spectrum --- have been lining up behind initiatives to codify this principle in law for US Internet carriers. The principal opposition to the coalition comes, unsurprisingly, from two quarters: the telecommunications companies, and libertarians.

My reaction to this is twofold. My first and predominant reaction is: I am troubled by the idea of getting the FCC involved in regulating how Internet service providers architect their networks. The Internet actually works pretty well these days, so it seems dangerous to get Congress monkeying around with its guts. And the question of what constitutes a "neutral" network is pretty subtle, as the term has no widely agreed-upon technical definition.

In the absence of a technical consensus, the output of the legislative process is likely to be either a mishmash of mistargeted micro-regulations, or a vague and overly broad mandate for the FCC. Who knows what will come out of that process, but in my opinion the most likely outcome is simple regulatory friction that slowly, invisibly eats away at network innovation. Network innovation won't go away, but certain kinds of innovation will become more difficult because of legal complications, and the Internet will suffer. Therefore, I suspect that any legislation written today will hurt the Internet more than it helps. It is with some surprise that I find myself agreeing with the telecom giants and the Cato Institute, and disagreeing with MoveOn, Google, etc. If network neutrality regulation passes now, I think progressive activists and technology companies alike will live to rue the day they begged for it.

My second reaction is that this whole debate strikes me as a kind of bizarre ritual theater in which people are making noises and gesticulating wildly, but nobody talks about the real issue.

Political outfits --- ranging from MoveOn to the Christian Coalition --- are worried that network providers will begin to discriminate based on the political content of messages. This is pretty unlikely. It's not easy for an algorithm to look at a bag of bytes and classify its political content; and network providers probably can't pay for the computational power required to apply such an algorithm to the many terabytes of data that flow across their networks daily.

And even if they could, why would they? There's no percentage there. In fact, I can think of two very strong reasons for them not to start filtering based on political content. First, there would be an enormous consumer backlash. Second, there would be enormous political fallout. The latter would include not only backlash against abuse of quasi-monopoly power, but possibly the imposition of responsibility for the content that flows across the pipes. Once you begin filtering based on political content, lawmakers may poke their heads in and wonder why you aren't filtering out all that kiddie porn and gambling and such too --- and if something gets through your filters, why can't we hold you liable? The network providers don't want to open that can of worms.

So, political censorship isn't the real issue here. Nor, pace Moby et al., is it interconnection with small media providers versus large ones. Verizon's not terribly likely to block access to your music blog. They might, someday, contract with certain service providers for improved performance. For example, they might strike a deal with iTunes to store songs in a local proxy cache, so that Verizon customers would observe slightly improved performance with iTunes, but not your music blog. That doesn't strike me as either disastrous or a betrayal of the Internet's principles. Networking researchers have been proposing schemes like this for years. In fact, Akamai's basically a third-party version of this scheme: people pay them to store content in caches close to where it's demanded, so Akamai-cached websites perform better than non-Akamai websites. Akamai's been operating since 1999, and so far the Internet hasn't been torn asunder.

So what's the real issue?

As Ars Technica noted back in January, Verizon CEO Ivan Seidenberg was making noise about Google's (over-)"use" of Verizon's bandwidth. And last November, SBC CEO Edward Whitacre complained about Google and Microsoft using "my pipes" (meaning, of course, SBC's pipes; Whitacre suffers from your usual case of CEO megalomania):

"So there's going to have to be some mechanism for these people who use these pipes to pay for the portion they're using. Why should they be allowed to use my pipes?"

In a way, you have to give Seidenberg and Whitacre credit. In making these noises, they display a level of stupidity and chutzpah that rivals the dudes from Jackass.

First, the chutzpah: Google does pay its ISP for its Internet connectivity, just as Verizon customers pay Verizon for their Internet connectivity. Yet Seidenberg claims to believe that Google should pay Verizon for the Internet connectivity that Verizon's customers have already paid for. It's as if Ford were to ask Wal-Mart to pay fees to Ford, because Wal-Mart's customers were driving to Wal-Mart in Fords.

Second, the stupidity: five and a half months later, Verizon's lobbyists are working overtime to prevent network neutrality legislation from passing. And guess who's paying for the lobbyists on the other side? In many ways, Seidenberg, Whitacre, and their telecom industry cronies brought this circus on themselves through overreaching arrogance and greed.

So, here's the real story. The telecom giants currently sell you Internet access, which is okay, but dull. Dumb pipes are cheap. But hey --- what if they could sell you lots of bundled services? That really gets the dollar signs flashing in their eyes. These are the companies that want to sell ring tone subscriptions for your cell phone, and bundled cable packages with more channels than you'll ever watch. Their dream is to add a dozen extra bullshit services to your Internet service bill, so that you're paying them eighty dollars per month instead of fifty.

The big problem with that plan is that once you have dumb pipes and smart endpoints --- in other words, the Internet --- the endpoints can build essentially any service on top of the network. Of course, this is fantastic for Internet users. Once you pay for Internet access, you automatically get to use every Internet application that's ever been invented: email, the web, instant messaging, peer-to-peer, and (increasingly) the two V's, voice and video. These last two really drive the telecom giants nuts, because they used to sell you voice and video: they're phone and cable companies.

Therefore, the most likely form of telecommunications discrimination in the foreseeable future is discrimination by application, not by content. Verizon wants to give preference to its voice services, and Comcast wants to give preference to its video services. They're deeply freaked out by Skype, Google Video, and the like. If they can convince customers that competing services are slow and crappy compared to their own offerings, they think they'll have a better chance of getting you to pay for their bullshit services. Failing that, they'd like to convince Google and other Internet companies to pay fees for non-degraded service. Think of it as protection money: "Nice customer base you got there. Sure would be a shame if your packets were dropped 20% more often than your competitor's..."

If network providers got serious about this, the results would be pretty bad. Network providers should not be picking winners and losers in the Internet applications game. Applications should succeed or fail on their own merits. Now, I think network discrimination schemes would fail in the long run, but that's just a hunch and it's really an open empirical question. Meanwhile, in the short run, discrimination schemes could cause major distortions in the Internet applications market; and when you consider the possible network effects in domains like Internet telephony, it's possible that these distortions could cause lingering damage, locking in inferior applications for years to come.

So I'm really glad that people are paying attention to network neutrality. But I'm also alarmed that so few of those people seem to understand what's really going on here, and I'm skeptical that now is the time to make laws about it. So far, the Internet's still neutral. My bottom-line recommendation would be to watch and wait.

(And also to increase competition in local ISP markets, which would give customers a choice when confronted with discriminatory network policies. Note that this wouldn't be a panacea, because in practice most localities would still be served by a few providers, each of which might have an incentive to discriminate, albeit in differing ways. Oligopolies don't necessarily lead to efficient markets.)

computer-science, public-policy, network-neutrality

---

p.s. Selected links on network neutrality:

• Ed Felten (here I discover, ruefully, that most of the substance of what I write above, as opposed to the half-assed guesses, has already been written by Felten):
  • How Would Two-Tier Internet Work?
  • Nuts and Bolts of Network Discrimination: Part One, Part Two, Encryption
  • Discrimination, Congestion, and Cooperation
  • The "Quality of Service argument"
  • Net Neutrality and Competition
• Lawrence Lessig Congressional testimony
• Cory Doctorow at BoingBoing
• Tim Wu's paper, Network Neutrality, Broadband Discrimination

Some scattered thoughts on interviews, Jorge Cham, computer science, and grad student hardship

So, I'm back from my first academic interview. Oddly enough, I had a great time. People tell me that this level of enjoyment fades after you've been to a dozen. Fortunately or unfortunately, I probably won't have that problem, because I probably won't have a dozen in-person interviews. I will also say that having a nice industry job offer in your back pocket makes these things much less stressful.

Which is all in the way of remarking that I saw Jorge Cham speak, not long ago, as part of his lecture tour on the travails of being a fledgling academic.

Jorge Cham --- or at least the lecture persona known as Jorge Cham --- is a brilliantly funny, smart, and compassionate guy, and I don't doubt that his strip and lecture tour are doing worlds of good for struggling grad students all over the country.

On the other hand, as a computer science grad student, I couldn't help but think: could it be possible that a grad student at Stanford computer science really had it that bad? In particular, Jorge's statements about the economic insecurity of grad students struck me as strange. Computer science is one of the few branches of academia for which the implicit bargain --- sacrifice now, and you'll get a good job later --- still holds. Now, that job may not be an academic job, but if you go to a good grad school in computer science and cannot land an academic job of some sort, then chances are that you weren't cut out for academia anyway.

Jorge --- like, for that matter, Cecilia and Nameless and Mike Slackenerny --- could get a very well-paying job in industry, at almost any time of his choosing, simply by walking away from the academic game. And this economic reality has consequences throughout the grad student experience --- at "good" schools (which certainly includes Stanford), we get paid a livable wage, and we're largely given the infrastructure we need to be productive, and we get decent support in our job search. Because we can walk away.

I understand that Jorge's speaking, in some sense, for all grad students, not just computer scientists. And I also understand that grad school poses emotional challenges that all the economic security in the world wouldn't fix. However, if I were in Jorge's place, I'd have confessed, in my lectures, that my deal was much sweeter than the average grad student's. I mean, I'd be slightly uneasy, coming from my current situation, laying claim to the full measure of grad student hardship.

C. Shalizi on crowds and algorithms; also further complaints from yours truly

C. Shalizi has many useful things to say, and to link, about "the wisdom of crowds", partly in response to something I posted a while back.

Shalizi includes a pointer to a Rational Herds: Economic Models of Social Learning (ISBN 052153092X). Aside from having really cute penguins on the cover --- reason enough to buy most books --- the book also looks intellectually fascinating, and instantly makes my to-read list, though with my recent binge of book-buying [0] I most likely won't get around to reading it anytime soon.

In related news, I actually read/skimmed large chunks of The Wisdom of Crowds whilst browsing during the aforementioned book-buying binge. I concluded that the book itself (as opposed to the publicity, or the vulgarized versions of Surowiecki's thesis that are making the rounds) is not exactly bad, but rather good, yet frustrating. Surowiecki's tackling an important subject. He writes with the fluency and accessibility you'd expect from a New Yorker writer. The book recounts many fascinating anecdotes, and it even lays out a set of criteria for organizing "wise crowds" that's sensible and convincing (though stated too vaguely for my tastes). But these strengths make the book's failures all the more disappointing. Each chapter contains at least a few things that get my ersatz-scientist hackles up: an overgeneralization from meager data, or an incomplete and vague summary of a more systematic study, or an example cherry-picked to support his point without adequate treatment of counterexamples [1]. The best ideas in Surowiecki's book aren't new, and the intellectual frame he puts around them often adds little [2]. Lastly, and perhaps most importantly, as Shalizi writes in the post linked above, although Surowiecki does give a nod to the difficulties of crowd organization, in general he does not place enough emphasis on it.

My guess, therefore, is that readers genuinely interested in the ideas Surowiecki discusses would be better off reading the primary sources in Surowieki's acknowledgments. I don't have a copy handy, and I regrettably forgot to scribble them down. Oh well. Next time I'm in a bookstore...

Bonus link: Radio National interview with Surowiecki.

---

[0] At the Cherry Creek Tattered Cover in Denver, last week, while visiting a friend; the bargain shelves should be labeled with warnings for compulsive verbivores.

[1] For example, one form of "crowd wisdom" that Surowiecki returns to several times is the fact that groups of people appear, in aggregate, to be very good at estimating quantities. One of Surowiecki's stories in support of this claim: in 1906, economist Francis Galton found that crowd of people at a fair were collectively able to estimate the weight of a thousand-pound-plus ox to within one pound, better than any individual in the crowd. He has a few more examples in this vein, but almost no discussion of the abundant counterexamples. For example, experiments show that, on average, people consistently overestimate the height of men and underestimate the height of women, even when they're shown photographs of the subjects standing next to common reference points. Surely a trained surveyor would do much better than a crowd in this case. Surowiecki briefly mentions some studies wherein experimenters were able to skew estimation results by using explicit suggestion, but he ignores systematic, consistent, a priori bias --- which gives the reader the impression that estimation bias is something induced in relatively rare and peculiar circumstances.

[2] Returning to the collective estimation problem in the previous footnote: the success of averaged estimates would lead me to conclude that the human senses can measure accurately, but with a random error that follows a symmetric (Gaussian?) distribution. This is interesting, but it says little about the "wisdom of crowds". Instead, it testifies to the value of repeated measurement, a bog-standard part of scientific orthodoxy. You will get similar results with inanimate scientific instruments (e.g., a thermometer or a light-sensitive CCD) operating near the limits of their precision: measure many times, and you get a better, rounder bell curve than if you measure only a couple of times. Surowiecki's framing seems simply superfluous here.

Another name for the "wisdom of crowds"

I just read yet another online essay that, at one point, referenced "the wisdom of crowds". This phrase has been getting a lot of attention lately from the chattering classes. I don't have time to give this idea a fuller treatment, and in fact I have not read James Surowiecki's book (which started all the ruckus), but I will say something that I've wanted to get out there for a long time:

"The wisdom of crowds" is just another name for "the behavior of distributed algorithms".

When you think about it, "Let's exploit the wisdom of crowds!" really means: "Let's set up a whole bunch of independently acting, loosely federated entities, each with an incomplete view of the system, and let's make them do some cognitive task." In other words, if a crowd ends up having any wisdom, it will have arrived at it through a distributed algorithm.

Why does this matter? Two reasons.

First, it de-mystifies the concept. "The wisdom of crowds" is a phrase precisely calibrated to mystify the thing it denotes. Consider the diction: "crowds", suggesting spontaneous, informal, natural gatherings; and "wisdom", suggesting a folksy knowledge born of experience, as opposed to, say, "intelligence", "cleverness", or "expertise". The phrase "wisdom of crowds" carries within it the seeds of the message that gosh darn it, if you just got those elitist social engineers out of the way, and let everybody alone to act on their common sense, everything would be just peachy. In fact, if you read the blurbs from the publisher's page, this is exactly the message that's being pushed --- if not by Surowiecki himself, then by his promoters, with his tacit assent.

By contrast, the phrase "the behavior of distributed algorithms" is a more forbidding thing, one that highlights a crucial fact: all systems for extracting knowledge from "crowds" are, in fact, intricate constructions that achieve their results through precise engineering of the rules governing the crowd.

This leads into my second point. Any computer scientist who has tangled with distributed systems knows that designing a distributed algorithm that actually does what you want it to do is extraordinarily tricky. On the other hand, it is really easy to design distributed algorithms that, for deviously subtle reasons, end up prone to behaviors like wildly unpredictable, bizarrely pathological oscillations, race conditions, deadlock, livelock, network floods, etc., etc., etc. Until you have studied the Paxos algorithm, or at least hacked on a distributed system (and I doubt very much that James Surowiecki has done either), you probably lack the humility and skepticism needed to evaluate distributed algorithms accurately.

Naïvely lauding the alleged "wisdom of crowds" obscures the critical issue, which is the design of the distributed algorithm --- i.e., the social organization of the crowd. What are its mechanisms for passing information? For reaching consensus? Where are the possibilities for feedback loops? What happens in the obscure corner cases that result from the interactions of all its features? Etc., etc.

There's no such thing as a free lunch, and gathering together a large number of independent actors does not magically make problem-solving any easier. In fact, it can make problem-solving incalculably harder. After you gather the crowd, you have to figure out how to make it do something useful, and it is by no means the case that you'll always get acceptable outcomes by letting each individual make decisions that "look sensible" (whatever that means) based on locally available information.

Now, as I said, I have not read Surowiecki's book. It is entirely possible that I'm being utterly unfair to him based on the yammerings of others. On the other hand, the publisher's excerpt is not encouraging.

---

UPDATE 2007-09-29: If you're coming from this ycombinator blog, then note that I wrote a followup after reading most of the book and my opinion of Surowiecki himself has only marginally improved.

Also, in retrospect, it seems to me that this post is more about the "wisdom of crowds" meme --- how and why it's been successful, what's wrong with it, and the role of Surowiecki's publicist in promoting it --- than about Surowiecki's book itself.

Michael Shamos voting testimony

Michael Shamos's July 2004 testimony before the House of Representatives regarding electronic voting machines. He is obviously a longtime electronic voting proponent. I link the testimony here in the interest of fairness, but I don't have time to rebut all his claims now, beyond saying that most of the arguments he attributes to DRE voting machine opponents are straw men (albeit subtly constructed straw men).

Most thoughtful DRE voting machine opponents acknowledge that electronic voting machines, in some form, can be superior to other forms of voting. We object to the bad design and lack of verifiability in the current generation of DRE voting machines, as well as the lack of transparency on the part of the voting machine manufacturers.

Unfortunately, Michael Shamos's testimony reads as a full-throated defense of electronic voting, with calls for verifiability and trustworthiness only coming at the very end. It therefore gives a misleading impression to lay readers.

p.s. Michael Shamos is a professor at CMU's School of Computer Science (though not, it is worth noting, in the Computer Science Department itself); but the list of computer scientists who have endorsed the contrary Resolution on Electronic Voting is rather more impressive. The older, hand-maintained version sorts by rough seniority and, well, if you recognize any of the names on that list, you'll see what I mean. Yes, OK, the appeal to authority is a fallacy, but Shamos seems to like putting "Ph.D., J.D." after his name, and his testimony is full of logical problems itself, so it's worth pointing out that we should not accord Shamos any special credibility because of his own credentials.

SHA break updates

So, apparently they didn't break full SHA-1, only SHA-0 and a reduced-round version of SHA-1. Interestingly, I heard tonight from a security researcher that when SHA-1 was being designed, the NSA suggested a minor tweak, without which full SHA-1 would be vulnerable to this attack.

This is alternately heartening and scary. It's heartening, obviously, because it shows that the NSA basically does want civilians to have good security. It's scary because it means that the NSA foresaw the possibility of this weakness a decade ago, which puts them a decade ahead of the combined might of the entire civilian cryptographic research community.

Time travel and computation

Today I came across Wikipedia's article on time loop logic. A mind-bending, yet elegant, idea. Be sure to read the linked article on the Novikov self-consistency principle as well.