Wednesday, June 22, 2016

We must reject watchlists if we are a nation of laws

I favor strict national gun regulation. There are bad ways to do it, and good ways, but almost any consistent regime would be an improvement over the status quo. If you had asked me the day before yesterday, I would have said that I'd support nearly any gun control measure that was brought before the U.S. Congress.

Well, congratulations, Democrats! You've discovered a way to do it, maybe the only way, that I find stupid and unconscionable: extending the power of "terrorist watch lists" into the realm of gun control. That you should stage a theatrical stunt on the House floor over this measure, of all measures, after you've spent my entire adult life caving cravenly to one right-wing authoritarian demand after another, from illegal war to the normalization of torture, beggars the imagination.

Right off the bat, let's be clear that this measure will have almost no effect on gun violence. But unlike most gun control measures, this one is not merely feeble; it is actively malign, because it further empowers an evil institution.

The so-called "terrorist watch list" is a fundamentally broken idea that is both impossible to implement well, and a moral catastrophe for the rule of law and human equality and liberty.

There are over a million identities on the watchlist, mashed together from many sources of unknown provenance and overseen by nobody with any accountability to disinterested review. Anybody who has worked with database integrations and human organizations of any size knows with total certainty that this watchlist is full of nonsense. Ted Kennedy was on the no-fly list. Bollywood movie star Shah Rukh Khan was on the watch list. The "terrorist watchlist" is a pile of garbage wrapped in a tire fire.

It can't help but be so: the count of people worldwide who engage in terrorism against civilians is miniscule. It is a numerical certainty that nearly all of the people who are on a million-member watchlist are entirely innocent and have no potential to commit a terrorist act.

And how did the data come to be such a fetid swamp of nonsense? Nobody will tell you. The contents of the watchlist are secret; the processes for getting an identity onto the watchlist are secret; the criteria for getting your identity off the watchlist are secret. Good luck if you end up on it, and you're somebody with less clout than a sitting United States Senator or an international celebrity.

Maybe it's time for a brief refresher on how a nation of laws is supposed to work. Laws must be known to the people who govern them. There must be an agreed-upon process — a due process, you might say — by which people are deprived of their rights under those laws. Once you have been convicted of a crime, the state's carceral machinery may act upon you, but until then, merely suspected persons retain their rights. And you don't lose your rights in secret, whereupon you may sue to get them back; the burden of proof is on the state to exercise this due process to take your rights away.

Making legal processes open to public inspection is the most powerful way that we know to ensure that their operation is just; that, for example, we are not merely turning people into second-class citizens for being Muslim or black or whatever the current least-favored category of citizens is. One would think that this argument, at least — that, as Black Lives Matter and related movements have made undeniably clear in recent years, the state operates in flagrantly discriminatory ways when it operates without scrutiny — would carry some currency, even in a left-of-center discourse that values civil liberties less and less as the Bush years recede into the distance.

Yet through the depressing machinery of tribalism, it has suddenly become conventional wisdom in progressive circles that all right-thinking people shall support a bill that further entrenches the influence of the racist, unaccountable, unconstitutional no-fly-list. Otherwise-intelligent people in my Twitter feed have even argued that passing this legislation is the first step towards "fixing" the watchlist:

Astonishing. Astonishing. I have no way of even processing the level of wishful thinking and partisan groupthink necessary for a reasonable person to make this argument in good faith. Can you think of a single example in history where giving a Kafkaesque bureaucratic apparatus additional unaccountable power led to its reform, let alone any such apparatus connected with the security state? I doubt it; the ratchet turns in the other direction.

I have an alternate prediction. Should this legislation be passed by Democrats, we can look forward to the positions around the watchlist becoming crystallized along partisan lines. Since empowering the watchlist will count as a signature political achievement for Democrats, attained through a highly memorable media stunt, henceforth Democrats will fight any efforts that even remotely smell like dismantling the watchlist; this will, of course, include any efforts at meaningful reform. As reverence for the immaculate watchlist turns into a shibboleth of partisan identification, enterprising Democrats will eventually start to propose even more unconstitutional measures to extend its influence into other areas of public life. The extensions will come with, at best, token reforms; perhaps these reforms will moderate its effects on upper-class and upper-middle-class people with surplus time and financial resources, but leave the overall system fundamentally unaccountable and outside any recognizable form of due process for nearly everybody on it. Millions more human beings will suddenly become second-class in the eyes of state; their circle of rights will gradually shrink. The normalization of secret law in the United States will accelerate. Neither Democrats nor Republicans will have the stomach to turn this ratchet backwards.

