Lex Spoon

The good and bad of type checking, by example

2012-01-25T03:26:00.000-08:00

I enjoyed watching Gilad Bracha present Dart to a group of Stanford professors and students. As one might expect, given Bracha's background, he spends considerable time on Dart's type system.

Several members of the audience seemed surprised to find a defender of Dart's approach to typing. They understand untyped languages such as JavaScript, and they understand strictly typed languages such as Java. However, they don't understand why someone would intentionally design a language where types, when present, might still fail to hold up at run time.

One blog post will never convince people one way or another on this question, but perhaps I can show the motivation and dissipate some of the stark mystification around Dart's approach. Let me provide two examples where type checking would complain about a program. Here's the first example:


String fileName = new File("output.txt");

I find examples like this very compelling. The programmer has made an easy mistake. There's no question it is a mistake; this code will always fail when it is run. Furthermore, a compiler can easily detect the mistake simply by assigning a type to each variable and expression and seeing if they line up. Examples like this make type checking look really good.

On the other hand, consider this example:


void drawWidgets(List<Widget> widgets) { ... }
List<LabelWidget> labels = computeLabels();
drawWidgets(labels);

This program is probably fine, but a traditional type checker is forced to reject it. Even though LabelWidget is a subclass of Widget, a List<LabelWidget> is not a subtype of List<Label>, so the function call in the last line will not type check. The problem is that the compiler has no way of knowing that drawWidgets only reads from its input list. If drawWidgets were to add some more widgets to the list, then there would be a type error.

There are multiple ways to address this problem. In Java, programmers are expected to rewrite the type signature of drawWidgets as follows:


void drawWidgets(List<? extends Widget> widgets) { ... }

In Scala, the answer would be to use an alternate List type that is covariant in its argument.

Whatever the solution, it is clear that this second example has a much different impact on developer productivity than does the first one. First of all, in this second example, the compiler is probably wrong, and it is just emitting an error to be on the safe side. Second, the corrected version of the code is much harder to understand than the original; in addition to parametric types, it also uses an bounded existential type variable. Third, it raises the bar for who can use this programming language. People who could be perfectly productive in a simply typed language will have a terrible time with quantifier-happy generic Java code. For a host of reasons, I feel that on net the type checker makes things worse in this second example. The cases where it prevents a real error are outweighed by all the problems.

Dart's type system is unusual in that it is consistent with both examples. It rejects code like the first example, but is quiet for code like the second one.

DNS takedowns alive and well

2012-01-22T11:17:00.000-08:00

I wrote earlier that PROTECT-IP and SOPA are getting relatively too much attention. Specifically, I mused about this problem:

First, DNS takedowns are already happening under existing law. For example, the American FBI has been taking down DNS names for poker websites in advance of a trial. SOPA and PROTECT-IP merely extend the tendrils rather than starting something new.

Today I read news that indeed, the FBI has taken down the DNS name for Megaupload.com. I'm not sure the American public is in tune with precisely what its federal government is doing.

The news has other sad aspects than the use of DNS takedowns. A few other aspects lept out for me:

There has been not yet been a trial. If I ask most Americans about how their legal system works, I expect one of the first things people would say is that, in America, people are innocent until proven guilty.
There is twenty years of jail time associated with the charges. Isn't that a little harsh for copyright violations? I think of jail as how you penalize murderers, arsonists, and others who are going to be a threat to the public if they are left loose. Intellectual property violations somehow seem to not make the cut.
It's an American law, but New Zealand police arrested some of the defendants.
The overall demeanor of the authorities comes off as rather thuggish. For example, they seized all manner of unrelated assets of the defendants, including their cars.

I am glad SOPA and PROTECT-IP went down. However, much of what protesters complained about is already happening.

DNS takedowns under fire in the U.S.

2012-01-02T06:59:00.000-08:00

I get the impression that SOPA, the latest version of a U.S. bill to enable DNS takedowns of non-American web sites, is under a lot of pressure. A major blow to its support is that the major gaming console companies backing out.

I am certainly heartened. However, the problem is still very real, for at least two reasons.

First, DNS takedowns are already happening under existing law. For example, the American FBI has been taking down DNS names for poker websites in advance of a trial. SOPA and PROTECT-IP merely extend the tendrils rather than starting something new.

Second, this bill won't be the last. So long as the Internet uses DNS, there is a vulnerability built right into the protocols. Secure DNS doesn't make it any better; on the contrary, it hands the keys to the DNS over to national governments.

The only long term way to fix this problem is to adjust the protocols to avoid a single point of vulnerability. It requires a new way to name resources on the Internet.

All software has bugs

2011-12-28T06:21:00.000-08:00

Johm Carmack has a great article up on his experience with bug-finder software such as Coverity and PC-Lint. One of his observations is this:

The first step is fully admitting that the code you write is riddled with errors. That is a bitter pill to swallow for a lot of people, but without it, most suggestions for change will be viewed with irritation or outright hostility. You have to want criticism of your code.

He feels that the party line for bug finders is true, that you may as well catch the easy bugs:

The value in catching even the small subset of errors that are tractable to static analysis every single time is huge.

I agree. One of the ways it is easier to talk to more experienced software developers is that they take this view for granted. When I talk to newer developers, or to non-engineers, they seem to think that if we spend enough time on something we can remove all the bugs. It's not possible for any body of code more than a few thousand lines. Removing bugs is more like purifying water. You can only manage the contaminants, not remove them. Thus, software quality should be thought of from an effort/reward point of view.

I also have found the following to be true:

This seems to imply that if you have a large enough codebase, any class of error that is syntactically legal probably exists there.

An example I always come back to is the Olin Shivers double word finder. The double word finder scans a text file and detects occurrences of the same word repeated twice in a row, which is usually a grammatical mistake in English. I have started running it on any multi-page paper I write, and it almost always finds at least one such instance that is legitimately an error. If an error can be made, it will be, so almost any automatic detector is going to find real errors.Another one that jives with me is:

NULL pointers are the biggest problem in C/C++, at least in our code.

I did a survey once of the forty most recently fixed bugs on the Squeak bug tracker, and I found that the largest single category of bugs was a null dereference. They were significantly higher than type errors, bugs where one type (e.g. string) was used where another was intended (e.g., open file).

I do part ways with Carmack on the relative value of bug finders:

Exhortations to write better code plans for more code reviews, pair programming, and so on just don’t cut it, especially in an environment with dozens of programmers under a lot of time pressure.

If we were to candidly rank methodology for improving quality, I'd put write better code above use bug finders. In fact, I'd put it second, right after regression testing. I could be wrong, but my intuition is that there are a number of low-effort ways to improve software before it is submitted, and the benefits are often substantial. Things like use a simpler algorithm and read your diff before committing add just minutes to the time for each patch but often save over an hour of post-commit debugging from a repro case.

All in all it's a great read on the value of bug finding tools. Highly recommended if you care about high-quality software. HT John Regehr.

Blizzard embraces pseudonyms

2011-12-17T09:58:00.000-08:00

Blizzard Software's lets you use the same name on multiple games and on multiple servers within the same game. Historically, they required you to use a "real name" (in their case, a name on a credit card). This week they announced that they are deploying a new system without that requirement:

A BattleTag is a unified, player-chosen nickname that will identify you across all of Battle.net – in Blizzard Entertainment games, on our websites, and in our community forums. Similar to Real ID, BattleTags will give players on Battle.net a new way to find and chat with friends they've met in-game, form friendships, form groups, and stay connected across multiple Blizzard Entertainment games. BattleTags will also provide a new option for displaying public profiles.[...] You can use any name you wish, as long as it adheres to the BattleTag Naming Policy.

I am glad they have seen the light. There are all sorts of problems with giving away a real [sic] name within a game.

From a technical perspective, the tradeoffs they choose for the BattleTag names are interesting and strike me as solid:

