04 February 2015

Why raising the dead is safe

Scientists have cloned a vintage virus. Still works! The article contains a nice explanation of why this is a safe thing to do:

“There's a theoretical risk of this, and we know that the nucleic acid of the virus was in great shape in our sample,” study author Eric Delwart of the University of California told New Scientist. “But old viruses could only re-emerge if they have significant advantages over the countless perfect viruses we have at present.”

I wonder if this is the conventional wisdom among biologists. I think I understand the argument. Delwart is saying that the viruses we have today are extremely well adapted to our environment, and a randomly selected virus from 700 years ago is correspondingly unlikely to have any particular advantage over them.

On the other hand, the same argument says that invasive species should never have an advantage over native ones, right?

And just generally, I think of natural selection as a greedy algorithm, which means it finds local maxima and gets stuck there. Randomly going back and thawing out 700-year-old viruses seems like simulated annealing—in other words it’s exactly what a computer scientist would do on purpose to help their evolutionary algorithms get unstuck!

All of which is just idle speculation coming from me. I should emphasize that it would be nuts to take a 43-word quote in a short blog post as fully characterizing anyone’s view on the subject. Presumably this has all been discussed to death by people who actually know something about it. I wonder where I can read more.

17 November 2014

Old programs

These remarks are my contribution to a keynote address by Eliza Brock Marcum at Nodevember, a JavaScript and Node.js conference in Nashville, Tennessee. Eliza’s talk was on history and the value of history in computing.

I’m always delighted by the light touch and stillness of early programming languages. Not much text; a lot gets done.

—Richard Gabriel, “50 in 50”

Old programming books are better on average than new ones.

Today there are a lot of meh programming books bringing down the average. Hastily written, barely edited, extravagantly typeset, quickly obsolete. Not bad, exactly, but not outstanding. Maybe you’ve written one!

The books we need aren’t necessarily being written. Fortunately a lot of them were written 30 years ago and they’re still good.

I’m going to drop a couple of examples here, but please take these as a literally random sample, not particular recommendations.

I was recently given this copy of Programming Pearls by Jon Bentley. He wrote for the ACM’s magazine before the ACM turned evil, and this is a collection of his columns. It was just one a big box of old programming books, but it stood out because it has some of the worst cover art I have ever encountered. I figured it had to be the content that was good.