Furthermore, having discovered again that "terrorism" is the magic word which can rally even the most spineless legislators into action and cow even the most intransigent opponents, Democrats will use this handy rhetorical cudgel to beat anybody who disagrees with them, just as Republicans did during the Bush years, until it is nearly meaningless with overuse. This will be used to pass all manner of additional legislation, equally stupid. Meanwhile, progressives like myself will be excoriated for allegedly being on the side of terrorists and right-wing loons, simply for opposing stupid and malign laws.

Friday, November 14, 2014

The goTo object pattern in Node.js code

I've been messing around with Node.js lately. Like everyone using Node.js, I've been wrestling with the fact that it forces programmers to use hand-rolled continuation passing style for all I/O. Of course, I could use something like async.waterfall() to eliminate boilerplate and deeply indented nested callbacks. However, since I am crazy, I am using Closure Compiler to statically typecheck my server code, and I don't like the way async.waterfall() defeats the typechecker.

You can stop reading here if you're perfectly happy with using async for everything, or perhaps if you're one of those people convinced that static typing is a boondoggle.

Anyway, I've been using a "goTo object" for my callbacks instead. The essence of the pattern is as follows:

  • Define a local variable named goTo whose members are your callbacks.
  • Asynchronous calls use goTo.functionName as the callback expression (usually the final argument to the asynchronous function).
  • At the end of the function, outside the goTo object, start the callback chain by calling goTo.start().

Here is an example, loosely patterned after some database code I recently wrote against the pg npm module. In raw nested-callback style, you would write the following:

var upsert = function(client, ..., cb) {
  client.connect(function(err, conn) {
    if (err) {
      cb(err);
      return;
    }
    
    conn.insert(..., function(err, result) {
      if (err) {
        if (isKeyConflict(err)) {
          conn.update(..., function(err, result) {
            conn.done();
            if (err) {
              cb(err);
              return;
            }
            cb(null, 'updated');
          });
        }
          
        conn.done();
        cb(err);
        return;
      }

      conn.done();
      cb(null, 'inserted');
    });
  });
};

With a goTo object, you write this:

var upsert = function(client, ..., cb) {
  var conn = null;

  var goTo = {
    start: function() {
      client.connect(..., goTo.onConnect);
    },

    onConnect: function(err, conn_) {
      if (err) {
        goTo.finish(err);
        return;
      }
      conn = conn_;  // Stash for later callbacks.
      conn.insert(..., goTo.onInsert);
    },

    onInsert: function(err, result) {
      if (err) {
        if (isKeyConflict(err)) {
          conn.update(..., goTo.onUpdate);
          return;
        }
        goTo.finish(err);
        return;
      }
      goTo.finish(null, 'inserted');
    },

    onUpdate: function(err, result) {
      if (err) {
        goTo.finish(err);
        return;
      }
      goTo.finish(null, 'updated');
    },

    finish: function(err, result) {
      if (conn) {
        conn.done();
      }
      cb(err, result);
    }
  };
  goTo.start();
};

This pattern is easy to annotate with accurate static types:

var upsert = function(...) {
  /** @type {?db.Connection} */
  var conn = null;

  var goTo = {
    ...

    /**
     * @param {db.Error} err
     * @param {db.Connection} conn_
     */
    onConnect: function(err, conn_) { ... },

    /**
     * @param {db.Error} err
     * @param {db.ResultSet} result 
     */
    onInsert: function(err, result) { ... },

    /**
     * @param {db.Error} err
     * @param {db.ResultSet} result
     */
    onUpdate: function(err, result) { ... },

    /**
     * @param {?db.Error} err
     * @param {string=} result
     */
    finish: function(err, result) { ... }
  };
  goTo.start();
};