If my BattleTag isn't unique, what makes me uniquely identifiable? How will I know I'm adding the right friend to my friends list?Each BattleTag is automatically assigned a 4-digit BattleTag code, which combines with your chosen name to create a unique identifier (e.g. AwesomeGnome#3592).

I'll go out on a limb and assume that the user interfaces that use this facility will indicate when you are talking to someone on your friends list. In that case, the system will be much like a pet names system, just with every name including a reasonable default nickname. When working within such UIs, they will achieve all of Zooko's Triangle. When working outside it, the security aspect will be weaker, because attackers can make phony accounts with a victim's nickname but a different numeric code. That's probably not important in practice, so long as all major activities happen within a good UI such as one within one of Blizzard's video games.

Regarding pseudonymity, I have to agree with the commenters on the above post. Why not do it this way to begin with and not bother with RealID? They can still support real [sic] names for people who want them, simply by putting a star next to the names of people whose online handle matches their credit card. Going forward, now that they've done this right, why not simply scrap RealID? It looks like high-level political face cover. You have to read closely in the announcement even to realize what they are talking about.

Joshua Gans on ebook lending

2011-12-01T07:38:00.000-08:00

Our approach to copyright is outdated now that we have a wide-spread Internet. What should we do? Joshua Gans proposes an approach based on lending and on tracking usage:

If lending is the appropriate mode for books, then how would the business of publishing look if it is built around lending rather than ownership? So here is my conjecture. All books are read on devices. Imagine that each device has built in a means of tracking what people read and how much. Imagine that it can also do this in a manner that respects privacy. Then the model I have in mind would allow publishers to receive money based on how much of a book people read and to price that at will.

I like the idea. One point of comparison is to the way radio works. In radio, the content is not DRMed, and you don't pay for each song you listen to. Instead, you subscribe in bulk to content and then flip around to whatever you feel like listening to. There are a variety of specific payment schemes on both sides of the arrangement. For the customer, I've encountered payment based on public taxes (Switzerland), by subscription (Sirius Radio), and by listening to ads (broadcast in the U.S.).

For the content producers, I am less clear about what contracts are out there. At least indirectly, however, they are paid more when there are more users listening to them. I imagine that radio has the same sort of marketing research that television does, and that radio stations know how many people are listening to their station and at what times. They then, through mechanisms that are probably kludgy, buy more of the popular music and less of the unpopular music.

It's a good idea, and I would be happy for it to catch on. Copies are trivial to make, nowadays, so the only ways to control copies are rather draconian. Far better to put a good society first and then find business models that work with it.

Dana Boyd on Pseudonyms

2011-11-28T20:55:00.000-08:00

I'm late to notice, but Dana Boyd has a good article up on the case for pseudonymity. She emphasizes the safety issues, which I certainly agree about.

Something I hadn't fully processed is that many people are using Facebook as an example that real names work. Perhaps this argument is so popular because the Zuckerbergs have publicly emphasized it. At any rate, it's a weak argument. For one thing, quite a number of Facebook profiles are using pseudonyms. See Lady Gaga, Ghostcrawler, and Anne Rice. If the Zuckerbergs really are trying to shut down pseudonyms, they're doing a terrible job of it. Another reason is that, as Boyd points out, Facebook is unusual for starting as a close-knit group of college grads. The membership it grew from is a group of people relatively uninterested in pseudonyms.

Reading the comments to Boyd's post, it appears that the main reasons people are convinced about pseudonyms is the hope that it will improve the level of conversation in a forum. I continue to be mystified by this perspective, but it does appear to be what is driving the most opponents of pseudonyms. I just don't get it. Partially I'm just used to an Internet full of pseudonyms. Partially it's just too easy to think about perfectly legitimate activities that wouldn't be good to pop up if someone does a web search on "Lex Spoon". People interested in that stuff should instead search for Saliacious Leximus. They'll avoid all the nerdy computer talk and get straight to the goods they are looking for.

Overall, pseudonyms appear to be one of those divides where people on each side have a hard time talking over the gulf. Apparently is is perfectly obvious to many people that if Google Plus and Facebook embraced pseudonyms, then their members would get overwhelmed by harassment and spam. Personally, I don't even understand the supposed threat. Why would I circle or friend a complete stranger? If I had, why wouldn't I simply unfriend them?

The Web version of interface evolution

2011-11-19T07:30:00.000-08:00

Nick Bradbury points out an important issue with web APIs:

I created FeedDemon 1.0 in 2003, and it was the first app I wrote that relied on web APIs. Now those APIs no longer exist, and almost every version of FeedDemon since then has required massive changes due to the shifting sands of the web APIs I've relied on.

There are a tangle of issues involved here.

One is that, for sure, web APIs are not a suitable way to build a self-contained system that will at least remain internally consistent indefinitely. You couldn't build a space probe using any web APIs that you don't control. By the time it got to Jupiter the protocols might well have changed. Even barring an intentional protocol change, the service might upgrade its software and accidentally break you.

Not all software is of this character, however. Most user-facing software is expected to stay compatible with the other software a particular user is taking advantage of. Most user-facing software has a mechanism for being updated after it's deployed.

The thought experiment I use here is to consider why the Lisp Machine is no use nowadays. These systems are very impressive; think Emacs, but with a better programming language, and with multiple for-profit companies writing professional software to run on it. Nonetheless, they are useless nowadays (and Emacs is as awesome as ever). That it is so is obvious, but what is the precise reason for it?

My best answer is that the world changed around them. Even without any explicit API break, Lisp Machines just don't have integration with other forms of software that its users would find important. That whole Internet thing is a simple example.

In general, most software is only useful if it is under active maintenance. The difference between zero maintenance and a little bit of maintenance is huge. If you are considering using software isn't under maintenance, run away! If you continue to use it, you will eventually find that you have become its maintainer yourself.

Which brings me back to APIs. APIs are never perfect, and so they evolve just like any other interface. The only way this is different for web APIs is that the clients do not get to choose when to upgrade. One day, the provider updates their software and it's simply on the new API. Gilad Bracha describes this as "versionless software".

Ideally, this evolution should involve discussion between the service provider and all of the clients. Exactly how those discussions work is a rich question that is similar to any other decision process by a number of stakeholders. For an API like one offered by Google, individual clients have very little influence on the API, so you have to decide whether to take it or leave it; part of that decision involves your expectation that the service provider will treat you well. In other cases, there might be a contractual agreement between a user of the service and its provider; in that case, any API changes could be worked out as part of negotiating the contract. In still other cases, a group of software users might meet in standards committees, as happens to some degree with the HTTP protocol.

In short, I really don't think that constant interface change is a fundamental reason to avoid web APIs. Instead, it's a fundamental part of most software development that you have to keep maintaining, whether or not the APIs you program against are accessed over the web. Instead, you should be choosy about what specific APIs you depend on. Just like you wouldn't want to depend on an ancient unmaintained hunk of software, you also wouldn't want to use a hyperactively maintained hunk of web service that has a completely different API from one week to the next. Think explicitly about the API evolution story for any service you depend on, and use your judgement.

Cloud9 is hitting limits with JavaScript

2011-11-08T17:09:00.000-08:00

Cloud9 has a well-written call for adding classes to JavaScript:

Adding classes to JavaScript is technically not hard -- yet, its impact can be profound. It lowers the barrier to entry for new JavaScript developers and reduces the incompatibility between libraries. Classes in JavaScript do not betray JavaScript’s roots, but are a pragmatic solution for the developer to more clearly express his or her intent. And in the end, that’s what programming languages are all about.

Their argument about library compatibility seems strong to me. It is reasonable to write a Python or Java library that stands alone and has minimal external dependencies. With JavaScript, however, the temptation is strong to work within a framework like Dojo or JQuery just so that you get basic facilities like, well, classes.It's a good argument. If I were working on a large JavaScript code base, however, I'd be strongly tempted to switch over to Dart. It already has the basic language facilities they yearn for, and it's going to move forward much more quickly.

Dennis Ritchie passes

2011-10-14T19:43:00.000-07:00

Dennis Ritchie, co-inventor of C and Unix, has passed away.

I first learned C at a summer camp for math enthusiasts. We implemented programs to generate fractals on Sun workstations (or was it SGIs?), and the language we implemented them in was C. I asked around about this interesting language, borrowed a book from someone, and soaked up the language like a sponge. I wish I could remember if the book was K&R, but I do remember reading through one of the first examples in it. The program read its input character by character and performed some transformation on them, perhaps converting them to uppercase, and printed out the result. I remember thinking it was a hard problem, and I remember a growing delight as the chapter broke the problem down into smaller pieces that mapped perfectly to C. I read over and over that ten line program, savoring the while loop and the stdio calls and the looping variable named "c" (or was it "ch"?).

Several years later, I gained access to the Unix machines at Clemson, and it was computing nirvana. The machines had a ubiquitous C compiler, a suite of Internet programs, preemptive multi-tasking, a good scripting language, a good shell, and a windowing operating system to run it all in. Compared to Windows 3.1, DOS (because Windows was a resource hog), batch files, debug.exe, and Pascal, these machines just felt right. It felt like I'd been walking with a fifty pound backpack for miles, and now I could set aside that backpack and walk more lightly.

Unix and C are just that good. At the time, those systems were more than a generation ahead of the IBM, Apple, and Commodore computers everyone was using at home. Nowadays, the number of Unix machines has only grown. Android, Apple, and ChromeOS machines all run Unix. If you can't beat 'em, join 'em.

Ritchie was instrumental in this revolution. Though few seem to have actually talked to the guy, the web is filled with testimonials. Here are a few of them that I have run across:

Schmidt on federal policy

2011-10-13T15:37:00.000-07:00

Eric Schmidt testified before Congress on its technology policy, and he tells the Washington Post that he is not happy.

Much of the issue he blames on age. For example:

And inevitably what happens is everyone says ‘yes,’ yet inevitably on the Hill you have an older gentleman or lady. The staffers—and the staffers are young—the staffers get it. They’re 25, 30 years old and they all get it. So that’s what we depend on. And of course we’ve hired ex-staffers as well. They all know each other. So that’s how it really works. And I believe what we’re doing is extremely defensible if it’s around ideas. I would have a lot of trouble if we in our industry started following the other kind of lobbying.

I'm not sure I agree. I know a lot of younger people that haven't thought through the horror that search neutrality will be if it goes through. I think there's a more fundamental problem computers are changing quickly. Search engines didn't exist twenty years ago, and twenty years from now, they will be completely different. How is it realistic for Washington to regulate something that completely changes every couple of decades?

I admit I appreciate his suggestion about how to improve the state of IT in the U.S. even further:

A classic example is H-1B visas. Now, the following arguments are so obvious, it’s hard for me to believe that anyone would believe that they’re false. These industries are full of very smart people. There are very smart people who don’t live in America. They come to America, we educate them at the best universities, they are smarter than I am, and then we kick them out. If they stayed in the country, let’s just review: They would create jobs, pay taxes, have high incomes, pay more taxes than the average American, and generally increase the GDP of the country. I hope my argument is clear, and if it isn’t I’ll start screaming about it. It’s the stupidest policy the government has with respect to high tech. So you have this conversation and people say “yes,” and you say, ”This is the single thing that you can do that will lead to innovation occurring in our country, and the future economic wealth of our country.” And then they don’t act.... It’s stupid. So my point is that if you want to get a sense of how to screw this up, to put it negatively, then make it harder for us to bring in the world’s smartest people.

Tell 'em, Eric!

Dart spec is online

2011-10-10T13:59:00.000-07:00

Google has posted a technical overview and a language specification for Dart, their new programming language for web browsers.

In short, the language is a skin around JavaScript. It provides syntax for parts of JavaScript that are left to convention, and it is designed to be easily compilable to JavaScript. It has optional types, class definitions, and a module syntax.

The type system has some controversial aspects, in particular an explicit choice not to bother about soundness. If I understand correctly, assigning an apple to a variable holding bananas would cause an error, but assigning an unknown fruit to a variable holding bananas would not. The idea is to pick up the egregious errors and otherwise leave the programmers alone.

Hat tip to Lambda the Ultimate, which has several interesting discussions in the comments.

The jlouis blog has a detailed breakdown of what's in the language. Delightfully, he includes the following homage to Blade Runner:

If all you know is Javascript, the language is probably pretty neat. But for a guy who has seen things you wouldn't believe. Haskell ships off the shoulder of MultiCore CPUs. Watched OCaml glitter in the dark near TAPL. All those moments will be lost in time, like tears in rain. Time to die.

What every guide says about child safety on the Internet

2011-10-07T08:10:00.000-07:00

At the same time that Blizzard and Google are fighting for real names only on the Internet, children's advocacy groups are fighting for exactly the opposite. Take a look at the top hits that come up if you do a web search on "advice to children online".

First there is ChildLine, a site targeted directly at children. Here is the entirety of their guide on how to stay safe:

How do I stay safe when playing games online?
Don’t use any personal information that might identify you. This could be your full name, home address, phone number or the name of your school.
Use a nickname instead of your real name and chose one that will not attract the wrong type of attention.
Look out for your mates. Treat your friend’s personal details like you would your own and do not share their details with others.

Not only do they suggest not using real names, it is pretty much the only advice they give.

Next is Safe Kids, a site targeted at parents. This site has a more detailed guide on things you can do to help a child say safe. Here is their number one suggestion under "Guidelines for parents":

Never give out identifying information—home address, school name, or telephone number—in a public message such as chat or newsgroups, and be sure you’re dealing with someone both you and your children know and trust before giving out this information via E-mail. Think carefully before revealing any personal information such as age, financial information, or marital status. Do not post photographs of your children in newsgroups or on web sites that are available to the public. Consider using a pseudonym, avoid listing your child’s name and E-mail address in any public directories and profiles, and find out about your ISP’s privacy policies and exercise your options for how your personal information may be used.

Third up is BullyingUK, a site dedicated to bullying in particular instead of general child abuse. Here are their first two pieces of advice for Internet saftey:

Never give out your real name
Never tell anyone where you go to school

The real names movement is not just out of touch with BBS culture and with norms of publication. It's also out of touch with child safety advocates.

Real names proponents talk about making Internet users accountable. Child advocates, meanwhile, strive for safety. Safety and accountability are in considerable tension. To be safe on a forum, one thing you really want is the ability to exit. You want children to be able to leave a forum that has turned sour and not have ongoing consequences from it. To contrast, real name proponents hope that if someone misbehaves and leaves a forum, there is some outside mechanism to track the person down and retaliate. That might sound good if the person tracked down is really a troll, but it's a chilling prospect if the person being hunted is a child.

Throttling via the event queue

2011-10-06T12:25:00.000-07:00

Here's a solution to a common problem that has some interestingadvantages.

The problem is as follows. In a reactive system, such as a userinterface, the incoming stream of events can sometimes beoverwhelming. The most common example is mouse-move events. If the OSsends an application a hundred mouse-move events per second, and ifthe processing of each event takes more than ten milliseconds, thenthe application will drift further and further behind. To avoid this,the application should discard enough events that it stays caught up. Thatis, it should throttle the event stream. How should it do so?

The solutions I have run into do one of two things. They either delaythe processing of events based on wall-clock time, or they requiresome sophisticated support from the event queue such as the ability tolook ahead in the queue. The solutions that use time have the problemthat they often introduce a delay that isn't necessary; the user willstop moving the mouse, but the application won't know it, so it willadd in a delay anyway. The solutions using fancy event queues are notalways possible, depending on the event queue, and anyway they makethe application behavior more difficult to understand and test.

An alternative solution is as follows. Give the application a notionof being paused, and have the application queue Unpause events toitself to get out of the paused state. The first time an eventarrives, process it as normal, but also pause the application andqueue an Unpause event. If any other events arrive event while theapplication is paused, simply queue them on the side. Once the Unpauseevent arrives, if there are any events on the side queue, drain theside queue, process the last event, and queue another Unpauseevent. If an Unpause event arrives before any other events are queued,then simply mark the application unpaused.

This approach has much of the advantages of looking ahead in the eventqueue, but it doesn't require any direct support for doing so. It alsohas as good of responsiveness under system load as appears possibleto achieve. If the system is lightly loaded, then every event is processed,and the system is just as responsive as it would be without the throttling.If the system is loaded, then enough events are skipped that the applicationavoids backlogging further and further behind. If the load is temporarily high,and then stops, then the last event will be processed promptly.

The one tricky part of implementing this kind of solution is postingthe Unpause event from the application back to the applicationitself. That event needs to be on the same queue that the other workis queuing up on, or the approach will not work. How to do thisdepends on the particular event queue in question. For the case of aweb browser, the best technique I know is to use setTimeout with atimeout of one millisecond.

Kudos to Princeton for an open-access policy

2011-10-06T11:19:00.000-07:00

It seems that Princeton has adopted an open-access policy for the papers their faculty publish.

...each Faculty member hereby grants to The Trustees of Princeton University a nonexclusive, irrevocable, worldwide license to exercise any and all copyrights in his or her scholarly articles published in any medium, whether now known or later invented, provided the articles are not sold by the University for a profit, and to authorize others to do the same.... The University hereby authorizes each member of the faculty to exercise any and all copyrights in his or her scholarly articles that are subject to the terms and conditions of the grant set forth above.

The legalese is making my head spin, but I think they are saying that the university gets full access to all faculty publications, and that the university is granting all faculty full access to their own publications. As a programmer, I yearn to write it in a more simple way, and probably to drop the "for a profit" part. Still, the spirit is there. Anything published by a Princeton faculty member will not be hidden exclusively behind a paywall.

Hat tip to Andrew Appel, who emphasizes that this policy is compatible with ACM's paywall:

Most publishers in Computer Science (ACM, IEEE, Springer, Cambridge, Usenix, etc.) already have standard contracts that are compatible with open access. Open access doesn't prevent these publishers from having a pay wall, it allows other means of finding the same information.

This is true, but I find it too gentle on ACM. The ACM is supposed to be the preeminent association of computer-science researchers in the United States. They would serve their members, not to mention science, if they made the articles open access. Charge the authors, not the readers.

Pseudonyms lead to uncivil forums?

2011-09-30T19:15:00.000-07:00

I am late to realize, but apparently, Google Plus is requiring a real names only. They go so far as to shut down accounts that are using a name they are suspicious of, and they're doing a lot of collateral damage to people with legal names that happen to sound funny.

The battle for "real names" is one that I have a hard time understanding. Partially this is because it is impossible to indicate which names are "real". Is it ones on legal papers? On a credit card or bank account? Ones people call you all the time? Partially it is that I started using forums at an impressionable age. Online forums are filled with pseudonyms and they work just fine. Hobbit and Ghostcrawler are the real names of real people in my world. It's all so normal and good that I have a hard time understanding why someone would want to shut it down.

Let me take a try at it, though, because I think it's important that pseudonymity thrive on the Internet.

The most common defense I hear for a real-names policy is that it improves the quality of posts in a forum. That's the reason Blizzard used when they announced they would require real names only on their official forums. As far as I can understand, the idea is that a "real name" gives some sort of accountability that a pseudonym does not.

There is much to say on this, but often a simple counter-example is the strongest evidence. Here are the first four Warcraft guilds I could find, by searching around on Google, that have online forums viewable by the public.

Feel free to peruse them and see what a forum is like without real names. At a glance, I don't see a single real name. Everyone is posting using names like Brophy, Porcupinez, and Nytetia. As well, after skimming a few dozen posts, I didn't find a single one that is uncivil. In fact, the overall impression I get is one of friendliness. Camaraderie. Just plain fun.

The tone of these forums is not surprising if you think about the relationship the members of a guild have with each other. This is just the sort of thing you see over and over again if you participate in Internet forums. It is just the kind of thing that will be shut down under a real names policy.

Teach your build tool jars, not classes

2011-09-26T08:00:00.000-07:00

As far as I can tell, the single compelling feature about ant as a build system is that it makes it easy to compile Java. I just encountered a wiki page where SCons developers are discussing some of the problems.

One of the problems is this:

Currently the DAG built by SCons is supposed to have knowledge about every single generated file so that the engine can work out which files need transformation. In a world where there is 1 -> 1 relationship between source file and generated file (as with C, C++, Fortran, etc.) or where there is 1 -> n relationship where the various n files can be named without actually undertaking the compilation, things are fine. For Java, and even more extremely for languages like Groovy, it is nigh on impossible to discover the names of the n files without running the compiler -- either in reality or in emulation.

It's actually worse. It's not really a 1->n compile. The 1 file on the left can only be compiled by consulting other input files, and if any of those files change, you also need to recompile. Determining the exact dependency graph is a rather complicated problem.

I believe such a graph is unavoidable and indispensable if you want to have a decent build tool. "Decent" is subjective, but surely anyone would say that rebuilds should be reliable. You don't generally get that with ant. If you are building with ant, your have probably gotten very familiar with "ant clean".

To address Java's build problems without having to use ant, what I do is set up my build files in terms of jar files rather than directories of class files. If you do that, then even though the Java or Scala compiler produces loads of class files, the build tool doesn't actually see them. They are created in a temporary directory, combined into a jar, and then the temporary directory is deleted. While it's true that you don't get the optimal rebuild this way if you change just one file, I'd usually use an IDE if I am repeatedly editing the files of a single Java or Scala module. If I change just one file at random, I'd prefer to have a safe rebuild than the absolute fastest one.

In principle you can update the build tool to accurately model all the class files. Ant's depend task does so, and the Simple Build Tool uses a scalac plugin to track dependencies. While I don't have experience with the SBT version, I have found the ant version to significantly slow down compiles and yet still not be completely reliable. I prefer to stick with jar files and have the build tool be reliable. Besides, you shouldn't have to use a particular build tool just because your project includes some code in some particular language. It doesn't scale as soon as you add a second language to the project.

A Scientist's Manifesto?

2011-08-23T15:29:00.000-07:00

I was disheartened today to read so many glowing reviews of Robert Winston's "Scientist's Manifesto".

I think of science as a way to search for knowledge. It involves forming explanations, making predictions based on those explanations, and then testing whether those predictions hold true. Scientists make claims, and they fight for those claims using objective evidence from repeatable experiments.

Winston promotes an alternative view of science, that scientists are people who are in a special inner circle. They've gone to the right schools, they've gone through the right processes, and they've had review by the right senior scientists. Essentially, they are priests of a Church of Science. His concern is then with the way in which members of this church communicate with the outside.

If that sounds overblown, take a look at item one in the 14-item manifesto. It even uses the term "layperson":

We should try to communicate our work as effectively as possible, because ultimately it is done on behalf of society and because its adverse consequences may affect members of the society in which we all live. We need to strive for clarity not only when we make statements or publish work for scientific colleagues, but also in making our work intelligible to the average layperson. We may also reflect that learning to communicate more effectively may improve the quality of the science we do and make it more relevant to the problems we are attempting to solve.

Aside from the general thrust of it, many individual items I disagree with. For example, I think of scientists interested in a topic as conferring with each other through relatively specialized channels. Thus item three is odd to me:

The media, whether written, broadcast or web-based, play a key role in how the public learn about science. We need to share our work more effectively by being as clear, honest and intelligible s possible in our dealings with journalists. We also need to recognize that misusing the media by exaggerating the potential of what we are studying, or belittling the work of other scientists working in the field, can be detrimental to science.

Of course, it makes perfect sense if you think of science as received wisdom that is then propagated to the masses.

I also think of science as seeking objective truth. I can't really agree the claim that it is relative:

We should reflect that science is not simply ‘the truth’ but merely a version of it. A scientific experiment may well ‘prove’ something, but a ‘proof’ may change with the passage of time as we gain better understanding.

I don't even think peer review is particularly scientific. The main purpose of peer review is to give a mechanism to measure the performance of academics. In some sense it measures how much other academics like you. Yet, item 8 in the manifesto claims that peer review is some sacred process that turns ordinary words into something special, much like the process behind a Fatwah:

Scientists are regularly called upon to assess the work of other scientists or review their reports before publication. While such peer review is usually the best process for assessing the quality of scientific work, it can be abused....

I have an alternative suggestion to people who want the public to treat scientists with esteem. Stop thinking of yourself as a priest, evangelist, or lobbyist trying to propagate your ideas. Instead, remember what it is that's special about your scientific endeavors. Explain your evidence, and invite listeners to repeat crucial parts of the experiment themselves. Don't just tell people you are a scientist. Show them.

Why LaTeX?

2011-08-19T06:49:00.000-07:00

Lance Fortnow laments that no matter how crotchety he gets he can't seem to give up LaTeX:

LaTeX is a great system for mathematical documents...for the 1980s. But the computing world changed dramatically and LaTeX didn't keep up. Unlike Unix I can't give it up. I write papers with other computer scientists and mathematicians and since they use LaTeX so do I. LaTeX still has the best mathematics formulas but in almost every other aspect it lags behind modern document systems.

I think LaTeX is better than he gives it credit for. I also think it could use a reboot. It really is a system from the 80s, and it's... interesting how many systems from the 70s and 80s are still the best of breed, still in wide use, but still not really getting any new development.

Here's my hate list for LaTeX:

The grammar is idiosyncratic, poorly documented, and context-dependent. There's no need for any of that. There are really good techniques nowadays for having a very extensible language nonetheless have a base grammar that is consistent in every file and supports self-documentation.
You can't draw outside the lines. For all the flexibility the system ought to have due to its macro system, I find the many layers of implementation to be practically impenetrable. Well written software can be picked up by anyone, explored, and modified. Not so with LaTeX--you have to do things exactly the way the implementers imagined, or you are in for great pain and terrible-looking output.
The error messages are often inscrutable. They may as well drop all the spew and just say, "your document started sucking somewhere around line 1308".
The documentation is terrible. The built-in documentation is hard to find and often stripped out anyway. The Internet is filled with cheesy "how to get started" guides that drop off right before they answer whatever question you have.
Installing fonts is a nightmare. There are standalone true-type fonts nowadays. You should be able to drop in a font and configure LaTeX to use it. That this is not possible suggests that the maintainers are as afraid of the implementation as I am.
Files are non-portable and hard to extract. This problem is tied up in the implementation technology. Layered macros in a global namespace are not conducive to careful management of dependencies, so everything tends to depend on everything.

However, as bad as that list is, the pros make it worth it:

Excellent looking output, especially if you use any math. If you care enough to use something other than ASCII, I would think that the document appearance trumps just about any other concern.
Excellent collaborative editing. You can save files in version control and use file-level merge algorithms effectively. With most document systems, people end up mailing each other the drafts, which is just a miserable way to collaborate.
Scripting and macros. While you can't reasonably change LaTeX itself, what you can easily do is add extra features to the front end by way of scripts and macros.
It uses instant preview instead of WYSIWYG. WYSIWYG editors lead to quirky problems that are easy to miss in proofreading, such as headers being at the wrong level of emphasis. While I certainly want to see what the output will look like all the time, I don't want to edit that version. I want to edit the code. When you develop something you really want to be good, you want very tight control.
Scaling. Many document systems develop problems when a document is more than 10-20 pages long. LaTeX keeps on chugging for at least up to 1000-page documents.

I would love to see a LaTeX reboot. The most promising contender I know of is the Lout document formatting system, but it appears to not be actively maintained.

Paul Chiusano on software patents

2011-08-15T11:17:00.000-07:00

Paul Chiusano reminds us why we would conceivably want software patents:

What I find irritating about all the software patent discussion is that patents are intended to benefit society - that is their purpose, "To promote the Progress of Science and useful Arts". But no one seems to want to reason about whether that is actually happening - that would mean doing things like thinking about how likely the invention was to be independely discovered soon anyway, estimating the multiplier of having the invention be in the public domain, etc. Instead we get regurgitation of this meme about making sure the little guy working in his basement gets compensated for his invention.

It's a good reminder. The point of patents is to make society better off.

The standard argument for patents requires, among other assumptions, that the patented inventions require a significant level of investment that would not otherwise occur. As Paul points out, that is not the case for software:

Software patents rarely make sense because software development requires almost no capital investment, and as a result, it is almost impossible for an individual to develop some software invention that would not be discovered by multiple other people soon in the future. Do you know of any individual or organization that is even capable of creating some software "invention" that would not be rediscovered independently anyway in the next five or ten years? I don't. No one is that far ahead of everyone else in software, precisely because there is no capital investment required and no real barriers to entry.

I agree.

I have read many posts where people try to fine tune software patents to make them less awful. I wish we could instead start by considering the more fundamental issue. Do we want software patents at all?

Schrag on updating the IRBs

2011-08-10T09:42:00.000-07:00

Zachary Schrag has a PDF up on recent efforts to update IRBs. Count me in as vehemently in favor of two of the proposals that are apparently up for discussion.

First, there is the coverage of fields that simply don't have the human risks that medical research does:

Define some forms of scholarship as non-generalizable and therefore not subject to regulation. As noted above, the current regulations define research as work “designed to develop or contribute to generalizable knowledge.” Since the 1990s, some federal officials and universities have held that journalism, biography, and oral history do not meet this criterion and are therefore not subject to regulation. However, the boundaries of generalizability have proven hard to define, and historians have felt uncomfortable describing their work as something other than research.

I would add computer science to the list. A cleaner solution is as follows:

Accept that the Common Rule covers a broad range of scholarship, but carve exceptions for particular methods. Redefining “research” is not the only path to deregulation contemplated by the ANPRM, so a third possibility would be to accept Common Rule jurisdiction but limit its impact on particular methods.

Schrag's PDF gives limited attention to this option, but it seems the most straightforward to me. If a research project involves interviews, studies, or workplace observations, then it's just shouldn't need ethics review. The potential harms are so minor that it should be fine to follow up on reports rather than to require ahead-of-time review.

Schrag also takes aim at exempt determinations:

Since the mid-1990s, the federal recommendation that investigators not be permitted to make the exemption determination, combined with the threat of federal sanction for incorrect determinations, has led institutions to insist that only IRB members or staff can determine a project to be exempt. Thus, “exempt” no longer means exempt, leaving researchers unhappy and IRBs overwhelmed with work.

Yes! What kind of absurd system declares a project exempt from review but then requires a review anyway?

TechDirt on the latest draft of PROTECT IP

2011-08-08T13:39:00.000-07:00

Tech Dirt has an analysis of the latest available version of PROTECT IP.

Yesterday, we got our hands on a leaked copy of the "summary" document put together by those writing the new version of COICA, now renamed the much more media friendly PROTECT IP Act. It looked bad, but some people complained that we were jumping ahead without the actual text of the bill, even if the summary document was pretty straightforward and was put together by the same people creating the bill. Thankfully, the folks over at Don't Censor the Internet have the full text of the PROTECT IP Act, which I've embedded below as well. Let's break it down into the good, the bad and the horribly ugly.

I find it hard to care about the nitty gritty details of the approach. The bill is still fundamentally about taking down DNS names on the mere allegation of infringement, and that seems like a very bad idea to me.

Brad on foreign CEOs

2011-08-07T10:35:00.000-07:00

Brad Templeton describes a good way to explain the current distribution of nationalities in the tech field:

I gave him one suggestion, inspired by something I saw long ago at a high-roller CEO conference for the PC industry. In a room of 400 top executives and founders of PC and internet startups, it was asked that all who were born outside the USA stand up. A considerable majority (including myself) stood. I wished every opponent of broader immigration could see that.

I agree with Brad that, at least in the software field, we benefit tremendously from foreign workers.

I suspect most observers would agree if they thought about it. You don't have to look just at executives. Walk into any software shop and you will see a large fraction of the workers who were born abroad. Futhermore, talk to any software developer about the job market, and it's not like they are hurting for work. If we sent all the foreign workers home, it's not like we'd have more American programmers at work. We'd simply have less total computer work being done.

It seems that software is getting swept up in laws and regulation that were developed with other fields in mind. If you follow the political discussions on the topic, it is always about lower-skilled jobs in fields where it is tough to start a new company. This depiction simply does not match computer science.

It's the same sort of thing that happens with research oversight. Research oversight is driven by the needs of medical research, and it just doesn't match the ethical issues that computer researchers face.

Inducing infringement alive and well

2011-08-07T07:37:00.000-07:00

Mitch Golden writes, in a good analysis of the legal state of LimeWire's file-sharing software, that inducing infringement was a key part of the October 2010 court case against them:

Interestingly, the court largely sidestepped the technical issues as to whether Gnutella itself had non-infringing uses or not, or whether a Gnutella client can be legally distributed. The court's decision instead turned on evidence submitted by the plaintiffs that LimeWire intended to facilitate filesharing.

I continue to feel that we are much better off leaving content carriers alone. Trying to make content carriers into IP policemen is not going to work out well.

Cedric on type erasure

2011-07-30T07:42:00.000-07:00

I've been meaning to get around to posting on type erasure, and Cedric Beust beat me to it:

The main problem is that reified generics would be incompatible with the current collections.... The extra type information also impacts the interoperability between languages within the JVM but also outside of it.

I completely agree. I used to rail on erasure until I got more experience with it.

The interoperability issue is one big reason I now like erasure. With erased types, the interop layer uses only a very simple type system. Knowledge of complicated type systems stays within the compilers for individual languages.

An additional reason is that it puts the cost of type checking in the compiler rather than in the runtime. With erased types, the compiler works hard to do its type checking, and if it signs off, the code is known to be type safe. At runtime, the types disappear and the code runs at full speed.

This property is more than just pretty. It is very helpful to an engineer trying to build anything using the language. When you write code, you want to know how it is going to perform. With erasure, the things you write convert directly to machine code, just with extra details added such as which variable goes in which register. With reification, you end up with extra crud being inserted everywhere. To understand performance under reified types, you have to reason about this additional type crud. You'd rather not have to.

A major milestone for Scala+GWT

2011-07-17T16:31:00.000-07:00

Stephen Haberman has announced that the majority of features in GWT's "Showcase" app are now available to Scala code as well. Aaron Novstrup did the original port to Scala, and Stephen's recent revamp of the GWT import code has gotten this much more functionality working.

Grzegorz Kossakowski has posted a compiled version on Dropbox for anyone that would like to click around in the final deployed version. A few of the things you will see working are:

Generators (see the "source code" tab)
Internationalization
Code splitting
Numerous built-in widgets

Scala+GWT still requires a lot of handholding to do anything with it, but this is a major milestone. Kudos to everyone who contributed!

Professors' letter against PROTECT-IP

2011-07-07T11:55:00.000-07:00

A number of professors have signed a letter to the U.S. Congress opposing Protect IP:

The undersigned are 108 professors from 31 states, the District of Columbia, and Puerto Rico who teach and write about intellectual property, Internet law, innovation,and the First Amendment. We strongly urge the members of Congress to reject the PROTECT-IP Act (the "Act"). Although the problems the Act attempts to address-–online copyright and trademark infringement–-are serious ones presenting new and difficult enforcement challenges, the approach taken in the Act has grave constitutional infirmities, potentially dangerous consequences for the stability and security of the Internet's addressing system, and will undermine United States foreign policy andstrong support of free expression on the Internet around the world.

The most important point raised in the letter is that it is a violation of free speech. Forgetting the constitutional issue in the U.S., isn't it a bad way for people to interact online? Shutting down a DNS address is much like cutting a person's phone access, something that is simply not done unless the person is about to be arrested. The authors accurately call it an "Internet death sentence". It's far overboard.

The letter also raises the issues with secure DNS, but I believe this is a counter-productive argument. Secure DNS is a gift to anyone who wants to cut off DNS records. Sure, PROTECT-IP as it stands might not work, but all that means is that Secure DNS version 2 will be updated to have a government back door. The problems of PROTECT-IP are not technical.

Most of all, I really wish people could be more creative about digital copyright. You can copy bits, but you can't copy skill. Thus, we would do better to sell skill than to sell the bits that result from them. We can make that change, but expect Hollywood to fight it.

Against manual formatting

2011-06-24T07:37:00.000-07:00

Programming languages are practically always expressed in text, and thus they provide the programmer with a lot of flexibility in the exact sequence of characters used to represent any one program. Examples of manual formatting are:

How many blank lines to put between different program elements
Whether to put the body of an if on the same line or a new line
Whether to sort public members before private members
Whether to sort members of a class top-down or bottom-up, breadth-first or depth-first

I've come to think we are better off not taking advantage of this flexibility. It takes a significant amount of time, and for well-written code, its benefits are small.First consider the time. The first place manual formatting takes time is in the initial entry of code. Programmers get their code to work, and then they have to spend time deciding what order to put everything in. It's perhaps not a huge amount of time, but it is time nonetheless.The second time manual formatting takes time is when people edit the code. The extract method refactoring takes very little time for a programmer using an IDE, but if the code is manually formatted, the programmer must then consider where to place the newly created method. It will take much longer to rearrange the new method than it did to create it.

Worse, sometimes the presentation the first programmer use doesn't make sense any longer after the edits that the second programmer made. In that case, the second programmer has to come up with a new organization. As well, they have to spend the time evaluating whether the new organization is worthwhile at all; to do that, they first have to spend time with the existing format trying to make it work. There is time being taxed away all over the place.

Meanwhile, what is the benefit? I posit that in well-written code, any structural unit should have on the order of 10 elements within it. A package should have about 10 classes, a class should have about 10 members, and a method should have about 10 statements. If a class has 50 members, it's way too big. If a method has 50 statements, it, too, is way too big. The code will be improved if you break the large units up into smaller ones.

Once you've done that, the benefit of manual formatting becomes really small. If you are talking about a class with ten members, who cares what order they are presented in? If a method has only 5 statements, does it matter how much spacing there is between them? Indeed, if the code is auto-formatted, then those 5 statements can be mentally parsed especially quickly. The human mind is an extraordinary pattern matcher, and it can match patterns faster that it has seen many times before.

I used to argue that presentation is valuable because programs are read more than written. However, then I tried auto-formatting and auto-sorting for a few months, and it was like dropping a fifty pound backpack that I'd been carrying around. Yes, it's possible to walk around like that, and you don't even consciously think about it after a while, but it really slows you down. What I overlooked in the past was that it's not just lexical formatting that can improve the presentation of a program. Instead of carefully formatting a large method, good programmers already divide large methods into smaller ones. Once this is done, manual formatting just doesn't have much left to do. So don't bother. Spend the time somewhere that has a larger benefit.

Universities behind borders

2011-06-15T14:12:00.000-07:00

Ronaldo Lemos has a written a thought-provoking article about the role of non-Brazilians in a Brazilian university. He interviews Volker Grassmuck, a German professor working at a Brazilian university, who feels that the result is intellectually insular:

People read the international literature in the fields I’m interested in in. But without having actual people to enter into a dialogue with this often remains a reproduction or at best an application of innovations to Brazil.

That is what I would expect. Academics want to work with other academics in the same specialty, and you aren't going to be able to build such units if you can only hire from the immediate locale. The people you really want will be elsewhere, and the people you get will spend their time trying to emulate them.

I feel that the U.S. is currently too strict on foreign workers for our own good, but we seem to be better off than in Brazil. In the U.S., once they finish groping you and finish making sure you aren't going to take a job in manual labor, you can do as you will. In Brazil, they make you redo your Ph.D. examinations, much like American states do with professional certifications such as dentistry and accounting.

It all seems very dirty to me. If you want a good intellectual atmosphere, you need to admit people from all over.

Peek IPv4 ?

2011-06-10T08:51:00.000-07:00

In its announcement about "IPv6 Day", the Internet Society (ISOC) casually remarked that IPv4 addresses are about to run out:

With IPv4 addresses running out this year, the industry must act quickly to accelerate full IPv6 adoption or risk increased costs and limited functionality online for Internet users everywhere.

This is highly misleading, and the recommended solution is not a good idea. I am sure if pressed the ISOC would respond that by "running out", they mean in the technical sense that some registrar or another has now given away all its addresses. However, the actual verbiage implies something far different. It implies that if you or I try to get an IPv4 address on January 1, 2012, we won't be able to do so. That implication is highly unlikely.

A better way to think about the issue is via price theory. From the price theory point of view, the number of IPv4 addresses at any time is finite, and each address has a specific owner. At the current time, every valid address is owned by some entity or another. (Thus, in some sense they "ran out" a long time ago.)

When a new person wants to get an IPv4 address for their own use, they must obtain the rights from some entity that already has one. While some large organizations can use political mechanisms to gain an IPv4 address, most people must purchase or rent the address from some entity that already owns one. Typically those IP addresses are bundled with a service contract that provides Internet bandwidth, though in some cases addresses can be purchased by themselves.

The price one pays gives us a way to think about the scarcity of addresses. Diamonds are relatively scarce, and their price is correspondingly high. Being 747s are even more scarce, and their price is even higher. For IP addresses, the price is surely rising over time as more and more people hook things up to the Internet. Already the price is high enough that, for example, most home users do not assign a separate publicly routable address to every IP device in their home. They make do with a single IP address from their Internet provider.

What is that price right now? The question is crudely phrased, because some addresses are more valuable than others, and all addresses come with some sort of strings attached. However, we can get a ballpark idea by considering a few data points:

Linode offers its subscribers an extra IP address for $1/month.
Linode offers an IP address along with an Internet hosting service for under $20/month.
Broadband providers such as Comcast and AT&T offer an IP address along with Internet connectivity for on the order of $50/month.

From these observations we can infer that the cost of an IP address is at most a few dollars per month. With the cost this low, I can't see any major site going to IPv6-only any time soon. A few dollars per month is a very low price to pay for a great deal of extra accessibility. With the protocols designed as they are right now, the reason to consider IPv6 is that it's a newer, better protocol, not because it has more available addresses.

I wish public communication about IPv6 would make this more clear. The Internet is important, and as such, it is important that the techies get it right. This isn't a minor technical detail.

Two kinds of type inference

2011-06-09T13:52:00.000-07:00

There are two separate lines of work on type inference. While theyare superficially similar, they face very different design constraints.Let me explain a few of those differences.To begin with, consider the following program. The two kinds ofinference reach different conclusions about it.


  class Foo {
    var x: Object = "a string"
    var y: String = "initial value"
    def copy() {
      y = x    // type error, or no?
    }
  }

Should this example type check? There are two points of view.

One point of view is that the compiler is able to prove that x onlyever holds strings. Therefore y only ever holds strings. Thus, therewill never be a type error at run time, and so the code can be allowedto run as is. This point of view might be called informationgathering. The tool analyzes the code, typically the wholeprogram, and learns type information about that code.

Another point of view is that x holds objects and y holds strings, sothe "x = y" line is a problem. Yes, the current version of xonly holds circles. However, the "x = y" line is using x outside ofits spec, and you don't want to use a variable outside of its speceven if you can temporarily get away with it. This point of view mightbe called slots and tabs. The slot y is not specced to holdthe tab x. From this point of view, the indicated line is an erroreven though the program doesn't have any real problems.

Every user-facing type checker I am familiar with is based on theslots and tabs point of view. The idea is that programmers use typesto provide extra structure to their programs. They don't want evennominal violations of the structure; they really want their types toline up the way they say they do. As a concrete example, imaginethe author of Foo checks in their code, and someone else addsto the program the following statement: "foo.x = Integer.valueOf(12)".Now the nominal type error has become a real one, but the author ofFoo has already gone home. It's better if the author of Foo found outthe problem rather than someone else.

That's one example difference between the two kinds of type inference.A slots-and-tab checker will flag errors that an information-gathererwould optimize away. Here are three other design constraints that differbetween the two.

Declarations are important for a type checker.For the typechecker to know what the slots and tabs are specced as, it must havedeclared types. In the above example, if x and y did not have declaredtypes on them, then the type checker for class Foo could not determinethat there is a problem. To contrast, an information gatherer doesn'tnecessarily pay much attention to declarations. It can usually inferbetter information by itself, anyway.

Changing a published type checker breaks builds. Fora language under development, once a type checker has been published,it takes great care to change it without breaking any existingbuilds. Consider the addition of generics to Java 1.5, where it took agreat deal of energy and cleverness to make it backwards compatiblewith all the existing Java code in the world. To contrast, aninformation gathering type inference can be swapped around atwhim. The only impact will be that programs optimize better or worseor faster or slower than before.

Type checkers must be simple. The type system of aslots-and-tabs type checker is part of the contract betwen thecompiler and a human developer. Human beings have to understand thesethings, human beings that for the most part have something better todo with their time than study types. As a result, there is tremendousdesign pressure on a slots-and-tabs type checker to make the overallsystem simple to understand. To contrast, the sky is the limit for aninformation gatherer. The only people who need to understand it arethe handful of people developing and maintaining it.

Overall, I wish there was some term in common use to distinguishbetween these two kinds of type inferencers. Alas, both kinds of theminfer things, and the things both of them infer aretypes, so the terminology seems inevitable.The best that can be done is to strive to understandwhich kind of type inferencer one is working with. Developers on oneor the other face different design constraints, and they will finddifferent chunks of the published literature to be relevant.

Martin Odersky on the state of Scala

2011-06-02T11:09:00.000-07:00

Martin Odersky talked today at ScalaDays about the state ofScala. Here are the highlights for me.

Tools and Documentation

He doesn't think documentation is a big issue at this point. Peopleused to complain to him about it all the time, and that has largelydied out. I know that this demand for documentation was a largemotivation for him to develop a book about Scala. Perhapsit helped.

He still thinks IDE support is an important problem. However, heclaims the Eclipse support has gotten good enough for him to switchhis compiler hacking from Emacs to Eclipse. That's high praise--Emacsusers don't switch! I will have to try it again.

He emphasizes binary compatibility. In practice, libraries need to berecompiled when a new version of Scala comes out, because inevitablysome trait or another has a new method in it. He has a number of waysto address this. He's long talked about tools to detect and fixproblems by analyzing the bytecodes, and that work is going to beemphasized at TypeSafe. Additionally, new today is that he plans todesignate stable releases of Scala that stay valid for a number ofyears and never have binary-incompatible changes.

He also pointed out that style checking tools would be helpful inlarger development groups. It's a good point. Such tools don't take alot of code, but I guess nobody has gotten interested enough in theproblem to whip one up.

Functional programming

Martin went through an extended example based on a2000 study comparing programming languages. In the study,students implemented a programming problem in one of seven differentprogramming languages. The study is interesting on its own if youhaven't read it before, and among other things shows that there ismuch more variability among programmers than among programminglanguages. However, we can learn something about programming languagesby comparing either the best or the median solutions in each language.

Scala shines well on the programming problem used in the study, andit's because of Scala's excellent support for running functions acrosscollections. Such facilities don't work well unless the language has aconcise notation for functions.Here is the bottom line on several different solutions:

Students using compiled languages: 200-300 lines of code
Students using scripting languages: ~100 lines of code
Martin's solution in Scala: 20-30 lines of code
A Java master's solution in Java: over 100 lines of code

I will attribute the "Java master" if I can find a reliable source, butMartin showed the Java example and it looked pretty reasonable at aglance. The reason it is so long compared to the Scala solution isthat instead of using collection operations, it defines severalrecursive methods that record their progress in extra parameters tothe methods. I've written a lot of code like that in the last few years.I think about the beautiful functional solution, and then I start overwith an imperative solution because inner classes in Java require everso much boilerplate.

Parallelism

Martin talked a bit on his latest thinking on making use of multiplecores, a problem that has obsessed programming-language research forseveral years now. One principle he emphasized is that people are muchmore able to find one solution that works than at finding all thepotential problems that can occur due to non-determinism. Thus, he'sinterested lately in programming-language constructs that are parallelyet still deterministic. That's a tough principle to achieve in anexpressive language! It rules out all of actors (!), agents, andsoftware-transactional memory, because they all have state, and thestate can change differently depending on the non-deterministicchoices the implementation makes.

Aside from the general talk on the challenges of parallelism, Martintalked a bit about the parallel collections in Scala. They're betterthan I realized. Their implementation uses fork-joinwith work stealing, rather than blindly creating lots of threads.As an additional twist, they adaptively choose a chunksize based on how much work stealing appears to be happening. If thereis no work stealing, then every node must be busy, so increase thechunk size.

To demonstrate how the collections can help, he made two tweaks to thephone-number solution to switch from sequential to parallelcollections. After doing so, the program ran 2.5 times faster on a4-core machine. One can imagine doing better than 2.5 times faster,but it's a very good start given how very easy the change was.

Domain-specific languages

Martin emphasized that Scala is excellent for DSLs. However, he pointsout, and I agree, that embedded DSLs in Scala mesh so well that theyare essentially just Scala code. I vastly prefer this style of DSLto the style where you embed the DSL but the constructs of the DSLdon't map well to constructs in the host language. Since the code isdoing something different from what it looks like it does, all kindsof weird bugs can arise. Whenever working on a DSL that doesn't embedin a straightforward way, I'd prefer to make it an external DSL witha plain old parser and interpreter.

Secure DNS supports PROTECT IP

2011-06-01T06:37:00.000-07:00

There is some commentary lately about a paper arguing that PROTECT IP is fundamentally incompatible with secure DNS. This argument is misleading in the extreme. The strategy with DNSSEC is to have root authorities digitally sign DNS records, just like with TLS. As such, it is vulnerable in the same place as TLS. Whoever controls the root servers has ultimate control over what Internet-connected computers will consider to be the truth.

Far from making PROTECT IP more difficult, a hypothetical success of DNSSEC would make it easier. With DNS as it currently works, governments must contend with what, from their perspective, are rogue DNS servers that continue to post "false" (meaning correct) addresses. Under DNSSEC, the rogue server's certificate chains will not check out. Whenever a government orders a domain name to be changed, the root servers will not just issue the new address, but presumably also cryptographically revoke the old one. It would all work as if it were the legitimate domain owner making the request instead of a government.

I don't think the technical arguments about PROTECT IP are convincing. DNS is by its nature a sitting duck. The technical argument I would make is that a global Hierarchy of Truth is not a good approach to security on the Internet. If you don't like PROTECT IP, then you shouldn't like DNSSEC nor DNS as we currently know it.

Given how things technically work right now, however, the best argument against PROTECT IP is simply that we don't want to live that way. Do we really want to live in a world where Sony or Blizzard or MGM can turn off a web site without the site owner getting to defend themselves in court? Is 20th century copyright really worth such heavy handed measures?

Google Wallet: Why NFC ?

2011-05-26T16:04:00.000-07:00

I was excited to read that Google is going to build a payment method based on a smartphone:

Today in our New York City office, along with Citi, MasterCard, First Data and Sprint, we gave a demo of Google Wallet, an app that will make your phone your wallet. You’ll be able to tap, pay and save using your phone and near field communication (NFC). We’re field testing Google Wallet now and plan to release it soon

I have long wished that payments could be made using an active device in the buyer's possession rather than having the buyer type secret information--a PIN--into a device the seller owns. It requires that a device the buyer has never seen before be dilligent about deleting the PIN after it is used. It also requires that a device the buyer has never seen before is making the same request to the bank that it is displaying on its screen. Security is much higher when using a device the buyer owns.

The main flaw with this approach is that it requires people to carry around these active devices. Google's bright idea is to make that device be a smartphone. Brilliant.

The one thing I don't understand is why Google is only supporting it using NFC. I had never heard of NFC until today, and for any readers like me, it is basically it's a really dumb, short-range, low-bandwidth wireless protocol. It sounds well-suited for the application, but no current phones support it.

An alternative approach that should work with current phones is to use bar code reading software. The seller's hardware would display a barcode that includes a description of what is being bought, the amount of money, and a transaction ID number. It would simultaneously upload the transaction information to Google. The buyer would scan the bar code, and if the user authorizes the payment, it would send authorization to Google. The seller would then receive notification that the payment has been authorized. For larger transactions, further rounds of verification are possible, but for groceries and gas, that could be the end of the story.

Why limit the feature to NFC devices? While NFC solutions look a little more convenient, barcodes don't look bad. Why not offer both?

Regehr on bounding the possible benefits of an idea

2011-05-25T07:34:00.000-07:00

John Regehr posted a good thought on bounding the possible benefits of an idea before embarking on weeks or months of development:

A hammer I like to use when reviewing papers and PhD proposals is one that (lacking a good name) I call the “squeeze technique” and it applies to research that optimizes something. To squeeze an idea you ask:
How much of the benefit can be attained without the new idea?
If the new idea succeeds wildly, how much benefit can be attained?
How large is the gap between these two?

I am not sure how big of a deal this is in academia. If you are happy to work in 2nd-tier or lower schools, then you probably need to execute well rather than to choose good ideas. However, it's a very big deal if you want to produce a real improvement to computer science.

The first item is the KISS principle: keep it simple, stupid. Given that human resources are usually the most tightly constrained, simple solutions are very valuable. Often doing nothing at all will already work out reasonably. Trickier, there is often a horribly crude solution to a problem that will work rather effectively. In such a case, be crude. There are better places to use your time.

The second item is sometimes called a speed of light bound, due to the speed of light being so impressively unbeatable. You ask yourself how much an idea could help even if you expend years of effort and everything goes perfectly. In many cases the maximum benefit is not that high, so you may as well save your effort. A common example is in speeding up a system. Unless you are working on a major bottleneck, any amount of speedup will not help very much.

IRBs under review

2011-05-19T15:46:00.000-07:00

There are several interesting blog entries up at blog.bioethics.gov concerning the ongoing presidential review of Internal Review Boards.

I liked this line:

“We pushed for an ethical reform of system, real oversight, and now we are left with this bureaucratic system, really a nitpicking monster,” Arras said, addressing Bayer. “And I am as stupefied as you are.”

I am not sure why this pattern would be stupefying. A great many things that people attempt to do don't work out as intended. IRBs are just one more for the list, albeit one that has lingered for decades.

I am not as sanguine about the reviewers about this conclusion about whether another "Guatemala" could happen:

“Of the many things that happened there, no, it could not happen again because of informed consent,” said Dafna Feinholz, chief of the Bioethics Section, Division of Ethics and Science and Technology, Sector for Social and Human Sciences, United Nations Educational, Scientific and Cultural Organization.

The idea is that since IRBs require informed consent of study participants, the Guatemala experiments could never again happen, because the study participants would know what is going on.

I hope so, but consider the following evil scenarios:

A wealthy autodidact negotiates directly with local authorities and runs the experiment on his own dime. No university is involved, so no IRB review even happens.
A university researcher learns about a disease outbreak in some part of the world. The researcher waits two years and then applies for a research grant to study the effects of the disease. Since the researcher did nothing for the first two years, there was nothing for the IRB to review.
The Professor Muckety, Chair of Hubert OldnDusty at BigGiantName University, announces a grand new experiment that he expects will cure cancer. He invites all of the upcoming faculty in his area to take part in it, and there will be numerous papers and great acclaim to all the participants. The IRB at BigGiantName U.'s is stacked with faculty that are totally brainwashed into thinking the experiment is for the greater good. Will they really take a stand against the project?

I would not be so sure that, despite all the efforts of IRBs, an evil experiment couldn't happen again.

Whenever something goes wrong, there is a natural reaction for everyone to yell, "DO SOMETHING!" IRBs are the result of such an outcry. They are there to project human subjects, but I don't believe they are very effective at that. I believe that the MucketyMucks largely breeze through the red tape doing whatever they like, and instead we are staffing a bunch of bureaucrats to check that the smaller players filed form T19-B in triplicate, double spaced and typed with a manual type writer.

To improve on the current mess, carving out a large exempt category would be a large improvement. Surveys, observations, and other experiments with minimal opportunity for harm shouldn't need prior review.

It was just getting started...

2011-05-17T11:18:00.000-07:00

There are many things wrong with California jumping in to regulate Facebook's privacy policies:

Facebook is a world-wide service, not a California service. Why is this up to California?
Facebook has over five hundred million users. That's five times more than the number of people who watch the SuperBowl. Whatever Facebook is doing, it must be pretty reasonable.
Social network sites tend to only last about five years before the next new hotness overtakes them. The odds are against Facebook lasting all that long.

All of these matter, but the last one is most peculiar to Internet services. I really want to see what the next social site is like, and the next site after that. I don't relish a long sequence of watered-down Facebook clones with all of their paperwork properly stamped and in order. How dreary.

A package universe for Lisp

2011-05-16T13:54:00.000-07:00

Quicklisp is a package manager for Common Lisp that is popular among Lisp programmers. I'm happy to read that one of their secrets to success is quality control in the central distribution:

Quicklisp has a different approach:
Quicklisp does not use any external programs like gpg, tar, and gunzip.
Quicklisp stores copies of project archives in a central location (hosted on Amazon S3 for reliability and served with Amazon CloudFront for speed).
Quicklisp computes a lot of project info in advance. Projects that don't build or don't work nicely with other projects don't get included.

I would quibble with the order of their bullet points, because the last point is overwhelmingly important. It isn't a little side benefit to have a well-defined distribution and to test the members of that distribution against each other. On the contrary, it's a make or break property of the system if you want users to have some level of confidence in the code they're downloading.

Sven Efftinge on Java-killer languages

2011-05-11T13:06:00.002-07:00

I just ran across Sven Efftinge's fun post on what he wants to see in a Java-killer language.

My list would be something like: remove boilerplate for common coding arrangements, make things easier to understand, be compatible with existing Java code, and otherwise leave everything alone.

Sven has a more detailed list. Here are his bullet points and some thoughts on them:

1. Don't make unimportant changes. Gosh yes. Changing = to :=, or changing the keywords, adds a barrier to entry for anyone learning the language. Don't do it without a real benefit.

2. Static typing. Static typing is one of those choices where the up-front choice is far from obvious and has many intangibles, but once you choose, many of the follow-up choices are fairly clear to people who know the area. I think it is perfectly reasonable to have untyped languages on the JVM, and I think it's perfectly reasonable to have simply typed languages with generics only used for collections. Note that the choice will strongly influence what sorts of applications the language is good for, however. Additionally, I would emphasize that today's type systems have gotten more convenient to use, so the niche for untyped languages is smaller than it used to be.

3. Don't touch generics. Java's type system is long in the tooth. While its basic parametric types are fine, there are parts that are simply bad: raw types, wildcards, arrays, and primitive types. If you are developing a Java killer, improving the type system is one of the ways you can improve the language. You'd be crazy not to consider it.

4. Use type inference. Absolutely. This is a large source of boilerplate in Java.

5. Care about tool support (IDE). I agree. When I joined the Scala project in 2005, I was glad to see that the core team was working on a number of tools, including: scaladoc, the scala command (repl, script runner, and object runner), scalap, ant tasks, and the Eclipse plugin. Nowadays there are even more tools, including an excellent IntelliJ plugin and integration with a larger number of build tools.

In a nutshell, making programmers productive requires more than a good programming language. There are huge benefits to good tools and rich libraries. The overall productivity of a programmer is something like the product of language, tools, and libraries.

6. Closures. Yes, please. The main reason to leave it out historically is the lack of garbage collection. I don't understand why Java has been so slow to adopt them, and I was terribly saddened to hear Guy Steele at OOPSLA 1998 pronouncing that Java didn't look like it really needed closures. It was surreal given the content of the talk that he had given just minutes before.

7. Get rid of old unused concepts. Yes, in general. However, this can be hard to do while also maintaining compatibility and generally letting people write things in a Java way if they want. For the specific things Sven lists: totally agreed about fall-through switch; totally agreed about goto, but it's not in Java anyway; not so sure about bit operations. Bit operations are useful on the JVM, and besides, Java's numerics work reasonably already. Better to focus on areas where larger wins are possible.

Free linking on the web?

2011-05-11T07:53:00.000-07:00

Lauren Weinstein has a great article up on the efforts of governments around the world to make Internet material disappear. One tactic for this is to go after search engines:

In Europe, one example of this is the so-called Spanish “right to be forgotten” -- currently taking the form of officials in Spain demanding that Google remove specific search results from their global listings that “offend” (one way or another) particular plaintiffs.

I agree with Weinstein's conclusion:

We are at the crossroads. Now is the time when we must decide if the Internet will continue its role as the most effective tool for freedom of information in human history, or if it will be adulterated into a mechanism for the suppression of knowledge, a means to subjugate populations with a degree of effectiveness that dictators and tyrants past could not even have imagined in their wildest dreams of domination.

The U.S. is in a position to affect that future. Currently, it is gradually inserting censorship backdoors into the Internet at the request of its music and film industries. It's not worth the cost. I freely admit that Hollywood is wonderful, but we should remember that Broadway is pretty cool, too. Unlike Hollywood, Broadway has business models that don't require an Internet overload.

Externally useful computer science results

2011-05-10T14:47:00.000-07:00

John Regehr asks what results in computer science would be directly useful outside the field. I particularly like his description of his motivation:

An idea I wanted to explore is that a piece of research is useless precisely when it has no transitive bearing on any externally relevant open problem.

A corollary of this rule is that the likelihood of a research program ever being externally useful is exponentially decreased by the number of fundamental challenges to the approach. Whenever I hear about a project relying on synchronous RPC, my mental estimate of likely external usability goes down tremendously. As well, there is the familiar case of literary deconstruction.

Regehr proceeds from here to speculate on what results in computer science would truly be useful. I like most of Regehr's list--go read it! I would quibble about artificial intelligence being directly useful; it would be better to be more specific. Is Watson an AI? It's not all that much like human intelligence, so perhaps it's not really AI, but it is a real tour de force of externally useful computer science.

One thing not on the list is better productivity for software developers, including tools, programming languages, and operating systems. When software developers get more done, more quickly, more reliably, anything that includes a computer can be built more quickly and cheaply.

Maintaining an intellectual nexus

2011-04-30T09:04:00.000-07:00

It saddens me to read the comments about Scala Days on scala-lang.org. The only two comments are from people who won't be coming because of U.S. border inspections. It's not possible to tell how many people really avoid the conference because of this problem. What we know, however, is that potential attendees are weighing it in their decision.

Paul Graham has written a great essay describing the conventional wisdom about the intellectual nexus that is Silicon Valley. One aspect he emphasizes is immigration:

I doubt it would be possible to reproduce Silicon Valley in Japan, because one of Silicon Valley's most distinctive features is immigration. Half the people there speak with accents. And the Japanese don't like immigration. When they think about how to make a Japanese silicon valley, I suspect they unconsciously frame it as how to make one consisting only of Japanese people. This way of framing the question probably guarantees failure.

A silicon valley has to be a mecca for the smart and the ambitious, and you can't have a mecca if you don't let people into it.

I've written before that the effective workspaces I've seen all involve a mix of workers from all over the world. Making people work with only people who look like each other and have the same accents is much like only allowing marriages within one's own clan. You get better matchups if you let people date more widely.

The same is true for conferences. Ideas feed back on each other, with multiple sparks contributing to starting the fire. It often takes more than one good idea to make progress on something. Any of those ideas alone doesn't get you part of the progress. It gets you none. Concentrating people together is an essential ingredient to having a productive conference.

Unfortunately, border control, xenophobia, and general empowerment of the police have increased with every U.S. president since the fall of the Berlin Wall. You wouldn't know it from the news or from the talking heads, but if you do some brief web research you can verify it is true. The current president brought us airport gropes and is also responsible for the line, "Because of recent circumstances, the underwear was taken away from him as a precaution to ensure that he did not injure himself". I don't detect any trend in a positive direction.

I'm spitting into the wind here in the hopes that any change must start somewhere. Xenophobia is not just wrong, and it's not just unpleasant. It's making us dumber and poorer.

Types are fundamentally good?

2011-04-25T10:47:00.000-07:00

Once in a while, I encounter a broad-based claim that it's fundamentally unsound to doubt the superiority of statically typed programming languages. Bob Harper has recently posted just such a claim:

While reviewing some of the comments on my post about parallelism and concurrency, I noticed that the great fallacy about dynamic and static languages continues to hold people in its thrall. So, in the same “everything you know is wrong” spirit, let me try to set this straight: a dynamic language is a straightjacketed static language that affords less rather than more expressiveness.

Much of the rest of the post then tries to establish that there is something fundamentally better about statically typed languages, so much so that it's not even important to look at empirical evidence.

Such a broad-based claim would be easier to swallow if it weren't for a couple of observations standing so strongly against it. First, many large projects have successfully been written without a static checker. An example would be the Emacs text editor. Any fundamental attack on typeless heathens must account for the fact that many of them are not just enjoying themselves, but successfully delivering on the software they are writing. The effect of static types, whether it be positive or negative, is clearly not overwhelming. It won't tank a project if you choose poorly.

A second observation is that in some programming domains it looks like it would be miserable to have to deal with a static type checker. Examples would be spreadsheet formulas and the boot scripts for a Unix system. For such domains, programmers want to write something quickly and then have the program do its job. A commonality among these languages is that live data is often immediately available, so programmers can just as well run the code on live data as fuss around with a static checker.

Armed with these broad observations from the practice of programming and the design of practical programming languages, it's easy to find problems with the fundamental arguments Harper makes:

"Types" are static, and "classes" are dynamic. As I've written before, run-time types are not just sensible, but widely used in the discussion of languages. C++ literally has "run-time types". JavaScript, a language with no static types, has a "typeof" operator whose return value is the run-time type. And so on. There are differences between run-time types and static types, but they're all still "types".
A dynamic language can be viewed as having a single static type for all values. While I agree with this, it's not a very useful point of view. In particular, I don't see what bearing this single "unitype" has on the regular old run-time types that dynamic languages support.
Static checkers have no real restrictions on expressiveness. This is far from the truth. There has been a steady stream of papers describing how to extend type checkers to check fairly straightforward code examples. In functional languages, one example is the GADTs needed to type check a simple AST interpreter. In object-oriented languages, the lowly flatten method on class List has posed difficulties, because it's an instance method on class List but it only applies if the list's contents are themselves lists. More broadly, well-typed collection libraries have proven maddeningly complex, with each new solution bringing with it a new host of problems. All of these problems are laughably easy if you don't have to appease a static type checker.
Dynamic languages are slow. For some reason, performance always pops up when a computer person argues a position that they think is obvious. In this case, most practitioners would agree that dynamic languages are slower, but there are many cases where the performance is perfectly fine. For example, so long as Emacs can respond to a key press before I press the next key, who cares if it took 10 microseconds or 100 microseconds? For most practical software, there's a threshold beyond which further performance is completely pointless.

Overall, type checkers are wonderful tools. However, any meaningful discussion about just how they are wonderful, and to what extent, needs to do a couple of things. First, it needs some qualifiers about the nature of the programming task. Second, it needs to rest on at least a little bit of empirical data.

Practical challenges for attribute grammars

2011-04-21T11:34:00.000-07:00

I've had occasion recently to work on a compiler implemented with an attribute grammar framework. Such frameworks let you declare attributes on AST nodes that are computed in terms of other attributes. In general, it's a powerful and convenient way to compute information about an AST, and I expect they make a lot of sense in tools that only analyze ASTs and don't generate or rewrite them. They save you from working out a specific computation order, because the tool can look at which attributes refer to which other ones and compute them all on demand.

For compilers, however, I no longer think attribute grammars work well. Let me describe three fundamental problems with attribute grammars for use in compilers.

Attributes can be inherited, meaning they look up in the AST to for information. Examples are the expected type of an expression, the enclosing module for any node, and the set of free variables available in some context. These computations cannot be computed unless the node in question really is attached to an AST. However, compilers create new AST nodes all the time, and while those new nodes are being set up, they can't possibly be attached yet. Thus, unattached nodes are inconsistent with inherited attributes.
Compilers change the AST. They desugar syntax into lower-level syntax, they optimize, they reorder parts of the program, and so on. Every time the AST changes, some cached attribute values become invalid. At that point, how do you flush the caches that are now invalid? To some extent you can get by by flushing all caches after every compiler phase. However, this means that later parts of a phase will see stale data compared to earlier parts. This situation results in bugs where, to fix them, you have to reason about the exact order that the traversal happens and the relationship of the stale data to the current version of the AST.
Attributes have unpredictable performance characteristics. When you see a reference to an attribute, it might be cached and take constant time. On the other hand, it might trigger a chain of attribute computations that chain across the whole program. It's much harder to convince yourself that a particular AST traversal will operate in linear time, because you don't know how expensive all the attribute computations are.

These are all potentially addressable, but they are serious challenges that any practical tool will need to face. As things stand, I haven't seen an attribute grammar framework that is there yet. They don't really achieve their main benefit, which is to save you from reasoning about order of evaluation of and dependencies between different attributes. You end up reasoning about them anyway to get the bugs out and the performance up.

Instead of storing attributes on the AST nodes and computing them with an attribute grammars framework, a more traditional approach is as follows. Store a few, carefully selected bits of information on nodes, such as the types of expressions. These things must be carefully maintained across all AST rewrites, and the compiler will be buggy if you get it wrong, so don't store too much this way. For most information, have each compiler phase compute and maintain whatever information it needs. This results in some amount of computation, but you can usually find a way to calculate whatever you need in linear time. Since any one phase will usually require at least linear time, anyway, this is sufficient for getting the compiler reasonably performant before you do your first profile run.

Programming in Scala available online

2011-04-13T17:29:00.000-07:00

Artima has graciously agreed to post the first edition of Programming in Scala online for free. It's now easier than ever to learn about Scala.

Appel on seal protocols for electronic voting

2011-04-04T12:08:00.000-07:00

Andrew Appel reminds the public that good election protocols were historically rather difficult to develop:

Democratic elections present a uniquely difficult set of problems to be solved by a security protocol. In particular, the ballot box or voting machine contains votes that may throw the government out of office. Therefore, it's not just the government--that is, election officials--that need evidence that no tampering has occurred, it's the public and the candidates.[...] In the late 19th century, after widespread, pervasive, and long-lasting fraud by election officials, democracies such as Australia and the United States implemented election protocols in an attempt to solve this problem. The struggle to achieve fair elections lasted for decades and was hard-fought.

It's a good point. I believe with modern mathematical tools, we should be able to develop good protocols much faster than a period of decades. However, before such problems can be solved, there must be an awareness that there is a problem at all. For whatever reason, elections all over the U.S. are using terrible voting machines and protocols that are worse than the old hole-punch machines. It's as if all these locales simply bought the voting machines with the lowest bid.

In general, government requisitions need to come with a long string of requirements, because officials are largely going to have to choose the cheapest product that meets the requirements. Anything not in the requirements is likely to be cut in the interest of cost savings. In the case of voting software, a key part of those requirements is to have sensible voting protocols.

Dan Wallach on fixing the certificate authorities

2011-04-01T09:43:00.000-07:00

I like the latest ideas from Dan Wallach about building better infrastructure for browsers to detect impostor web sites.

First, there's this:

A straightforward idea is to track the certs you see over time and generate a prominent warning if you see something anomalous. This is available as a fully-functioning Firefox extension, Certificate Patrol. This should be built into every browser.

This is similar to pet names, but is more similar to the way SSH works. Like Pet Names, this approach will tell you if you visit a site and its certificate has changed. Unlike Pet Names, it won't say anything when you visit a new site. There's a trade off there. Either is a big improvement on the current state, though I suspect pet names could lead to a better overall user interface. The reason is that pet names can be integrated with the browser's bookmarks.

Second, there's this more speculative request:

In addition to your first-hand personal observations, why not leverage other resources on the network to make their own observations? For example, while Google is crawling the web, it can easily save SSL/TLS certificates when it sees them, and browsers could use a real-time API much like Google SafeBrowsing.

The Y property would give us this effect. What if, when you got a Google search result, it not only told you the URLs for the hits but also the certificates for those pages? You can then only be attacked if the attacker fools both you and also every Google web crawler.

Let me add one thing. If web protocols used these two tricks, how important would certificate authorities be? These two decentralized techniques strike me as so much more effective that certificate authorities are a waste of time. If you already know that a site is the same one you've visited a dozen times, and you already know it's the same site that Google thinks it is, what do you care about what some Iranian agency thinks of the site?

A computer science journal with open access

2011-03-30T08:57:00.000-07:00

Since writing that economics has an online open-access journal, I've been informed that computer science has at least one: Logical Methods in Computer Science. Mea culpa.

Perhaps the ACM can follow their lead.

When stateful code is better

2011-03-29T14:38:00.000-07:00

One branch of functional-programming enthusiasts have long strived to eliminate state from programming. By doing so, you end up with program code that supports equational reasoning. If you know a=b in one part of the code, then you can freely replace a by b and b by a anywhere else in the code. Since there's no state, the program will still behave the same. It's good stuff.

Nonetheless, state is essential for good code in most languages. You don't want to live without it. Take a moment to consider the more practical of functional programming languages, and see how programmers in those languages have voted with their feet. ML, the most popular typed, strict functional language, includes ref cells in the core language. Haskell, the most popular typed, lazy functional language, includes not just the state monad but also UnsafeIO. Lisp and Scheme, the most popular untyped functional languages, shamelessly include state everywhere. It's a clean sweep. Functional programmers are using languages that have state.

Why is this? Let me describe a couple of programming problems that any practical language needs to be able to solve. Both of these problems are easy with state and hair-pulling without. Any language without state will give programmers a tough time with these problems, so such languages don't become popular. The two problems are: logging, and the model-view architecture.

With logging, what you'd like to do is write your program as normal and then insert log messages here and there in the code. As much as possible, you want to avoid disturbing the core logic of the program with the logging behavior. Solving this problem using state is so easy it's hard to even talk about. All you do is use that state, typically an external file system. Every time you want to log something, write the message to the state.

What if you want to log without state? In that case, you have to pass around the log as a parameter to every function in the program that might want to log anything. Every function gets an extra parameter which is the state of the log before the function call. Such functions must also return that extra parameter, after updating, when they finish. This approach has two large problems. First, it requires pervasive changes throughout the code base to pass around the latest version of the log. Second, it's highly error prone. For example, the following function logs two messages but accidentally discards the first one:

def doTwoThings(log) = {
val log1 = write(log, "about to do first thing")
doFirstThing()
val log2 = write(log, "about to do second thing")
doSecondThing()
return log2
}

This kind of problem can probably be prevented with linear types, and many functional language researchers would observe this and go do a bunch of research on linear types. Until they come up with something, your best bet is to use state.

A second example is event handling in the model-view architecture that is so pervasive in practical code. In the model-view architecture, you write the program in two layers: one layer for the core model of the software and one layer for the view. Views have a pointer to their models, and whenever the model changes they update themselves. This way, the model code stands alone and can be analyzed and unit tested without needing a user interface. The view, meanwhile, focuses on user interfaces, and can be tested on its own if you stub out the model. It's a fine architecture, well worth its popularity. Here's the challenge for stateless programming: how do you update the model in response to an event?

In a stateful language, what programmers can do is mutate the model in place. Every pointer from the view to the model will still be valid, so the view doesn't need any changes to its structure. Again, it's so simple it is hard to even talk about.

Now consider a stateless language. In a stateless language, you must not only update the model, but must also update any view object that refers to any part of the model that changed. Likewise, you have to update any view object that has a reference to any such view object, transitively. There's no theoretical bar from programming like this. However, your process-event object ends up taking a view as an argument, just so that it can update all the pointers from the view to the updated model. This approach is tedious and error-prone in the same way as with stateless logging. It's very easy to leave some parts of the view pointing to old parts of the model. If you do that, things will mostly work, but there will be stale data in parts of the view.

In general, stateless code is usually better. However, I can't escape believing that for logging and for the model-view architecture, it's the stateful version that is best. These problems share the aspect that there are references from one component (main application, view) to a separate component (log file, model), and the second component is undergoing change. By letting the reference be stateful, the two components can work with each other at arm's distance. Contrary to its usual reputation, state in such cases is a help rather than a hindrance for building useful abstractions.

Economics now has an online journal

2011-03-28T06:57:00.000-07:00

Economics joins the ranks of those fields with an online academic journal. All papers are free for download. They've even back-posted all the old papers back to 1970. Feel free to click through and browse around. There's no registration or charge.

The next best thing to open access is preprint archives, the most prominent of which is ArXiv (pronounced "archive"). ArXiv is infrastructure to upload papers that are usually also submitted to a journal or conference. I first heard of preprint archives as used among physics researchers. Physics is a natural enough field to kick this off considering that they built the the World Wide Web to host their papers. Physicists publish in journals that have long review and publication delays, on the order of 6-12 months, and they seem to have realized that a 6-12 month ping time is not good for a group conversation.

I applaud BPEA going open access, and I wish computer science proceedings would do the same thing. Currently, all the American conferences are published through the ACM digital library, which has a dizzying array of subscription plans that has been designed to maximize profit. The current model in computer science is that CS research is IP for the ACM to sell for profit, much like a CD or a DVD. I would prefer a model where CS research is meant to advance science. Pay walls have a damping effect on discussion, and science without discussion isn't really science at all.

Certificate authority compromised

2011-03-24T07:03:00.000-07:00

Wired reports:

In a fresh blow to the fundamental integrity of the internet, a hacker last week obtained legitimate web certificates that would have allowed him to impersonate some of the top sites on the internet, including the login pages used by Google, Microsoft and Yahoo e-mail customers.

As a rule of thumb, a system that requires the entire world to cooperate and do things right is unlikely to work very well. This is particularly true for security software, where the very point of the software is to defend against those that misbehave.

The good news is that TLS certificates aren't that effective anyway, so the breach didn't cause much harm. The harm is more like someone breaking through a gauzy curtain than someone breaking into a bank vault. Few people notice if they are even connected via http or https, and TLS only helps for https connections. As well, if you connect to bankammerica.com instead of bankamerica.com, certificates won't save you. Further, what exactly can a certification authority ever certify even if everything checks out? Pretty much all they can do is verify that you are connecting to the owner of the given DNS address. It doesn't mean that bankamerica.com is really the web site for the Bank of America you are trying to contact.

TLS certificates are a case of following a beautiful theory that mismatches reality. The theory is that people gain trust in a web site by having a lot of third-party certificates attesting to that web site's authenticity. The more reputable the sites, the better.

To see that this is an odd theory, consider how it is that we believe a person we are talking to is who we think they are. It's almost never because we checked their ID and are savvy enough to know whether it's a fake ID or not. A more plausible source of trust is that we recognize that we're talking to the same person we talked to yesterday. Another more likely way is that we were introduced to the person by someone else that we trust, so we tentatively start talking to the new person based on that contact.

There are web analogies for both of these processes. If we visit the same site two days in a row, our browsers could tell us this via an improved bookmarking system such as the Pet Names toolbar. If one site links to another site, then we gain confidence in the second site corresponding to how we thought about the first site. That's hyperlinking, and it could be improved by a system like YURLs.

Neither such mechanism, however, is getting much attention. The action is all in certificate chains. For some reason, engineers are fixating on an approach where truth descends down a hierarchy and where end users are able to study and act on these delivered truths. Web protocols would be better, it seems to me, if they relied on more realistic models of identification that mirror what we do in our social lives.

Prior permission for indexing books?

2011-03-23T11:07:00.000-07:00

Timothy Lee writes that the agreements backing Google Books are undergoing renegotiation. He argues that Google should seek a fundamental legal principle rather than negotiating a contract via class-action law.

Fair use exists as a kind of safety valve for the copyright system, to ensure that it does not damage free speech, innovation, and other values. Although formally speaking judges are supposed to run through the famous four factor test to determine what counts as a fair use, in practice an important factor is whether the judge perceives the defendant as having acted in good faith. Google has now spent three years looking for a way to build its Book Search project using something other than fair use, and come up empty.

I like this approach better myself. It's better to have simple, common-sense rules about proper rules of engagement than to have a thousand-page contract that nobody has even read in its entirety. For books, part of the common sense rules would include that indexing is allowed, and that abandonware is largely free reign, at least until the owner shows up again.

To contrast, the current approach has Google negotiating a contract that will bind all authors. That seems a little weird given that all authors aren't really present. It doesn't seem like a good fit for contract negotiation. It's one of those rare beasts that is a good fit for our legislative bodies to sort out.

Robin Hanson against IRBs

2011-03-23T05:51:00.000-07:00

Robin Hanson makes the case against Internal Review Boards for research on human subjects:

IRBs seem a good example of concern signaling leading to over-reaction and over-regulation. It might make sense to have extra regulations on certain kinds of interactions, such as giving people diseases on purpose or having them torture others. But it makes little sense to have extra regulation on researchers just because they are researchers. That mainly gets in the way of innovation, of which we already have too little.

I agree with Robin. Mistreatment of fellow humans should certainly be stopped. However, why should academic researchers have to go before a board any time they want to interact with humans, just because they are researchers?

For the majority of legal responses that our society makes, the approach we take is that people act first and then, if there is wrongdoing, the legal system follows up. For example, you don't get interviewed before you buy a gallon of gas. You get interviewed after a house burned down with your car parked outside of it. You don't go before a board before you grade a stack of papers. You go before a board after it is rumored that you told people what other people's grades were. Prior review is stifling.

People who defend IRBs probably assume that they will apply a large dose of common sense about what is dangerous and what is not. For example, surely the IRBs for an area like computer science will simply green light research all day long. In practice, it seems they look for work to do to justify their budgets. Witness the treatment of "exempt" research, where IRBs that have the manpower to do so tend to require review even of "exempt" research projects.

I can only speculate why such a useless and harmful institution persists, but a big part of my guess is that Robin's signalling explanation is correct. If you are the president of a university, could you ever take a stand against IRBs? Such a stand would have the appearance of signalling that you are soft on protection of humans. I wish that people would pay less attention to signals and more attention to results. Pay less attention to how many institutes, regulations, and vice presidencies have been created, and pay more attention to exactly how a university is treating the people it draws data from.

Defining neutral web search

2011-03-21T15:10:00.000-07:00

I like South Bend Seven's depiction of that process:

"Let's adjust the learning parameter to .00125 and the momentum factor to .022." "Sure thing, but we better run that by Legal first." There's a recipe for success

Perhaps in 40-50 years, there will be a stable version of the World Wide Web that it makes sense to clamp down with regulation, including search neutrality. However, right new, the web is changing way too fast.

Looking backward, imagine what kind of standards would have been written for a web search back when Alta Vista was the best. What are the odds that a government effort would have a reasonable approach to ranking pages according to linkage patterns? How about deciding what counts as a keyword? Is Zeitgeist one word or two? How about the "did you mean" results? If such an attempt had succeeded, then today we wouldn't even know about these innovations. They would have been squashed by the regulation before anyone could try.

Looking forward, imagine all the ways the web might change in the coming decade. What if more of the web moves into social spaces that have severe privacy needs, such as Facebook and Orkut? What if more of the content uses rich media, as do physical magazines, and is less possible to describe using plain text? What if things go the other way, and the web's information becomes a scattering of little sentences that are glued together on the fly for a particular user's settings?

The search neutrality project can only impoverish our Internet. I'm not clear on why the American government has jurisdiction over the "World" Wide Web, but to the extent they do, I hope they do the right thing and just go take a nap.

Battling over the top-level domains

2011-03-16T12:56:00.000-07:00

Brad Templeton has some good comments up on top-level domains in the DNS.

Their heart is in the right place, because Verisign’s monopoly on “.com” — which has become the de facto only space where everybody wants a domain name, if they can get it — was a terrible mistake that needs to be corrected. We need to do something about this, but the plan of letting other companies get generic TLDs which are ordinary English words, with domains like “.sport” and “.music” (as well as .ibm and .microsoft) is a great mistake.

There is one option Brad doesn't mention: do away with TLDs. This would have two advantages. First, it would remove needless drag from the current system. Everyone agrees that TLDs are nearly useless and that practically everyone goes for .com anyway. Web browsers even add a .com for you automatically if you leave it off. Why bother adding it at all? Second, it would remove security problems that happen due to confusion about a top-level domain, e.g. mixing up Amazon.fr and Amazon.rf.

More ambitiously, it would be nice to move away from registering English-language words at all. Instead, use IP addresses as the globally unique address. To get English-language names for web sites, use something that is not globally unique, such as pet names. I wish I could point to a concrete implementation of such a system to rely on, but I believe a good system could be designed.

If such a system sounds weird, ponder for a moment just how much you trust DNS names, anyway. If you want to go to Bank of America's web site, which is more reliable. You typing out bankofamerica.com letter-for-letter perfectly, or doing a web search on "Bank of America" and using the top hit? As this example shows, DNS as it stands is not a particularly good solution for naming sites using English-language words. It's merely a tolerable system that sort of works, that has become a de facto standard at this point.

Trial by jury in the U.S.

2011-03-06T07:14:00.000-08:00

Pretty sad stuff from the WikiLeaks case:

Pfc. Bradley E. Manning, the Army intelligence analyst accused of leaking government files to WikiLeaks, will be stripped of his clothing every night as a “precautionary measure” to prevent him from injuring himself, an official at the Marine brig at Quantico, Va., said on Friday. Private Manning will also be required to stand outside his cell naked during a morning inspection, after which his clothing will be returned to him, said a Marine spokesman, First Lt. Brian Villiard.

Imagine how he'll be treated if he is actually convicted of anything.

I don't believe that U.S. oversight over most any aspect of the Internet will make things better. I don't expect them to support content carriers in the best of times, and certainly not ones like WikiLeaks that post material embarrassing to the U.S.

Avoiding big-bang updates

2011-03-01T07:00:00.000-08:00

A big-bang update is a system update where the entire system must be shut down, multiple components are upgraded in parallel, and then the whole system is turned back on. If it goes well, then BANG, the whole system is upgraded in one big swoop. If it goes well, you lose a day or two of work from everyone working on that system, which is already pretty bad, but at least it's only a day or two. It often doesn't go well, however. Often, there is some dependency that snuck through early testing, and the one or two days extends into three, four, or five as engineers panic to patch up the lurking problems.

With a little foresight, big-bang updates can usually be avoided. The basic requirement is that system components can be updated one by one, without needing to update multiple components at the same time. That, in turn, implies that the bulk of components need to tolerate both the current versions of all other components as well as the upcoming version. Solve the multi-version dependency problem, and you can avoid big-bang updates.

Depending on multiple versions can be tricky. A common situation that arises, for any kind of system, is a desire to change a name that is shared between two different components. If the components are modules of source code, then the name might be a class name that is exported from one module and imported by others. If the components are hooked up using HTTP, then the names might be URLs. The temptation is to change the name, but that leads to a big-bang update. Every component that uses the name has to be updated at the same time. To avoid the big bang, try to find a way to support both the old name and the new name during a transition period. Then all components can be updated one by one to support both names. Once everything has been updated, it is possible to gradually drop support for the old name. It takes longer but it avoids a big bang.

An instance of the problem in programming languages is that module interfaces often tempt programmers into big-bang updates. For example, experienced Java system developers frequently exhort fellow developers not to change any interface once it's published. If you do change such an interface, then all users and all implementers of the interface have to update simultaneously. Bang. With Java as it stands, a better approach is to define a new interface with the desired changes and use dynamic typing to decide whether to use the old or new interface in any given circumstance. Alternatively, of course, an components-friendly programming language could directly support interface evolution directly in the language.

External validation

2011-02-25T12:46:00.000-08:00

Robin Hanson points to an article by Vladimir M about when you can trust the results of an academic field.

When looking for information about some area outside of one’s expertise, it is usually a good idea to first ask what academic scholarship has to say on the subject. In many areas, there is no need to look elsewhere for answers: respectable academic authors are the richest and most reliable source of information, and people claiming things completely outside the academic mainstream are almost certain to be crackpots.

Robin's angle is Bayesian. He argues that we should trust academics by default, because they are experts, but that we should adjust our level of belief if the field is ideologically driven:

However, let us accept for the sake of argument that all else equal in ideological fields intellectual progress is slower, and claims tend to be make with more overconfidence. What exactly would this imply for your beliefs about this area?

I have a rather different perspective, and several of the commenters seem to agree. I think of academia as a club of intellectuals, but not one that is always motivated by the search for objective truth. Many academics don't seem to be bothered with objective truth at all, but more are interested in being at the forefront of some movement. As one commenter points out, such academics are more like lawyers advocating a cause than they are experts seeking the truth.

A better way to find experts in a field is to look for external validation. Look for people and ideas that have stood some test that you don't have to be an expert to verify. You don't have to know much about artificial intelligence to know that IBM is good at it., because they've proven it with their Watson Jeopardy player.

Brad on Watson

2011-02-18T14:53:00.000-08:00

Brad's Ideas has a number of neat comments about the Watson Jeapordy match. One thing Brad mentions made me wonder about Jeopardy mechanics:

You can buzz in as soon as Trebek stops speaking. If you buzz early, you can’t buzz again for 0.2 seconds. Watson gets an electronic signal when it is time to buzz, and then physically presses the button. The humans get a light, but they don’t bother looking at it, they try timing when Trebek will finish. I think this is a serious advantage for Watson.

I agree that this is a big advantage to Watson. However, I don't understand why it works this way. The reason you can't buzz early is because it makes the game annoying to watch and unpleasant to participate in. Alex would constantly be interrupted as the contestants race to buzz in and cut him off.

However, making contestants hit the buzzer just when Alex finishes adds a substantial dexterity element to the game. Watson has an advantage in this dexterity game, but who cares? Everyone wants to know if Watson is smart, not if he can press a button with millisecond precision.

A better way to handle the buzzer, it seems to me, would be to let people buzz in early but not to count it until Alex finishes the question. At that point, if more than one person has buzzed in, the winner is selected randomly. Otherwise, it's a speed race, with no precision to the timing. This slight change in the algorithm should remove the precision timing from buzzing in and make it more of a race to figure out the answer the fastest.

Ken Jennings reflects on Watson

2011-02-18T07:00:00.000-08:00

Ken Jennings, arguably the all-time champion at Jeopardy, has a great article on Slate. He reflects on his and Brad Rutter's match with Watson.

I expected Watson's bag of cognitive tricks to be fairly shallow, but I felt an uneasy sense of familiarity as its programmers briefed us before the big match: The computer's techniques for unraveling Jeopardy! clues sounded just like mine. That machine zeroes in on key words in a clue, then combs its memory (in Watson's case, a 15-terabyte data bank of human knowledge) for clusters of associations with those words. It rigorously checks the top hits against all the contextual information it can muster: the category name; the kind of answer being sought; the time, place, and gender hinted at in the clue; and so on. And when it feels "sure" enough, it decides to buzz. This is all an instant, intuitive process for a human Jeopardy! player, but I felt convinced that under the hood my brain was doing more or less the same thing.

Computers 1, Humans 0

2011-02-16T08:21:00.000-08:00

One of the two Watson Jeopardy games has now been televised, and Watson won handily. Watson has $35,734, Rutter has $10,400, and Jennings has $4,800. Watson has more than twice the other two's scores combined. We'll find out tonight whether the computer can hold its lead.

It was an interesting match to watch. The audience was the most excited Jeopardy audience I've ever seen, and they were rooting for Watson. When he took a guess and got it right, there was a thunderclap of applause. When he had to make a wager, as with a daily double, they broke up laughing at Watson's odd-ball wagers such as $6,345.

The game was much closer than the score indicates. For many of the questions, all three contestants would know the answer, and it was a race to ring in the fastest. On many of them, if Watson had needed six seconds rather than five to figure out its answer, a human would have rung in first.

One thing I was surprised about was the Final Jeopardy question. The category was "U.S. cities", and I thought Watson would knock it out of the park. I thought it would bet high and answer it easily. The opposite was the case. The computer had no idea what the names of airports mean. Apparently, even with all the time contestants are given for Final Jeopardy, it couldn't connect the dots from "World War II" to "O'Hara" and "Midway". Yet, it still did okay in the end, because it only bet about $1000 on the question. Did it bet so low because of the category, or did the programmers have Watson be categorically cautious in Final Jeopardy?

I don't know, but one thing is clear. Humanity has met its trivia overlords, and they're made of silicon. This game show duel is just a spectacle, but take a moment to look what it means for the future. The way Watson is competing ultimately relies on a large, natural-language database. Unlike with Cyc or the Semantic Web, the computer doesn't need humans to explicitly re-encode information into a machine-friendly synthetic language. It is directly using the natural-language texts we wrote for communicating among ourselves.

The applications are far-reaching. At the simplest, Watson hints at greatly improved web searching, both when looking for pages and when looking for information. Other applications are in medicine. Imagine a Watson that had read a hospital's case files and a medical school's entire library, including the latest journal articles? No doctor can match that. For knowledge workers in any domain, imagine how much it would help to have a personal Watson that had read every email the person had ever sent or received? Natural-language processing has just passed a tipping point.

More about Watson is available on the Jeopardy web site.

Fight with fire and get burned

2011-02-15T16:05:00.000-08:00

I almost wrote earlier about Google's promotion of other Google sites like Maps as part of its search result, but I didn't. It seemed too silly. Now I read that the issue might be heating up after all. In a recent interview, Google spokespersons claim that there is strong activity in D.C. to turn the issue into a serious anti-trust case.

One of Google's defenses is that there's no such thing as a neutral web search algorithm:

Google has recently brought in executives to discuss how neutrality can’t be achieved in search because the company’s algorithm is based on subjective factors to ensure users get accurate results.

I completely agree. A neutral web search is bound to be a bad web search. A good web search is heavily biased toward what the user wants, and any search provider is going to have to use their judgment on what the user will want.

However, I also feel the same about network neutrality. The Internet is not a star topology, where we route packets into a central router and then it spits them back out to other people connected to it. It's a complex network that no one in the world has a full map of. The routing decisions at each node can be quite complex, and good routers are almost never going to treat all packets the same. A neutral router is a bad router.

Additionally, I always felt the same way about browser neutrality. The best operating system shells have thorough integration with a web browser instead of just forking off a web browser application. It makes for a better user interface, and software engineers seem to agree if you look at what they build rather than their opinion on this case. There have been a number of good OSes with built-in browsers, including two by Google: Android and ChromeOS. A browser-neutral OS is a bad OS.

I hope Google does not get stuck with search neutrality provisions. I must say, though, that they invited the wolf into the hen house.

Watson, the new Deep Blue

2011-02-14T06:16:00.000-08:00

IBM worked long to build a chess computer that can rival the world's best chess players. Now they have built a computer that does something harder: answer pointless trivia questions. Harder for a computer, anyway. Airing starts tonight, and I can't wait.

Part of the fun of it is that this is an application that still requires one of the biggest computers that anyone on the planet can build:

Well the body of Watson, which is not on camera, is like 10 huge refrigerators, in an air-conditioned room.... Watson has the power of a couple thousand laptops working together.

On the down side, it's not a particularly elegant machine:

Instead of just trying one approach, saying 'We're going to do it statistically' or 'We're going to teach the computer a million different rules about the world,' IBM just tried a very pragmatic approach, which said that if there's anything that works, we're going to include it in this. So they've got hundreds of different algorithms all trying a different approach to understanding the clue and trying to figure out the answer. And then it's up to the computer to look at thousands of different candidate answers and pick out the one that's most likely to be right.

POSIX for Java

2011-02-12T08:04:00.000-08:00

I've long felt that Java sorely lacks for not having a standard POSIX interface. Every significant platform that the full version of Java runs on has POSIX, so it's no loss in portability to outright support it. Yet, the lack of POSIX support can really hurt applications that want to do something like scripting. Developers on the ground are left using crummy hacked-together scripting languages just because they provide POSIXY things, most especially process control. Process control is key because once you have good process control, you can shell out for the rest.

I'm over three years late to notice it, but JRuby has an excellent solution to this problem:

So the idea behind JNA (jna.dev.java.net) is to use a foreign function interface library (libffi in this case) to wire up C libraries programmatically. This allows loading a library, inspecting its contents, and providing interfaces for those functions at runtime. They get bound to the appropriate places in the Java interface implementation, and JNA does some magic under the covers to handle converting types around. And so far, it appears to do an outstanding job.

With this code in JRuby, we now have fully complete chmod and chown functionality. Before, we had to either shell out for chmod or use Java 6 APIs that wouldn't allow setting group bits, and we always had to shell out for chown because there's no Java API for it. Now, both work *flawlessly*.

I wonder how this is working out in practice? I wonder if anyone's tried it for Scala? I wonder if Oracle will adopt it into the Java mainline?

Interestingly, Squeak went through a similar history with its own native method interface. The initial version marked native methods with an integer index, and that index was looked up in a table of function pointers inside the VM. The next iteration was like JNI, and because it named native methods with strings, you could link in new ones with shared libraries. After that came an iteration much like JNA, called FFI. Like JNA, Squeak's FFI lets you access existing library directly without needing to write any glue code beyond a specification of the type signature of what you're calling.

The main differences for the Squeak version of this history are (1) they did it years earlier (2003 versus 2007), and (2) the platform maintainers immediately adopted it as a core feature. It would be great if Java could adopt the same thing as a core feature. Is there even a JSR for it, though? My initial Google searches aren't turning anything up.

Accreditation in software engineering

2011-02-07T11:09:00.000-08:00

The Wall Street Journal has an article up on licensing. They make a claim that looks correct to me:

"Occupations prefer to be licensed because they can restrict competition and obtain higher wages," said Morris Kleiner, a labor professor at the University of Minnesota. "If you go to any statehouse, you'll see a line of occupations out the door wanting to be licensed."

The article covers a lot of the common issues, including mention of some of the more ridiculous license regimes such as for barbers and manicurists.

In software engineering, accreditation is much less prevalent than in other professions. The places I am aware of accreditation cropping up are for the more pigeon-hole parts of the craft, jobs where there's a well-defined set of tasks and a well-defined skill set for meeting those tasks. Examples are maintenance of Oracle databases or of Microsoft Exchange servers. Even in these cases, there is nothing illegal about performing the task without a license, and I'd hazard that more such systems are run without than with a formally certified technician.

The majority of software engineers I've encountered have no such license or certification at all. They are more jacks of all trades. They have all worked in some specialty or another at some point or another, but they've rarely completed an entire certification course. When hiring such an engineer, it's relatively complicated to evaluate them compared to licensed professions, but if you choose well, you typically get an enormously more productive worker than simply grabbing someone who has jumped through the right hoops.

All of this seems pretty good to me. Thus, unlike workers in most professions, I would argue against any formal licensing for software engineers. There are three big reasons:

The track record of attempts is not good. Some large-scale efforts, such as those with UML-based death by paperwork, have been real productivity sinks for anyone who tried them. Other large-scale efforts, such as extreme programming, are so loose and hazy they are more rules of thumb than anything that could be taught and tested in a certification program. The best I've seen have been local customs adopted by individual development groups, but I've even seen a lot of these work out pretty miserably in practice and be retracted after a year or two.
The profession is very young, and its practices are still being developed. For example, distributed version control has gone from theoretical to the norm in the last ten years. Garbage collection has gone from theoretical to the norm in the last thirty years. Even if we found some genius of software engineering who could describe today's best practices, it would quickly go out of date.
The nature of the profession is to innovate. Unlike with plumbing or with shaving whiskers, a large proportion of new software written is something that's never been done before. It's wrong to think of most software as building a cog to fit into a well-specified gear in a well-specified machine. It's better to think of it like a business plan or a social arrangement or a new kind of tool. What kind of accreditation would make sense for the creators of Google, Facebook, or the Phillips screwdriver?

Will Exim support its users or its philosophy?

2011-02-05T13:45:00.000-08:00

I wrote several years ago that I don't like when software lectures its users about how their suffering is going to help the greater good:

It is frustrating when programmers decide to lecture their users instead of supporting them. I just spent over an hour trying to get my mail to relay through EPFL's mail servers using the restrictive channels EPFL allows, only to find that Exim has its own restrictions. The two sets of restrictions are workable by themselves but do not have a solution together. The only way to make Exim and EPFL both happy is for them not to talk to each other. Bleh. I think I will stick with EPFL and replace Exim.

I still feel the same way. Both EPFL's admins and Exim's maintainers were unreasonably stubborn. Good software helps its users in their actual situations, not in some idealized alternate world. Good software works on crummy half-baked networks instead of needing everything around it to be in perfect condition.

Curiously, there's a chance now for Exim to change its mind and support SSMTP after all. Simon Arlott has written a drop-in patch that adds the support to Exim and linked it on my ancient feature request to Exim. Will Exim take the patch? The Exim of 2006 would have said no way. What will the Exim of 2010 say? Do they want users, or obscure philosophical purity?

DNS shutdowns are up and running

2011-02-04T15:31:00.000-08:00

Via Freedom to Tinker, I read:

ICE executed seizure warrants against the 10, ATDHE.NET, CHANNELSURFING.NET, HQ-STREAMS.COM, HQSTREAMS.NET, FIRSTROW.NET, ILEMI.COM, IILEMI.COM, IILEMII.COM, ROJADIRECTA.ORG and ROJADIRECTA.COM, by demanding that registries redirect nameserver requests for the domains to 74.81.170.110, where a colorful "This domain name has been seized by ICE" graphic is displayed.

As I've written earlier, this is a bad way for people to civilly coexist on the Internet. Let me count a few of the ways:

DNS is a crude weapon. Disabling a domain name is like disabling an entire postal zip code. The collateral damage can easily be larger than the intended damage.
This option isn't needed if you convict the defendant, because then you have legal rights against the defendant's business assets, anyway. It's only useful if you are preemptively shutting down a business that you haven't had time to bother taking to court.
There's no good legal theory where the U.S. government has authority over .com and .net addresses. If the U.S. has rights over .com and .net, why not Canada, or the state of Florida? Why not the Bahamas?
One of the sites, Rojadirecta, has already successfully defended itself in court. In Spain. The U.S. has successfully turned off their DNS record anyway.

It all comes across as rather thuggish. To briefly try and outline how we might approach these issues in a more principled and civil way, it might go like this:

Leave DNS and routing alone, much like we leave speech mostly free. This implies that law enforcement can't do much about people who are broadcasting copyrighted material from the North Pole, but realistically, they can't anyway. They can still convict the native citizens that download it.
If a wrong has happened, then try the person or organization that did the deed. Don't go after a DNS provider, an ISP, a router manufacturer, a software author, or any other intermediary who merely provided a general-purpose tool.

Tech Talk on Scala+GWT

2011-02-02T16:46:00.000-08:00

Grzegorz Kossakowski gave a tech talk on his Scala+GWT project that is now online.

Slides are available here.

The talk was around September, and there has been a lot of progress since then. For example, the system can now compile and run a much larger subset of Scala.

Does IPv6 have hope?

2011-02-02T07:51:00.000-08:00

That probably sounds like a strange question. 6 > 4, and IPv6 is simply the newer version of IPv4. Everyone will eventually be upgraded, right?

That's not really accurate. IPv6 is not backwards compatible with IPv4. Despite the name, it's really a different protocol. From a technical perspective, asking if we will all upgrade to IPv6 is similar to asking if we will all sidegrade to IPX. The only difference is in the branding. IPv6 sounds like an upgrade.

Dan Bernstein has a great article up on the technical issues with migrating to IPv6. In general, the plans that IPv6 advocates are discussing involve every node on the Internet upgrading to support IPv6 and IPv4 simultaneously, and then we can make a big switchover. At first blush, this sounds like a good plan. It worked for HTTP, and as Bernstein points out, it worked for MX records for SMTP servers. However, so far at least, IPv6 isn't designed to work that way.

The problem is that, unlike with these other examples, it's not a simple software upgrade to simultaneously support IPv6 and IPv4. Most distressingly, every node on the Internet needs to additionally have an IPv6 address. That alone is a fatal flaw. It's simply not going to happen. With the MX record transition, nodes without an MX record simply fell back on their A record, which they already had. With the HTTP transition, HTTP/1.1 was and remains an optional extension. Every node can always fall back to HTTP/1.0 or even HTTP/0.9. With IPv6, however, any node that doesn't have an IPv6 address simply doesn't get to play.

The same thing is happening with DNS. In addition to allocating all those IPv6 addresses, you need to add them to DNS. Until every DNS record is updated to have both IPv6 and IPv4 addresses in it, it's not possible to flip the switch.

As a separate issue, does anyone really care about the other features of IPv6 other than the extended address space? IPv6 comes with a host of features, and some of the more complicated and computationally expensive ones like IPsec are mandatory. These strike me as things that would better as optional extensions, and indeed, most of these features except the larger address space are already being explored as such.

Overall, the main thing that IPv6 brings us over IPv4 is the larger address space. Why not make that an optional extension, too? The IP packet format already allows for extensions. Routers trying to forward an extended-address packet could simply ping each other before doing it, and if the next router in the chain doesn't support them, bounce back a "host not reachable" packet. Lots of software would need updating, e.g. the socket APIs used on end point software would need to support optional, longer addresses. However, the changes would be much smaller than are required to support IPv6.

So if the best transition to big address spaces is to extend IPv4 rather than stage a simultaneous leap to IPv6, what is going to happen? One possibility is that such an IPv4++ will be designed, it will be rebranded as IPv6, and everyone will simply ignore the failed experiments with a more radically different IPv6. Another possibility is that such an IPv4++ will be rebranded as IPv7. This is all branding and politics, though I must say that the most honest thing would be to simply call it IPv4.

Another possibility is that everyone interested in big addresses will get suckered into the IPv6 quagmire, and it just won't happen. This isn't clearly a bad thing. The "small" address space of IPv4 is plenty large if we continue to have an Internet that is a patchwork of interconnected networks rather than a true globally controlled network. With the smaller address space, my coffee maker can still send a packet to your coffee maker, but from each coffee maker's perspective it will be sending packets out into the cloud. That seems healthy, to me. Perhaps you want to support virtual coffee makers, or to have transparent coffee maker failover. It's not really my business exactly how you route my packet in your network. Why would you want to export a node address to me that tries to pinpoint a specific machine?

A more exotic possibility is that some other network gains market share. Some network that offers real, pressing advantages, unlike IPv6. A packet-switching network protocol is like a social network or an instant messaging system. New networks take over old ones by initially offering something attractive enough that people will operate on both networks simultaneously. Once enough people are on the new network, they can start taking it for granted, and the old network can deflate in usage very rapidly. Really, though, what possible improvement would the packet switching layer have that would encourage that initial batch of people to use the new one in parallel to the old one? Clearly it's nothing in the laundry list of features in IPv6, because adoption has been really tepid. Further, all the really good network improvements have been possible to retrograde onto IPv4.

My best guess is that we continue on with IPv4 plus extensions. More tentatively, I would guess that we never get around to extending it for larger address spaces. If larger address spaces do become a pressing concern, however, I'd expect IPv4 to be extended rather than for the whole world to waste time on switching to completely new protocol. It's just good engineering.

That scary Internet

2011-01-31T11:29:00.000-08:00

National governments are coming to fear the Internet as a potentially disruptive mechanism for their publics. China and Australia have installed national firewalls to attempt to filter information crossing their borders to and from the greater Internet. Most recently, Egypt has recently shut down portions of its Internet infrastructure.

Many reports speak of the Egyptian shut down as a done deal. However, this is a misleading viewpoint. In point of fact, many Egyptians are still connected to the Internet through various means. The Internet is architected so that packets can take any route available from their source IP to their destination IP. As the old saying goes, "The Net interprets censorship as damage and routes around it". Like with so many other things, an official shut down just shuts down official business. Criminals don't care, nor do most of the general public.

Regarding the American kill switch, I must wonder how the discussion has gotten as far as it did given American politics. Aside from being technically hopeless, and for making times of peace more dangerous, it just doesn't seem American to let the president shut down a major category of speech. Has there ever been a U.S. president that tried to get a media kill switch, i.e. the ability to shut down every newspaper, pamphlet, printer, and copying machine at the press of a button?

Overall, I expect this gradual creeping oversight to know no bounds. The U.S. government is ham-handed, its members would universally prefer not to be discussed, and units such as the FCC are seeking a new reason to exist. Instead of gradually fighting each individual effort as they attempt to chip away at the open Internet, I would prefer a categorical principle that the U.S. government just does not have authority over the Internet. There's no reason they should, and they're not even competent.

Software patents help what, again?

2011-01-06T13:11:00.000-08:00

Via James Robertson, I read that Interval is suing about a dozen major software companies over patent infringement. I am having trouble finding an original link to the case information, but here's a link to one copy of Interval's opening volley.

Here's the IP Interval is suing over:

The ’507 patent describes an invention that enables a user to efficiently review a large body of information by categorizing and correlating segments of information within the body of information and generating displays of segments that are related to the primary information being viewed by the user.

From this alone, you might thing they have some advanced technique for categorizing and showing related information. No, they really are claiming that the whole idea of showing users a list of items related to the one they are looking at is an Interval invention. For example, here is their complaint about eBay:

Defendant eBay has infringed and continues to infringe one or more claims of the ’507 patent under 35 U.S.C. § 271. eBay operates the eBay.com and Half.com websites, which provide content such as product listings and advertisements to users. In order to help users find additional content that may be of interest, the software and hardware that operate these websites compare the available content items to determine whether they are related. When a user views a particular content item, the eBay.com and Half.com websites generate displays of related content items so as to inform the user that the related items may be of interest. For example, as demonstrated by Exhibit 8, when a user views a particular product listing on eBay.com, the eBay.com website displays both the selected product information (identified by the orange box) and links to other related products (identified by the green boxes). The hardware and software associated with the eBay websites identified above and any other eBay websites that perform this function infringe at least claims 20, 21, 22, 23, 24, 27, 28, 31, 34, 37, 63, 64, 65, 66, 67, 70, 71, 74, 77, and 80 of the ’507 patent under 35 U.S.C. § 271.

The theory behind patents is that, without patent protection, nobody would have invented the idea in question. By offering patent protection, companies will devote resources to research that they otherwise would not have. Can anyone seriously believe, however, that we would have more innovation if all of AOL, Apple, eBay, Facebook, Google, Netflix, Office Depot, OfficeMax, Staples, Yahoo, or YouTube had honored this patent and not shown similar items on their web sites? Does anyone believe that if Interval hadn't "invented" this idea, that nobody else would have?

An additional part of the rationale for patents is that the idea are difficult to develop, that they would only emerge if significant private resources were dedicated to its research. That, too, is hard to believe for this idea. How long did it take the guys at Interval to come up with this idea? Five minutes, maybe?

I have an idea how to stimulate the software industry. Stop issuing software patents.

References without page numbers

2011-01-03T11:45:00.000-08:00

James Robertson asks how we can reference a part of a book, if we read the book on a Kindle or other electronic medium:

...what does a page number even mean? It should be simple to graft the physical form page number into the metadata, but as we go forward, there may well be books for which no physical form exists. What then?

This isn't a new problem, but it's exacerbated by current norms of book publishing. Printed books often don't number their sub-entities at a finer grained level than chapters, so if you don't have the physical version in front of you, all you can cite is the chapter. Worse, if someone else has a physical version, and you're reading the electronic version, it's problematic if they give you a cite for a page number.

It's an old problem, though, and it has a lot of old solutions. It comes up any time the same text is printed multiple times with different page numbers. Two examples would be codes of law and the Christian Bible. If you want to cite a part of one of these, it's poor form to use a page number, because that page number is only valid for a specific printing. You instead make reference to the detailed numbers that have been applied to the sub-entities of the text.

Going forward, it would help if books started containing more fine-grained numberings as a matter of course. In theory we could instead use character count or word counts, but that has two problems. It is prone to differences in convention, e.g. how many characters is a paragraph indent, and how many words are in counter-revolutionary. Worse, it doesn't work well for people using the print version, who would need a specially printed version with the position counts on the bottom of each page or in the margins.

Bill Venners foresaw this problem for Programming in Scala, and he was careful to publish the ebook version such that it has the exact same page numbers as the printed book. This is possible because the ebook is a PDF file, and PDF files have the same pagination on every device. In addition to the consistent page numbering, the book includes fine-grained number of all the sections, figures, tables, and larger programming listings, so you can also cite things that way. In short, feel free to copiously cite parts of Programming in Scala. Don't worry about the ebook readers--they'll be able to look up your references just fine.

That's not how it works

2010-12-22T15:49:00.000-08:00

James Robertson shares this depressing quote from the FCC:

"A commercial arrangement between a broadband provider and a third party to directly or indirectly favor some traffic over other traffic in the connection to a subscriber of the broadband provider (i.e., 'pay for priority') would raise significant cause for concern," the Commission then elaborates. This is because "pay for priority would represent a significant departure from historical and current practice."

Follow the link for analysis.

Let me focus just on this part. The FCC, here, joins the ranks of those who think the Internet is a star topology. The apparent model is that there's an Internet, and then everyone plugs their computer into the Internet. When one user routes a packet to another user, it takes two hops: one to the center node, and one to the other user. Everything that happens within this mythical center node is abstracted away.

As an aside, the FCC also presents a view of the Internet where a handful of providers are sending broadcasts to the masses. Individuals don't contract for Internet services. They are "consumers", and they "subscribe" to the feeds. Leave that aside for now.

The Internet is not a star topology, but a general network. When you send a packet to someone else, it usually takes a dozen or two hops to get to them. How fast it gets to them depends enormously on the intermediate nodes that are taken along the way. I used to play around with traceroute and watch just what routes the packets take under various circumstances. I saw some particularly striking examples when I worked on a Department of Defense bulletin board and watched how packets route between a university network and a DoD machine. Let's just say the routes favored security over latency. They'd go a LONG way in order to go through carefully controlled choke points.

Because the Internet works this way, people who provide Internet services work hard to make sure their servers are well connected with respect to their users. For example, if you want to provide service to British folks, then you really want to get a server up on the island. It wasn't so long ago that all major ftp sites had clones in the UK. Sending data across the English Channel, much less the Atlantic Ocean, was just horrendously slow. When you install an extra server in the UK, you must pay for it.

Relocating a server is just one option. It's also possible to lease network connections between where your server is and where you want the IP traffic to route to. When you do that, you will have to pay whomever you are leasing the bandwidth from.

In short, if you want better connectivity, you have to pay for it. The more you pay, the better the connectivity you get. What the FCC calls a disturbing development is a hair split away from how things already work. They seem to be riding on the notion of whether you pay a broadband provider or some other entity. I fail to see what a big difference it makes.

Let's try a few thought experiments and compare them to the star-topology model. Suppose Netflix pays Comcast to let them install some servers in the same building as a major Comcast hub. Is anything wrong with that? I don't see why. They'll get better bandwidth, but they're paying for all the expenses. Similarly, suppose Netflix, on their own dime, installs new network fiber from their data center to a major Comcast hub. Is there anything wrong with that? Again, I don't see it. After Netflix lays that network, would there be anything wrong with Comcast plugging into it and routing traffic to and from it? Again, I can't see how it would help users for them to decline.

Where the FCC seems to draw the line is when you go past barter and use more fungible resources. What if, instead of Netflix installing new network fiber itself, it pays Comcast to do it. And what if, instead of Comcast laying new fiber for each customer, they split the cost over different customers, giving more access to those who pay more. From the FCC's view, this goes from totally normal to something they've never seen in the past. From my view, this is how things work already. You pay more to get more bandwidth.

I wish the FCC would just abandon trying to regulate Internet service. I want a neutral network, but I don't see how the FCC is going to anything but hurt. I want the Internet we have, not something like broadcast TV, cable, wired telephony, or cellular telephony. I don't think it is a coincidence that the Internet is both less regulated and far more neutral than these other networks.

Every paper and book on our laptops?

2010-12-17T14:52:00.000-08:00

Dick Lipton speculates on that question:

Today there are applications like Citeseer that contain about one million papers. The total storage for this is beyond the ability of most of us to store on our laptops. But this should change in the near future. The issue is that the number of papers will continue to grow, but will unlikely grow as fast as memory increases. If this is the case then an implication is that in the future we could have all the technical papers from an area on our own devices. Just as realtime spelling is useful, realtime access to technical papers seems to be a potentially exciting development.[...]
Right now there are too many books, even restricted to a subfield like mathematics, to have all of them stored on a single cheap device. But this large—huge—amount of memory could easily become a small one in the future.

I agree for Citeseer, and I agree for the local library. Very soon, if not already, we will have laptops that can hold the entirety of Citeseer and the entirety of the local library's collection of books. I was impressed when I looked at the file sizes for Project Gutenberg. Shakesperean plays take a few tens of kilobytes, and the largest archive they supply is a dual-sided DVD with over 29,000 books. I still remember the shock when I looked at a directory listing on their web site and the file sizes looked so small I thought the software must be broken.

As an aside, I wish I could say that the Association for Computing Machinery thought this way. Their current thinking that they'll have an online digital library that they take a toll on. If they really wanted to help science, they'd mail you a pre-indexed thumb drive you can load into your laptop and have all papers up until that date. I would bet that someone in physics works this out long before the ACM does. Who knows, though.

All this said, papers and books are backward looking. Nowadays, papers and books are developed as electronic content and then, only at delivery time, printed onto paper. An increasing amount of interesting material is simply never printed at all. Want a copy of the Scala Language Specification? It's essentially a book, but you won't find it at the local library. Over time, printed word is becoming a niche application. You only need it for reading something in depth, or if you want to physically hand it to someone. For the former, print on demand works more and more frequently, and for the latter, the number of times it happens is decreasing. As well, electronic ink just keeps getting better.

From the perspective of interesting words, as opposed to printed papers and books, it will take longer before personal computers can hold all the, ahem, material that is out there. It includes not just papers and books written by mathematicians, but also forum messages, blog posts, and even Facebook and Twitter messages written by all manner of people. Perhaps even then we are already at the point where our machines have enough storage, but it's certainly a lot more data than just for Citeseer and the library.

Of course, most people are only interested in a tiny fraction of all that information. Perhaps Dick Lipton really only cares about math papers from famous mathematicians. If the precise data interesting to someone can be identified, then the storage requirements for keeping a personal copy are much more reasonable, and in fact we probably are already there. However, identifying that subset of the data is, in general, entirely non-trivial.

Checked in debugging and profiling?

2010-12-15T08:30:00.000-08:00

Engineers of all walks insert extra debugging probes into what they're building. The exterior surface of the artifact is often silent about what goes inside, so the extra probes give engineers important extra information. They can use that information to more quickly test theories about what the artifact is doing. They use these tests to improve performance, debug faulty behavior, or to gain extra assurance that the artifact is behaving correctly.

Software engineering is both the same and different in this regard. Software certainly benefits from extra internal probes, and for all of the standard reasons. A common way to insert such probes is to insert debug or trace messages that get logged to a file. If the messages have a timestamp on them, then they help in profiling for performance. For fine-grained profiling, log messages can be so slow as to affect the timing. In such a case, the timing data might be gathered internally using cheap arithmetic operations, and then summary information emitted at the end. This is all the same, I would imagine, in most any form of engineering.

What's different with software is that it's soft. Software can be changed very easily, and then changed back again. If you're building something physical, then you can change the spec very easily, but building a new physical device to play with involves a non-trivial construction step. With software, the spec is the artifact. Change the spec and you've changed the artifact.

As such, a large number of debugging and profiling probes are not worth checking into version control and saving. Several times now I've watched a software engineer work on a performance problem, develop profiling probes as they do so, and then check in those probes when they are finished. The odd thing I've noticed, however, is that usually that same programmer started by disabling or deleting the stuff checked in by the previous programmer. Why is that? Why keep checking in code that the next guy usually deletes anyway?

This question quantifies over software projects, so it's rather hard to come up with a robust reason why it happens. Let me hazard two possible explanations.

One explanation is that it's simply very easy to develop new probes that do exactly what is desired. When the next engineer considers their small build-or-buy decision--build new probes, or buy the old ones--the expense of rebuilding is so small that the buy option is not very tempting.

The other explanation is that it's a problem of premature generalization. If you build a profiling system based on the one profiling problem you are facing right now, you are unlikely to support the next profiling problem that comes up. This is only a partial explanation, though. I see new profiling systems built all the time when the old one could have been made to work. Usually it's just easier to build a new one.

Whatever the reason, I am currently not a fan of checking in lots of debugging and profiling statements into version control. Keep the checked-in code lean and direct. Add extra probes when you need them, but take them back out before you commit. Instead of committing the probes to the code base, try to get your technique into your group's knowledge base. Write it up in English and then post it to a wiki or a forum. If you are fortunate enough to have Wave server, post it there.

Typing arithmetic in Datalog

2010-12-14T09:20:00.000-08:00

Unlike in imperative languages, arithmetic in Datalog can execute indifferent orders. If you write a formula z=x+y in animperative language, then the meaning is that you compute x, youcompute y, and then you add them together to produce z. If you want tounderstand the typing of such an expression, you first find the typesof x and y, and then look at the numeric conversion rules to see whatthe type of z must be. If x is a 32-bit integer and y is a 64-bitfloating-point number, then z will be a 64-bit floating-point number.

In Datalog, there are additional options for using the sameformula. Oneoption is to do as in an imperative language, compute x and y, andthen use the arithmetic formula to compute z. However, you could justas well compute x and z and then subtract to find y. In total thereare four different ways to use the formula: you could use it tocompute x, y, or z, or if all three are already computed, you couldadd them up and verify that they are in a proper relation with eachother. How can we reason about the typing implications aboutan arithmetic formula matching?

Call such a constraint an arithmetic type constraint. Such aconstraint must treat x, y, and z symmetrically, so think of them asbeing in a set. That is, an arithmetic type constraint is defined by a setof variables. If the variables are x, y, and z, then the arithmeticconstraint for them could be written arith({x,y,z}).

It appears to work well to treat an arithmetic constraint asequivalent to the following set of individual constraints:

 
  // constraints for arith({x,y,z}) are:
  x <= lub(y, z)
  y <= lub(x, z)
  z <= lub(x, y)

In these constraints, "<=" means subtype-of, and"lub" means least upper bound. The lub of twotypes is the smallest type that is a supertype of both of them.For numeric types, humor me and think of subtyping as includingvalid numeric upcasts, so int32 is a subtype of float64.This post is already too long to get into subtypingversus numeric conversion.

Try these equations on a few examples, and it appears to workwell. For example, if x and y are already known to be int32, thenthese constraints imply that z is no larger than lub(int32,int32),which is just int32. As another example, if x is an int32 but y and zare completely unknown, then these constraints give no new bound toanything. As a final example, if all three variables already have aknown type, but one of them is a larger type than the other two, thenthe third one can be shrunk to the lub of the other two.

In general, these constraints will only allow the types of threevariables to be in one of the following four combinations:

All three types are completely unknown.
One type is known but the other two are unknown.
All three types are the same.
Two of the types are the same, and the third type is a subtype of the other two.

The first two cases will eventually lead to a compile-timeerror, because the programmer has introduced variables butnot provided a way to reliably bind those variables to values.The third option is a normal, happy case, where there are nonumeric conversions being applied. The fourth optionis most interesting, in my view, because there is an operationbetween two types and the result is the lub of those two types.Notably absent from the list is any combination where all three typesare different.

As one final wrinkle, it's arguably more programmer friendly to alwaysperform arithmetic on at least 32-bit if not 64-bit values. Otherwise,when a programmer writes 127+1, they might get 8-bit arithmetic andthus an overflow. To make arithmetic work that way, it's possible toadd a minimum type to an arithmetic constraint. For example,arith({x,y,z},int64) would be an arithmetic constraintover x, y, and z, and a minimum result type of 64-bit integers. Thiswould be equivalent to the following combination of constraints:

  
  // constraints for arith({x,y,z}, int64) are:
  x <= lub(y, z, int64)
  y <= lub(x, z, int64)
  z <= lub(x, y, int64)

Published literature as fencing?

2010-12-09T07:31:00.000-08:00

"Any discourse will have to be peer-reviewed in the same manner as our paper was, and go through a vetting process so that all discussion is properly moderated," wrote Felisa Wolfe-Simon of the NASA Astrobiology Institute. "The items you are presenting do not represent the proper way to engage in a scientific discourse and we will not respond in this manner."

Felisa Wolfe-Simon is responding here to attacks on a paper she recently published. This is a widely held view, that science takes place on some higher plane of discourse. In this view, ordinary speech is not enough to move the discussion forward. You must go through the publication process just in order to state your counter-argument. Science then progresses by an exchange of one high-minded paper after another.

Hogwash. This romantic picture has no relation to science in the fields I am familiar with.

A killer mismatch between this picture and reality is that counter-arguments are not publishable. If someone publishes the results of a horribly botched experiment, it would serve science to dissect that experiment and show the problem. However, there aren't any peer-reviewed journals to publish it in. If you take the quoted stance seriously, then you must believe it's not proper to criticize published research at all.

A second mismatch is that, in the fields I am familiar with, nobody in the field learns a major new result through the publication process. When someone has a new idea, they talk to their colleagues about it. They speak at seminars and workshops. They write messages to mailing lists about it. They recruit students to work on it, and students post all over the place. Everyone knows what everyone is working on and the way they are doing it. Everyone knows the new ideas long before they have any evidence for them, and they learn about the new pieces of evidence pretty quickly as well.

Researchers debate all right, but not via publication. They email lists. They write each other. They give public speeches attacking each other's ideas. Others in the field do all of the same, and they are often more convincing due to being less invested in the conclusions.

In short, declining to participate in discussions outside the publication process is often presented as some sort of high ground. This is a backwards and dangerous notion. It means that you are not defending your ideas in the forums that convince the experts.

Floating-point computation: if you don't care what you compute

2010-11-24T09:39:00.000-08:00

There's an old saw among programmers that "I can make this program run arbitrarily fast, so long as you don't care what it produces". When you put it like that, it's obviously a bad idea: you always care about the output, even for a random number generator. In practice, this question comes up all the time, just not stated as starkly. Nowhere is this situation more common than with floating-point computations.

William Kahan has written a windy tour of error accumulation for floating-point and posted it online. The content is much like a blog, but he's publishing it as an ever-growing PDF file. Here are a few of the several interesting take-aways:

There's no "mindless" way to remove floating point error from your program. It takes some work.
Using high-precision floating-point is remarkably effective in practice. Take whatever size floating-point number you think you need, double the number of bits, and then compute over those.
Running your program in different rounding modes is remarkably effective at detecting whether your program is unstable. If rounding at the 53rd bit of precision makes any difference at all in your program's output, then your implementation is so unstable that you are probably generating bad results.

Thinking on these problems, I have a new-found love of interval arithmetic. As Kahan discusses in detail, interval arithmetic gives you a proven bound on how large your error can be. As he also discusses, though, if you mindlessly implement a mathematical formula exactly the way it is written, your intervals tend to be outrageously large. It is common, for example, for the proven error bars to double after every computation.

My question is why mainstream languages don't support interval arithmetic? If they did, then programmers could include asserts in their code about the size of the error bars at each step of a computation. Initially, these assertions would all fail, due to the intervals being way too large. However, with some cleverness and patience, programmers could get the intervals much smaller. Over time, programmers would build up a toolbox of techniques that apply in most situations. It would fit right in with how software engineering is performed nowadays.

Programming this way sounds like it would take longer to implement numerics than what I am used to. What's the alternative though? Graphics programs aside, don't we want to implement correct output, not just output that looks good? Imagine if a tech-savvy client asked how accurate our program's output was? We'd have to say, "I don't really know".

Can the FCC touch cable?

2010-11-19T08:03:00.000-08:00

Brian Stelter says no:

There is little the Federal Communications Commission can say about Fox News or MSNBC since the channels are on cable, not delivered over the broadcast airwaves.

True, but don't rest too easy. The FCC has whatever authority that U.S. Congress gives it. It's been lobbying for explicit authority over cable and the Internet, and they'll get it if the public wants them to have it.

We have a chance to leave behind the bad old days where U.S. citizens are "protected" from seeing anything that D.C. folks would consider objectionable. Getting there requires that the FCC not regulate the new networks, and they really want to.

Mac computers for programmers?

2010-11-16T09:25:00.000-08:00

I temporarily switched to an Apple Mac laptop, but after about two years I switched back to Linux. Here's why.

My original reasoning was that Macs support all the Unix goodness I value for programming, and furthermore they have better shell features such as network configuration and file managers. True, they have a higher price, and they are closed source, but it's worth spending money on good tools, and I don't plan to hack the kernel or the graphics engine, right? After a long sequence of individual observations, I came to realize this summation is not very accurate.

Software support. The software support can be summed up as: everything I need is available on Macs, none of it works better, some of it works worse, and a lot of it needs to be installed manually. In detail:

The X server is crashy. I lost a lot of time trying to make X apps work decently, but they just don't.
Eclipse works identically to Linux.
Java works identically, though for the longest time they were stuck at version 1.5 when the rest of the world was using 1.6.
There's no Debian or Ubuntu, but there is Fink. Fink has several essential packages, most importantly Latex. However, it's an order of magnitude smaller than the Linux distributions it mimicks. I like software distributions. They provide a great way for software developers to help each other. With Apple, you get what Apple gives you and the third-party market is much skimpier.
Gnu Emacs works fine. I experimented with Aquamacs for a long time, to try and do better than on Linux, but I found it had a lot of quirky problems.
Scripts work just like in Linux.
Scala and Scheme Shell work fine.
I tried the built-in calender, email, and contacts support. Ultimately I switched to Google equivalents, however, which are much better.
The built-in word processor and spreadsheet are just OpenOffice, the same as on Linux.

Operating system shell. Apple is famed as building great user interfaces. I'm coming to ask why that is, though. Sometimes they make something easy, and sometimes they make it impossible and then try to pretend like you'd never want to do it. It's as if they optimized for demos and didn't do any user studies. Over time, I found myselef replacing one chunk of the shell after another. Specifically:

Display management I will concede: it works great on a Mac. If I unplug an external monitor in a Mac, the display mode readjusts to display just on the built-in monitor. If I unplug an external monitor on Linux, it stays in that state, and it can be really difficult to get the display fixed back up.
Suspending to disk and to ram is about the same on both. I've had times where my Mac wouldn't resume, and I've had times when resuming a suspend-to-ram took longer than fully booting a Linux machine from scratch.
VPN software works better on Linux, in my experience. The Internet was developed on ancestors of Linux, so it has good networking in its genes.
The file manager on Linux is superior. I pulled my hair out trying to find a way to manipulate archive files (tar, zip, jar) with the Mac finder. There's nothing built in for it on a Mac, and I tried 2-3 extensions but none of them worked well. They act like archive files don't exist.
The default terminal program on a Mac is terrible. There's a decent replacement named iTerm, and iTerm is about par with gnome-terminal.
The window manager doesn't do multiple desktops. I hear there are extensions for that, but I never braved trying one.
The window manager shifts focus at the granularity of an application, and it has a notion of "application" that is terrible for programmers. If you click on any terminal window, they all come forward. If you click on any browser window, they all come forward. Likewise for hiding: you hide one terminal, they all go away. In general, the window manager is optimized for the way a graphics designer or an audio engineer works: 3-4 apps at a time at the most. When I program, I have 3-4 browser windows and 3-4 terminal windows, each with their own tabs internally.
The app launcher bar is okay, but I prefer how the Gnome launcher has a row of mini-icons plus a nice hierarchical menu of the whole system's software. I have tons of software installed, so a row of gigantic icons doesn't work.
Selecting wifi networks works well, but then it also does on Linux nowadays.
Network sharing is better on Macs. I use network sharing on a laptop maybe once a year, but when I do, it's easier on a Mac. On Linux, I have to install some extra software, pray my wifi driver has AP Mode, and read some docs on how to configure it all.

I would sum up the system software as sometimes much better and often much worse. Several aspects that work great out of the box on Linux, I have to install upgrades on a Mac to match it.

When I add up all the above individual things, I notice that there is hardly anything I particularly like about Macs, and there is quite a lot where I have to replace things to get it up to par. The applications I use aren't any better, and are sometimes worse. Surprisingly, the system software isn't particularly good, either. I vastly prefer Ubuntu to Fink -- it's just a larger, richer community. Also, while I don't hack the kernal or graphics software myself, it is nice to be able to apply patches that third-party people have written.

Macs are good computers for programmers, to be sure, but I'd still give Linux the edge.

Two good reads on digital copyright

2010-11-11T12:46:00.000-08:00

David Friedman raises an excellent thought experiment: what if the web had come first, rather than printed documents?

If the web had come first, issues of copyright and credit would have applied only to the rare case where someone chose to copy instead to link. Indeed, the relevant laws and norms might never have developed, since the very fact that what you were reading was a quote rather than a link, written by the quoter rather than the quotee, would be sufficient reason not to trust it.

I agree. The model we have is at odds with what makes sense on the Internet, and the Internet is already a much more important vehicle of communication than any print media. We should adjust our law to make sense for the Internet and let print gracefully decline as the preeminent way to share content.

Friedman's post is apropos for my own blog surfing, because I just now read Lawrence Lessig's For the Love of Culture that he posted back in January. It's a rich subject, so let me give two punchlines. Here's one:

Before we continue any further down this culturally asphyxiating road, can we think about it a little more? Before we release a gaggle of lawyers to police every quotation appearing in any book, can we stop for a moment to consider whether this way of organizing access to culture makes sense? Does this complexity get us something we would not get under the older system? Does this innovation in obsessive control produce any new understanding? Is it really progress?

Whether he is overstating things depends on your point of view. If you are Google, then all current law is just a hand shake with the president away from being changed to something else. It took Google to pull off Google Print. Larry and Sergei couldn't have done it alone when they were students, because it violated a thick cobweb of law, regulation, and copyright agreements. It's a disturbing state. Google Print involves an incomprehensible mess of legal agreements, but worse, the next hundred bright ideas about content sharing just aren't going to get off the ground.

How to arrange things differently is a big topic. Lessig has an important starting point in this comment:

We are about to change that past, radically. And the premise for that change is an accidental feature of the architecture of copyright law: that it regulates copies.

Focusing on copies is awkward when, on a computer, copies are ubiquitous. Computationally, copies are actually cheaper than actually displaying the content.

There are a lot of alternate approaches we could use than controlling the right to copy. As two examples, charging for performances and charging for access to a large archive are both possibilities. The first step, though, is to recognize that we have a problem.

Funmath notation for "calculating" on paper

2010-11-11T07:54:00.000-08:00

I was recently pointed to the Funmath project. Funmath is a mathematical notation that is meant to make manipulation on paper be fast and reliable. It is headed by Raymond Boute.

I don't understand the notation well enough to say how well it works, but I most certainly appreciate the goal. If you learn the notation and rules of algebraic and calculus notation, you can fearlessly race through rewrites as fast as you can move your pencil. The notation means exactly what it looks like, and the rewrites can be done through simple mental pattern matching. To contrast, all manner of other parts of math notation don't work so well. If a formula involves existential or universal quantifiers, set comprehensions, summations, lists, or even functions, then there is a lot of "it means what I mean" in the notation people use. Each step of a derivation has to be very carefully considered, because you can't just pattern match. You have to do a deep parse and figure out exactly which of the possible options each bit of notation really means.

Boute has an interesting historical explanation of this difference. Algebraic notation developed before the dawn of computers, so people computed on paper all the time. As a result, the notation evolved to support paper computation. Logical notation, on the other hand, hasn't been as pressing for computation on paper. Interest has risen in the last few decades, but almost everyone involved is entering their formulas directly into computers. There was never a period of time when logical notation was more heavily used on paper than on computers, so a step was skipped.

In attempting to fill in that gap, Boute has applied design rules that are familiar in programming language design. Particularly interesting to me is that he handles all variable-binding forms by using a single notation for function literals. This is exactly like the function literals that get bandied about in programming-language design circles. In math notation, as in programming languages, having a lightweight syntax for function literals means you can cut out a lot of syntactic forms. In Funmath, summation and quantifiers don't get special syntax. They are library functions that take other functions as arguments. Summation takes a function and maps it to the sum of its range. Quantifiers take a function and map it to a truth value.

If Funmath is as advertised, then it is as much a step up for logic notation as Arabic numerals were over Roman. I wonder if anyone outside the core research group has given it a try?

Type checkers aren't just error detectors

2010-11-11T07:26:00.000-08:00

Type checking is frequently put forward as a way to find errors that otherwise would have slipped through testing. I've never found this a very compelling argument, though. Before software is released, or even a patch committed to the shared repository, the developers go through various kinds of effort to convince themselves that the latest changes to the software behave correctly. There are a myriad of ways to do that, ranging across code inspection, testing, and formal methods, but whatever ways are chosen, the software doesn't move forward until it's been verified. At that point, not that many type errors can realistically remain.

There are larger advantages to having a type checker. Let me describe three.

Data Modelling. A lot of what programmers do is develop a model of the data their programs work on. All modelling approaches I know, bar none,involve using types. For example, ORM, UML, XML DTDs, Protobuf schemas,and SQL schemas all use types prominently. If you have types in the programminglanguage, then the program itself can embed parts of the data model explicitly.

A Second Perspective. In all software groups I have been a part of,most of the software written gets far less code review than would bebeneficial. Software gets much better just by having people scan theireyes across it and think about it, but practicing engineers dread spendingthe time to do it. A type checker forces programmers to understand theircode two ways: the logical behavior, and the type signatures. By doing so,they force programmers to do a little bit more code review.

Adding rigidity. Typed languages have a higher percentageof sensible programs in them. Just like it's easier to dial a TV than a radio, it's easierto code in a typed language. You can turn a TV dial to just any old location;you have to choose among a small, discrete number of settings.When writing new program code, you can write a rough sketchand then use the type checker to guide you on the details. Forrefactoring, you can make an inital change and let the IDE guide youto the other ones. It's much faster than if you have to run the testsuite more often or have to filter through raw text searches.

Which city will first have auto autos?

2010-11-03T19:24:00.001-07:00

Automatic automobiles, that is. Robin Hanson asks:

So a huge upcoming policy question is: when will what big cities manage to coordinate to change road law to achieve these huge auto-auto economic gains? Thirty years from now we may look back and lament that big city politics was so broken that no big cities could manage it. Or perhaps history will celebrate how the first big city to do it dramatically increased its importance on the world scene.

A good question. The commenters point to Brad Templeton's site, where he has done a lot of work to analyze just that question.

I'll ask a milder question than Robin. Where's the first city where we can even drive [sic] one of these cars at all? Ted Turner, are you reading? Wouldn't you like to ride around Atlanta in an auto auto?

Copyright law versus audio archives

2010-11-03T19:12:00.000-07:00

The U.S. Library of Congress writes:

"Were copyright law followed to the letter, little audio preservation would be undertaken. Were the law strictly enforced, it would brand virtually all audio preservation as illegal," the study concludes, "Copyright laws related to preservation are neither strictly followed nor strictly enforced. Consequently, some audio preservation is conducted."

More at OS News, which has a link to the 181-page study by the Library of Congress.

Hat Tip to James Robertson.

I'd be a lot more comfortable if the U.S. Congress simply passed reasonable legislation to begin with. I don't hold out hope for it. What does give me hope, however, is that cheap technology indirectly allows all sorts of common-sense copying activity to become de facto allowed.

Whatever paper fantasies Congress puts out, they aren't really going to lock up everyone who makes a mix tape or sets up a home media server. Historically, the tape recorder, the photocopier, and the VCR did wonders for fair use. Going forward, DRM-free Linux and Android computers can work similar magic for digital content.

Learning can be measured

2010-10-30T09:56:00.000-07:00

I've served as a teacher in a number of roles. I've taught math in a private high school, and I've taught undergraduate and graduate computer science. I also tutored constantly throughout all of my own schooling. Based on this experience, I'd like to emphasize one stance in the discussions that are going around about education reform this (and every) election season.

Learning can be measured.

Teachers know how to test their students to see whether they're learning what is intended. When I taught trigonometry and linear algebra, it really wasn't that hard to figure out which students were able to do it and which weren't. I gave them sample problems, gave them an hour, and then look at how they did on it. This gave tremendous insight into what the capabilities of the people in the class were. Any teacher who can't do this is basically failing at their job. It's just part of what teachers do.

Standardized tests are also pretty good. Granted, they have their problems. The questions leave little room for the grader to use judgment, and the graders don't have any extra information about the students than what is on the test. However, standardized tests also have benefits. The questions are much better devised and worded. They probe the student's skills in more ways, and so that answers to the questions more clearly indicate how the student is doing. The test makers have a larger view of their field than any individual teacher, so they avoid the temptation to grind an ax about some particular sub-sub-sub-topic. Additionally, the same lack of judgment that the graders have means that the grades are more objective. It is a more subtle story than I should get into in this post, but suffice to say that an apple a day for your teacher really does make a difference. Standardized tests can pierce through the reputation bubbles within a school and see how each student is really performing.

As it works out in practice, I have to say that standardized tests are quite good at measuring knowledge level, possibly even better than the home-grown tests. Most of my experience with standardized tests is at the high school level, but in that experience they're pretty good. I and my fellow students got exactly the grades that would be expected based on what we knew: we did well on standardized tests in our best areas, and we did badly in areas we didn't know so well. Further, from the talking I've done with more experienced high school teachers, they believe the tests, too. They can, more often than not, guess the exact grade on a scale of 1-5 that any student will get on an AP exam.

In short, measuring learning isn't too hard if you are willing to use standardized tests. Look at how the students do at the beginning and end of the year, and you'll know how well the teacher taught them.

I believe most teachers would agree with all of the above, but they say the opposite when it comes to measuring teachers themselves. I suppose no one likes oversight.

Scientific medicine

2010-10-29T06:49:00.000-07:00

Thorfinn of Gene Expression has a great post up on the difficulty of generating knowledge, even in a relatively hard science like medicine:

Doctors believe in breaking fevers, though there is no evidence that helps. Flu shots also don’t seem to work. I’ve also mentioned how uclers came to be declared a disease due to “stress”, when in fact they were clearly due to bacterial infection. Meanwhile, several large-scale tests of medicine use — from the RAND insurance study, or the 2003 Medicare Drug expansion — find minimal evidence that more medicine leads to better health.
[...]
I think our body of medical knowledge does illustrate how hard it can be to generate reliable knowledge, even in cases when we can easily run numerous experiments on a randomized basis.

Softer sciences have an envy of the hard sciences. Their researchers envy how reliable the experimental results are in a physics or chemistry experiment. In the hard sciences, it's possible to do controlled experiments where all of the relevant variables are controlled. Further, the models are simple enough that there aren't a host of alternative models that can explain any experiment. For example, if your theory is that the acceleration due to gravity is the same for all masses of objects, and your experiment is consistent with that theory, it's hard to come up with any simpler theory that would explain the same thing. "It doesn't matter" is already as simple as it gets.

I spent a lot of time with the Learning Sciences group at Georgia Tech. While they put an admirably high effort into careful experimental validation of their tools, methods, and theories, they were quite frank that the experimental data were hard to draw inferences from. They could describe a situation, but they couldn't reliably tell you the why of a situation.

The problem is that even with randomized trials, there are so many variables that it's hard to draw any strong conclusions. There is always a plausible explanation based on one of the uncontrolled variables. For learning sciences, a particularly troublesome variable is the presence of an education researcher in the process. Students seem to always do better when there's an experimenter present. Take away the experimenter, and the whole social dynamic changes, and that has a bigger effect than the particular tool. Seymour Papert's Mindstorms is a notorious example. Papert paints a beautiful picture of students learning deep things in his Logo-based classrooms, a picture that has inspired large numbers of educators. I highly recommend it to any would-be teacher. However, nobody can replicate exactly what he describes. It seems you need Papert, not just his tools, and Papert is darned hard to emulate.

All too often we focus on a small effect that is dwarfed by the other variables. The teacher, the software engineer, and the musician are more important than the tools. In how many other areas of knowledge have we fallen into this trap? We ask a question that seems obviously the one to ask--Logo, or Basic? Emacs, or vi? Yet, that question is framed so badly that we are doomed to failure no matter how good are experiments are. We end up comparing clarinets to marimbas, and from that starting point we'll never understand harmony and rhythm.

Against an Internet Blacklist

2010-10-28T17:42:00.000-07:00

There is a bill in the U.S. Senate to set up a blacklist for American citizens:

The main mechanism of the bill is to interfere with the Internet's domain name system (DNS), which translates names like "www.eff.org" or "www.nytimes.com" into the IP addresses that computers use to communicate. The bill creates a blacklist of censored domains; the Attorney General can ask a court to place any website on the blacklist if infringement is "central" to the purpose of the site.

To draw an analogy, this is like ordering someone's phone line to be disconnected based on a simple court order. It's not a good plan even if it were limited to sites that were clearly infringing copyright. Shouldn't the site owner get a day in court before their access is cut off?

Needless to say, I don't think we should have a DNS blacklist in America. We shouldn't adopt totalitarian information control just to prop up the current crop of companies that are in industry. Indeed, why should we work so hard to prop up yesterday's business models, anyway? We may as well try to bring back the horse and buggy.

Visa restrictions strike again

2010-10-23T10:28:00.000-07:00

The band Incognito is not visiting Atlanta this year:

We did all I could to make this happen, but my band and I were not given the deposits that were agreed and after much toing a froing severe delays to our arrangements and our visa applications has made our deadlines impossible.

American visa requirements are holding hostage all sorts of beneficial social activity. It stops economic, intellectual, and in this case cultural improvement.

Fay and I had a wonderful time hearing Incognito play in Switzerland. They are an extraordinarily international band, having members from several different continents. Maybe they'll have better luck next year getting past the American border control.

The simple way to use CUPS from Windows

2010-10-05T18:34:00.000-07:00

In the hopes of steering someone else away from a tar pit, don't bother messing around with Samba if all you want to do is print over the network to a Linux box. Just do two simple things:

Set the printer up using CUPS, the standard print software for Linux.
In the Windows "Add Printer" dialog, click the option that allows a URL, and paste in the URL to your printer. It will be like: http://<computer-ip>:631/printers/<cups-printer-name> . When it asks for a printer maker, specify "Generic" "MS Publisher Imagesetter".

Gah! I lost over an hour fooling around with Samba docs, because I hadn't realized Windows supports CUPS directly.

Hat tip to the BSDpants blog. They write:

So, I know!, Windows means samba and there's a port named "cups-samba". This must be just what I'm looking for. ... Well, it was kind of what I was looking for. But, it was too much trying to do things the Windows way. A little painful. What I discovered in digging around was that I didn't need cups-samba or even samba. CUPS by default leaves a port open for printing and you can use IPP to print directly to a CUPS printer via the network, even from Windows, and using generic, Windows Postscript printer drivers already on your Windows machine (probably).

I never understood why Windows network printing was any more complicated than this. Just have a standard protocol, and then any client can speak to it. All you should have to do on the client is paste in a URL.

Even now, I note that Windows is dying to have you select a driver. What's up with "MS Publisher Imagesetter" ? I wish they'd let go of the concept. If the user has joined the 1990s and specified a URL for their printer, that should be all they have to say about the matter. Anything so specialized that a URL alone is not enough could use some other mechanism.

In praise of foreign workers

2010-09-30T07:32:00.000-07:00

It's election season in the U.S., and the television is filled again with advertisements discussing foreign workers.

This is a large subject, but let me emphasize one thing: the ads have it backwards for software jobs. I want foreigners working with me. They are valuable members of the teams I've been on, and they create as many jobs as the take.

Whenever one of my coworkers has visa trouble, it's a real harm to the team. We lose lots of time, often days if not weeks, just due to the person filing papers, making phone calls, and travelling to offices. The national offices involved are far from friendly about the whole thing, either. They often keep bank hours, and they sometimes require presence in person. If you make any little mistake, the letters don't say, "You seem to have forgotten to file form IS-1042-T. Could you please resubmit it?" They are more like, "Get out, you rotten terrorist scum! If you aren't gone by tomorrow, your assets will be seized." This all leads to a situation where the person isn't in the best frame of mind to do good work.

Supposedly the point of this is to protect American workers. The economics behind that doesn't apply to software, however. Most of the ones I've worked with have a backlog of 5-10 times the amount of work they are doing that would be valuable to do if only they had a clone. When a foreign worker comes to the U.S. to work on computers, they don't knock someone else out of a job. They do one of those things that was previously being left on the table.

Moreover, having more people in the industry means that we all get smarter. They enrich the intellectual community. Smarter programmers are more productive, and more productive programmers make higher wages. Without foreign workers, we aren't as capable as we could be.

In short, I truly wish that most all barriers to foreign workers would be dropped in my industry. They're based on xenophobia and bigotry, and I'm embarrassed every time one of my coworkers must deal with it. If someone can get a computer job in the U.S., then let them come. They expand the pie by far more than they consume.

It really was just about Flash

2010-09-12T07:51:00.001-07:00

There are a number of platform wars going on right now, on various classes of computers. One of them is over the market for applications on consumer mobile devices. At the OS level, there are Android, iOS, Windows, RIM, and others. There are also cross-OS platforms, such as HTML and Flash. It's a good time to be on the buying side of a mobile device. Extraordinary levels of effort are being put into making each platform appeal to users.

Sometimes, though, the moves are not in consumers' interest. Apple's ban of alternate programming languages on the iPhone is just such a move. Jobs can say all he likes that Flash apps are inherently bad, but few truly agree. A more precise statement is that Flash, many feel, isn't the best possible tool in general. Programmers, however, are more important than the specific tools. I'm sure that the best Flash apps that were banned are better than the worst apps currently being allowed. If the app store simply focused on quality itself, rather than implementation technology, then iPhone users would get an improved selection of apps to install.

Jobs knows this, and so he hasn't really been blocking all alternate languages from his platform. Just the Flash ones:

Other cross-platform compiler makers had had no such trouble, even during the monthslong stretch when the now-obsolete Apple policy had supposedly been in effect. Both Appcelerator and Unity Technologies, which sell iOS programming tools, stressed on Thursday that developers using their compilers had been able to get ported programs into the App Store since April.

Sick stuff. Happily, as word came out, the legality of the approach is starting to fray. Apple needs to either explicitly and specifically block Flash--thus facing anti-trust issues--or drop the bogusly general block. They've now chosen to drop the general ban, which is really the best thing for users.

The most important problem in computer science

2010-09-05T06:24:00.000-07:00

Richard Lipton chooses The Projector Problem:

I believe that we are sorely in need of an Edison who can invent a projector system that actually works.

Here here. What makes this so hard? I've had a lot of opportunity to muse on it while waiting at the beginning of talks while people fiddle with projector and laptop settings. Here are the main ones that have come to mind:

It takes an obscure manual intervention to turn on the projector output. Thinkpads have the best option, but it's not saying much: you hold down Fn and press F5. On other systems, you have to fish around in the UI for the screen settings dialog. Given the importance of this problem, I think it deserves a large button right next to the VGA port.
The laptop doesn't detect the projector's resolution. I'm sure it can, because CRTs have had this ability for eons. It's vanishingly rare that anyone will want a resolution other than the projector's max resolution, but for some reason the screen settings UIs don't just do that for you. In many cases they don't even gray out the settings that aren't going to work on that projector.
The settings UIs are universally terrible for switching to projection mode. On an Apple, you are given a list of 10-20 resolutions, almost all of which are bad ideas. On Windows, you have to click to a separate tab to even get to the place where you can turn on projector output and modify resolution. The NVidia UI on Linux, meanwhile, takes the horror to a new level. It would take a small novel to describe it all, so let me just mention that it involves knowing what "Twinview" is. Thanks, NVidia. You took what should be a trivial problem and instead of just making it work, you are making it a teaching moment for customers to learn your brand names.
If you use an Apple product, you additionally have the problem of finding the right dongle before you can plug in. These things are like pencils and pens: no matter how much you replenish the supply, they keep disappearing. Once one conference room loses one of its dongles, people start borrowing them between rooms, so they all share in the pain. I tried carrying my own, but that doesn't work, because eventually I loan it out and it disappears. There must be some alternate universe that is collecting all the Apple dongles from this one. They really just disappear.

This doesn't seem like a terribly challenging problem, really. It just takes a laptop maker to consider it a problem worth solving. A laptop maker could, if it chose, have a VGA port with a big "Project" button next to it. When pressed, it would switch to mirrored display mode at the max resolution the projector supports, and it would pop up a dialog asking if everything looks ok. If the user clicks Yes, that's it -- done. If the user clicks no, it would switch back to the previous resolution and drop the user into a settings dialog.

Would any laptop maker care to do this, or are you all going to keep working on those gimicky CD player buttons?

Patents as Mutual Assured Destruction

2010-08-30T14:41:00.000-07:00

The best way I can understand the popularity of software patents is that they protect incumbent companies from newcomers. Large incumbent companies accumulate patents, they use them to litigate against small newcomers who have no patents of their own, and they form patent-sharing agreements with each other to prevent the same thing from happening to them. Occasionally it comes back to bite one of the incumbents, but for the most part they seem to believe it comes out in their favor.

One place this arrangement fails, though, is if one of the incumbents decides not to play for the long term. See, the reason incumbents don't sue each other over patents is that they fear the counter-suit. It's classic M.A.D.: mutual assured destruction.

However, what if an incumbent is on their way out of the computer business, either because they are shifting focus or because they are retiring? Well, in that case, the fear of a counter-suit would be nonexistent, wouldn't it? Count me in as one who thinks Paul Allen's recent actions suggest he is planning to retire, or at the very least get out of computers. My next best guesses are that he is trying to make some sort of point, or that he is simply unsavvy about the software industry. Neither of these sounds especially likely.

Rubik's Cube's difficulty cracked

2010-08-11T16:22:00.001-07:00

I'm late to notice this, but recently a team proved that a Rubik's Cube can always be solved in 20 moves or less, regardless of its initial configuration. It had already been proven, back in 1995, that at least one initial configuration requires 20 moves to solve. Thus, all positions can be solved in 20 moves, and some positions require the full 20.

What is particularly interesting is that the these researchers found the 20-move bound by having a computer solve all of the 4E19 initial positions exhaustively. The best proof that didn't do an exhaustive search only proved an upper bound of 22 moves.

I wonder if a human-digestible proof will be found for the 20-move upper bound, or if we'll be left with computers generating the stronger proof? At any rate, this is yet one more problem where a mathematical result depends crucially on some very heavy computation.

Pseudonymity

2010-07-08T17:48:00.000-07:00

People participating in online forums are better off being identified by pseudonyms rather than by their legal names. This is pretty engrained in me after many years of participating in such forums, so it takes some soul searching to explain. Let me try and distill out three points.

First, people have multiple parts of their lives, and they don't want them to mix. There are many reasons why this is good, but at the very least let's observe that this is how most people arrange their lives. There's work, and there's play. On the Internet, pseudonyms allow these separate lives to be separated more effectively.

Second, it fights prejudice. What makes prejudice so bad is not just that people are judged wrongly, but that they are judged wrongly using information that really should be irrelevant. Using pseudonyms means that this irrelevant information can be completely non-present. If your name is Julie or Juan or Duk-Kwan, you can expect to get a different--unfairly different--reaction if people learn your name, and thus your probable gender or ethnicity.

Finally, let me emphasize that pseudonyms are not anonymous. They are actual names, and they accumulate a reputation just like any other name. "Tom Cruise" is a pseudonym, but it's a name that has a very strong reputation (of one sort or another). So it goes with online pseudonyms, as well.

Given this, readers won't be surprised that I oppose Blizzard's trend toward using a "real" ID, "real" meaning a name on the credit card that pays for an account. Already, if you want to participate in cross-server chat on their games, you have to expose your credit-card name to everyone on your cross-server friends list. Now they are talking about changing the official forums to use credit-card names rather than

The idea seams to be that if people post under their credit-card names rather than their Warcraft character names, then they'll post better content to the forums. I don't agree this is a sufficient reason for the change, and I don't even think they are going to get the result the hope for.

Aside from all this heavy stuff, why in the world is a fantasy online computer game going this way? Grey Shade says it best:

But that’s it, you get it? That’s why I play. That’s why my friends play. Because we like to come home from a long day of being John Smith or Jane Doe and get on the computer and MURDER SOME REALLY AWESOME INTERNET DRAGONS.

UPDATE: Blizzard cancelled enforced real names on the forums, and said they are going to strive to prevent real names leaking in-game for people who want that. Good choices! Crisis averted. Everyone can go back, now, to killing Internet dragons.

A foreign film I'd love to see

2010-07-01T07:37:00.000-07:00

Java 4 ever is a hilarious trailer for a made up movie. It has all the cliches from a Hollywood warm-human-tale kinda movie, but instead of being about forbidden cross-sect love, it's about open computer standards.

Beware that the trailer is R rated at one point.

HT Ted Neward

Wrapping code is slow on Firefox

2010-06-29T13:56:00.000-07:00

UPDATE: Filed as bug 576630 with Mozilla. It would be great if this slowdown can be removed, because wrapping chunks of code in a function wrapper is a widely useful tool to have available.

I just learned, to my dismay, that adding a single layer of wrapping around a body of JavaScript code can cause Firefox to really slow down. That is, there are cases where the following code takes a second to load:

statement1
statement2
...
statement1000

Yet, the following equivalent code takes 30+ seconds to load:

(function() {
statement1
statement2
...
statement1000
})()

This is disappointing, because wrapping code inside a function is a straightforward way to control name visibility. If this code defines a bunch of new functions and vars, you might not want them all to be globally visible throughout a browser window. Yet, because of this parsing problem on Firefox, simply adding a wrapper function might not be a good idea.

After some investigation, the problem only arises when there are a lot of functions defined directly inside a single other function. Adding another layer of wrapping gets rid of the parse time problem. That is, the following parses very quickly:

(function() {
(function() {
statement1
..
statement10
})()
...
(function() {
statement991
...
statement1000
})()
})()

Of course, to use this approach, you have to make sure that the cross-references between the statements still work. In general this requires modifying the statements to install and read properties on some object that is shared among all the chunks.

Example Code and Timings

I wrote a Scala script named genslow.scala that generates two files: test.html and module.html. Load the first page in firefox, and it will cause a load of the second file into an iframe. An alert will pop up once all the code is loaded saying how long the load took.

There are three variables the top of the script that can be used to modify module.html. On my machine, I get the following timings:

default: 1,015 ms
jslink: 1,135 ms
wrapper: 34,288 ms
wrapper+jslink: 52,078 ms
wrapper+jslink+chunk: 1,188 ms

The timings were on Firefox 3.6.3 on Linux. I only report the first trial in the above table, but the pattern is robust across hitting reload.

Mass Effect for Xb^H^H Windows

2010-06-23T07:08:00.001-07:00

I just got Mass Effect for Windows, but after reading the README file, I fear for the computer it will be installed on:

Game Known Issues
-----------------
In Mass Effect you will occsaionally find elevators that connect different
locations. While riding in an elevator the game is loading significant amounts
of information and modifying data. We recommend against saving the game after
an elevator is activated until the player departs the elevator. Saving during
elevator trips can occasional cause unusual behaviors.

Okay, I can see that being hard to fix. Load/save systems are often tricky, and being between zones would only make it worse. It goes on, though:

Mass Effect does not run on a system using a GMA X3000 video card, a general
protection fault error appear after double clicking the start icon.

Um, wow. That's it? It just doesn't work if you have this card?

Mass Effect does not run optimally on the Sapphire Radeon x1550 series of video
cards. We recommend that Mass Effect is not played on a system with this video
card.

Or that one?

Mass Effect does not run optimally on the NVIDIA GeForce 7100 series of video
cards. We recommend that Mass Effect is not played on a system with this video
card.

That one, either? Methinks they should list the cards it does work with, and on the box, not in a README file.

Mass Effect does not run optimally on a computer with a Pentium 4 CPU with a
FSB below 800 MHz under Windows Vista. We recommend that Mass Effect is not
played on a system with this CPU and operating system combination.

Err, okay. This kinda goes along with "minimum system requirements".

The the NVIDIA 8800 Series of video cards can require significant time (30
seconds or more) to change resolutions. This is due to a required
recalculation of thousands of video shaders.

"Required". As if they couldn't have precomputed shaders for the 10-20 most common resolutions. As if any other game has this problem.

After reading this, I wasn't confident. Sure enough, I get a General Protection Fault on startup. As extra weirdness, it reports a "file not found" exception from within some graphics library.

Overall, I guess what the developers did is make the Xbox version first, and then make a half-hearted attempt to port to Windows. If I'd realized how flaky this is, I probably would have passed it over.

Commutative? Associative? Idemflabitical?!

2010-06-18T17:11:00.000-07:00

Guy Steele has a noble goal in mind for the Fortress library:

I have noticed that when I give talks about Fortress and start talking about the importance of algebraic properties for parallel programming, I often see many pairs of eyes glaze over, if only a bit. It occurs to me that maybe not everyone is conversant or comfortable with the terminology of modern albegra (maybe they had a bad experience with the New Math back in the 1960s, a fate I barely escaped), and this may obscure the essential underlying ideas, which after all are not that difficult, and perhaps even obvious to the average programmer when explained in everyday terms.

It's a good goal. Using technical terms often obscures the real point one is trying to make. Worse, technical terms are often dress up a claim to sound like it says much more than it does. For all kinds of reasons, it is better to well-known informal terms whenever they will work.

Nonetheless, I am not so sure about changing terms like commutative and associative in the Fortress library. It looks like a case where the hard part is not in the terminology, but in the underlying theory itself. Once a programmer understands the theory well enough to work with the library, they'll almost certainly know the standard formal terms anyway.

A similar issue come up for Scala, where writers of very flexible libraries end up working with rather complicated static types. In such cases, there is no getting around understanding how the Scala type system works. The Scala collections library is deep mojo.

That doesn't mean the complexity must leak out to users of the library, however. In both cases, the designers of core libraries must think hard, because they are working with deep abstractions. If the designers do well, then users of these libraries will find everything working effortlessly.