And it’s good. I challenge you to name a programming book with as much sheer joy in its pages as there is in the first twenty pages of this book. There’s this one page with three programs written in three different languages that work together to solve a problem because that’s the Unix way. The right way.


    #define WORDMAX 101
    {   char thisword[WORDMAX], sig[WORDMAX];
        while (scanf("%s", thisword) != EOF) {
            strcpy(sig, thisword);
            qsort(sig, strlen(sig), 1, compchar);
            printf("%s %s\n", sig, thisword);


    $1 != prev  { prev = $1; if (NR > 1) printf "\n" }
                { printf "%s ", $2 }
    END         { printf "\n" }


    sign <dictionary | sort | squash >gramlist

Publication date: 1986. These programs still run today.

This month I opened a book that was written in 1977 and unexpectedly found the annotated source code of an operating system in it. It’s chapter 5. Seventy pages of a slim, 300-page book that isn’t even about operating systems. It’s Architecture of Concurrent Programs by Per Branch Hansen.

It says that the whole operating system, including some parts that aren’t in the book, is five thousand lines of code. It was written by a team of two.

Imagine understanding a whole operating system.

(In fact later I found out this book contains listings from four different small operating systems. It also contains a summary of the book in Danish.)

These old books are a delight to read. The programs in them are a delight to read. There is beauty and poetry in them. This will sound trite, but they were written in a simpler world. They really were. Programming was simpler. There was no client/server divide. No HTTP, no URLs, no network, no browser, no events, no queues, no GUI. There was no concept of your data living in some other database process. You always had your hands on the data directly. These programs have a clarity and simplicity and immediacy that is strange to us now. But I can’t shake the feeling this is what we need to be striving for.

If you haven’t experienced it, you can’t strive for it. You’re designing the platform we’re all going to be using tomorrow.

Read yesterday’s programs. We’ll all be better off.

The past is a foreign country: they do things differently there.

—L. P. Hartley

There is another reason to dip into the past. Travel is broadening.

Programming was once younger, and people had crazy ideas. Ideas that were uncontaminated by practice, formed by brains that weren’t ground down by hard experience.

One out of every thousand crazy ideas you hear is going to change your life.

Take functional programming. The first major functional programming language was APL, implemented in 1963. It looked like this (example from Wikipedia):

life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

And when did the golden age of functional programming begin? It was last Tuesday actually. Yeah. We need it today.

Seven years ago I remember sitting in an ECMAScript standard committee meeting, thinking we can’t expect JS programmers to understand closures and lexical scoping. I have never been more wrong in my life. FP is here to stay (with slighty different syntax, as it turns out). It only took 50 years to catch on.

The operating system I was telling you about earlier? That was never a commercial product. As far as I can tell it never went anywhere. And yet.

That book is full of ideas that make me think of Erlang (but it was written 9 years before Erlang) and even more so, Rust (but it was 25 years before Rust).

It makes me want to build new things.

27 January 2014

He who fights the future

Over a hundred years ago a Scandinavian philosopher, Sören Kierkegaard, made a profound observation about the future. … “He who fights the future,” remarked the philosopher, “has a dangerous enemy. The future is not, it borrows its strength from the man himself, and when it has tricked him out of this, then it appears outside of him as the enemy he must meet.”

We in the western world have rushed eagerly to embrace the future—and in so doing we have provided that future with a strength it has derived from us and our endeavors. Now, stunned, puzzled and dismayed, we try to withdraw from the embrace, not of a necessary tomorrow, but of that future which we have invited and of which, at last, we have grown perceptibly afraid. In a sudden horror we discover that the years now rushing upon us have drained our moral resources and have taken shape out of our own impotence. At this moment, if we possess even a modicum of reflective insight, we will give heed to Kierkegaard’s concluding wisdom: “Through the eternal,” he enjoins us, “we can conquer the future.”

The advice is cryptic; the hour late. Moreover, what have we to do with the eternal? Our age, we know, is littered with the wrecks of war, of outworn philosophies, of broken faiths. We profess little but the new and study only change.

—Loren Eiseley, The Firmament of Time, 1960.

ORD Camp 2013

Last year I spent a weekend at ORD Camp, a Chicago unconference populated by hackers of all descriptions.

There was a heady mix of 3d printing enthusiasts, robot-builders, programmers, drinkers, dreamers, proud Chicagoans, and werewolves. Everyone brought a talk, or an activity, or at least a bottle.

I couldn’t make it this year. Here’s what I remember from 2013.

  • Christina Pei brought lockpicking sets and gave everyone a chance to use them. It’s not hard to pick a Master key lock with two simple metal tools! I found out about The Open Organization of Lockpickers (@toool). And I learned that it is legal to own lockpicks in 49 states, the one exception being my own home state of Tennessee. (Note that many cities have their own lockpick possession laws, so the rest of you are not necessarily out of the woods.)

  • Strangers host and producer Lea Thau crammed a two-hour-plus workshop on storytelling into 40 minutes, leaving time for attendees to write—and then for a few to tell—true stories of their own lives. Awesome.

  • Human cannonball Kate McGroarty (@KateMcGroarty) did a mile-a-minute improv workshop. I learned: you can define a character just by choosing a funky shape for your spine. Or the way you walk. Also, the best gift you can give your improv partner is a name. Marvel at the speed with which your mind fills in a character for: “Earl”. “Anastasia”. I think my wife and I are going to host an improv party at our house. When did we stop being shy people? I blame Kate.

  • Third Coast International Audio Festival artistic director Julie Shapiro’s session was called Choose Your Own Audio Adventure. Lights off, bunch of nerds in a room listening to beautiful short scraps of audio and voting on what to play next. One example: Radiolab’s story of what happened on day 86 of Aleksander Gamme’s trek to the South Pole (just the first 5 minutes).

  • Jim Blandy’s session, live-coding the lambda calculus, was as virtuosic as you’d expect, if you know him.

  • Around a table, I asked Louis Wasserman what kind of math he studied before he got into programming, and he said combinatorics. What little I know of combinatorics (I said) is a few counting techniques, and the proofs for those always seem really ugly, with a lot of tricky case analysis. To counter that notion, Louis showed me a surprising proof of a theorem about complete subgraphs. I hope I get around to blogging it here later. It’s dead sexy.

  • And I got to chat with Jennifer Brandel, lead producer of WBEZ’s Curious City and organizer of Dance Dance Party Party. The common thread here seems to be: these are beautiful, beautiful things that could totally happen in your city.

Even with all that, my favorite parts of the trip are not even on the list, because they’d be boring to you. Meeting people I’ve wanted to meet for a long time. Listening to music.

Honestly I spent most of the time at ORD Camp sick or else in introvert people-overload. But the event is still unfolding in my head. It was unique, and I’m grateful for it.

Here, have a list of books

Someone linked me to an image, “Top 10 Books I Want My Kids To Read”. It’s now a dead link, but this isn’t about that particular list anyway.

The books on the list were not children’s books. They were books the author hoped his children would read, eventually. How, then, does such a list differ from “Ten Books I Would Recommend To Anyone”?

  1. You might choose books that act on the mind, hoping they will help fulfill your parental responsibility.
  2. You might choose books that tell your kids who you are, and why.
  3. You might choose books that are special to your family.

I guess in the first category, I’d pick some of these:

  • Silas Marner by George Eliot. It’s not superb, but good enough, and it’s about how what you do changes you morally, even if your motives have nothing in particular to do with morality. Morality tales that resonate with one person often ring hollow to the next person, so this is no slam dunk.
  • A Tale of Two Cities. Amazing.
  • The Gospel of Luke. It’s just good, and the message is about love.
  • The Handbook of Epictetus. (However, I do also recommend this every time anyone asks for book recommendations.)

I’m tempted to put in a pair books about science and how it works. Maybe The Demon-Haunted World by Carl Sagan and the book I’m reading now, The Firmament of Time by Loren Eiseley. But I’m not sure those rise to the level of the others, and it’s not like I’m well read enough in this area to make good picks.

In the second category:

  • Ox-Cart Man. This book tells more about me than anything. All the nerd stuff you see in my life is window dressing; the implicit moral background to this poem is where I’m really coming from. (Sorry to disappoint you!)
  • The Handbook of Epictetus. This again? Yes.
  • The Moon Is a Harsh Mistress by Robert Heinlein. I don’t know if I should recommend this. I haven’t tried to read it lately. I read it at an impressionable age and was impression’d.
  • Mountains Beyond Mountains by Tracy Kidder. If you can square this pick with the Heinlein pick, you understand me better than I do.

This list doesn’t make a very flattering self-portrait. I’m moralistic but I’m not sure what is right.

In the third category:

  • The Phantom Tollbooth by Norton Juster. Rhyme and reason for all ages.
  • The Thirteen Clocks by James Thurber. Rich verbal liquor in a fairy-tale-shaped container, and not a moral in sight.

That is only nine.

I don’t think any book I’ve ever read is indispensable, but books are indispensable.

20 January 2014

Lisp Machines

I’m doing some casual research on Lisp Machines. I find myself wishing for the patience of a reference librarian. Or just a very patient friend to lend moral support.

Dead links everywhere. Decay is a natural thing, and on the whole I am grateful that the Web decays. It just doesn’t suit my purpose at the moment.

As recently as 2007:

A wiki has been set up to capture some notes about using lispm's
and the unlambda emulators.  Contributions are welcome and
encouraged.  Thanks to Dan Moniz for setting it up and all who
have contributed.


Tim Newsham

The link is not exactly broken, but the wiki doesn’t work anymore. Imagine two bits of software, once friends, one still alive, one mysteriously vanished who knows when.

But soon enough, the message itself will vanish from the web too; and this message you’re reading now; and in time, the Blogger service. Gone the way of the Lisp Machine itself, interesting to some, gone over the horizon of what’s worth preserving.

01 April 2013

The halting problem and garbage collection

At Talk Day, after Brandon Bradley’s talk about the halting problem, Martha Kelly asked: if it’s impossible to predict the future course of an arbitrary program, how can garbage collectors tell which objects will be used and which can be collected?

Martha’s right. There is a connection!

    function easy() {
        var obj = new Object;

If gc() does garbage collection, then certainly it could collect the new Object, since we are never going to use it. But many garbage collectors will not collect it yet, since there is still a variable referring to that object.

You might think, well, those garbage collectors are stupid. If I ever wrote a garbage collector, it would be perfectly precise, retaining only objects that the program will use in the future, and collecting all others.

Alas, there’s a simple halting-problem-like proof that a perfectly precise garbage collector is impossible.

    function hard() {
        var obj = new Object;
        var objWasGarbage = isThisObjectGarbageOrNot(obj);
        if (objWasGarbage)

The Catch-22 goes like this:

  • If isThisObjectGarbageOrNot(obj) returns true, then the Object is not garbage. It will be used later by alert(obj).
  • But if it returns false, then the object really is garbage: it will never be used.

So it seems the function isThisObjectGarbageOrNot() cannot possibly live up to its name in this case. But that is exactly the function which our perfect garbage collector would need in order to do its job perfectly! Therefore a perfect GC cannot exist.

Real GCs err on the side of caution and retain any objects that aren’t known to be garbage. They use reachability as a (conservative) estimate of which objects the program will use in the future.

27 August 2012

Privacy as a weapon

Remember the bogus bomb threats at the University of Pittsburgh? Apparently they were sent by email, anonymously, through a system called Mixmaster. The email passed through a computer in New York, which the FBI seized in April.

Now it is natural to wonder why we even have such things. Why is it OK for people to send email anonymously when it can cause such mayhem? Here’s what the computer’s owners have to say about it:

Q: Doesn’t Mixmaster/anonymous remailers enable criminals to do bad things?

A: Criminals can already do bad things. Since they’re willing to break laws, they already have lots of options available that provide better privacy than mixmaster provides. They can steal cell phones, use them, and throw them in a ditch; they can crack into computers in Korea or Brazil and use them to launch abusive activities; they can use spyware, viruses, and other techniques to take control of literally millions of Windows machines around the world.

Mixmaster aims to provide protection for ordinary people who want to follow the law. Only criminals have privacy right now, and we need to fix that.

All this is true, up to a point. Criminals have actually done all those things. It is also entirely plausible, though, that the particular culprit in question chose Mixmaster. Shortly after that server was seized, the bomb threats stopped.

My thoughts about privacy have changed. I used to think this:

People who keep secrets have something to hide.

I understood at the time that it was a simplistic truism, but it seemed useful anyway. But it’s not useful, because:

People who wear clothes have something to hide.

See? It just doesn't work. Here is what I think now:

Everyone has something to hide from a sufficiently reprehensible adversary.

It doesn’t trip off the tongue quite as lightly.

The FBI in this case was presumably acting with the best intentions, but many governments around the world are plenty reprehensible. Privacy cuts both ways. The ability to track down a miscreant sending bogus bomb threats is exactly the same thing as the ability of an oppressive government to track down activists and rebels and kill them. This is a real concern in some places, and people in those places have to use secure systems that protect their privacy or else give up the fight.

I do think it’s good to have some form of technological constraint on government surveillance, in addition to a reasonable system of checks and balances (requiring warrants for wiretaps, for example). Tracking people down and finding out every detail of what they’ve been doing should be hard. If it’s not, the government will eventually just track everything we do.

People who work on privacy and censorship-circumvention software have already shifted to building systems where there’s no central equipment to seize. Systems like Tor. Governments still have ways of attacking such systems, technologically and otherwise. How governments have tried to block Tor is a startling and absolutely fascinating 2011 talk about this. Watch the first five minutes of that.

One last thing. Anyone in the U.S. will recognize the “Criminals can already do bad things” quote as an argument against gun control. Whether it’s anonymity or a handgun, powerful tools have both offensive and defensive uses. Giving everyone such power is dangerous. Taking this power away from the people is dangerous.

Four hours

On Sunday I had the pleasure of introducing a C/C# programmer to Python.

I always tell people it only takes 4 hours to learn Python, and I say it because it’s true. But when I actually see someone pick up a whole new language from scratch, port some existing scrap of C code to Python, learn where the documentation is, set up virtualenv, and write a web app that sends somebody a text message, all in four hours f’real wall-clock time, well. It gets me right here.

When I was interviewing for Mozilla, Mike Schroepfer asked me two questions. (I bombed them both; to this day I have no idea why they hired me.) One was something like: why is it that dynamically-typed languages can be so much more productive than statically-typed languages? I mumbled something inane about not having to write out the types. Worst answer ever, and I knew it.

It was especially chastening because I had spent a lot of time thinking about it, apparently without drawing any insightful conclusions.

The question seems a little passé to me now, but only because about a decade of my life was a fantastically stupid flame war over that one thing. Not because we really finished with it.

I wonder if we could have a better discussion about this now that we’re all grown up. Maybe I’d have something intelligent to contribute now.

19 August 2012

Time travel

In the garden-variety time travel story, there is a single, fully logically consistent timeline. Trying to change the past is futile. There can be no change. You can be the proximate cause of whatever actually happens, if that’s your thing.

Of course it is never quite clear why nothing could be changed. It just happens that nothing changes, however mightily the characters strive to change things, as if by coincidence. Or Fate is watching—but why is watching enough? Doesn’t Fate actually have to intervene somehow to make everything line up?

It occurred to me once that there could be a possible physical theory to explain this, using fixed points.

I’m not surprised that someone already thought of this. I’m a little surprised that it was Richard Feynman, in a paper titled “Classical electrodynamics in terms of direct interparticle action,” back in 1949.

The Stanford Encyclopedia of Philosophy’s entry on Time Travel and Modern Physics, section 3, explains all.

13 August 2012

A bit more about the library

Nashville hack day happened Saturday and it was awesome. Click the link—every single talk was great, and that page has slides, links, source code, etc. for all of them.

Mine was on sorting and searching at the library.

The talk starts out talking about what happens if you take a book off the library shelves and put it back in the wrong place. When I wrote it, I got curious, so sent email to the library, asking:

Hi, I have a few questions about the library system.

  1. How many books are in the library system?
  2. Do you ever take a full inventory of the library, scanning every book on the shelves?
  3. If not, is there any other way to know if a book is missing? (that is, the catalog shows it as Available but it's not actually on the shelves in the right place)
  4. If you do track missing books, how many are missing right now? How long does it usually take for them to turn up?

I'm not planning a book heist. :) I'm preparing a talk about information technology and libraries for a local event for software engineers.

Engineers are always interested in “failure modes” -- that is, what happens when something goes wrong.

I didn’t get the response in time to change the talk, but the library sent me email this morning with these answers:

  1. There are 1,629,308 items in the collection.
  2. No, we do not do a complete inventory of our entire collection.
  3. We do monthly weeding (de-selection) reports for items that haven't circulated in 1-2 years and that usually catches most missing items. We cover almost the entire collection within one year. However, we also will do a system-wide ILS report and change items automatically to missing status in the computer that haven't circulated in branches in a very long time. We also do this for items stuck in transit mode between locations for a long time.
  4. We do not track missing items at a level that will provide us with statistics like return rate. Anecdotally, however, it is rare that missing items are located again. They are usually missing because of theft.

(I’ll just note that the way they actually track missing items means they wouldn’t detect items that are only misshelved for a month or two. There might be a lot of them. I find two or three every week.)

Anyway, the talk was picked up on Reddit programming and got some wonderful comments. My favorites:

  • “My high school did a volunteer day where we took our entire class year and spent an hour in a class learning how they sort the library books, then sent us each to a section to go through, find misplaced books and put them back in order. It took 2-300 of us ~5 hours to sort all of the library.” –Kimano

  • “This posting reminds of when I visited a warehouse that had automated storage and retrieval of items from the warehouse.

    “One of the cool things that had to happen periodically was essentially the real-world equivalent of defragmenting a hard disk. If you think a hard disk is slow, imagine how slow it is to physically move pallets and cartons!” —grandzooby

  • “The reason we can insert books in a shelf is that there are some gaps distributed between books, and insertion shifts a couple books around to make space. Insertion sort is O(n log n) is a fun research paper that describes a similar way to organize data in arrays, with enough bogus elements (gaps) for insertion to be logarithmic time, but not so many that binary search is super-logarithmic.” —phkuong

And several folks linked me to ShelvAR, a super-cool augmented reality app for keeping library books in order. (Incidentally, those guys seriously need to cheat to get higher apparent performance!)

Hack day was so great that I can’t wait to do another one.

01 May 2012

Why I am not a teacher

(This is in response to Why CS graduates don’t teach which didn’t sound quite right to me.)

Why don’t I quit my job and become a teacher? I’ve thought about it, but

  • Money.

  • It seems like public school teachers have to spend a lot of time just fighting active sabotage—whether it’s the legislature, school boards, textbook publishers, administrators, parents, students, other teachers, etc. In a lot of these stories everyone comes off badly. I hate politics.

  • I’m used to being empowered to make whatever changes are necessary so that I can do my job. Teachers can’t even begin to do that. They don’t control the curriculum, class sizes, external interruptions, disruptive students, prerequisites, and most importantly they have no control over the goal (test scores). It sounds awful.

  • There’s a major “classroom management” component of teaching that I would find stressful and probably unrewarding. I don’t expect I’d be any good at it either. (Money aside, this is the biggest sticking point. I probably just can’t do the work.)

  • Here in Tennessee, to teach in a public school, I would have to enroll in education courses. This isn’t a huge deal, but it’s basically a lot of unpaid overtime and I’ve never heard anybody say anything nice about that kind of part-time program. Maybe I’d be pleasantly surprised. (Go on, tell me I’d be pleasantly surprised.)

Bottom line, being a programmer is easy: it’s mostly just programming. I love teaching more than I love programming. If being a teacher were mostly about teaching, I might have to give it a shot. I wish it was. But it’s just not.

…Is it? Go on, tell me it is.

08 April 2012

Friar Tuck’s theorem

“Well, then, good fellow, holy father, or whatever thou art,” quoth Robin, “I would know whether this same Friar is to be found upon this side of the river or the other.”

“Truly, the river hath no side but the other,” said the Friar.

“How dost thou prove that?” asked Robin.

“Why, thus;” said the Friar, noting the points upon his fingers. “The other side of the river is the other, thou grantest?”

“Yea, truly.”

“Yet the other side is but one side, thou dost mark?”

“No man could gainsay that,” said Robin.

“Then if the other side is one side, this side is the other side. But the other side is the other side, therefore both sides of the river are the other side. Q. E. D.”

“’T is well and pleasantly argued,” quoth Robin; “yet I am still in the dark...”

—from The Merry Adventures of Robin Hood by Howard Pyle

02 April 2012

Understanding a place

Involuntary blockquote:

I’m here, talking to you about talking to rocks, partly because a volcano blew out sideways, and fifteen years later, I turned to look at another volcano I’d known my whole life and saw the same lateral eruption rip it apart thousands of years in the past. “What happened to me,” St. Helens said, “is exactly what happened to them. Your San Francisco Peaks were a peak before that day. Oh, and it would’ve been a really bad idea to stand where you’re standing now, what with the lahar and all.”

I just stood there with my jaw agape, looking from the lahar deposit to the gash in my beloved Peaks, sputtering the occasional overwhelmed expletive as the thrill of realization and the enormity of what had happened pinned me to ground that was perfectly safe for the geologic moment.

This is what I want to give you, my dear readers: the indescribable euphoria that comes from understanding a place for the very first time.

—Dana Hunter (@dhunterauthor), introducing her new blog, Rosetta Stones.

21 March 2012


Andrew Weissmann, the top lawyer at the FBI, says the Supreme Court made a distinction about the Fourth Amendment, which guards against unreasonable searches and seizures, ruling that computers that follow suspects are much more intrusive than people doing the same thing.

“The court essentially is saying that you have an expectation of privacy even though if it was done by humans there would be no violation,” Weissmann says. “But because it's done by machines, it is.”

I guess I should read more about this decision. I mean, on the one hand, it seems to me there’s a pretty obvious practical difference that is going to affect the number of people the government ends up tracking twenty years down the road (in an “all of them” vs. “not so very many of them” sort of way). Not to put too fine a point on it, but if there weren’t a real difference, the FBI wouldn’t be bitching about the decision. On the other hand, yeah, the Fourth Amendment doesn’t seem to be drawing that kind of distinction. So hmmm.

“And the problem with that is that a search warrant requires probable cause to be shown and many of these techniques are things that you use in order to establish probable cause,” Weissmann says. “If you require probable cause for every technique, then you are making it very very hard for law enforcement.”

I am so glad I don’t have the kind of job that would be a lot easier if only we didn’t have a Bill of Rights.

Source: NPR: FBI Still Struggling With Supreme Court’s GPS Ruling