Some notes on this pattern:

  • It is slightly more verbose than the naive nested-callback version. However, the indentation level does not grow linearly in the length of the call chain, so it scales better with the complexity of the operation. If you add a couple more levels to the nested-callback version, you have "Tea-Party Code", whereas the goTo object version stays the same nesting depth.
  • As in the nested-callback style, error handlers must be written by hand in each callback, which is still verbose and repetitive: the phrase if (err) { goTo.finish(err); return; } occurs repeatedly. On the other hand, you retain the ability to handle errors differently in one callback, as we do here with key conflicts on insertion.
  • Callbacks in the goTo object can have different types, and they will still be precisely typechecked.
  • The pattern generalizes easily to branches and loops (not surprising: it's just an encoding of old-school goto).
  • Data that is initialized during one callback and then used in later callbacks must be declared at top-level as a nullable variable. The top-level variable list can therefore get cluttered. More annoyingly, if your code base heavily uses non-nullable type annotations (Closure's !T), you will have to insert casts or checks when you use the variable, even if you can reason from the control flow that it will be non-null by the time you use it.
  • Sometimes I omit goTo.start(), and just write its contents at top-level, using the goTo object for callbacks only. This makes the code slightly more compact, but has the downside that the code no longer reads top-down.
  • There is no hidden control flow. The whole thing is just a coding idiom, not a library, and you don't have to reason about any complex combinator application going on behind the scenes. Therefore, for example, exceptions propagate exactly as you'd expect just from reading the code.
  • The camelCase identifier goTo is used because goto is a reserved word in JavaScript (reserved for future use; it currently has no semantics).

For comparison, here is the example rewritten with async.waterfall():

var async = require('async');

var upsert = function(client, ..., finalCb) {
  var conn = null;
  async.waterfall([
    function(cb) {
      client.connect(..., cb);
    },

    function(conn_, cb) {
      conn = conn_;
      client.insert(..., cb);
    }

  ], function(err, result) {
    if (isKeyConflict(err)) {
      client.update(..., function(err, result) {
        conn.done();
        if (err) {
          finalCb(err);
          return;
        }
        finalCb(null, 'updated');
      });
      return;
    }

    conn.done();
    if (err) {
      finalCb(err);
      return;
    }
    finalCb(null, 'inserted');
  });
};

In some ways, this is better and terser than the goTo object. Most importantly, error handling and operation completion are isolated in one location. Also, blocks in the waterfall are anonymous, so you're not cluttering up your code with extra identifiers.

On the other hand, this has some downsides, which are mostly the flip sides of some properties of goTo objects:

  • Closure, like most generic type systems, only supports arrays of homogeneous element type (AFAIK Typescript shares this limitation update: fixed in 1.3; see comments). Therefore, the callbacks in async.waterfall()'s first argument must be typed with their least upper bound, function(...[*]), thus losing any useful static typing for the callbacks and their arguments.
  • Any custom error handling for a particular callback must be performed in the shared "done" callback. Note that for the above example to work, the error object must carry enough information so that isKeyConflict() (whose implementation is not shown) can return true for insertion conflicts only. Otherwise, we have introduced a defect.
  • Only a linear chain of calls is supported. Branches and loops must be hand-rolled, or you have to use additional nested combinators. This doesn't matter for this example, but branches and loops aren't uncommon in interesting application code.

Now, goTo objects are not strictly superior to the alternatives in all situations. The pattern still has some overhead and boilerplate. For one or two levels of callbacks, you should probably just write in the naive nested callback style. If you have a linear callback chain of homogeneous type, or if you just don't care about statically typing the code, async.waterfall() has some advantages.

Plus, popping up a level, if you are writing lots of complex logic in your server, I'm not sure Node.js is even the right technology base. Languages where you don't have to write in continuation-passing style in the first place may be more pleasurable, terse, and straightforward. I mean, look: I've been reduced to programming with goto, the original harmful technology. By writing up this post, I'm trying to make the best of a bad situation, not leaping out of my bathtub crying eureka.

Anyway, caveats aside, I just thought I'd share this pattern in case anyone finds it useful. Yesterday I was chatting about Node.js with a friend and when I mentioned how I was handling callback hell, he seemed mildly surprised. I thought everybody was using some variant of this already, at least wherever they weren't using async. Apparently not.


p.s. The above pattern is, of course, not confined to Node.js. It could be used in any codebase written in CPS, in a language that has letrec or an equivalent construct. It's hard to think of another context where people intentionally write CPS by hand though.

Monday, November 10, 2014

A lottery is a tax on... people who are good at reasoning about risk-adjusted returns?

Rescued from the drafts folder because John Oliver has rendered it timely.

People who consider themselves smart sometimes joke that a lottery is a tax on people who are bad at math.

The root of this reasoning is that the expected return on investment for a lottery ticket is negative. It can't help but be otherwise: the lottery turns a profit, hence the payout multiplied by the probability of winning must be less than the price of the ticket. Therefore, the reasoning goes, the people who buy lottery tickets must be incapable of figuring this out. Ha ha, let us laugh at the rubes and congratulate ourselves on our superiority.

One rejoinder is that the true value of a lottery ticket, to the buyer, is the entertainment value of the fantasy of winning. One obtains the fantasy with probability 1 and thus as long as the entertainment value of this fantasy exceeds the price of the ticket, the buyer comes out ahead.

There is something to this. But I think a stronger claim can be made.

A lottery is the mirror image of catastrophe insurance. Note that buying insurance also has a negative expected return. Provided their actuarial tables are accurate, insurance companies turn a profit. Therefore the probability of being compensated for your loss, multiplied by the compensation, must be less than the cost of the insurance premiums. But nobody says that insurance is a tax on people who are bad at math. Quite the opposite: buying insurance is viewed as a sign of prudence.

The issue, of course, is that the naive expected return calculation fails to adequately consider the nature of risk and catastrophe. At certain thresholds, financial consequences as experienced by human beings become strongly nonlinear, probably due to the declining marginal utility of money. Suffering complete ruin due to, say, a car accident entails such severe consequences that we are willing to accept a modestly negative expected return in exchange for the assurance that it will simply never occur.

A lottery is simply the flip side of this coin. The extremely rare event is a hugely positive one, instead of a hugely negative one, huge enough to produce qualitative rather than merely quantitative changes to your lifestyle. And one accepts a modestly negative expected return, not so that one can avoid the risk, but that one can be exposed to the risk.

If you are a member of the educated, affluent middle class, there is an excellent chance that your instinct rebels, and you're already hunting for the flaw in this reasoning. Surely there's something sad, and not prudent, about those largely working-class souls who buy a lottery ticket every week, rather than rolling that $52 per year into a safe index fund at a post-tax rate of return of roughly 2.5% per annum, at which rate their investment, if it somehow survived unperturbed the ups and downs of a life that is considerably more exposed to financial risk than a middle-class person's, might compound to the princely sum of a couple months' rent by the time they die, or alternatively enough to pay for a slightly nicer coffin.

And maybe there is a flaw in this reasoning. I'm not completely convinced myself and I'm not going to start buying lottery tickets. But I'm honestly having trouble finding the flaw. Any indictment of spending (small amounts of) money on lottery tickets must surely also apply to buying insurance. If it is worth overpaying a little bit to eliminate the possibility of a hugely negative outcome, surely it is worth overpaying a little bit to create the possibility of a hugely positive outcome. The situations are symmetric, and I think one can only break the symmetry by admitting the validity of loss-aversion (usually viewed as irrational by economists) or something similar.

Alternatively, if you have access to the actuarial tables of your insurance company, then perhaps you can argue that a lottery is, quantitatively, simply a worse deal than your insurance typically is... but you probably don't have access to those actuarial tables. And I sincerely doubt that the widespread middle-class snobbery towards lottery players is based on quantitative calculations of this sort. (Actually, I strongly suspect that it is based on a fallacious, gut-instinct "folk probability" feeling that gambling on any extremely remote event, like winning the lottery, is somehow inherently foolish.)

So what's the flaw? I ask this question non-rhetorically; that is, I am genuinely curious about the answer.


p.s. None of the above, of course, is to say that I think the taxation effect of lotteries, which is staggeringly regressive, is a good thing. I would strongly support the replacement of lotteries with progressive tax increases plus transfer payments! Gambling addiction is bad too. But these things seem distinct from the notion that playing the lottery in small amounts is irrational in some game-theoretic sense.

Wednesday, October 01, 2014

On recent events in Hong Kong, and related lessons from American history

The BBC reports:

In China, an editorial in People's Daily warned of "unimaginable consequences" if the protests continued...

Unimaginable consequences! I literally can't imagine, actually. They can't roll out the tanks this time. In the age of ubiquitous digital photography and the Internet, it won't be a few grainy shots of one guy with a shopping bag.

I've been telling people for a while that I think that Chinese leaders are way too fearful of political protests. Look at the United States. Street protests may have affected the course of history a half century ago, but in my lifetime, street protests in America have proven to be ephemeral outbursts of emotion, more a substitute for change than a precursor of it. As I've said before, the system of government by elected representatives has evolved a nearly 100% effective immune system against alteration via protest.

For example, a hundred thousand people took to the streets of New York protesting the Iraq war. A decade later, we appear to be mired in eternal war in the Middle East. At this stage, I have serious doubts that the United States military will leave the Middle East in my lifetime. But those protestors, oh, I bet they felt heroic, like they were doing something world-changing when they were marching down that street in such massive numbers. Even that one inevitable guy holding the "Free Mumia" sign at the anti-war rally.

China's leaders need to learn to relax. Rather than clamping down on protests, they should learn from the West: create free speech zones, let the protestors expend their energy, let them lose focus and direction as the tide of life's million distractions gradually erodes their morale, and meanwhile make all the important decisions in incredibly boring committee meetings and reports, which are freely available (and sometimes even broadcast on television channels that nobody watches) but too numerous and too dull for any normal person to keep up with.

It turns out that if you construct your society just right, the drama and glamour of protests can be used, in a judo move, to undermine their effectiveness. The protest becomes a big identity-affirmation party, an end-in-itself. The shorthand "demo" (for "demonstration"), which is what many activist groups in the U.S. call a street protest, is apropos: the point becomes to show off. After the demo winds down, a bunch of energy has been expended, yet the same people are in charge and are even quite likely to be re-elected.

I don't know quite how we got here, and I'm not saying that I have a better answer, but I will note that if you told aliens that a widely held theory of change among many political activists on Earth was

  1. throw a parade;
  2. the government changes its behavior.

then the aliens might be confused. They might ask: what is the mechanism that you propose for this causal effect, given that the formal mechanisms for altering laws generally make no reference to parades, but rather to activities that take place mostly indoors, such as voting, drafting legislation, bureaucratic rule-making, and court decisions?

Ultimately, the Chinese government's attitude towards protest displays a deep, perhaps even touchingly naive faith in the raw power of people to change the government. It is heartwarming, in an odd way. And, all cynicism aside, I sincerely wish the Chinese people the best with the whole protest thing. Maybe they can keep it working better than we did.

Thursday, September 18, 2014

US ISPs do not deserve much credit for increasing broadband speeds

Disclaimer: I worked for Google from 2006-2013, although not on Fiber.

Towards the end of this Twitter thread sparked by Timothy B. Lee, a commenter writes (by way of defending US ISPs):

Internet speeds have increased 1500% in ten years. 250k Wi-Fi hotspots are now available. That's progress.

When I read this, I just thought, this is such bullshit. Taking it apart with sufficiently satisfying thoroughness requires more than 140 characters, so I'm going to say it here.

US ISPs are riding the wave of technological progress. Giving them credit for the wave is evidence of cluelessness so extreme as to strongly suggest intellectual dishonesty.

First, crediting ISPs for the spread of wireless hotspots is especially egregious: it's a bit like giving them credit for Moore's Law. Even if ISPs had completely failed to increase speeds beyond dial-up, people would still want local networks without the hassle of Ethernet cables. The development and spread of wireless technology was not driven by ISPs. In fact, in some ways the opposite is true, as many ISPs retained official policies against running an open wireless hotspot (or even connecting multiple devices via NAT!) long after broadband became widely available.

Second, as for a 15x improvement in ten years[0]: that might sound impressive to some people, but all I can think is that ten years equals nearly seven doublings of Moore's Law and 27 = 128. Network speed doesn't track transistor density exactly, but computing technology is full of exponential curves like this (storage density, for example, doubles even faster than Moore's Law). To anyone with a clue about computing technology, 15x in 10 years obviously sounds somewhere between mediocre and lousy. In fact, Nielsen's Law predicts compound improvement of 57x over 10 years, or nearly 4x the observed improvement claimed by Dietz.[1] When Dietz calls out 15x improvement as a talking point in ISPs' favor, he is trying to rhetorically exploit an information asymmetry, namely his audience's presumed ignorance of exponential curves in computing technology.

Therefore, the reality is that US ISPs are badly managed technological laggards, just like everyone thinks.

In fact, the pace at which ISPs have taken up technological innovation is so bad that an entrant from another industry was able to enter the market and, without even trying very hard, spank the incumbents so thoroughly that it became a national embarrassment.

Google does so many things so well that you may not even be properly surprised by this fact. Let me try to give you a visceral feel for how anomalous Google Fiber is. Consider what happened when Google entered a market where its major competitor really was pushing innovation to the limit: consider Android. Google had to dedicate hundreds of its best and hardest-working engineers to the project and enlist the support of essentially every other company in the industry, and after eight hard-fought years, the best it can show for its efforts is rough technological parity with Apple.

Or, to take an example where Google was the defender, consider what happened when Microsoft decided to enter the search engine market. Again, this is a market where the strongest competitor really was pushing innovation to the limit. Billions of dollars and millions of engineer-hours later, Bing's search quality is still slightly worse than Google's.

I don't know the head count for Google Fiber (and even if I did, it would be covered by my NDA) but I will venture a strong guess that its engineering head count is far less than Android's, like at least an order of magnitude. In Google's product portfolio, judging by the scale of investment and strategic value, Google Fiber is basically a hobby, one that Google would never even have tried if US ISPs were remotely as good at their jobs as, say, ISPs in South Korea. And yet, technologically, Google Fiber simply outclassed these incumbents, who are supposedly competing and innovating furiously to earn your dollar.[2]

Imagine you had a friend who claimed to be training super-hard at tennis. But whenever you're at the courts, you see them go out to the court, set up the tennis ball machine, and swat lethargically at balls for about ten minutes, after which they sit down to sip an energy drink and diddle around on their phone. Then, one day, your niece, who's in reasonably good shape but has never picked up a tennis racket in her life, drops by, and she walks onto the court and crushes your friend in straight sets without breaking a sweat. You might reasonably question whether your friend was really training as hard as they claim.

In short, lauding the big US ISPs for their piddling achievements is the soft bigotry of low expectations.

But don't worry, ISPs, America isn't giving up on you. We believe that if you're subjected to the right mixture of tough love, including the right kinds of competition and regulation, you're capable of achieving just as much as Google Fiber did. Or, at a minimum, we believe that the ISP market is capable of achieving that. In the meantime, we'll try hard to ignore the risible bullshit of telecom hacks who claim that you're doing well enough.


[0] Engineers generally use multiples rather than percentages to describe improvements of this magnitude. Dietz's use of "increased 1500%" rather than 15x is a classic PR hack's way of making modestly sized numbers seem gigantic.

[1] Nielsen's predictions are fitted to observations, but those observations are for "high-end users". Dietz's number, which presumably describes mean or median users, reveals how poorly ISPs have done at making high-speed internet affordable despite the march of technology. Note that we do not see this failure in other, more competitive areas of computing technology: Intel's mid-range notebook-class processors follow Moore's Law just as well as its high-end server chips.

[2] This paragraph contains a logical honeypot for telecom hacks, who are likely to see an argument that they think they can debunk, but which they can only debunk by resorting to utter bullshit, which they will promptly be called upon. See if you can spot it.