research!rsc

Go Proposal Process: Scaling Discussions

2019-08-22T10:00:00-04:00

[I’ve been thinking a lot recently about the Go proposal process, which is the way we propose, discuss, and decide changes to Go itself. Like nearly everything about Go, the proposal process is an experiment, so it makes sense to reflect on what we’ve learned and try to improve it. This post is the fourth in a series of posts about what works well and, more importantly, what we might want to change.]

The current proposal process refers to “discussion on the issue tracker” and, in the case of a design doc, a “final discussion,” but we’ve never written more about how to make those discussions effective. A discussion of a small is typically a dozen messages or fewer; those are easy. Discussion of large changes is more difficult and does not always work well.

Scaling One Discussion

As a forum for active discussion of large changes, the GitHub issue tracker has serious flaws. As I write this, the “try” issue takes seven seconds to load, and when it does it reports that there are 798 comments but only displays the first 29, then a marker for “773 hidden items,” and then the last 25. Hiding most of the discussion makes it impossible to search the page, which leads to people making points that have already been said. (For comparison, my outdated, manually curated summary page loads and displays 611 comments in 300ms. The problem is not the size of the raw data.) Using a discussion forum that displayed the entire discussion would be a step in the right direction. After that, it would likely help to display a threaded tree of messages, both to make clear what a reply is replying to and also to allow skipping over subthreads that are uninteresting for one reason or another. After that, it would likely help to add comment ranking that affects display order, to help surface the most important comments. One idea raised was to use /r/golang or a new subreddit for the large proposal discussions, and that seems worth considering further.

At the contributor summit, we asked that each discussion have someone serve in the role of “facilitator.” The facilitator tries to point out possible misunderstandings as they happen, makes sure that a few people don’t dominate the conversation, and tries to bring quiet people into the conversation. One point raised was whether it would make sense for the online proposal discussion to have a clear facilitator whose job is to keep a summary or decision document up-to-date as well as to keep the discussion on topic and non-repeating as much as possible. (In the first few days of a particularly active discussion, this might approach a full-time job.)

While better software and better process would help manage a large discussion, though, there is a point of diminishing returns, and we shouldn’t focus on this one discussion to the exclusion of what precedes it. It is possible that instead of trying to scale one discussion we should scale by having many discussions.

Scaling with Many Discussions

As I mentioned in the large changes post, one problem with “try” was simply that it should have been a second design draft, not a proposal. Making it a proposal with a timeline made everyone feel like they had to rush to comment before a decision was made. In the more relaxed setting of evaluating a design draft, the more distributed “post a thoughtful experience report somewhere and link it to the wiki” scales much better and seems to be working well.

Requiring large changes to start with a series of design drafts creates space for a variety of different conversations about the designs, in different forums and media. Any important points discovered in those conversations can be reported back to the proposal issue and influence future drafts, without having to put every comment on the proposal issue. These various discussions would also help impacted users get up to speed on the details of the proposal, again without having every comment on the issue itself.

Overall, having many discussions would in turn reduce the criticality of the issue tracker discussion itself and therefore the demands the discussion places on the discussion forum, whether that’s GitHub, Reddit, or something else. (As one data point, the Go modules issue received only 242 comments, compared to the current 798 for “try”, quite possibly because there had already been so much community discussion in other forums before the issue was filed.)

Scaling with Offline Discussions

Another fascinating idea raised at the contributor summit is to make use of the Go Meetup network in the discussions of the most important, largest changes, such as generics. The idea would be to prepare materials to help meetup organizers (or others) lead and facilitate discussions at each local meetup. Then, crucially, we could gather summaries of feedback from each meetup and possibly even iterate this process. What I like most about this idea is that it engages a portion of the user community (at least potentially) different from “people who have the time and energy to keep up with GitHub,” by taking the discussion to them. (I plan to write a future post about representation more broadly.)

Scaling with Decision Documents

Another way to reduce the load placed on the GitHub issue discussion would be to shift the focus to writing a “decision document” laying out the various points raised and presenting as fairly as possible both sides of the decision to be made. Then the discussion would serve primarily to suggest additions or changes to the decision document. This would have the important effect that someone who looked away for a week or two could catch up not by reading every message that arrived in the interim but instead by looking at what had changed in the much shorter document. We already do this informally for very large issues by trying to post summary comments occasionally; formalizing this in a separate document might help encourage people to start at the document instead of the discussion. The decision document could also be a new section in the proposal design document, but perhaps a separate document would be easier to point at. I filed issue 33791 to track this idea.

Summary

Overall, it seems clear we can do better at scaling and managing a single large discussion, but I think it is equally clear that process adjustments such as having many discussions or producing a decision document could make the final discussion easier and shorter, which would be a complementary, and possibly larger, win. If I had to choose one aspect of discussions to focus on, I think I would focus on addressing the underlying social problem by taking steps to turn down the importance and heat of the final discussion, such as creating space for multiple discussions and introducing a decision document as a way to focus the energy of the discussion, instead of falling into the engineer’s fallacy of “let’s build a better discussion forum.”

Again, this is the fourth post in a series of posts thinking and brainstorming about the Go proposal process. Everything about these posts is very rough. The point of posting this series—thinking out loud instead of thinking quietly—is so that anyone who is interested can join the thinking.

I encourage feedback, whether in the form of comments on these posts, comments on the newly filed issues, mail to rsc@golang.org, or your own blog posts (please leave links in the comments). Thanks for taking the time to read these and think with me.

The next post will be about how the process for proposing large changes could be made smoother with some kind of official mechanism for experiments and prototypes.

Go Proposal Process: Large Changes

2019-08-15T12:00:00-04:00

[I’ve been thinking a lot recently about the Go proposal process, which is the way we propose, discuss, and decide changes to Go itself. Like nearly everything about Go, the proposal process is an experiment, so it makes sense to reflect on what we’ve learned and try to improve it. This post is the third in a series of posts about what works well and, more importantly, what we might want to change.]

The proposal process we have today recognizes two kinds of proposal: trivial (no design doc) and non-trivial (design doc). An initial proposal issue can be just a few lines describing the idea, which is then discussed on the GitHub issue. Most proposals exit the process after this discussion. Typical reasons for declining a proposal at this stage include some combination of:

The proposal is a duplicate of a previous proposal.
The proposal is not specific enough to evaluate. For example, issue 20142 suggests to do something—but not something specific—about accidental nil dereferences.
The proposal is not backwards compatible. For example, issue 33454 proposed first to change the type signature of log.(*Logger).SetOutput and then was revised to change only the semantics instead. Both would be backwards-incompatible changes.
The proposal can already be implemented as a package outside the standard library. For example, the problem solved by issue 33454—logging to multiple writers—is easily solved with `io.MultiWriter.
The proposal does not address a common enough problem to merit a change or addition to the language or standard library. For example, issue 26262 suggested a new %*T print verb that would have little applicability and is easily implemented as a one-line function if needed.
The proposal violates a core design principle or goal of the package. For example, issue 33449 suggested adding indirect template calls to text/template, but that would invalidate the safety analysis in html/template.

The typical reason for accepting a proposal at this stage is that the details are simple and straightforward enough that they can be stated crisply and clearly without a design doc, and there is general agreement about moving forward. The specifics can range from significant to trivial, from issue 19069 (extend release support timeline) to issue 18086 (add json.Valid) to issue 20023 (document that os.NewFile returns an error when passed a negative file descriptor).

Other proposals are intricate enough or have subtle enough implications to merit writing a design document, which we save in the proposal design repo. For example, here are the design documents for testing subtests alias declarations (abandoned), type aliases, and mid-stack inlining.

The brief issue tracker discussion contemplated in the proposal process works well for small changes, even those with subtle implications requiring a design document. But it breaks down for what we might think of as large changes. Larger changes don't necessarily have longer design docs, but they tend to have larger issue tracker discussions, because more people are affected by the result. Recent examples include the discussion of the Go 1.13 error value changes (404 comments as of August 1) and of course the try builtin (798 comments).

Large Checklist

One idea raised was to leave the process for small changes unaffected but add more process for large changes. That in turn requires identifying large changes. One suggestion was to create a rubric based on a checklist of how much of the Go ecosystem a change affects. For example:

Is the change user-visible at all?
Does it require any changes to any documentation?
Are its effects confined to a single package?
Does it require changes to the language spec?
Does it require users to change existing scripts or workflows?
Does it require updating introductory materials?
And so on.

If the score is high, the proposal could require more process or at least more care. And if the proposal is accepted, the checklist answers would help plan the rollout.

Large Process

One piece of added process for large changes could be a pre-proposal stage, when the design is simply a draft being explored, not a change ready to be proposed and decided on. We consciously avoided the word “proposal” last year when we published the Go 2 draft designs last summer, to make clear that those designs were still in progress and being proposed as-is. That clear framing served everyone well, and, in retrospect, “try” was a large enough change that the new design we published last month should have been a second draft design, not a proposal with an implementation timeline. (Contrast the urgency many felt during the “try” discussion with the relative calm around last week's second draft design for generics.)

Another piece of added process for large changes could be a pre-proposal experimentation period of some kind (more on that in a future post).

And when a large change does migrate out of draft design to be formally proposed for acceptance, another piece of added process could be a different kind of discussion, or more discussions (more on that in a future post too).

I filed issue 33670 to track the idea of identifying large changes and adding more process for them.

Again, this is the third post in a series of posts thinking and brainstorming about the Go proposal process. Everything about these posts is very rough. The point of posting this series—thinking out loud instead of thinking quietly—is so that anyone who is interested can join the thinking.

The next post is about how proposal discussions might be scaled to handle large changes with many impacted users giving feedback.

Go Proposal Process: Clarity & Transparency

2019-08-07T14:00:00-04:00

[I’ve been thinking a lot recently about the Go proposal process, which is the way we propose, discuss, and decide changes to Go itself. Like nearly everything about Go, the proposal process is an experiment, so it makes sense to reflect on what we’ve learned and try to improve it. This post is the second in a series of posts about what works well and, more importantly, what we might want to change.]

In the discussions I’ve had with contributors recently, the most important takeaway for me was that there needs to be more clarity about the overall process for making decisions and also more transparency, to make it easier to observe and follow along. The introduction of the proposal process was an important step toward those concerns, but more is needed.

Documentation

One of the explicit goals we listed in 2015 was to make the process clear to new contributors, but many people are unaware that the proposal process is documented at all. It is linked on the contributor guidelines, but many people who participate in the process do not send code changes and thus have no reason to read that doc. One idea raised was to have gopherbot comment with a link whenever the proposal label is added to a GitHub issue.

The proposal process description is also missing some details. It links to a few important talks from 2015 but does not explicitly say what the relevant material is; not many people are going to watch the entire talk to find out. And in some discussions people who have read the proposal process doc have told us they didn’t even know the talks existed, despite being linked in the doc. Obviously those links are not working.

Also, we introduced a longer process, with two rounds of review, for Go 2 language changes, but it is only documented in a blog post. That blog post is linked from the proposal process doc, but having everything on one page would reach more readers.

I filed issue 33524 to make sure we update the README to stand alone.

Issue Status

Once you know about the proposal process, there is still not much clarity about the state of any particular proposal. The only labels we have are Proposal and Proposal-Accepted. (Proposals that are closed without the Proposal-Accepted label are the ones that have been declined.) We’ve already added two rounds of review for Go 2 changes, and we may want to formalize the idea of design drafts for large changes, prior to the usual proposal process (a topic for a future post). As the process gets more formalized, it would help if there was a clear answer to “where is this specific issue in the process?” Other bug trackers allow defining custom metadata fields that we could use to store this information. GitHub being GitHub, there is no direct support for any of this.

A possible solution to both of these issues—not knowing about the process and not knowing where the issue is in the process—would be for gopherbot to insert and maintain a block of text at the top of the issue description with a link to the process, information about the state of the issue, and any other information we might identify that would help people arriving at the issue learn where things stand. I filed issue 33522 for that idea.

Review Minutes

One of the explicit goals of the process was to “commit to timely evaluations of proposals” (quoting Andrew Gerrand’s talk). Initially, proposals piled up without timely evaluation. In late 2015, Andrew started a regular meeting to help make sure that core Go team members delivered on our promise of timely evaluation. The primary activity of this meeting is to make sure proposals are moving along in the process, receiving feedback, and not being forgotten.

We documented the meetings explicitly in 2018:

Proposal Review
A group of Go team members holds “proposal review meetings” approximately weekly to review pending proposals.
The principal goal of the review meeting is to make sure that proposals are receiving attention from the right people, by cc’ing relevant developers, raising important questions, pinging lapsed discussions, and generally trying to guide discussion toward agreement about the outcome. The discussion itself is expected to happen on the issue tracker, so that anyone can take part.
The proposal review meetings also identify issues where consensus has been reached and the process can be advanced to the next step (by marking the proposal accepted or declined or by asking for a design doc).

Even so, it has come up a few times in online discussions and also at contributor day that people don’t understand who the proposal review group is or what it does. More transparency here would help as well.

At about the same time as we documented the meetings (at least as best I remember), I created a “team” named @golang/proposal-review on GitHub to try to make it clear who was in the meetings. Unfortunately, I didn’t know at the time that GitHub never allows non-members of an organization to view team membership lists, even when the group is “public.” So while nearly all Go project contributors can see the list, everyone else cannot. For the record, today that group is Andy Bonventre, Brad Fitzpatrick, Robert Griesemer, Ian Lance Taylor, Rob Pike, Steve Francia, and me, although not everyone attends every meeting.

One suggestion made at contributor day was to publish minutes of the review meetings. All the actions we take are visible on the GitHub issues themselves, but there was no easy way to aggregate them and see the review work as a whole.

As of yesterday’s meeting, we have started collecting minutes in issue 33502.

Keeping the minutes in an issue enables easy cross-referencing in both directions between the issues and the minutes; seeing the links to the minutes appear in the proposal issues should help with understanding the process. The minutes also record who participated in each meeting, so that membership is clear even without visibility of the GitHub team, which we could probably now delete.

Writing those minutes yesterday forced us to be a bit more careful about explaining the reasons why we did things, which should be helpful in making the process clearer and will likely result in clarifications in the proposal process document itself, once we have a few more meetings with minutes under our belts.

Decisions

The goal of the proposal discussions is to reach clear agreement on whether to accept or decline a proposal. What happens when there is not clear agreement?

The original proposal process document (2015) said:

In Go development historically, a lack of agreement means decline. If there is disagreement about whether there is agreement, adg@ is the arbiter.

In 2016, we realized that the Go user community was large enough that most important decisions would not reach complete agreement. After discussion on issue 17129, we updated the doc to explain what happens in that case. At the same time, adg@ moved on to other work and I took on the arbiter role. The document now said:

The goal of the final discussion is to reach agreement on the next step: (1) accept or (2) decline. The discussion is expected to be resolved in a timely manner. If clear agreement cannot be reached, the arbiter (rsc@) reviews the discussion and makes the decision to accept or decline.

This version made it seem like, in the absence of clear agreement, the arbiter could make up any answer, which of course is not the case.

In the 2018 revisions that documented the review meetings, I tried to add more details that process, but in what turned out to be a differently misleading way, unfortunately conflating proposal review with arbitration of proposal decisions:

Consensus and Disagreement
The goal of the proposal process is to reach general consensus about the outcome in a timely manner.
If general consensus cannot be reached, the proposal review group decides the next step by reviewing and discussing the issue and reaching a consensus among themselves. If even consensus among the proposal review group cannot be reached (which would be exceedingly unusual), the arbiter (rsc@) reviews the discussion and decides the next step.

In retrospect, this conflation of proposal review and contended proposal decisions has been an unhelpful source of confusion about the weekly proposal review meetings, which are nearly entirely concerned with the review/triage/gardening described in the previous section. In contrast, the handling of contended decisions happens very rarely, maybe once a year. These two activities—review and deciding contended proposals—have historically been done by the same people, but that is not a fundamental requirement. It probably makes sense to separate these two activities so that they can be handled by different groups. I filed issue 33528 for this.

Again, this is the second post in a series of posts thinking and brainstorming about the Go proposal process. Everything about these posts is very rough. The point of posting this series—thinking out loud instead of thinking quietly—is so that anyone who is interested can join the thinking.

The next post is about how the proposal process should scale down to tiny changes and up to large ones.

Thinking about the Go Proposal Process

2019-08-05T12:02:00-04:00

I’ve been thinking a lot recently about the Go proposal process, which is the way we propose, discuss, and decide changes to Go itself. Like nearly everything about Go, the proposal process is an experiment, so it makes sense to reflect on what we’ve learned and try to improve it. This post is the first in a series of posts about what works well and, more importantly, what we might want to change.

This post is focused on where we are now and how we got here. Later posts will focus on specific areas where we might improve. At our annual contributor summit held at Gophercon last week, about thirty or so contributors from outside Google attended and helped us on the Go team think through many of these areas. Their suggestions figure prominently in the posts to follow, as, I hope, will yours.

(If you are curious what the contributor summit is, here’s Sam Whited’s recap of our first such summit in 2017. This year’s was pretty similar in spirit, although with different discussion topics. This year there were about 60 people in the room, roughly evenly split between members of the Go team at Google and contributors from outside Google.)

Proposal Process

When we started Go, we launched with instructions on day one detailing how to send us code changes, which are of course the core of any open source project. Around five years ago we noticed that despite the many code contributions, most change proposals were made by the Go team at Google, even when motivated and driven by feedback from the broader Go user community. One reason, we realized, was that the process for proposing changes was nearly completely undocumented. To try to address this, we introduced a formal change proposal process in 2015, now documented at golang.org/s/proposal. For more background, see Andrew Gerrand’s 2015 GopherCon talk, starting at 27m17s (only a few minutes). In that talk, Andrew said, “It’s important to note that this process is an experiment. We’re still kind of discussing exactly how that process should work.”

I talked at GopherCon this year about the experiment, simplify, ship cycle we use for just about everything. Like with other parts of Go, we’ve learned from our experiments using the proposal process and made adjustments in the past, and of course we intend to keep doing that.

The current proposal process is documented as four steps:

The author creates a brief issue clearly describing the proposal. (No need for a design document just yet.)
Discussion on the GitHub issue aims to triage the proposal into one of three buckets: accept; decline; or ask for a detailed design doc addressing an identified list of concerns.
If the previous step ended at accept/decline, we’re done. Otherwise, the author writes a design doc, which is discussed on the GitHub issue.
Once comments and design doc revisions wind down, a final discussion aims to reach a final accept or decline decision.

See the full document for details.

A Random Sample

As I write this, there are 1633 GitHub issues labeled Proposal. Of the 1187 that have been closed, 170 were accepted, about 14%.

To get a sense of the submissions, discussions, and outcomes, here are twenty selected at random (by a Perl script).

#11502 A security response policy for Go (39 comments, accepted)
#14991 add a builtin splice function for easier slice handling (7 comments)
#16844 freeze net/rpc (20 comments, accepted)
#17672 remote runtime (9 comments)
#18303 flag.failf should return an error with Cause() error (15 comments)
#18662 Struct field tags for directional Marshal/Unmarshal (6 comments)
#21360 add a build tag "test" (14 comments)
#21592 add an in-memory writer/seeker to io package (9 comments)
#22247 Add sync.Map.Len() method (5 comments)
#22918 go/doc: consts/vars should be grouped with types by their computed type (31 comments)
#23331 encoding/json: export the offset method of the Decoder (7 comments)
#23789 add uuid generator to stdlib (13 comments)
#24410 Add some way to explore packages and structs inside. (6 comments)
#25273 add token to syntax to reduce error boilerplate (2 comments)
#25518 x/vgo: allow aliases in go.mod (10 comments)
#25670 don’t include cgo with net on Unix by default (7 comments)
#26803 mime/multipart: add (*Reader).NextRawPart to avoid quoted-printable decoding (9 comments, accepted)
#26822 flag: clean up error message (20 comments, accepted)
#30886 cmd/go: allow replacing a subdirectory within a package (4 comments)
#31041 package and file organisation (7 comments)

One is significant. Most are small. A few are not well-defined. Most had fewer than ten comments. This is typical.

Process Evolution

For many people, the proposal process represents not those small changes and suggestions in the random sample but instead larger proposed changes, like type aliases (2016), monotonic time (2017), Go modules (2018), new number literals (2019), and the abandoned “try” proposal (2019).

These large changes are of course important, and in each of these we’ve learned a bit more about what works and what doesn’t for making successful changes.

The discussion of the original aliases proposal helped us understand the importance of motivating changes, like my codebase refactoring talk and article motivated type aliases. During that experience, someone introduced me to Rust’s “no new rationale” rule, which we have tried to follow when making difficult decisions since then. I reflected more about motivation for changes, using both aliases and monotonic time as examples, in my GopherCon 2017 talk kicking off Go 2.

Although there were parts of the Go modules proposal that did not go well, the general approach of spending significant time discussing the ideas before starting the formal proposal process did seem to help: at the time that we accepted the modules proposal, the GitHub conversation and reactions were overwhelmingly in favor.

One thing we learned from aliases and then from modules was the importance of having an implementation people can try and also the importance of having the changes ready to be committed at the start of a development cycle. We adopted this idea explicitly for Go 2 language changes, and it was successful for the smaller Go 1.13 changes like the new number literal syntax.

For the recent “try” proposal, we followed the evolving process, including making changes available for people to use early in a cycle, and the discussion and reactions were much more heated than we expected. We abandoned the proposal only a week before the summit, and one thing was eager to discuss with contributors was what had been different about “try” and how to continue to improve the process to make future changes smoother. (If the discussion about “try” was difficult, what will happen when we discuss generics?)

Improvement Areas

The discussions we had over six hours or so at the contributor summit surfaced at least six different areas where we might improve the proposal process specifically and the Go project’s community engagement more generally. I plan to write a post about each of these themes, but I’ll summarize them briefly here too. I’d be happy to hear suggestions for any other important areas that I’ve missed.

Clarity & Transparency. Adding clarity and transparency about how we make changes to Go—making that process easier to follow and to participate in—was the original motivation for creating the proposal process. There’s more we could do, including publishing a record of proposal decisions. (Most of the proposal review group’s time is spent not on decisions but on adding people to issues, pinging requests for more information, and so on.) Update: See the “Clarity & Transparency” post for more thoughts.

Scaling the Process. The proposal process is meant to lightweight enough to apply to very small changes, such as the recently accepted proposal to add a SubexpIndex method to regexp.Regexp. As the proposed change gets bigger, it may make sense to introduce additional process. For example, we were careful at Gophercon 2018 to publish our thoughts about error handling and generics as “design drafts” not proposals. For a large enough change, perhaps publishing iterating on design drafts should formally be the first step of the process. Update: See the “Sizing Changes” post for more thoughts.

Scaling Discussions. GitHub’s issue tracker is not particularly effective at large discussions. For large changes, we may want to investigate alternatives, and we certainly want to make sure to have more discussion long before it is time to make any decisions. For example, publishing multiple design drafts, giving talks, and publishing articles are all ways to engage helpful discussion before reaching the point in the proposal process where decisions are being made.

Prototypes & Experiments. For most non-trivial changes it is helpful to understand them by trying them out before making a decision. We do this as a matter of course for small changes: we always have at least a few months between when a change is made and the corresponding release, during which we can reconsider, adjust, or remove it. We arrange to land language changes on day 1 of a development cycle to maximize that window. But for large changes we probably need a way to make prototypes available separately, to give even more time, a bit like the vgo prototype for Go modules.

Community Representation. Andrew said in 2015 that he hoped the proposal process would “make the process more accessible to anybody who really wants to get involved in the design of Go.” We definitely get many more proposals from outside the Go team now than we did in 2015, so in that sense it has succeeded. On the other hand, we believe there are over a million Go programmers, but only 2300 different GitHub accounts have commented on proposal issues, or a quarter of one percent of users. If this were a random sample of our users, that might be fine, but we know the participation is skewed to English-speaking GitHub users who can take the time to keep up with the Go issue tracker. To make the best possible decisions we need to gather input from more sources, from a broader cross-section of the population of the Go community, by which I mean all Go users. (On a related note, anyone who describes “the Go community” as having a clear opinion about anything must have in mind a much narrower definition of that group: a million or more people can’t be painted with a single brush.)

Community Coordination. We have had mixed results attempting to engage the broader Go community in the work of developing Go. The clearest success is the technical development of the Go source code itself. Today, I count exactly 2,000 email addresses in the Go CONTRIBUTORS file, and only 310 from google.com or golang.org. The next biggest success is probably the proposal process itself: I estimate that the Go team accounts for about 15% of proposals overall and about 30% of accepted proposals. We also created a few working groups, most notably the package management committee in 2016 and the developer experience and community outreach working groups in 2017. Each one had aspects that worked well and aspects that didn’t. More recently, the golang-tools group started in 2018 is coming up on its first birthday and seems to be operating well. We should try to learn from the successful and unsuccessful aspects of all these groups and try to create new, successful, sustainable groups.

I plan to post about a new theme every day or two, starting with the ones in the previous section, until I run out of interesting thoughts.

Please remember as you read these posts that the goal here is thinking, brainstorming, looking for good ideas. There are almost certainly bad ideas in these posts too. Don’t assume that everything I mention will happen, especially not in the exact form described. Everything about these posts is very rough. The point of posting this series—thinking out loud instead of thinking quietly—is so that anyone who is interested can join the thinking.

I encourage feedback, whether in the form of comments on the posts, mail to rsc@golang.org, or your own blog posts (please leave links in the comments). Thanks for taking the time to read these and think with me.

Go Proposals

2019-08-05T12:01:00-04:00

These are the posts in the August 2019 “Go Proposals” series:

“Thinking about the Go Proposal Process” [PDF].
“Go Proposal Process: Clarity & Transparency” [PDF].
“Large Changes” [PDF].
“Scaling Discussions” [PDF].

These are Go issues filed to track (or in one case implement) ideas discussed in the series:

#33502 proposal: meeting minutes
This issue collects the minutes of each proposal review meeting. Star the issue to follow along with what happens each week.
#33522 proposal: gopherbot: add proposal process status box to each proposal issue
Discussed in “Clarity & Transparency.”
#33524 proposal: update proposal/README.md to stand alone
Discussed in “Clarity & Transparency.”
#33528 proposal: separate proposal review from contended decision-making
Discussed in “Clarity & Transparency.”
#33670 proposal: identify large changes & add more process
Discussed in “Large Changes.”
#33791 proposal: add explicit decision doc for large changes
Discussed in “Scaling Discussions.”

Transparent Logs for Skeptical Clients

2019-03-01T11:00:00-05:00

Suppose we want to maintain and publish a public, append-only log of data. Suppose also that clients are skeptical about our correct implementation and operation of the log: it might be to our advantage to leave things out of the log, or to enter something in the log today and then remove it tomorrow. How can we convince the client we are behaving?

This post is about an elegant data structure we can use to publish a log of N records with these three properties:

For any specific record R in a log of length N, we can construct a proof of length O(lg N) allowing the client to verify that R is in the log.
For any earlier log observed and remembered by the client, we can construct a proof of length O(lg N) allowing the client to verify that the earlier log is a prefix of the current log.
An auditor can efficiently iterate over the records in the log.

(In this post, “lg N” denotes the base-2 logarithm of N, reserving the word “log” to mean only “a sequence of records.”)

The Certificate Transparency project publishes TLS certificates in this kind of log. Google Chrome uses property (1) to verify that an enhanced validation certificate is recorded in a known log before accepting the certificate. Property (2) ensures that an accepted certificate cannot later disappear from the log undetected. Property (3) allows an auditor to scan the entire certificate log at any later time to detect misissued or stolen certificates. All this happens without blindly trusting that the log itself is operating correctly. Instead, the clients of the log—Chrome and any auditors—verify correct operation of the log as part of accessing it.

This post explains the design and implementation of this verifiably tamper-evident log, also called a transparent log. To start, we need some cryptographic building blocks.

Cryptographic Hashes, Authentication, and Commitments

A cryptographic hash function is a deterministic function H that maps an arbitrary-size message M to a small fixed-size output H(M), with the property that it is infeasible in practice to produce any pair of distinct messages M₁ ≠ M₂ with identical hashes H(M₁) = H(M₂). Of course, what is feasible in practice changes. In 1995, SHA-1 was a reasonable cryptographic hash function. In 2017, SHA-1 became a broken cryptographic hash function, when researchers identified and demonstrated a practical way to generate colliding messages. Today, SHA-256 is believed to be a reasonable cryptographic hash function. Eventually it too will be broken.

A (non-broken) cryptographic hash function provides a way to bootstrap a small amount of trusted data into a much larger amount of data. Suppose I want to share a very large file with you, but I am concerned that the data may not arrive intact, whether due to random corruption or a man-in-the-middle attack. I can meet you in person and hand you, written on a piece of paper, the SHA-256 hash of the file. Then, no matter what unreliable path the bits take, you can check whether you got the right ones by recomputing the SHA-256 hash of the download. If it matches, then you can be certain, assuming SHA-256 has not been broken, that you downloaded the exact bits I intended. The SHA-256 hash authenticates—that is, it proves the authenticity of—the downloaded bits, even though it is only 256 bits and the download is far larger.

We can also turn the scenario around, so that, instead of distrusting the network, you distrust me. If I tell you the SHA-256 of a file I promise to send, the SHA-256 serves as a verifiable commitment to a particular sequence of bits. I cannot later send a different bit sequence and convince you it is the file I promised.

A single hash can be an authentication or commitment of an arbitrarily large amount of data, but verification then requires hashing the entire data set. To allow selective verification of subsets of the data, we can use not just a single hash but instead a balanced binary tree of hashes, known as a Merkle tree.

Merkle Trees

A Merkle tree is constructed from N records, where N is a power of two. First, each record is hashed independently, producing N hashes. Then pairs of hashes are themselves hashed, producing N/2 new hashes. Then pairs of those hashes are hashed, to produce N/4 hashes, and so on, until a single hash remains. This diagram shows the Merkle tree of size N = 16:

The boxes across the bottom represent the 16 records. Each number in the tree denotes a single hash, with inputs connected by downward lines. We can refer to any hash by its coordinates: level L hash number K, which we will abbreviate h(L, K). At level 0, each hash’s input is a single record; at higher levels, each hash’s input is a pair of hashes from the level below.

h(0, K) = H(record K)
h(L+1, K) = H(h(L, 2 K), h(L, 2 K+1))

To prove that a particular record is contained in the tree represented by a given top-level hash (that is, to allow the client to authenticate a record, or verify a prior commitment, or both), it suffices to provide the hashes needed to recompute the overall top-level hash from the record’s hash. For example, suppose we want to prove that a certain bit string B is in fact record 9 in a tree of 16 records with top-level hash T. We can provide those bits along with the other hash inputs needed to reconstruct the overall tree hash using those bits. Specifically, the client can derive as well as we can that:

T = h(4, 0)
= H(h(3, 0), h(3, 1))
= H(h(3, 0), H(h(2, 2), h(2, 3)))
= H(h(3, 0), H(H(h(1, 4), h(1, 5)), h(2, 3)))
= H(h(3, 0), H(H(H(h(0, 8), h(0, 9)), h(1, 5)), h(2, 3)))
= H(h(3, 0), H(H(H(h(0, 8), H(record 9)), h(1, 5)), h(2, 3)))
= H(h(3, 0), H(H(H(h(0, 8), H(B)), h(1, 5)), h(2, 3)))

If we give the client the values [h(3, 0), h(0, 8), h(1, 5), h(2, 3)], the client can calculate H(B) and then combine all those hashes using the formula and check whether the result matches T. If so, the client can be cryptographically certain that B really is record 9 in the tree with top-level hash T. In effect, proving that B is a record in the Merkle tree with hash T is done by giving a verifiable computation of T with H(B) as an input.

Graphically, the proof consists of the sibling hashes (circled in blue) of nodes along the path (highlighted in yellow) from the record being proved up to the tree root.

In general, the proof that a given record is contained in the tree requires lg N hashes, one for each level below the root.

Building our log as a sequence of records hashed in a Merkle tree would give us a way to write an efficient (lg N-length) proof that a particular record is in the log. But there are two related problems to solve: our log needs to be defined for any length N, not just powers of two, and we need to be able to write an efficient proof that one log is a prefix of another.

A Merkle Tree-Structured Log

To generalize the Merkle tree to non-power-of-two sizes, we can write N as a sum of decreasing powers of two, then build complete Merkle trees of those sizes for successive sections of the input, and finally hash the at-most-lg N complete trees together to produce a single top-level hash. For example, 13 = 8 + 4 + 1:

The new hashes marked “x” combine the complete trees, building up from right to left, to produce the overall tree hash. Note that these hashes necessarily combine trees of different sizes and therefore hashes from different levels; for example, h(3, x) = H(h(2, 2), h(0, 12)).

The proof strategy for complete Merkle trees applies equally well to these incomplete trees. For example, the proof that record 9 is in the tree of size 13 is [h(3, 0), h(0, 8), h(1, 5), h(0, 12)]:

Note that h(0, 12) is included in the proof because it is the sibling of h(2, 2) in the computation of h(3, x).

We still need to be able to write an efficient proof that the log of size N with tree hash T is a prefix of the log of size N′ (> N) with tree hash T′. Earlier, proving that B is a record in the Merkle tree with hash T was done by giving a verifiable computation of T using H(B) as an input. To prove that the log with tree hash T is included in the log with tree hash T′, we can follow the same idea: give verifiable computations of T and T′, in which all the inputs to the computation of T are also inputs to the computation of T′. For example, consider the trees of size 7 and 13:

In the diagram, the “x” nodes complete the tree of size 13 with hash T₁₃, while the “y” nodes complete the tree of size 7 with hash T₇. To prove that T₇’s leaves are included in T₁₃, we first give the computation of T₇ in terms of complete subtrees (circled in blue):

T₇ = H(h(2, 0), H(h(1, 2), h(0, 6)))

Then we give the computation of T₁₃, expanding hashes as needed to expose the same subtrees. Doing so exposes sibling subtrees (circled in red):

T₁₃ = H(h(3, 0), H(h(2, 2), h(0, 12)))
= H(H(h(2, 0), h(2, 1)), H(h(2, 2), h(0, 12)))
= H(H(h(2, 0), H(h(1, 2), h(1, 3))), H(h(2, 2), h(0, 12)))
= H(H(h(2, 0), H(h(1, 2), H(h(0, 6), h(0, 7)))), H(h(2, 2), h(0, 12)))

Assuming the client knows the trees have sizes 7 and 13, it can derive the required decomposition itself. We need only supply the hashes [h(2, 0), h(1, 2), h(0, 6), h(0, 7), h(2, 2), h(0, 12)]. The client recalculates the T₇ and T₁₃ implied by the hashes and checks that they match the originals.

Note that these proofs only use hashes for completed subtrees—that is, numbered hashes, never the “x” or “y” hashes that combine differently-sized subtrees. The numbered hashes are permanent, in the sense that once such a hash appears in a tree of a given size, that same hash will appear in all trees of larger sizes. In contrast, the “x” and “y” hashes are ephemeral—computed for a single tree and never seen again. The hashes common to the decomposition of two different-sized trees therefore must always be permanent hashes. The decomposition of the larger tree could make use of ephemeral hashes for the exposed siblings, but we can easily use only permanent hashes instead. In the example above, the reconstruction of T₁₃ from the parts of T₇ uses h(2, 2) and h(0, 12) instead of assuming access to T₁₃’s h(3, x). Avoiding the ephemeral hashes extends the maximum record proof size from lg N hashes to 2 lg N hashes and the maximum tree proof size from 2 lg N hashes to 3 lg N hashes. Note that most top-level hashes, including T₇ and T₁₃, are themselves ephemeral hashes, requiring up to lg N permanent hashes to compute. The exceptions are the power-of-two-sized trees T₁, T₂, T₄, T₈, and so on.

Storing a Log

Storing the log requires only a few append-only files. The first file holds the log record data, concatenated. The second file is an index of the first, holding a sequence of int64 values giving the start offset of each record in the first file. This index allows efficient random access to any record by its record number. While we could recompute any hash tree from the record data alone, doing so would require N–1 hash operations for a tree of size N. Efficient generation of proofs therefore requires precomputing and storing the hash trees in some more accessible form.

As we noted in the previous section, there is significant commonality between trees. In particular, the latest hash tree includes all the permanent hashes from all earlier hash trees, so it is enough to store “only” the latest hash tree. A straightforward way to do this is to maintain lg N append-only files, each holding the sequence of hashes at one level of the tree. Because hashes are fixed size, any particular hash can be read efficiently by reading from the file at the appropriate offset.

To write a new log record, we must append the record data to the data file, append the offset of that data to the index file, and append the hash of the data to the level-0 hash file. Then, if we completed a pair of hashes in the level-0 hash file, we append the hash of the pair to the level-1 hash file; if that completed a pair of hashes in the level-1 hash file, we append the hash of that pair to the level-2 hash file; and so on up the tree. Each log record write will append a hash to at least one and at most lg N hash files, with an average of just under two new hashes per write. (A binary tree with N leaves has N–1 interior nodes.)

It is also possible to interlace lg N append-only hash files into a single append-only file, so that the log can be stored in only three files: record data, record index, and hashes. See Appendix A for details. Another possibility is to store the log in a pair of database tables, one for record data and one for hashes (the database can provide the record index itself).

Whether in files or in database tables, the stored form of the log is append-only, so cached data never goes stale, making it trivial to have parallel, read-only replicas of a log. In contrast, writing to the log is inherently centralized, requiring a dense sequence numbering of all records (and in many cases also duplicate suppression). An implementation using the two-table database representation can delegate both replication and coordination of writes to the underlying database, especially if the underlying database is globally-replicated and consistent, like Google Cloud Spanner or CockroachDB.

It is of course not enough just to store the log. We must also make it available to clients.

Serving a Log

Remember that each client consuming the log is skeptical about the log’s correct operation. The log server must make it easy for the client to verify two things: first, that any particular record is in the log, and second, that the current log is an append-only extension of a previously-observed earlier log.

To be useful, the log server must also make it easy to find a record given some kind of lookup key, and it must allow an auditor to iterate over the entire log looking for entries that don’t belong.

To do all this, the log server must answer five queries:

Latest() returns the current log size and top-level hash, cryptographically signed by the server for non-repudiation.
RecordProof(R, N) returns the proof that record R is contained in the tree of size N.
TreeProof(N, N′) returns the proof that the tree of size N is a prefix of the tree of size N′.
Lookup(K) returns the record index R matching lookup key K, if any.
Data(R) returns the data associated with record R.

Verifying a Log

The client uses the first three queries to maintain a cached copy of the most recent log it has observed and make sure that the server never removes anything from an observed log. To do this, the client caches the most recently observed log size N and top-level hash T. Then, before accepting data bits B as record number R, the client verifies that R is included in that log. If necessary (that is, if R ≥ its cached N), the client updates its cached N, T to those of the latest log, but only after verifying that the latest log includes everything from the current cached log. In pseudocode:

validate(bits B as record R):
    if R ≥ cached.N:
        N, T = server.Latest()
        if server.TreeProof(cached.N, N) cannot be verified:
            fail loudly
        cached.N, cached.T = N, T
    if server.RecordProof(R, cached.N) cannot be verified using B:
        fail loudly
    accept B as record R

The client’s proof verification ensures that the log server is behaving correctly, at least as observed by the client. If a devious server can distinguish individual clients, it can still serve different logs to different clients, so that a victim client sees invalid entries never exposed to other clients or auditors. But if the server does lie to a victim, the fact that the victim requires any later log to include what it has seen before means the server must keep up the lie, forever serving an alternate log containing the lie. This makes eventual detection more likely. For example, if the victim ever arrived through a proxy or compared its cached log against another client, or if the server ever made a mistake about which clients to lie to, the inconsistency would be readily exposed. Requiring the server to sign the Latest() response makes it impossible for the server to disavow the inconsistency, except by claiming to have been compromised entirely.

The client-side checks are a little bit like how a Git client maintains its own cached copy of a remote repository and then, before accepting an update during git pull, verifies that the remote repository includes all local commits. But the transparent log client only needs to download lg N hashes for the verification, while Git downloads all cached.N – N new data records, and more generally, the transparent log client can selectively read and authenticate individual entries from the log, without being required to download and store a full copy of the entire log.

Tiling a Log

As described above, storing the log requires simple, append-only storage linear in the total log size, and serving or accessing the log requires network traffic only logarithmic in the total log size. This would be a completely reasonable place to stop (and is where Certificate Transparency as defined in RFC 6962 stops). However, one useful optimization can both cut the hash storage in half and make the network traffic more cache-friendly, with only a minor increase in implementation complexity. That optimization is based on splitting the hash tree into tiles, like Google Maps splits the globe into tiles.

A binary tree can be split into tiles of fixed height H and width 2^H. For example, here is the permanent hash tree for the log with 27 records, split into tiles of height 2:

We can assign each tile a two-dimensional coordinate, analogous to the hash coordinates we’ve been using: tile(L, K) denotes the tile at tile level L (hash levels H·L up to H·(L+1)), Kth from the left. For any given log size, the rightmost tile at each level may not yet be complete: the bottom row of hashes may contain only W < 2^H hashes. In that case we will write tile(L, K)/W. (When the tile is complete, the “/W” is omitted, understood to be 2^H.)

Storing Tiles

Only the bottom row of each tile needs to be stored: the upper rows can be recomputed by hashing lower ones. In our example, a tile of height two stores 4 hashes instead of 6, a 33% storage reduction. For tiles of greater heights, the storage reduction asymptotically approaches 50%. The cost is that reading a hash that has been optimized away may require reading as much as half a tile, increasing I/O requirements. For a real system, height four seems like a reasonable balance between storage costs and increased I/O overhead. It stores 16 hashes instead of 30—a 47% storage reduction—and (assuming SHA-256) a single 16-hash tile is only 512 bytes (a single disk sector!).

The file storage described earlier maintained lg N hash files, one for each level. Using tiled storage, we only write the hash files for levels that are a multiple of the tile height. For tiles of height 4, we’d only write the hash files for levels 0, 4, 8, 12, 16, and so on. When we need a hash at another level, we can read its tile and recompute the hash.

Serving Tiles

The proof-serving requests RecordProof(R, N) and TreeProof(N, N′) are not particularly cache-friendly. For example, although RecordProof(R, N) often shares many hashes with both RecordProof(R+1, N) and RecordProof(R, N+1), the three are distinct requests that must be cached independently.

A more cache-friendly approach would be to replace RecordProof and TreeProof by a general request Hash(L, K), serving a single permanent hash. The client can easily compute which specific hashes it needs, and there are many fewer individual hashes than whole proofs (2 N vs N²/2), which will help the cache hit rate. Unfortunately, switching to Hash requests is inefficient: obtaining a record proof used to take one request and now takes up to 2 lg N requests, while tree proofs take up to 3 lg N requests. Also, each request delivers only a single hash (32 bytes): the request overhead is likely significantly larger than the payload.

We can stay cache-friendly while reducing the number of requests and the relative request overhead, at a small cost in bandwidth, by adding a request Tile(L, K) that returns the requested tile. The client can request the tiles it needs for a given proof, and it can cache tiles, especially those higher in the tree, for use in future proofs.

For a real system using SHA-256, a tile of height 8 would be 8 kB. A typical proof in a large log of, say, 100 million records would require only three complete tiles, or 24 kB downloaded, plus one incomplete tile (192 bytes) for the top of the tree. And tiles of height 8 can be served directly from stored tiles of height 4 (the size suggested in the previous section). Another reasonable choice would be to both store and serve tiles of height 6 (2 kB each) or 7 (4 kB each).

If there are caches in front of the server, each differently-sized partial tile must be given a different name, so that a client that needs a larger partial tile is not given a stale smaller one. Even though the tile height is conceptually constant for a given system, it is probably helpful to be explicit about the tile height in the request, so that a system can transition from one fixed tile height to another without ambiguity. For example, in a simple GET-based HTTP API, we could use /tile/H/L/K to name a complete tile and /tile/H/L/K.W to name a partial tile with only W hashes.

Authenticating Tiles

One potential problem with downloading and caching tiles is not being sure that they are correct. An attacker might be able to modify downloaded tiles and cause proofs to fail unexpectedly. We can avoid this problem by authenticating the tiles against the signed top-level tree hash after downloading them. Specifically, if we have a signed top-level tree hash T, we first download the at most (lg N)/H tiles storing the hashes for the complete subtrees that make up T. In the diagram of T₂₇ earlier, that would be tile(2, 0)/1, tile(1, 1)/2, and tile(0, 6)/3. Computing T will use every hash in these tiles; if we get the right T, the hashes are all correct. These tiles make up the top and right sides of the tile tree for the given hash tree, and now we know they are correct. To authenticate any other tile, we first authenticate its parent tile (the topmost parents are all authenticated already) and then check that the result of hashing all the hashes in the tile produces the corresponding entry in the parent tile. Using the T₂₇ example again, given a downloaded tile purporting to be tile(0, 1), we can compute

h(2, 1) = H(H(h(0, 4), h(0, 5)), H(h(0, 6), h(0, 7)))

and check whether that value matches the h(2, 1) recorded directly in an already-authenticated tile(1, 0). If so, that authenticates the downloaded tile.

Summary

Putting this all together, we’ve seen how to publish a transparent (tamper-evident, immutable, append-only) log with the following properties:

A client can verify any particular record using O(lg N) downloaded bytes.
A client can verify any new log contains an older log using O(lg N) downloaded bytes.
For even a large log, these verifications can be done in 3 RPCs of about 8 kB each.
The RPCs used for verification can be made to proxy and cache well, whether for network efficiency or possibly for privacy.
Auditors can iterate over the entire log looking for bad entries.
Writing N records defines a sequence of N hash trees, in which the nth tree contains 2 n – 1 hashes, a total of N² hashes. But instead of needing to store N² hashes, the entire sequence can be compacted into at most 2 N hashes, with at most lg N reads required to reconstruct a specific hash from a specific tree.
Those 2 N hashes can themselves be compacted down to 1.06 N hashes, at a cost of potentially reading 8 adjacent hashes to reconstruct any one hash from the 2 N.

Overall, this structure makes the log server itself essentially untrusted. It can’t remove an observed record without detection. It can’t lie to one client without keeping the client on an alternate timeline forever, making detection easy by comparing against another client. The log itself is also easily proxied and cached, so that even if the main server disappeared, replicas could keep serving the cached log. Finally, auditors can check the log for entries that should not be there, so that the actual content of the log can be verified asynchronously from its use.

Appendix A: Postorder Storage Layout

The file-based storage described earlier held the permanent hash tree in lg N append-only files, one for each level of the tree. The hash h(L, K) would be stored in the Lth hash file at offset K · HashSize

Crosby and Wallach pointed out that it is easy to merge the lg N hash tree levels into a single, append-only hash file by using the postorder numbering of the binary tree, in which a parent hash is stored immediately after its rightmost child. For example, the permanent hash tree after writing N = 13 records is laid out like:

In the diagram, each hash is numbered and aligned horizontally according to its location in the interlaced file.

The postorder numbering makes the hash file append-only: each new record completes between 1 and lg N new hashes (on average 2), which are simply appended to the file, lower levels first.

Reading a specific hash from the file can still be done with a single read at a computable offset, but the calculation is no longer completely trivial. Hashes at level 0 are placed by adding in gaps for completed higher-level hashes, and a hash at any higher level immediately follows its right child hash:

seq(0, K) = K + K/2 + K/4 + K/8 + ...
seq(L, K) = seq(L–1, 2 K + 1) + 1 = seq(0, 2^L (K+1) – 1) + L

The interlaced layout also improves locality of access. Reading a proof typically means reading one hash from each level, all clustered around a particular leaf in the tree. If each tree level is stored separately, each hash is in a different file and there is no possibility of I/O overlap. But when the tree is stored in interlaced form, the accesses at the bottom levels will all be near each other, making it possible to fetch many of the needed hashes with a single disk read.

Appendix B: Inorder Storage Layout

A different way to interlace the lg N hash files would be to use an inorder tree numbering, in which each parent hash is stored between its left and right subtrees:

This storage order does not correspond to append-only writes to the file, but each hash entry is still write-once. For example, with 13 records written, as in the diagram, hashes have been stored at indexes 0–14, 16–22 and 24, but not yet at indexes 15 and 23, which will eventually hold h(4, 0) and h(3, 1). In effect, the space for a parent hash is reserved when its left subtree has been completed, but it can only be filled in later, once its right subtree has also been completed.

Although the file is no longer append-only, the inorder numbering has other useful properties. First, the offset math is simpler:

seq(0, K) = 2 K
seq(L, K) = 2^L+1 K + 2^L – 1

Second, locality is improved. Now each parent hash sits exactly in the middle of its child subtrees, instead of on the far right side.

Appendix C: Tile Storage Layout

Storing the hash tree in lg N separate levels made converting to tile storage very simple: just don’t write (H–1)/H of the files. The simplest tile implementation is probably to use separate files, but it is worth examining what it would take to convert an interlaced hash storage file to tile storage. It’s not as straightforward as omitting a few files. It’s not enough to just omit the hashes at certain levels: we also want each tile to appear contiguously in the file. For example, for tiles of height 2, the first tile at tile level 1 stores hashes h(2, 0)–h(2, 3), but neither the postorder nor inorder interlacing would place those four hashes next to each other.

Instead, we must simply define that tiles are stored contiguously and then decide a linear tile layout order. For tiles of height 2, the tiles form a 4-ary tree, and in general, the tiles form a 2^H-ary tree. We could use a postorder layout, as in Appendix A:

seq(0, K) = K + K/2^H + K/2^2H + K/2^3H + ...
seq(L, K) = seq(L–1, 2^H K + 2^H – 1) + 1 = seq(0, 2^H·L (K+1) – 1) + L

The postorder tile sequence places a parent tile immediately after its rightmost child tile, but the parent tile begins to be written after the leftmost child tile is completed. This means writing increasingly far ahead of the filled part of the hash file. For example, with tiles of height 2, the first hash of tile(2, 0) (postorder index 20) is written after filling tile(1, 0) (postorder index 4):

The hash file catches up—there are no tiles written after index 20 until the hash file fills in entirely behind it—but then jumps ahead again—finishing tile 20 triggers writing the first hash into tile 84. In general only the first 1/2^H or so of the hash file is guaranteed to be densely packed. Most file systems efficiently support files with large holes, but not all do: we may want to use a different tile layout to avoid arbitrarily large holes.

Placing a parent tile immediately after its leftmost child’s completed subtree would eliminate all holes (other than incomplete tiles) and would seem to correspond to the inorder layout of Appendix B:

But while the tree structure is regular, the numbering is not. Instead, the offset math is more like the postorder traversal. A simpler but far less obvious alternative is to vary the exact placement of the parent tiles relative to the subtrees:

seq(L, K) = ((K + B – 2)/(B – 1))_B || (1)_B^L

Here, (X)_B means X written as a base-B number, || denotes concatenation of base-B numbers, (1)_B^L means the base-B digit 1 repeated L times, and the base is B = 2^H.

This encoding generalizes the inorder binary-tree traversal (H = 1, B = 2), preserving its regular offset math at the cost of losing its regular tree structure. Since we only care about doing the math, not exactly what the tree looks like, this is probably a reasonable tradeoff. For more about this surprising ordering, see my blog post, “An Encoded Tree Traversal.”

An Encoded Tree Traversal

2019-02-25T12:00:00-05:00

Every basic data structures course identifies three ways to traverse a binary tree. It’s not entirely clear how to generalize them to k-ary trees, and I recently noticed an unexpected ordering that I’d like to know more about. If you know of references to this ordering, please leave a comment or email me (rsc@swtch.com).

Binary Tree Orderings

First a refresher about binary-tree orderings to set up an analogy to k-ary trees.

Preorder visits a node before its left and right subtrees:

Inorder visits a node between its left and right subtrees:

Postorder visits a node after its left and right subtrees:

Each picture shows the same 16-leaf, 31-node binary tree, with the nodes numbered and also placed horizontally using the order visited in the given traversal.

It was observed long ago that one way to represent a tree in linear storage is to record the nodes in a fixed order (such as one of these), along with a separate array giving the number of children of each node. In the pictures, the trees are complete, balanced trees, so the number of children of each node can be derived from the number of total leaves. (For more, see Knuth Volume 1 §2.3.1; for references, see §2.3.1.6, and §2.6.)

It is convenient to refer to nodes in a tree by a two-dimensional coordinate (l, n), consisting of the level of the node (with 0 being the leaves) and its sequence number at that level. For example, the root of the 16-node tree has coordinate (4, 0), while the leaves are (0, 0) through (0, 15).

When storing a tree using a linearized ordering such as these, it is often necessary to be able to convert a two-dimensional coordinate to its index in the linear ordering. For example, the right child of the root—node (3, 1)—has number 16, 23, and 29 in the three different orderings.

The linearized pre-ordering of (l, n) is given by:

seq(L, 0) = 0 (L is height of tree)
seq(l, n) = seq(l+1, n/2) + 1 (n even)
seq(l, n) = seq(l+1, n/2) + 2^l+1 (n odd)

This ordering is awkward because it changes depending on the height of the tree.

The linearized post-ordering of (l, n) is given by:

seq(0, n) = n + n/2 + n/4 + n/8 + ...
seq(l, n) = seq(l–1, 2 n + 1) + 1 = seq(0, 2^l n + 2^l – 1) + l

This ordering is independent of the height of the tree, but the leaf numbering is still a little complex.

The linearized in-ordering is much more regular. It’s clear just looking at it that seq(0, n) = 2 n, and in fact a single equation applies to all levels:

seq(l, n) = 2^l+1 n + 2^l – 1

If you need to linearize a complete binary tree, using the in-order traversal has the simplest math.

k-ary Tree Orderings

The three binary orderings correspond to visiting the node after 0, 1, or 2 of its child subtrees. To generalize to k-ary trees, we can visit the node after any number of subtrees from 0 to k, producing k+1 orderings. For example, for k = 3, here are the four generalized orderings of a 27-leaf, 39-node 3-ary tree:

Preorder (inorder-0):

Inorder-1:

Inorder-2:

Postorder (inorder-3):

Just looking at the leaves of each, none of them has a nice simple form with regular gaps like the seq(0, n) = 2 n of in-order traversal for binary trees. Instead, both the possible “in-order” traversals end up with equations more like the post-order traversal. What happened? Where did the nice, regular pattern go?

An Unexpected Ordering

In a binary tree, the in-order numbering has the property that after the first leaf, one new parent (non-leaf) node is introduced before each additional one leaf. This works out nicely because the number of parent nodes in a binary tree of N leaves is N–1. The number of parents nodes in a k-ary tree of N leaves is (N–1)/(k–1), so we could try to build a nicer numbering by, after the first leaf, introducing one new parent node before each additional k–1 leaf nodes. That is, the leaves would be numbered by

seq(0, n) = n + (n+k–2)/(k–1),

which gives this leaf structure:

But how do we fill in the gaps? The first three triples—0, 2, 3 and 5, 6, 8 and 9, 11, 12—clearly get nodes 1, 4, 7, and 10 as their three parents and one grandparent, but which is the grandparent? The binary in-order traversal was very self-similar, so let’s try the same thing here: after the first node, reserve one node for higher levels before each k–1 nodes at this level. That is, the parents are 1, 7, 10, and the grandparent is 4.

Applying this process throughout the tree, we end up with this traversal order (inorder-G, for gap-induced):

For contrast, here is the ordering from the previous section that visited each node after its first subtree (inorder-1):

The inorder-1 traversal has a regular tree structure but irregular numbering. In contrast, the inorder-G traversal has an irregular tree structure but very regular numbering that generalizes the binary inorder numbering:

seq(l, n) = k^l (n+k–2)/(k–1) + k^l-1 + k^l-2 + ... + k⁰

For a binary tree, inorder-1 and inorder-G are the same: the traversal has both a regular tree structure and a regular numbering. But for k-ary trees, it seems you can pick only one.

The regularity of the numbering is easiest to see in base k. For example, here is the binary inorder traversal with binary numbering:

The bottom row uses numbers ending in 0; the next row up uses numbers ending in 01; then 011; and so on.

For the 3-ary tree, it is the inorder-G traversal (not inorder-1 or inorder-2) that produces an equivalent pattern:

The bottom row uses numbers ending in 0 or 2; the next row up uses numbers ending in 01 or 21; then 011 or 211; and so on. The general rule is that

seq(l, n) = ((n+k–2)/(k–1))_k || (1)_k^l

where (x)_k means x written as a base-k number, || denotes concatenation of base-k numbers, and (1)_k^l means the base-k digit 1 repeated l times.

Through a roundabout way, then, we’ve ended up with a tree traversal that’s really just a nice base-k encoding. There must be existing uses of this encoding, but I’ve been unable to find any or even determine what its name is.

Our Software Dependency Problem

2019-01-23T11:00:00-05:00

For decades, discussion of software reuse was far more common than actual software reuse. Today, the situation is reversed: developers reuse software written by others every day, in the form of software dependencies, and the situation goes mostly unexamined.

My own background includes a decade of working with Google’s internal source code system, which treats software dependencies as a first-class concept,¹ and also developing support for dependencies in the Go programming language.²

Software dependencies carry with them serious risks that are too often overlooked. The shift to easy, fine-grained software reuse has happened so quickly that we do not yet understand the best practices for choosing and using dependencies effectively, or even for deciding when they are appropriate and when not. My purpose in writing this article is to raise awareness of the risks and encourage more investigation of solutions.

What is a dependency?

In today’s software development world, a dependency is additional code that you want to call from your program. Adding a dependency avoids repeating work already done: designing, writing, testing, debugging, and maintaining a specific unit of code. In this article we’ll call that unit of code a package; some systems use terms like library or module instead of package.

Taking on externally-written dependencies is an old practice: most programmers have at one point in their careers had to go through the steps of manually downloading and installing a required library, like C’s PCRE or zlib, or C++’s Boost or Qt, or Java’s JodaTime or JUnit. These packages contain high-quality, debugged code that required significant expertise to develop. For a program that needs the functionality provided by one of these packages, the tedious work of manually downloading, installing, and updating the package is easier than the work of redeveloping that functionality from scratch. But the high fixed costs of reuse mean that manually-reused packages tend to be big: a tiny package would be easier to reimplement.

A dependency manager (sometimes called a package manager) automates the downloading and installation of dependency packages. As dependency managers make individual packages easier to download and install, the lower fixed costs make smaller packages economical to publish and reuse.

For example, the Node.js dependency manager NPM provides access to over 750,000 packages. One of them, escape-string-regexp, provides a single function that escapes regular expression operators in its input. The entire implementation is:

var matchOperatorsRe = /[|\\{}()[\]^$+*?.]/g;

module.exports = function (str) {
	if (typeof str !== 'string') {
		throw new TypeError('Expected a string');
	}
	return str.replace(matchOperatorsRe, '\\$&');
};

Before dependency managers, publishing an eight-line code library would have been unthinkable: too much overhead for too little benefit. But NPM has driven the overhead approximately to zero, with the result that nearly-trivial functionality can be packaged and reused. In late January 2019, the escape-string-regexp package is explicitly depended upon by almost a thousand other NPM packages, not to mention all the packages developers write for their own use and don’t share.

Dependency managers now exist for essentially every programming language. Maven Central (Java), Nuget (.NET), Packagist (PHP), PyPI (Python), and RubyGems (Ruby) each host over 100,000 packages. The arrival of this kind of fine-grained, widespread software reuse is one of the most consequential shifts in software development over the past two decades. And if we’re not more careful, it will lead to serious problems.

What could go wrong?

A package, for this discussion, is code you download from the internet. Adding a package as a dependency outsources the work of developing that code—designing, writing, testing, debugging, and maintaining—to someone else on the internet, someone you often don’t know. By using that code, you are exposing your own program to all the failures and flaws in the dependency. Your program’s execution now literally depends on code downloaded from this stranger on the internet. Presented this way, it sounds incredibly unsafe. Why would anyone do this?

We do this because it’s easy, because it seems to work, because everyone else is doing it too, and, most importantly, because it seems like a natural continuation of age-old established practice. But there are important differences we’re ignoring.

Decades ago, most developers already trusted others to write software they depended on, such as operating systems and compilers. That software was bought from known sources, often with some kind of support agreement. There was still a potential for bugs or outright mischief,³ but at least we knew who we were dealing with and usually had commercial or legal recourses available.

The phenomenon of open-source software, distributed at no cost over the internet, has displaced many of those earlier software purchases. When reuse was difficult, there were fewer projects publishing reusable code packages. Even though their licenses typically disclaimed, among other things, any “implied warranties of merchantability and fitness for a particular purpose,” the projects built up well-known reputations that often factored heavily into people’s decisions about which to use. The commercial and legal support for trusting our software sources was replaced by reputational support. Many common early packages still enjoy good reputations: consider BLAS (published 1979), Netlib (1987), libjpeg (1991), LAPACK (1992), HP STL (1994), and zlib (1995).

Dependency managers have scaled this open-source code reuse model down: now, developers can share code at the granularity of individual functions of tens of lines. This is a major technical accomplishment. There are myriad available packages, and writing code can involve such a large number of them, but the commercial, legal, and reputational support mechanisms for trusting the code have not carried over. We are trusting more code with less justification for doing so.

The cost of adopting a bad dependency can be viewed as the sum, over all possible bad outcomes, of the cost of each bad outcome multiplied by its probability of happening (risk).

The context where a dependency will be used determines the cost of a bad outcome. At one end of the spectrum is a personal hobby project, where the cost of most bad outcomes is near zero: you’re just having fun, bugs have no real impact other than wasting some time, and even debugging them can be fun. So the risk probability almost doesn’t matter: it’s being multiplied by zero. At the other end of the spectrum is production software that must be maintained for years. Here, the cost of a bug in a dependency can be very high: servers may go down, sensitive data may be divulged, customers may be harmed, companies may fail. High failure costs make it much more important to estimate and then reduce any risk of a serious failure.

No matter what the expected cost, experiences with larger dependencies suggest some approaches for estimating and reducing the risks of adding a software dependency. It is likely that better tooling is needed to help reduce the costs of these approaches, much as dependency managers have focused to date on reducing the costs of download and installation.

Inspect the dependency

You would not hire a software developer you’ve never heard of and know nothing about. You would learn more about them first: check references, conduct a job interview, run background checks, and so on. Before you depend on a package you found on the internet, it is similarly prudent to learn a bit about it first.

A basic inspection can give you a sense of how likely you are to run into problems trying to use this code. If the inspection reveals likely minor problems, you can take steps to prepare for or maybe avoid them. If the inspection reveals major problems, it may be best not to use the package: maybe you’ll find a more suitable one, or maybe you need to develop one yourself. Remember that open-source packages are published by their authors in the hope that they will be useful but with no guarantee of usability or support. In the middle of a production outage, you’ll be the one debugging it. As the original GNU General Public License warned, “The entire risk as to the quality and performance of the program is with you. Should the program prove defective, you assume the cost of all necessary servicing, repair or correction.”⁴

The rest of this section outlines some considerations when inspecting a package and deciding whether to depend on it.

Design

Is package’s documentation clear? Does the API have a clear design? If the authors can explain the package’s API and its design well to you, the user, in the documentation, that increases the likelihood they have explained the implementation well to the computer, in the source code. Writing code for a clear, well-designed API is also easier, faster, and hopefully less error-prone. Have the authors documented what they expect from client code in order to make future upgrades compatible? (Examples include the C++⁵ and Go⁶ compatibility documents.)

Code Quality

Is the code well-written? Read some of it. Does it look like the authors have been careful, conscientious, and consistent? Does it look like code you’d want to debug? You may need to.

Develop your own systematic ways to check code quality. For example, something as simple as compiling a C or C++ program with important compiler warnings enabled (for example, -Wall) can give you a sense of how seriously the developers work to avoid various undefined behaviors. Recent languages like Go, Rust, and Swift use an unsafe keyword to mark code that violates the type system; look to see how much unsafe code there is. More advanced semantic tools like Infer⁷ or SpotBugs⁸ are helpful too. Linters are less helpful: you should ignore rote suggestions about topics like brace style and focus instead on semantic problems.

Keep an open mind to development practices you may not be familiar with. For example, the SQLite library ships as a single 200,000-line C source file and a single 11,000-line header, the “amalgamation.” The sheer size of these files should raise an initial red flag, but closer investigation would turn up the actual development source code, a traditional file tree with over a hundred C source files, tests, and support scripts. It turns out that the single-file distribution is built automatically from the original sources and is easier for end users, especially those without dependency managers. (The compiled code also runs faster, because the compiler can see more optimization opportunities.)

Testing

Does the code have tests? Can you run them? Do they pass? Tests establish that the code’s basic functionality is correct, and they signal that the developer is serious about keeping it correct. For example, the SQLite development tree has an incredibly thorough test suite with over 30,000 individual test cases as well as developer documentation explaining the testing strategy.⁹ On the other hand, if there are few tests or no tests, or if the tests fail, that’s a serious red flag: future changes to the package are likely to introduce regressions that could easily have been caught. If you insist on tests in code you write yourself (you do, right?), you should insist on tests in code you outsource to others.

Assuming the tests exist, run, and pass, you can gather more information by running them with run-time instrumentation like code coverage analysis, race detection,¹⁰ memory allocation checking, and memory leak detection.

Debugging

Find the package’s issue tracker. Are there many open bug reports? How long have they been open? Are there many fixed bugs? Have any bugs been fixed recently? If you see lots of open issues about what look like real bugs, especially if they have been open for a long time, that’s not a good sign. On the other hand, if the closed issues show that bugs are rarely found and promptly fixed, that’s great.

Maintenance

Look at the package’s commit history. How long has the code been actively maintained? Is it actively maintained now? Packages that have been actively maintained for an extended amount of time are more likely to continue to be maintained. How many people work on the package? Many packages are personal projects that developers create and share for fun in their spare time. Others are the result of thousands of hours of work by a group of paid developers. In general, the latter kind of package is more likely to have prompt bug fixes, steady improvements, and general upkeep.

On the other hand, some code really is “done.” For example, NPM’s escape-string-regexp, shown earlier, may never need to be modified again.

Usage

Do many other packages depend on this code? Dependency managers can often provide statistics about usage, or you can use a web search to estimate how often others write about using the package. More users should at least mean more people for whom the code works well enough, along with faster detection of new bugs. Widespread usage is also a hedge against the question of continued maintenance: if a widely-used package loses its maintainer, an interested user is likely to step forward.

For example, libraries like PCRE or Boost or JUnit are incredibly widely used. That makes it more likely—although certainly not guaranteed—that bugs you might otherwise run into have already been fixed, because others ran into them first.

Security

Will you be processing untrusted inputs with the package? If so, does it seem to be robust against malicious inputs? Does it have a history of security problems listed in the National Vulnerability Database (NVD)?¹¹

For example, when Jeff Dean and I started work on Google Code Search¹²—grep over public source code—in 2006, the popular PCRE regular expression library seemed like an obvious choice. In an early discussion with Google’s security team, however, we learned that PCRE had a history of problems like buffer overflows, especially in its parser. We could have learned the same by searching for PCRE in the NVD. That discovery didn’t immediately cause us to abandon PCRE, but it did make us think more carefully about testing and isolation.

Licensing

Is the code properly licensed? Does it have a license at all? Is the license acceptable for your project or company? A surprising fraction of projects on GitHub have no clear license. Your project or company may impose further restrictions on the allowed licenses of dependencies. For example, Google disallows the use of code licensed under AGPL-like licenses (too onerous) as well as WTFPL-like licenses (too vague).¹³

Dependencies

Does the code have dependencies of its own? Flaws in indirect dependencies are just as bad for your program as flaws in direct dependencies. Dependency managers can list all the transitive dependencies of a given package, and each of them should ideally be inspected as described in this section. A package with many dependencies incurs additional inspection work, because those same dependencies incur additional risk that needs to be evaluated.

Many developers have never looked at the full list of transitive dependencies of their code and don’t know what they depend on. For example, in March 2016 the NPM user community discovered that many popular projects—including Babel, Ember, and React—all depended indirectly on a tiny package called left-pad, consisting of a single 8-line function body. They discovered this when the author of left-pad deleted that package from NPM, inadvertently breaking most Node.js users’ builds.¹⁴ And left-pad is hardly exceptional in this regard. For example, 30% of the 750,000 packages published on NPM depend—at least indirectly—on escape-string-regexp. Adapting Leslie Lamport’s observation about distributed systems, a dependency manager can easily create a situation in which the failure of a package you didn’t even know existed can render your own code unusable.

Test the dependency

The inspection process should include running a package’s own tests. If the package passes the inspection and you decide to make your project depend on it, the next step should be to write new tests focused on the functionality needed by your application. These tests often start out as short standalone programs written to make sure you can understand the package’s API and that it does what you think it does. (If you can’t or it doesn’t, turn back now!) It is worth then taking the extra effort to turn those programs into automated tests that can be run against newer versions of the package. If you find a bug and have a potential fix, you’ll want to be able to rerun these project-specific tests easily, to make sure that the fix did not break anything else.

It is especially worth exercising the likely problem areas identified by the basic inspection. For Code Search, we knew from past experience that PCRE sometimes took a long time to execute certain regular expression searches. Our initial plan was to have separate thread pools for “simple” and “complicated” regular expression searches. One of the first tests we ran was a benchmark, comparing pcregrep with a few other grep implementations. When we found that, for one basic test case, pcregrep was 70X slower than the fastest grep available, we started to rethink our plan to use PCRE. Even though we eventually dropped PCRE entirely, that benchmark remains in our code base today.

Abstract the dependency

Depending on a package is a decision that you are likely to revisit later. Perhaps updates will take the package in a new direction. Perhaps serious security problems will be found. Perhaps a better option will come along. For all these reasons, it is worth the effort to make it easy to migrate your project to a new dependency.

If the package will be used from many places in your project’s source code, migrating to a new dependency would require making changes to all those different source locations. Worse, if the package will be exposed in your own project’s API, migrating to a new dependency would require making changes in all the code calling your API, which you might not control. To avoid these costs, it makes sense to define an interface of your own, along with a thin wrapper implementing that interface using the dependency. Note that the wrapper should include only what your project needs from the dependency, not everything the dependency offers. Ideally, that allows you to substitute a different, equally appropriate dependency later, by changing only the wrapper. Migrating your per-project tests to use the new interface tests the interface and wrapper implementation and also makes it easy to test any potential replacements for the dependency.

For Code Search, we developed an abstract Regexp class that defined the interface Code Search needed from any regular expression engine. Then we wrote a thin wrapper around PCRE implementing that interface. The indirection made it easy to test alternate libraries, and it kept us from accidentally introducing knowledge of PCRE internals into the rest of the source tree. That in turn ensured that it would be easy to switch to a different dependency if needed.

Isolate the dependency

It may also be appropriate to isolate a dependency at run-time, to limit the possible damage caused by bugs in it. For example, Google Chrome allows users to add dependencies—extension code—to the browser. When Chrome launched in 2008, it introduced the critical feature (now standard in all browsers) of isolating each extension in a sandbox running in a separate operating-system process.¹⁵ An exploitable bug in an badly-written extension therefore did not automatically have access to the entire memory of the browser itself and could be stopped from making inappropriate system calls.¹⁶ For Code Search, until we dropped PCRE entirely, our plan was to isolate at least the PCRE parser in a similar sandbox. Today, another option would be a lightweight hypervisor-based sandbox like gVisor.¹⁷ Isolating dependencies reduces the associated risks of running that code.

Even with these examples and other off-the-shelf options, run-time isolation of suspect code is still too difficult and rarely done. True isolation would require a completely memory-safe language, with no escape hatch into untyped code. That’s challenging not just in entirely unsafe languages like C and C++ but also in languages that provide restricted unsafe operations, like Java when including JNI, or like Go, Rust, and Swift when including their “unsafe” features. Even in a memory-safe language like JavaScript, code often has access to far more than it needs. In November 2018, the latest version of the NPM package event-stream, which provided a functional streaming API for JavaScript events, was discovered to contain obfuscated malicious code that had been added two and a half months earlier. The code, which harvested large Bitcoin wallets from users of the Copay mobile app, was accessing system resources entirely unrelated to processing event streams.¹⁸ One of many possible defenses to this kind of problem would be to better restrict what dependencies can access.

Avoid the dependency

If a dependency seems too risky and you can’t find a way to isolate it, the best answer may be to avoid it entirely, or at least to avoid the parts you’ve identified as most problematic.

For example, as we better understood the risks and costs associated with PCRE, our plan for Google Code Search evolved from “use PCRE directly,” to “use PCRE but sandbox the parser,” to “write a new regular expression parser but keep the PCRE execution engine,” to “write a new parser and connect it to a different, more efficient open-source execution engine.” Later we rewrote the execution engine as well, so that no dependencies were left, and we open-sourced the result: RE2.¹⁹

If you only need a tiny fraction of a dependency, it may be simplest to make a copy of what you need (preserving appropriate copyright and other legal notices, of course). You are taking on responsibility for fixing bugs, maintenance, and so on, but you’re also completely isolated from the larger risks. The Go developer community has a proverb about this: “A little copying is better than a little dependency.”²⁰

Upgrade the dependency

For a long time, the conventional wisdom about software was “if it ain’t broke, don’t fix it.” Upgrading carries a chance of introducing new bugs; without a corresponding reward—like a new feature you need—why take the risk? This analysis ignores two costs. The first is the cost of the eventual upgrade. In software, the difficulty of making code changes does not scale linearly: making ten small changes is less work and easier to get right than making one equivalent large change. The second is the cost of discovering already-fixed bugs the hard way. Especially in a security context, where known bugs are actively exploited, every day you wait is another day that attackers can break in.

For example, consider the year 2017 at Equifax, as recounted by executives in detailed congressional testimony.²¹ On March 7, a new vulnerability in Apache Struts was disclosed, and a patched version was released. On March 8, Equifax received a notice from US-CERT about the need to update any uses of Apache Struts. Equifax ran source code and network scans on March 9 and March 15, respectively; neither scan turned up a particular group of public-facing web servers. On May 13, attackers found the servers that Equifax’s security teams could not. They used the Apache Struts vulnerability to breach Equifax’s network and then steal detailed personal and financial information about 148 million people over the next two months. Equifax finally noticed the breach on July 29 and publicly disclosed it on September 4. By the end of September, Equifax’s CEO, CIO, and CSO had all resigned, and a congressional investigation was underway.

Equifax’s experience drives home the point that although dependency managers know the versions they are using at build time, you need other arrangements to track that information through your production deployment process. For the Go language, we are experimenting with automatically including a version manifest in every binary, so that deployment processes can scan binaries for dependencies that need upgrading. Go also makes that information available at run-time, so that servers can consult databases of known bugs and self-report to monitoring software when they are in need of upgrades.

Upgrading promptly is important, but upgrading means adding new code to your project, which should mean updating your evaluation of the risks of using the dependency based on the new version. As minimum, you’d want to skim the diffs showing the changes being made from the current version to the upgraded versions, or at least read the release notes, to identify the most likely areas of concern in the upgraded code. If a lot of code is changing, so that the diffs are difficult to digest, that is also information you can incorporate into your risk assessment update.

You’ll also want to re-run the tests you’ve written that are specific to your project, to make sure the upgraded package is at least as suitable for the project as the earlier version. It also makes sense to re-run the package’s own tests. If the package has its own dependencies, it is entirely possible that your project’s configuration uses different versions of those dependencies (either older or newer ones) than the package’s authors use. Running the package’s own tests can quickly identify problems specific to your configuration.

Again, upgrades should not be completely automatic. You need to verify that the upgraded versions are appropriate for your environment before deploying them.²²

If your upgrade process includes re-running the integration and qualification tests you’ve already written for the dependency, so that you are likely to identify new problems before they reach production, then, in most cases, delaying an upgrade is riskier than upgrading quickly.

The window for security-critical upgrades is especially short. In the aftermath of the Equifax breach, forensic security teams found evidence that attackers (perhaps different ones) had successfully exploited the Apache Struts vulnerability on the affected servers on March 10, only three days after it was publicly disclosed, but they’d only run a single whoami command.

Watch your dependencies

Even after all that work, you’re not done tending your dependencies. It’s important to continue to monitor them and perhaps even re-evaluate your decision to use them.

First, make sure that you keep using the specific package versions you think you are. Most dependency managers now make it easy or even automatic to record the cryptographic hash of the expected source code for a given package version and then to check that hash when re-downloading the package on another computer or in a test environment. This ensures that your build use the same dependency source code you inspected and tested. These kinds of checks prevented the event-stream attacker, described earlier, from silently inserting malicious code in the already-released version 3.3.5. Instead, the attacker had to create a new version, 3.3.6, and wait for people to upgrade (without looking closely at the changes).

It is also important to watch for new indirect dependencies creeping in: upgrades can easily introduce new packages upon which the success of your project now depends. They deserve your attention as well. In the case of event-stream, the malicious code was hidden in a different package, flatmap-stream, which the new event-stream release added as a new dependency.

Creeping dependencies can also affect the size of your project. During the development of Google’s Sawzall²³—a JIT’ed logs processing language—the authors discovered at various times that the main interpreter binary contained not just Sawzall’s JIT but also (unused) PostScript, Python, and JavaScript interpreters. Each time, the culprit turned out to be unused dependencies declared by some library Sawzall did depend on, combined with the fact that Google’s build system eliminated any manual effort needed to start using a new dependency.. This kind of error is the reason that the Go language makes importing an unused package a compile-time error.

Upgrading is a natural time to revisit the decision to use a dependency that’s changing. It’s also important to periodically revisit any dependency that isn’t changing. Does it seem plausible that there are no security problems or other bugs to fix? Has the project been abandoned? Maybe it’s time to start planning to replace that dependency.

It’s also important to recheck the security history of each dependency. For example, Apache Struts disclosed different major remote code execution vulnerabilities in 2016, 2017, and 2018. Even if you have a list of all the servers that run it and update them promptly, that track record might make you rethink using it at all.

Conclusion

Software reuse is finally here, and I don’t mean to understate its benefits: it has brought an enormously positive transformation for software developers. Even so, we’ve accepted this transformation without completely thinking through the potential consequences. The old reasons for trusting dependencies are becoming less valid at exactly the same time we have more dependencies than ever.

The kind of critical examination of specific dependencies that I outlined in this article is a significant amount of work and remains the exception rather than the rule. But I doubt there are any developers who actually make the effort to do this for every possible new dependency. I have only done a subset of them for a subset of my own dependencies. Most of the time the entirety of the decision is “let’s see what happens.” Too often, anything more than that seems like too much effort.

But the Copay and Equifax attacks are clear warnings of real problems in the way we consume software dependencies today. We should not ignore the warnings. I offer three broad recommendations.

Recognize the problem. If nothing else, I hope this article has convinced you that there is a problem here worth addressing. We need many people to focus significant effort on solving it.
Establish best practices for today. We need to establish best practices for managing dependencies using what’s available today. This means working out processes that evaluate, reduce, and track risk, from the original adoption decision through to production use. In fact, just as some engineers specialize in testing, it may be that we need engineers who specialize in managing dependencies.
Develop better dependency technology for tomorrow. Dependency managers have essentially eliminated the cost of downloading and installing a dependency. Future development effort should focus on reducing the cost of the kind of evaluation and maintenance necessary to use a dependency. For example, package discovery sites might work to find more ways to allow developers to share their findings. Build tools should, at the least, make it easy to run a package’s own tests. More aggressively, build tools and package management systems could also work together to allow package authors to test new changes against all public clients of their APIs. Languages should also provide easy ways to isolate a suspect package.

There’s a lot of good software out there. Let’s work together to find out how to reuse it safely.

References

Rachel Potvin and Josh Levenberg, “Why Google Stores Billions of Lines of Code in a Single Repository,” Communications of the ACM 59(7) (July 2016), pp. 78-87. https://doi.org/10.1145/2854146 (⇡)
Russ Cox, “Go & Versioning,” February 2018. https://research.swtch.com/vgo (⇡)
Ken Thompson, “Reflections on Trusting Trust,” Communications of the ACM 27(8) (August 1984), pp. 761–763. https://doi.org/10.1145/358198.358210 (⇡)
GNU Project, “GNU General Public License, version 1,” February 1989. https://www.gnu.org/licenses/old-licenses/gpl-1.0.html (⇡)
Titus Winters, “SD-8: Standard Library Compatibility,” C++ Standing Document, August 2018. https://isocpp.org/std/standing-documents/sd-8-standard-library-compatibility (⇡)
Go Project, “Go 1 and the Future of Go Programs,” September 2013. https://golang.org/doc/go1compat (⇡)
Facebook, “Infer: A tool to detect bugs in Java and C/C++/Objective-C code before it ships.” https://fbinfer.com/ (⇡)
“SpotBugs: Find bugs in Java Programs.” https://spotbugs.github.io/ (⇡)
D. Richard Hipp, “How SQLite is Tested.” https://www.sqlite.org/testing.html (⇡)
Alexander Potapenko, “Testing Chromium: ThreadSanitizer v2, a next-gen data race detector,” April 2014. https://blog.chromium.org/2014/04/testing-chromium-threadsanitizer-v2.html (⇡)
NIST, “National Vulnerability Database – Search and Statistics.” https://nvd.nist.gov/vuln/search (⇡)
Russ Cox, “Regular Expression Matching with a Trigram Index, or How Google Code Search Worked,” January 2012. https://swtch.com/~rsc/regexp/regexp4.html (⇡)
Google, “Google Open Source: Using Third-Party Licenses.” https://opensource.google.com/docs/thirdparty/licenses/#banned (⇡)
Nathan Willis, “A single Node of failure,” LWN, March 2016. https://lwn.net/Articles/681410/ (⇡)
Charlie Reis, “Multi-process Architecture,” September 2008. https://blog.chromium.org/2008/09/multi-process-architecture.html (⇡)
Adam Langley, “Chromium’s seccomp Sandbox,” August 2009. https://www.imperialviolet.org/2009/08/26/seccomp.html (⇡)
Nicolas Lacasse, “Open-sourcing gVisor, a sandboxed container runtime,” May 2018. https://cloud.google.com/blog/products/gcp/open-sourcing-gvisor-a-sandboxed-container-runtime (⇡)
Adam Baldwin, “Details about the event-stream incident,” November 2018. https://blog.npmjs.org/post/180565383195/details-about-the-event-stream-incident (⇡)
Russ Cox, “RE2: a principled approach to regular expression matching,” March 2010. https://opensource.googleblog.com/2010/03/re2-principled-approach-to-regular.html (⇡)
Rob Pike, “Go Proverbs,” November 2015. https://go-proverbs.github.io/ (⇡)
U.S. House of Representatives Committee on Oversight and Government Reform, “The Equifax Data Breach,” Majority Staff Report, 115th Congress, December 2018. https://oversight.house.gov/report/committee-releases-report-revealing-new-information-on-equifax-data-breach/ (⇡)
Russ Cox, “The Principles of Versioning in Go,” GopherCon Singapore, May 2018. https://www.youtube.com/watch?v=F8nrpe0XWRg (⇡)
Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan, “Interpreting the Data: Parallel Analysis with Sawzall,” Scientific Programming Journal, vol. 13 (2005). https://doi.org/10.1155/2005/962135 (⇡)

Coda

This post is a draft of my current thinking on this topic. I hope that sharing it will provoke productive discussion, attract more attention to the general problem, and help me refine my own thoughts. I also intend to publish a revised copy of this as an article elsewhere. For both these reasons, unlike most of my blog posts, this post is not Creative Commons-licensed. Please link people to this post instead of making a copy. When a more final version is published, I will link to it here.

Why Add Versions To Go?

2018-06-07T10:20:00-04:00

People sometimes ask me why we should add package versions to Go at all. Isn't Go doing well enough without versions? Usually these people have had a bad experience with versions in another language, and they associate versions with breaking changes. In this post, I want to talk a little about why we do need to add support for package versions to Go. Later posts will address why we won't encourage breaking changes.

The go get command has two failure modes caused by ignorance of versions: it can use code that is too old, and it can use code that is too new. For example, suppose we want to use a package D, so we run go get D with no packages installed yet. The go get command will download the latest copy of D (whatever git clone brings down), which builds successfully. To make our discussion easier, let's call that D version 1.0 and keep D's dependency requirements in mind (and in our diagrams). But remember that while we understand the idea of versions and dependency requirements, go get does not.

$ go get D

Now suppose that a month later, we want to use C, which happens to import D. We run go get C. The go get command downloads the latest copy of C, which happens to be C 1.8 and imports D. Since go get already has a downloaded copy of D, it uses that one instead of incurring the cost of a fresh download. Unfortunately, the build of C fails: C is using a new feature from D introduced in D 1.4, and go get is reusing D 1.0. The code is too old.

$ go get C

Next we try running go get -u, which downloads the latest copy of all the code involved, including code already downloaded.

$ go get -u C

Unfortunately, D 1.6 was released an hour ago and contains a bug that breaks C. Now the code is too new. Watching this play out from above, we know what go get needs to do: use D ≥ 1.4 but not D 1.6, so maybe D 1.4 or D 1.5. It's very difficult to tell go get that today, since it doesn't understand the concept of a package version.

Getting back to the original question in the post, why add versions to Go?

Because agreeing on a versioning system—a syntax for version identifiers, along with rules for how to order and interpret them—establishes a way for us to communicate more precisely with our tools, and with each other, about which copy of a package we mean. Versioning matters for correct builds, as we just saw, but it enables other interesting tools too.

For example, the obvious next step is to be able to list which versions of a package are being used in a given build and whether any of them have updates available. Generalizing that, it would be useful to have a tool that examines a list of builds, perhaps all the targets built at a given company, and assembles the same list. Such a list of versions can then feed into compliance checks, queries into bug databases, and so on. Embedding the version list in a built binary would even allow a program to make these checks on its own behalf while it runs. These all exist for other systems already, of course: I'm not claiming the ideas are novel. The point is that establishing agreement on a versioning system enables all these tools, which can even be built outside the language toolchain.

We can also move from query tools, which tell you about your code, to development tools, which update it for you. For example, an obvious next step is a tool to update a package's dependencies to their latest versions automatically whenever the package's tests and those of its dependencies continue to pass. Being able to describe versions might also enable tools that apply code cleanups. For example, having versions would let us write instructions “when using D version ≥ 1.4, replace the common client code idiom x.Foo(1).Bar(2) with x.FooBar()” that a tool like go fix could execute.

The goal of our work adding versions to the core Go toolchain—or, more generally, adding them to the shared working vocabulary of both Go developers and our tools—is to establish a foundation that helps with core issues like building working programs but also enables interesting external tools like these, and certainly others we haven't imagined yet.

If we're building a foundation for other tools, we should aim to make that foundation as versatile, strong, and robust as possible, to enable as many other tools as possible, with as little hindrance as possible to those tools. We're not just writing a single tool. We're defining the way all these tools will work together. This foundation is an API in the broad sense of something that programs must be written against. Like in any API, we want to choose a design that is powerful enough to enable many uses but at the same time simple, reliable, consistent, coherent, and predictable. Future posts will explore how vgo's design decisions aim for those properties.

What is Software Engineering?

2018-05-30T10:00:00-04:00

Nearly all of Go’s distinctive design decisions were aimed at making software engineering simpler and easier. We've said this often. The canonical reference is Rob Pike's 2012 article, “Go at Google: Language Design in the Service of Software Engineering.” But what is software engineering?

Software engineering is what happens to programming
when you add time and other programmers.

Programming means getting a program working. You have a problem to solve, you write some Go code, you run it, you get your answer, you’re done. That’s programming, and that's difficult enough by itself. But what if that code has to keep working, day after day? What if five other programmers need to work on the code too? Then you start to think about version control systems, to track how the code changes over time and to coordinate with the other programmers. You add unit tests, to make sure bugs you fix are not reintroduced over time, not by you six months from now, and not by that new team member who’s unfamiliar with the code. You think about modularity and design patterns, to divide the program into parts that team members can work on mostly independently. You use tools to help you find bugs earlier. You look for ways to make programs as clear as possible, so that bugs are less likely. You make sure that small changes can be tested quickly, even in large programs. You're doing all of this because your programming has turned into software engineering.

(This definition and explanation of software engineering is my riff on an original theme by my Google colleague Titus Winters, whose preferred phrasing is “software engineering is programming integrated over time.” It's worth seven minutes of your time to see his presentation of this idea at CppCon 2017, from 8:17 to 15:00 in the video.)

As I said earlier, nearly all of Go’s distinctive design decisions have been motivated by concerns about software engineering, by trying to accommodate time and other programmers into the daily practice of programming.

For example, most people think that we format Go code with gofmt to make code look nicer or to end debates among team members about program layout. But the most important reason for gofmt is that if an algorithm defines how Go source code is formatted, then programs, like goimports or gorename or go fix, can edit the source code more easily, without introducing spurious formatting changes when writing the code back. This helps you maintain code over time.

As another example, Go import paths are URLs. If code said import "uuid", you’d have to ask which uuid package. Searching for uuid on godoc.org turns up dozens of packages. If instead the code says import "github.com/pborman/uuid", now it’s clear which package we mean. Using URLs avoids ambiguity and also reuses an existing mechanism for giving out names, making it simpler and easier to coordinate with other programmers.

Continuing the example, Go import paths are written in Go source files, not in a separate build configuration file. This makes Go source files self-contained, which makes it easier to understand, modify, and copy them. These decisions, and more, were all made with the goal of simplifying software engineering.

In later posts I will talk specifically about why versions are important for software engineering and how software engineering concerns motivate the design changes from dep to vgo.

Go and Dogma

2017-01-09T09:00:00-05:00

[Cross-posting from last year’s Go contributors AMA on Reddit, because it’s still important to remember.]

One of the perks of working on Go these past years has been the chance to have many great discussions with other language designers and implementers, for example about how well various design decisions worked out or the common problems of implementing what look like very different languages (for example both Go and Haskell need some kind of “green threads”, so there are more shared runtime challenges than you might expect). In one such conversation, when I was talking to a group of early Lisp hackers, one of them pointed out that these discussions are basically never dogmatic. Designers and implementers remember working through the good arguments on both sides of a particular decision, and they’re often eager to hear about someone else’s experience with what happens when you make that decision differently. Contrast that kind of discussion with the heated arguments or overly zealous statements you sometimes see from users of the same languages. There’s a real disconnect, possibly because the users don’t have the experience of weighing the arguments on both sides and don’t realize how easily a particular decision might have gone the other way.

Language design and implementation is engineering. We make decisions using evaluations of costs and benefits or, if we must, using predictions of those based on past experience. I think we have an important responsibility to explain both sides of a particular decision, to make clear that the arguments for an alternate decision are actually good ones that we weighed and balanced, and to avoid the suggestion that particular design decisions approach dogma. I hope the Reddit AMA as well as discussion on golang-nuts or StackOverflow or the Go Forum or at conferences help with that.

But we need help from everyone. Remember that none of the decisions in Go are infallible; they’re just our best attempts at the time we made them, not wisdom received on stone tablets. If someone asks why Go does X instead of Y, please try to present the engineering reasons fairly, including for Y, and avoid argument solely by appeal to authority. It’s too easy to fall into the “well that’s just not how it’s done here” trap. And now that I know about and watch for that trap, I see it in nearly every technical community, although some more than others.

A Tour of Acme

2012-09-17T11:00:00-04:00

People I work with recognize my computer easily: it's the one with nothing but yellow windows and blue bars on the screen. That's the text editor acme, written by Rob Pike for Plan 9 in the early 1990s. Acme focuses entirely on the idea of text as user interface. It's difficult to explain acme without seeing it, though, so I've put together a screencast explaining the basics of acme and showing a brief programming session. Remember as you watch the video that the 854x480 screen is quite cramped. Usually you'd run acme on a larger screen: even my MacBook Air has almost four times as much screen real estate.

The video doesn't show everything acme can do, nor does it show all the ways you can use it. Even small idioms like where you type text to be loaded or executed vary from user to user. To learn more about acme, read Rob Pike's paper “Acme: A User Interface for Programmers” and then try it.

Acme runs on most operating systems. If you use Plan 9 from Bell Labs, you already have it. If you use FreeBSD, Linux, OS X, or most other Unix clones, you can get it as part of Plan 9 from User Space. If you use Windows, I suggest trying acme as packaged in acme stand alone complex, which is based on the Inferno programming environment.

Mini-FAQ:

Q. Can I use scalable fonts? A. On the Mac, yes. If you run acme -f /mnt/font/Monaco/16a/font you get 16-point anti-aliased Monaco as your font, served via fontsrv. If you'd like to add X11 support to fontsrv, I'd be happy to apply the patch.
Q. Do I need X11 to build on the Mac? A. No. The build will complain that it cannot build ‘snarfer’ but it should complete otherwise. You probably don't need snarfer.

If you're interested in history, the predecessor to acme was called help. Rob Pike's paper “A Minimalist Global User Interface” describes it. See also “The Text Editor sam”

Correction: the smiley program in the video was written by Ken Thompson. I got it from Dennis Ritchie, the more meticulous archivist of the pair.

Minimal Boolean Formulas

2011-05-18T00:00:00-04:00

28. That's the minimum number of AND or OR operators you need in order to write any Boolean function of five variables. Alex Healy and I computed that in April 2010. Until then, I believe no one had ever known that little fact. This post describes how we computed it and how we almost got scooped by Knuth's Volume 4A which considers the problem for AND, OR, and XOR.

A Naive Brute Force Approach

Any Boolean function of two variables can be written with at most 3 AND or OR operators: the parity function on two variables X XOR Y is (X AND Y') OR (X' AND Y), where X' denotes “not X.” We can shorten the notation by writing AND and OR like multiplication and addition: X XOR Y = X*Y' + X'*Y.

For three variables, parity is also a hardest function, requiring 9 operators: X XOR Y XOR Z = (X*Z'+X'*Z+Y')*(X*Z+X'*Z'+Y).

For four variables, parity is still a hardest function, requiring 15 operators: W XOR X XOR Y XOR Z = (X*Z'+X'*Z+W'*Y+W*Y')*(X*Z+X'*Z'+W*Y+W'*Y').

The sequence so far prompts a few questions. Is parity always a hardest function? Does the minimum number of operators alternate between 2ⁿ−1 and 2ⁿ+1?

I computed these results in January 2001 after hearing the problem from Neil Sloane, who suggested it as a variant of a similar problem first studied by Claude Shannon.

The program I wrote to compute a(4) computes the minimum number of operators for every Boolean function of n variables in order to find the largest minimum over all functions. There are 2⁴ = 16 settings of four variables, and each function can pick its own value for each setting, so there are 2¹⁶ different functions. To make matters worse, you build new functions by taking pairs of old functions and joining them with AND or OR. 2¹⁶ different functions means 2¹⁶·2¹⁶ = 2³² pairs of functions.

The program I wrote was a mangling of the Floyd-Warshall all-pairs shortest paths algorithm. That algorithm is:

// Floyd-Warshall all pairs shortest path
func compute():
    for each node i
        for each node j
            dist[i][j] = direct distance, or ∞
    
    for each node k
        for each node i
            for each node j
                d = dist[i][k] + dist[k][j]
                if d < dist[i][j]
                    dist[i][j] = d
    return

The algorithm begins with the distance table dist[i][j] set to an actual distance if i is connected to j and infinity otherwise. Then each round updates the table to account for paths going through the node k: if it's shorter to go from i to k to j, it saves that shorter distance in the table. The nodes are numbered from 0 to n, so the variables i, j, k are simply integers. Because there are only n nodes, we know we'll be done after the outer loop finishes.

The program I wrote to find minimum Boolean formula sizes is an adaptation, substituting formula sizes for distance.

// Algorithm 1
func compute()
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    loop
        changed = false
        for each function f
            for each function g
                d = size[f] + 1 + size[g]
                if d < size[f OR g]
                    size[f OR g] = d
                    changed = true
                if d < size[f AND g]
                    size[f AND g] = d
                    changed = true
        if not changed
            return

Algorithm 1 runs the same kind of iterative update loop as the Floyd-Warshall algorithm, but it isn't as obvious when you can stop, because you don't know the maximum formula size beforehand. So it runs until a round doesn't find any new functions to make, iterating until it finds a fixed point.

The pseudocode above glosses over some details, such as the fact that the per-function loops can iterate over a queue of functions known to have finite size, so that each loop omits the functions that aren't yet known. That's only a constant factor improvement, but it's a useful one.

Another important detail missing above is the representation of functions. The most convenient representation is a binary truth table. For example, if we are computing the complexity of two-variable functions, there are four possible inputs, which we can number as follows.

X	Y	Value
false	false	00₂ = 0
false	true	01₂ = 1
true	false	10₂ = 2
true	true	11₂ = 3

The functions are then the 4-bit numbers giving the value of the function for each input. For example, function 13 = 1101₂ is true for all inputs except X=false Y=true. Three-variable functions correspond to 3-bit inputs generating 8-bit truth tables, and so on.

This representation has two key advantages. The first is that the numbering is dense, so that you can implement a map keyed by function using a simple array. The second is that the operations “f AND g” and “f OR g” can be implemented using bitwise operators: the truth table for “f AND g” is the bitwise AND of the truth tables for f and g.

That program worked well enough in 2001 to compute the minimum number of operators necessary to write any 1-, 2-, 3-, and 4-variable Boolean function. Each round takes asymptotically O(2^2ⁿ·2^2ⁿ) = O(2^2ⁿ⁺¹) time, and the number of rounds needed is O(the final answer). The answer for n=4 is 15, so the computation required on the order of 15·2^2⁵ = 15·2³² iterations of the innermost loop. That was plausible on the computer I was using at the time, but the answer for n=5, likely around 30, would need 30·2⁶⁴ iterations to compute, which seemed well out of reach. At the time, it seemed plausible that parity was always a hardest function and that the minimum size would continue to alternate between 2ⁿ−1 and 2ⁿ+1. It's a nice pattern.

Exploiting Symmetry

Five years later, though, Alex Healy and I got to talking about this sequence, and Alex shot down both conjectures using results from the theory of circuit complexity. (Theorists!) Neil Sloane added this note to the entry for the sequence in his Online Encyclopedia of Integer Sequences:

%E A056287 Russ Cox conjectures that X₁ XOR ... XOR X_n is always a worst f and that a(5) = 33 and a(6) = 63. But (Jan 27 2006) Alex Healy points out that this conjecture is definitely false for large n. So what is a(5)?

Indeed. What is a(5)? No one knew, and it wasn't obvious how to find out.

In January 2010, Alex and I started looking into ways to speed up the computation for a(5). 30·2⁶⁴ is too many iterations but maybe we could find ways to cut that number.

In general, if we can identify a class of functions f whose members are guaranteed to have the same complexity, then we can save just one representative of the class as long as we recreate the entire class in the loop body. What used to be:

for each function f
    for each function g
        visit f AND g
        visit f OR g

can be rewritten as

for each canonical function f
    for each canonical function g
        for each ff equivalent to f
            for each gg equivalent to g
                visit ff AND gg
                visit ff OR gg

That doesn't look like an improvement: it's doing all the same work. But it can open the door to new optimizations depending on the equivalences chosen. For example, the functions “f” and “¬f” are guaranteed to have the same complexity, by DeMorgan's laws. If we keep just one of those two on the lists that “for each function” iterates over, we can unroll the inner two loops, producing:

for each canonical function f
    for each canonical function g
        visit f OR g
        visit f AND g
        visit ¬f OR g
        visit ¬f AND g
        visit f OR ¬g
        visit f AND ¬g
        visit ¬f OR ¬g
        visit ¬f AND ¬g

That's still not an improvement, but it's no worse. Each of the two loops considers half as many functions but the inner iteration is four times longer. Now we can notice that half of tests aren't worth doing: “f AND g” is the negation of “¬f OR ¬g,” and so on, so only half of them are necessary.

Let's suppose that when choosing between “f” and “¬f” we keep the one that is false when presented with all true inputs. (This has the nice property that f ^ (int32(f) >> 31) is the truth table for the canonical form of f.) Then we can tell which combinations above will produce canonical functions when f and g are already canonical:

for each canonical function f
    for each canonical function g
        visit f OR g
        visit f AND g
        visit ¬f AND g
        visit f AND ¬g

That's a factor of two improvement over the original loop.

Another observation is that permuting the inputs to a function doesn't change its complexity: “f(V, W, X, Y, Z)” and “f(Z, Y, X, W, V)” will have the same minimum size. For complex functions, each of the 5! = 120 permutations will produce a different truth table. A factor of 120 reduction in storage is good but again we have the problem of expanding the class in the iteration. This time, there's a different trick for reducing the work in the innermost iteration. Since we only need to produce one member of the equivalence class, it doesn't make sense to permute the inputs to both f and g. Instead, permuting just the inputs to f while fixing g is guaranteed to hit at least one member of each class that permuting both f and g would. So we gain the factor of 120 twice in the loops and lose it once in the iteration, for a net savings of 120. (In some ways, this is the same trick we did with “f” vs “¬f.”)

A final observation is that negating any of the inputs to the function doesn't change its complexity, because X and X' have the same complexity. The same argument we used for permutations applies here, for another constant factor of 2⁵ = 32.

The code stores a single function for each equivalence class and then recomputes the equivalent functions for f, but not g.

for each canonical function f
    for each function ff equivalent to f
        for each canonical function g
            visit ff OR g
            visit ff AND g
            visit ¬ff AND g
            visit ff AND ¬g

In all, we just got a savings of 2·120·32 = 7680, cutting the total number of iterations from 30·2⁶⁴ = 5×10²⁰ to 7×10¹⁶. If you figure we can do around 10⁹ iterations per second, that's still 800 days of CPU time.

The full algorithm at this point is:

// Algorithm 2
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    loop
        changed = false
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g
                    d = size[ff] + 1 + size[g]
                    changed |= visit(d, ff OR g)
                    changed |= visit(d, ff AND g)
                    changed |= visit(d, ff AND ¬g)
                    changed |= visit(d, ¬ff AND g)
        if not changed
            return

func visit(d, fg):
    if size[fg] != ∞
        return false
    
    record fg as canonical

    for each function ffgg equivalent to fg
        size[ffgg] = d
    return true

The helper function “visit” must set the size not only of its argument fg but also all equivalent functions under permutation or inversion of the inputs, so that future tests will see that they have been computed.

Methodical Exploration

There's one final improvement we can make. The approach of looping until things stop changing considers each function pair multiple times as their sizes go down. Instead, we can consider functions in order of complexity, so that the main loop builds first all the functions of minimum complexity 1, then all the functions of minimum complexity 2, and so on. If we do that, we'll consider each function pair at most once. We can stop when all functions are accounted for.

Applying this idea to Algorithm 1 (before canonicalization) yields:

// Algorithm 3
func compute()
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    for k = 1 to ∞
        for each function f
            for each function g of size k − size(f) − 1
                if size[f AND g] == ∞
                    size[f AND g] = k
                    nsize++
                if size[f OR g] == ∞
                    size[f OR g] = k
                    nsize++
        if nsize == 2^2ⁿ
            return

Applying the idea to Algorithm 2 (after canonicalization) yields:

// Algorithm 4
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    for k = 1 to ∞
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g of size k − size(f) − 1
                    visit(k, ff OR g)
                    visit(k, ff AND g)
                    visit(k, ff AND ¬g)
                    visit(k, ¬ff AND g)
        if nvisited == 2^2ⁿ
            return

func visit(d, fg):
    if size[fg] != ∞
        return
    
    record fg as canonical

    for each function ffgg equivalent to fg
        if size[ffgg] != ∞
            size[ffgg] = d
            nvisited += 2  // counts ffgg and ¬ffgg
    return

The original loop in Algorithms 1 and 2 considered each pair f, g in every iteration of the loop after they were computed. The new loop in Algorithms 3 and 4 considers each pair f, g only once, when k = size(f) + size(g) + 1. This removes the leading factor of 30 (the number of times we expected the first loop to run) from our estimation of the run time. Now the expected number of iterations is around 2⁶⁴/7680 = 2.4×10¹⁵. If we can do 10⁹ iterations per second, that's only 28 days of CPU time, which I can deliver if you can wait a month.

Our estimate does not include the fact that not all function pairs need to be considered. For example, if the maximum size is 30, then the functions of size 14 need never be paired against the functions of size 16, because any result would have size 14+1+16 = 31. So even 2.4×10¹⁵ is an overestimate, but it's in the right ballpark. (With hindsight I can report that only 1.7×10¹⁴ pairs need to be considered but also that our estimate of 10⁹ iterations per second was optimistic. The actual calculation ran for 20 days, an average of about 10⁸ iterations per second.)

Endgame: Directed Search

A month is still a long time to wait, and we can do better. Near the end (after k is bigger than, say, 22), we are exploring the fairly large space of function pairs in hopes of finding a fairly small number of remaining functions. At that point it makes sense to change from the bottom-up “bang things together and see what we make” to the top-down “try to make this one of these specific functions.” That is, the core of the current search is:

for each canonical function f
    for each function ff equivalent to f
        for each canonical function g of size k − size(f) − 1
            visit(k, ff OR g)
            visit(k, ff AND g)
            visit(k, ff AND ¬g)
            visit(k, ¬ff AND g)

We can change it to:

for each missing function fg
    for each canonical function g
        for all possible f such that one of these holds
                * fg = f OR g
                * fg = f AND g
                * fg = ¬f AND g
                * fg = f AND ¬g
            if size[f] == k − size(g) − 1
                visit(k, fg)
                next fg

By the time we're at the end, exploring all the possible f to make the missing functions—a directed search—is much less work than the brute force of exploring all combinations.

As an example, suppose we are looking for f such that fg = f OR g. The equation is only possible to satisfy if fg OR g == fg. That is, if g has any extraneous 1 bits, no f will work, so we can move on. Otherwise, the remaining condition is that f AND ¬g == fg AND ¬g. That is, for the bit positions where g is 0, f must match fg. The other bits of f (the bits where g has 1s) can take any value. We can enumerate the possible f values by recursively trying all possible values for the “don't care” bits.

func find(x, any, xsize):
    if size(x) == xsize
        return x
    while any != 0
        bit = any AND −any  // rightmost 1 bit in any
        any = any AND ¬bit
        if f = find(x OR bit, any, xsize) succeeds
            return f
    return failure

It doesn't matter which 1 bit we choose for the recursion, but finding the rightmost 1 bit is cheap: it is isolated by the (admittedly surprising) expression “any AND −any.”

Given find, the loop above can try these four cases:

Formula	Condition	Base x	“Any” bits
fg = f OR g	fg OR g == fg	fg AND ¬g	g
fg = f OR ¬g	fg OR ¬g == fg	fg AND g	¬g
¬fg = f OR g	¬fg OR g == fg	¬fg AND ¬g	g
¬fg = f OR ¬g	¬fg OR ¬g == ¬fg	¬fg AND g	¬g

Rewriting the Boolean expressions to use only the four OR forms means that we only need to write the “adding bits” version of find.

The final algorithm is:

// Algorithm 5
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    // Generate functions.
    for k = 1 to max_generate
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g of size k − size(f) − 1
                    visit(k, ff OR g)
                    visit(k, ff AND g)
                    visit(k, ff AND ¬g)
                    visit(k, ¬ff AND g)

    // Search for functions.
    for k = max_generate+1 to ∞
        for each missing function fg
            for each canonical function g
                fsize = k − size(g) − 1
                if fg OR g == fg
                    if f = find(fg AND ¬g, g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if fg OR ¬g == fg
                    if f = find(fg AND g, ¬g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if ¬fg OR g == ¬fg
                    if f = find(¬fg AND ¬g, g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if ¬fg OR ¬g == ¬fg
                    if f = find(¬fg AND g, ¬g, fsize) succeeds
                        visit(k, fg)
                        next fg
        if nvisited == 2^2ⁿ
            return

func visit(d, fg):
    if size[fg] != ∞
        return
    
    record fg as canonical

    for each function ffgg equivalent to fg
        if size[ffgg] != ∞
            size[ffgg] = d
            nvisited += 2  // counts ffgg and ¬ffgg
    return

func find(x, any, xsize):
    if size(x) == xsize
        return x
    while any != 0
        bit = any AND −any  // rightmost 1 bit in any
        any = any AND ¬bit
        if f = find(x OR bit, any, xsize) succeeds
            return f
    return failure

To get a sense of the speedup here, and to check my work, I ran the program using both algorithms on a 2.53 GHz Intel Core 2 Duo E7200.

	————— # of Functions —————			———— Time ————
Size	Canonical	All	All, Cumulative	Generate	Search
0	1	10	10
1	2	82	92	< 0.1 seconds	3.4 minutes
2	2	640	732	< 0.1 seconds	7.2 minutes
3	7	4420	5152	< 0.1 seconds	12.3 minutes
4	19	25276	29696	< 0.1 seconds	30.1 minutes
5	44	117440	147136	< 0.1 seconds	1.3 hours
6	142	515040	662176	< 0.1 seconds	3.5 hours
7	436	1999608	2661784	0.2 seconds	11.6 hours
8	1209	6598400	9260184	0.6 seconds	1.7 days
9	3307	19577332	28837516	1.7 seconds	4.9 days
10	7741	50822560	79660076	4.6 seconds	[ 10 days ? ]
11	17257	114619264	194279340	10.8 seconds	[ 20 days ? ]
12	31851	221301008	415580348	21.7 seconds	[ 50 days ? ]
13	53901	374704776	790285124	38.5 seconds	[ 80 days ? ]
14	75248	533594528	1323879652	58.7 seconds	[ 100 days ? ]
15	94572	667653642	1991533294	1.5 minutes	[ 120 days ? ]
16	98237	697228760	2688762054	2.1 minutes	[ 120 days ? ]
17	89342	628589440	3317351494	4.1 minutes	[ 90 days ? ]
18	66951	468552896	3785904390	9.1 minutes	[ 50 days ? ]
19	41664	287647616	4073552006	23.4 minutes	[ 30 days ? ]
20	21481	144079832	4217631838	57.0 minutes	[ 10 days ? ]
21	8680	55538224	4273170062	2.4 hours	2.5 days
22	2730	16099568	4289269630	5.2 hours	11.7 hours
23	937	4428800	4293698430	11.2 hours	2.2 hours
24	228	959328	4294657758	22.0 hours	33.2 minutes
25	103	283200	4294940958	1.7 days	4.0 minutes
26	21	22224	4294963182	2.9 days	42 seconds
27	10	3602	4294966784	4.7 days	2.4 seconds
28	3	512	4294967296	[ 7 days ? ]	0.1 seconds

The bracketed times are estimates based on the work involved: I did not wait that long for the intermediate search steps. The search algorithm is quite a bit worse than generate until there are very few functions left to find. However, it comes in handy just when it is most useful: when the generate algorithm has slowed to a crawl. If we run generate through formulas of size 22 and then switch to search for 23 onward, we can run the whole computation in just over half a day of CPU time.

The computation of a(5) identified the sizes of all 616,126 canonical Boolean functions of 5 inputs. In contrast, there are just over 200 trillion canonical Boolean functions of 6 inputs. Determining a(6) is unlikely to happen by brute force computation, no matter what clever tricks we use.

Adding XOR

We've assumed the use of just AND and OR as our basis for the Boolean formulas. If we also allow XOR, functions can be written using many fewer operators. In particular, a hardest function for the 1-, 2-, 3-, and 4-input cases—parity—is now trivial. Knuth examines the complexity of 5-input Boolean functions using AND, OR, and XOR in detail in The Art of Computer Programming, Volume 4A. Section 7.1.2's Algorithm L is the same as our Algorithm 3 above, given for computing 4-input functions. Knuth mentions that to adapt it for 5-input functions one must treat only canonical functions and gives results for 5-input functions with XOR allowed. So another way to check our work is to add XOR to our Algorithm 4 and check that our results match Knuth's.

Because the minimum formula sizes are smaller (at most 12), the computation of sizes with XOR is much faster than before:

	————— # of Functions —————
Size	Canonical	All	All, Cumulative	Time
0	1	10	10
1	3	102	112	< 0.1 seconds
2	5	1140	1252	< 0.1 seconds
3	20	11570	12822	< 0.1 seconds
4	93	109826	122648	< 0.1 seconds
5	366	936440	1059088	0.1 seconds
6	1730	7236880	8295968	0.7 seconds
7	8782	47739088	56035056	4.5 seconds
8	40297	250674320	306709376	24.0 seconds
9	141422	955812256	1262521632	95.5 seconds
10	273277	1945383936	3207905568	200.7 seconds
11	145707	1055912608	4263818176	121.2 seconds
12	4423	31149120	4294967296	65.0 seconds

Knuth does not discuss anything like Algorithm 5, because the search for specific functions does not apply to the AND, OR, and XOR basis. XOR is a non-monotone function (it can both turn bits on and turn bits off), so there is no test like our “if fg OR g == fg” and no small set of “don't care” bits to trim the search for f. The search for an appropriate f in the XOR case would have to try all f of the right size, which is exactly what Algorithm 4 already does.

Volume 4A also considers the problem of building minimal circuits, which are like formulas but can use common subexpressions additional times for free, and the problem of building the shallowest possible circuits. See Section 7.1.2 for all the details.

Code and Web Site

The web site boolean-oracle.swtch.com lets you type in a Boolean expression and gives back the minimal formula for it. It uses tables generated while running Algorithm 5; those tables and the programs described in this post are also available on the site.

Postscript: Generating All Permutations and Inversions

The algorithms given above depend crucially on the step “for each function ff equivalent to f,” which generates all the ff obtained by permuting or inverting inputs to f, but I did not explain how to do that. We already saw that we can manipulate the binary truth table representation directly to turn f into ¬f and to compute combinations of functions. We can also manipulate the binary representation directly to invert a specific input or swap a pair of adjacent inputs. Using those operations we can cycle through all the equivalent functions.

To invert a specific input, let's consider the structure of the truth table. The index of a bit in the truth table encodes the inputs for that entry. For example, the low bit of the index gives the value of the first input. So the even-numbered bits—at indices 0, 2, 4, 6, ...—correspond to the first input being false, while the odd-numbered bits—at indices 1, 3, 5, 7, ...—correspond to the first input being true. Changing just that bit in the index corresponds to changing the single variable, so indices 0, 1 differ only in the value of the first input, as do 2, 3, and 4, 5, and 6, 7, and so on. Given the truth table for f(V, W, X, Y, Z) we can compute the truth table for f(¬V, W, X, Y, Z) by swapping adjacent bit pairs in the original truth table. Even better, we can do all the swaps in parallel using a bitwise operation. To invert a different input, we swap larger runs of bits.

Function		Truth Table (`f` = f(V, W, X, Y, Z))
f(¬V, W, X, Y, Z)		`(f&0x55555555)<< 1 \| (f>> 1)&0x55555555`
f(V, ¬W, X, Y, Z)		`(f&0x33333333)<< 2 \| (f>> 2)&0x33333333`
f(V, W, ¬X, Y, Z)		`(f&0x0f0f0f0f)<< 4 \| (f>> 4)&0x0f0f0f0f`
f(V, W, X, ¬Y, Z)		`(f&0x00ff00ff)<< 8 \| (f>> 8)&0x00ff00ff`
f(V, W, X, Y, ¬Z)		`(f&0x0000ffff)<<16 \| (f>>16)&0x0000ffff`

Being able to invert a specific input lets us consider all possible inversions by building them up one at a time. The Gray code lets us enumerate all possible 5-bit input codes while changing only 1 bit at a time as we move from one input to the next:

0, 1, 3, 2, 6, 7, 5, 4,
12, 13, 15, 14, 10, 11, 9, 8,
24, 25, 27, 26, 30, 31, 29, 28,
20, 21, 23, 22, 18, 19, 17, 16

This minimizes the number of inversions we need: to consider all 32 cases, we only need 31 inversion operations. In contrast, visiting the 5-bit input codes in the usual binary order 0, 1, 2, 3, 4, ... would often need to change multiple bits, like when changing from 3 to 4.

To swap a pair of adjacent inputs, we can again take advantage of the truth table. For a pair of inputs, there are four cases: 00, 01, 10, and 11. We can leave the 00 and 11 cases alone, because they are invariant under swapping, and concentrate on swapping the 01 and 10 bits. The first two inputs change most often in the truth table: each run of 4 bits corresponds to those four cases. In each run, we want to leave the first and fourth alone and swap the second and third. For later inputs, the four cases consist of sections of bits instead of single bits.

Function		Truth Table (`f` = f(V, W, X, Y, Z))
f(W, V, X, Y, Z)		`f&0x99999999 \| (f&0x22222222)<<1 \| (f>>1)&0x22222222`
f(V, X, W, Y, Z)		`f&0xc3c3c3c3 \| (f&0x0c0c0c0c)<<1 \| (f>>1)&0x0c0c0c0c`
f(V, W, Y, X, Z)		`f&0xf00ff00f \| (f&0x00f000f0)<<1 \| (f>>1)&0x00f000f0`
f(V, W, X, Z, Y)		`f&0xff0000ff \| (f&0x0000ff00)<<8 \| (f>>8)&0x0000ff00`

Being able to swap a pair of adjacent inputs lets us consider all possible permutations by building them up one at a time. Again it is convenient to have a way to visit all permutations by applying only one swap at a time. Here Volume 4A comes to the rescue. Section 7.2.1.2 is titled “Generating All Permutations,” and Knuth delivers many algorithms to do just that. The most convenient for our purposes is Algorithm P, which generates a sequence that considers all permutations exactly once with only a single swap of adjacent inputs between steps. Knuth calls it Algorithm P because it corresponds to the “Plain changes” algorithm used by bell ringers in 17th century England to ring a set of bells in all possible permutations. The algorithm is described in a manuscript written around 1653!

We can examine all possible permutations and inversions by nesting a loop over all permutations inside a loop over all inversions, and in fact that's what my program does. Knuth does one better, though: his Exercise 7.2.1.2-20 suggests that it is possible to build up all the possibilities using only adjacent swaps and inversion of the first input. Negating arbitrary inputs is not hard, though, and still does minimal work, so the code sticks with Gray codes and Plain changes.

Zip Files All The Way Down

2010-03-18T00:00:00-04:00

Stephen Hawking begins A Brief History of Time with this story:

A well-known scientist (some say it was Bertrand Russell) once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: “What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise.” The scientist gave a superior smile before replying, “What is the tortoise standing on?” “You're very clever, young man, very clever,” said the old lady. “But it's turtles all the way down!”

Scientists today are pretty sure that the universe is not actually turtles all the way down, but we can create that kind of situation in other contexts. For example, here we have video monitors all the way down and set theory books all the way down, and shopping carts all the way down.

And here's a computer storage equivalent: look inside r.zip. It's zip files all the way down: each one contains another zip file under the name r/r.zip. (For the die-hard Unix fans, r.tar.gz is gzipped tar files all the way down.) Like the line of shopping carts, it never ends, because it loops back onto itself: the zip file contains itself! And it's probably less work to put together a self-reproducing zip file than to put together all those shopping carts, at least if you're the kind of person who would read this blog. This post explains how.

Before we get to self-reproducing zip files, though, we need to take a brief detour into self-reproducing programs.

Self-reproducing programs

The idea of self-reproducing programs dates back to the 1960s. My favorite statement of the problem is the one Ken Thompson gave in his 1983 Turing Award address:

In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program. Since this is an exercise divorced from reality, the usual vehicle was FORTRAN. Actually, FORTRAN was the language of choice for the same reason that three-legged races are popular.

More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source. If you have never done this, I urge you to try it on your own. The discovery of how to do it is a revelation that far surpasses any benefit obtained by being told how to do it. The part about “shortest” was just an incentive to demonstrate skill and determine a winner.

Spoiler alert! I agree: if you have never done this, I urge you to try it on your own. The internet makes it so easy to look things up that it's refreshing to discover something yourself once in a while. Go ahead and spend a few days figuring out. This blog will still be here when you get back. (If you don't mind the spoilers, the entire Turing award address is worth reading.)

(Spoiler blocker.)

http://www.robertwechsler.com/projects.html

Let's try to write a Python program that prints itself. It will probably be a print statement, so here's a first attempt, run at the interpreter prompt:

>>> print 'hello'
hello

That didn't quite work. But now we know what the program is, so let's print it:

>>> print "print 'hello'"
print 'hello'

That didn't quite work either. The problem is that when you execute a simple print statement, it only prints part of itself: the argument to the print. We need a way to print the rest of the program too.

The trick is to use recursion: you write a string that is the whole program, but with itself missing, and then you plug it into itself before passing it to print.

>>> s = 'print %s'; print s % repr(s)
print 'print %s'

Not quite, but closer: the problem is that the string s isn't actually the program. But now we know the general form of the program: s = '%s'; print s % repr(s). That's the string to use.

>>> s = 's = %s; print s %% repr(s)'; print s % repr(s)
s = 's = %s; print s %% repr(s)'; print s % repr(s)

Recursion for the win.

This form of self-reproducing program is often called a quine, in honor of the philosopher and logician W. V. O. Quine, who discovered the paradoxical sentence:

“Yields falsehood when preceded by its quotation”
yields falsehood when preceded by its quotation.

The simplest English form of a self-reproducing quine is a command like:

Print this, followed by its quotation:
“Print this, followed by its quotation:”

There's nothing particularly special about Python that makes quining possible. The most elegant quine I know is a Scheme program that is a direct, if somewhat inscrutable, translation of that sentiment:

((lambda (x) `(,x ',x))
'(lambda (x) `(,x ',x)))

I think the Go version is a clearer translation, at least as far as the quoting is concerned:

/* Go quine */
package main
import "fmt"
func main() {
 fmt.Printf("%s%c%s%c\n", q, 0x60, q, 0x60)
}
var q = `/* Go quine */
package main
import "fmt"
func main() {
 fmt.Printf("%s%c%s%c\n", q, 0x60, q, 0x60)
}
var q = `

(I've colored the data literals green throughout to make it clear what is program and what is data.)

The Go program has the interesting property that, ignoring the pesky newline at the end, the entire program is the same thing twice (/* Go quine */ ... q = `). That got me thinking: maybe it's possible to write a self-reproducing program using only a repetition operator. And you know what programming language has essentially only a repetition operator? The language used to encode Lempel-Ziv compressed files like the ones used by gzip and zip.

Self-reproducing Lempel-Ziv programs

Lempel-Ziv compressed data is a stream of instructions with two basic opcodes: literal(n) followed by n bytes of data means write those n bytes into the decompressed output, and repeat(d, n) means look backward d bytes from the current location in the decompressed output and copy the n bytes you find there into the output stream.

The programming exercise, then, is this: write a Lempel-Ziv program using just those two opcodes that prints itself when run. In other words, write a compressed data stream that decompresses to itself. Feel free to assume any reasonable encoding for the literal and repeat opcodes. For the grand prize, find a program that decompresses to itself surrounded by an arbitrary prefix and suffix, so that the sequence could be embedded in an actual gzip or zip file, which has a fixed-format header and trailer.

Spoiler alert! I urge you to try this on your own before continuing to read. It's a great way to spend a lazy afternoon, and you have one critical advantage that I didn't: you know there is a solution.

(Spoiler blocker.)

http://www.robertwechsler.com/thebest.html

By the way, here's r.gz, gzip files all the way down.

$ gunzip < r.gz > r
$ cmp r r.gz
$

The nice thing about r.gz is that even broken web browsers that ordinarily decompress downloaded gzip data before storing it to disk will handle this file correctly!

Enough stalling to hide the spoilers. Let's use this shorthand to describe Lempel-Ziv instructions: Ln and Rn are shorthand for literal(n) and repeat(n, n), and the program assumes that each code is one byte. L0 is therefore the Lempel-Ziv no-op; L5 hello prints hello; and so does L3 hel R1 L1 o.

Here's a Lempel-Ziv program that prints itself. (Each line is one instruction.)

	Code	Output
no-op	`L0`
no-op	`L0`
no-op	`L0`
print 4 bytes	`L4 L0 L0 L0 L4`	`L0 L0 L0 L4`
repeat last 4 printed bytes	`R4`	`L0 L0 L0 L4`
print 4 bytes	`L4 R4 L4 R4 L4`	`R4 L4 R4 L4`
repeat last 4 printed bytes	`R4`	`R4 L4 R4 L4`
print 4 bytes	`L4 L0 L0 L0 L0`	`L0 L0 L0 L0`

(The two columns Code and Output contain the same byte sequence.)

The interesting core of this program is the 6-byte sequence L4 R4 L4 R4 L4 R4, which prints the 8-byte sequence R4 L4 R4 L4 R4 L4 R4 L4. That is, it prints itself with an extra byte before and after.

When we were trying to write the self-reproducing Python program, the basic problem was that the print statement was always longer than what it printed. We solved that problem with recursion, computing the string to print by plugging it into itself. Here we took a different approach. The Lempel-Ziv program is particularly repetitive, so that a repeated substring ends up containing the entire fragment. The recursion is in the representation of the program rather than its execution. Either way, that fragment is the crucial point. Before the final R4, the output lags behind the input. Once it executes, the output is one code ahead.

The L0 no-ops are plugged into a more general variant of the program, which can reproduce itself with the addition of an arbitrary three-byte prefix and suffix:

	Code	Output
print 4 bytes	`L4 aa bb cc L4`	`aa bb cc L4`
repeat last 4 printed bytes	`R4`	`aa bb cc L4`
print 4 bytes	`L4 R4 L4 R4 L4`	`R4 L4 R4 L4`
repeat last 4 printed bytes	`R4`	`R4 L4 R4 L4`
print 4 bytes	`L4 R4 xx yy zz`	`R4 xx yy zz`
repeat last 4 printed bytes	`R4`	`R4 xx yy zz`

(The byte sequence in the Output column is aa bb cc, then the byte sequence from the Code column, then xx yy zz.)

It took me the better part of a quiet Sunday to get this far, but by the time I got here I knew the game was over and that I'd won. From all that experimenting, I knew it was easy to create a program fragment that printed itself minus a few instructions or even one that printed an arbitrary prefix and then itself, minus a few instructions. The extra aa bb cc in the output provides a place to attach such a program fragment. Similarly, it's easy to create a fragment to attach to the xx yy zz that prints itself, minus the first three instructions, plus an arbitrary suffix. We can use that generality to attach an appropriate header and trailer.

Here is the final program, which prints itself surrounded by an arbitrary prefix and suffix. [P] denotes the p-byte compressed form of the prefix P; similarly, [S] denotes the s-byte compressed form of the suffix S.

	Code	Output
print prefix	`[P]`	`P`
print p+1 bytes	`L`p+1 `[P] L`p+1	`[P] L`p+1
repeat last p+1 printed bytes	`R`p+1	`[P] L`p+1
print 1 byte	`L1 R`p+1	`R`p+1
print 1 byte	`L1 L1`	`L1`
print 4 bytes	`L4 R`p+1 `L1 L1 L4`	`R`p+1 `L1 L1 L4`
repeat last 4 printed bytes	`R4`	`R`p+1 `L1 L1 L4`
print 4 bytes	`L4 R4 L4 R4 L4`	`R4 L4 R4 L4`
repeat last 4 printed bytes	`R4`	`R4 L4 R4 L4`
print 4 bytes	`L4 R4 L0 L0 L`s+1	`R4 L0 L0 L`s+1
repeat last 4 printed bytes	`R4`	`R4 L0 L0 L`s+1
no-op	`L0`
no-op	`L0`
print s+1 bytes	`L`s+1 `R`s+1 `[S]`	`R`s+1 `[S]`
repeat last s+1 bytes	`R`s+1	`R`s+1 `[S]`
print suffix	`[S]`	`S`

(The byte sequence in the Output column is P, then the byte sequence from the Code column, then S.)

Self-reproducing zip files

Now the rubber meets the road. We've solved the main theoretical obstacle to making a self-reproducing zip file, but there are a couple practical obstacles still in our way.

The first obstacle is to translate our self-reproducing Lempel-Ziv program, written in simplified opcodes, into the real opcode encoding. RFC 1951 describes the DEFLATE format used in both gzip and zip: a sequence of blocks, each of which is a sequence of opcodes encoded using Huffman codes. Huffman codes assign different length bit strings to different opcodes, breaking our assumption above that opcodes have fixed length. But wait! We can, with some care, find a set of fixed-size encodings that says what we need to be able to express.

In DEFLATE, there are literal blocks and opcode blocks. The header at the beginning of a literal block is 5 bytes:

If the translation of our L opcodes above are 5 bytes each, the translation of the R opcodes must also be 5 bytes each, with all the byte counts above scaled by a factor of 5. (For example, L4 now has a 20-byte argument, and R4 repeats the last 20 bytes of output.) The opcode block with a single repeat(20,20) instruction falls well short of 5 bytes:

Luckily, an opcode block containing two repeat(20,10) instructions has the same effect and is exactly 5 bytes:

Encoding the other sized repeats (Rp+1 and Rs+1) takes more effort and some sleazy tricks, but it turns out that we can design 5-byte codes that repeat any amount from 9 to 64 bytes. For example, here are the repeat blocks for 10 bytes and for 40 bytes:

The repeat block for 10 bytes is two bits too short, but every repeat block is followed by a literal block, which starts with three zero bits and then padding to the next byte boundary. If a repeat block ends two bits short of a byte but is followed by a literal block, the literal block's padding will insert the extra two bits. Similarly, the repeat block for 40 bytes is five bits too long, but they're all zero bits. Starting a literal block five bits too late steals the bits from the padding. Both of these tricks only work because the last 7 bits of any repeat block are zero and the bits in the first byte of any literal block are also zero, so the boundary isn't directly visible. If the literal block started with a one bit, this sleazy trick wouldn't work.

The second obstacle is that zip archives (and gzip files) record a CRC32 checksum of the uncompressed data. Since the uncompressed data is the zip archive, the data being checksummed includes the checksum itself. So we need to find a value x such that writing x into the checksum field causes the file to checksum to x. Recursion strikes back.

The CRC32 checksum computation interprets the entire file as a big number and computes the remainder when you divide that number by a specific constant using a specific kind of division. We could go through the effort of setting up the appropriate equations and solving for x. But frankly, we've already solved one nasty recursive puzzle today, and enough is enough. There are only four billion possibilities for x: we can write a program to try each in turn, until it finds one that works.

If you want to recreate these files yourself, there are a few more minor obstacles, like making sure the tar file is a multiple of 512 bytes and compressing the rather large zip trailer to at most 59 bytes so that Rs+1 is at most R64. But they're just a simple matter of programming.

So there you have it: r.gz (gzip files all the way down), r.tar.gz (gzipped tar files all the way down), and r.zip (zip files all the way down). I regret that I have been unable to find any programs that insist on decompressing these files recursively, ad infinitum. It would have been fun to watch them squirm, but it looks like much less sophisticated zip bombs have spoiled the fun.

If you're feeling particularly ambitious, here is rgzip.go, the Go program that generated these files. I wonder if you can create a zip file that contains a gzipped tar file that contains the original zip file. Ken Thompson suggested trying to make a zip file that contains a slightly larger copy of itself, recursively, so that as you dive down the chain of zip files each one gets a little bigger. (If you do manage either of these, please leave a comment.)

P.S. I can't end the post without sharing my favorite self-reproducing program: the one-line shell script #!/bin/cat.

UTF-8: Bits, Bytes, and Benefits

2010-03-05T00:00:00-05:00

UTF-8 is a way to encode Unicode code points—integer values from 0 through 10FFFF—into a byte stream, and it is far simpler than many people realize. The easiest way to make it confusing or complicated is to treat it as a black box, never looking inside. So let's start by looking inside. Here it is:


Unicode code points		UTF-8 encoding (binary)

00-7F	(7 bits)	0tuvwxyz
0080-07FF	(11 bits)	110pqrst 10uvwxyz
0800-FFFF	(16 bits)	1110jklm 10npqrst 10uvwxyz
010000-10FFFF	(21 bits)	11110efg 10hijklm 10npqrst 10uvwxyz

The convenient properties of UTF-8 are all consequences of the choice of encoding.

All ASCII files are already UTF-8 files.
The first 128 Unicode code points are the 7-bit ASCII character set, and UTF-8 preserves their one-byte encoding.
ASCII bytes always represent themselves in UTF-8 files. They never appear as part of other UTF-8 sequences.
All the non-ASCII UTF-8 sequences consist of bytes with the high bit set, so if you see the byte 0x7A in a UTF-8 file, you can be sure it represents the character z.
ASCII bytes are always represented as themselves in UTF-8 files. They cannot be hidden inside multibyte UTF-8 sequences.
The ASCII z 01111010 cannot be encoded as a two-byte UTF-8 sequence 11000001 10111010. Code points must be encoded using the shortest possible sequence. A corollary is that decoders must detect long-winded sequences as invalid. In practice, it is useful for a decoder to use the Unicode replacement character, code point FFFD, as the decoding of an invalid UTF-8 sequence rather than stop processing the text.
UTF-8 is self-synchronizing.
Let's call a byte of the form 10xxxxxx a continuation byte. Every UTF-8 sequence is a byte that is not a continuation byte followed by zero or more continuation bytes. If you start processing a UTF-8 file at an arbitrary point, you might not be at the beginning of a UTF-8 encoding, but you can easily find one: skip over continuation bytes until you find a non-continuation byte. (The same applies to scanning backward.)
Substring search is just byte string search.
Properties 2, 3, and 4 imply that given a string of correctly encoded UTF-8, the only way those bytes can appear in a larger UTF-8 text is when they represent the same code points. So you can use any 8-bit safe byte at a time search function, like strchr or strstr, to run the search.
Most programs that handle 8-bit files safely can handle UTF-8 safely.
This also follows from Properties 2, 3, and 4. I say “most” programs, because programs that take apart a byte sequence expecting one character per byte will not behave correctly, but very few programs do that. It is far more common to split input at newline characters, or split whitespace-separated fields, or do other similar parsing around specific ASCII characters. For example, Unix tools like cat, cmp, cp, diff, echo, head, tail, and tee can process UTF-8 files as if they were plain ASCII files. Most operating system kernels should also be able to handle UTF-8 file names without any special arrangement, since the only operations done on file names are comparisons and splitting at /. In contrast, tools like grep, sed, and wc, which inspect arbitrary individual characters, do need modification.
UTF-8 sequences sort in code point order.
You can verify this by inspecting the encodings in the table above. This means that Unix tools like join, ls, and sort (without options) don't need to handle UTF-8 specially.
UTF-8 has no “byte order.”
UTF-8 is a byte encoding. It is not little endian or big endian. Unicode defines a byte order mark (BOM) code point FFFE, which are used to determine the byte order of a stream of raw 16-bit values, like UCS-2 or UTF-16. It has no place in a UTF-8 file. Some programs like to write a UTF-8-encoded BOM at the beginning of UTF-8 files, but this is unnecessary (and annoying to programs that don't expect it).

UTF-8 does give up the ability to do random access using code point indices. Programs that need to jump to the nth Unicode code point in a file or on a line—text editors are the canonical example—will typically convert incoming UTF-8 to an internal representation like an array of code points and then convert back to UTF-8 for output, but most programs are simpler when written to manipulate UTF-8 directly.

Programs that make UTF-8 more complicated than it needs to be are typically trying to be too general, not wanting to make assumptions that might not be true of other encodings. But there are good tools to convert other encodings to UTF-8, and it is slowly becoming the standard encoding: even the fraction of web pages written in UTF-8 is nearing 50%. UTF-8 was explicitly designed to have these nice properties. Take advantage of them.

For more on UTF-8, see “Hello World or Καλημέρα κόσμε or こんにちは世界,” by Rob Pike and Ken Thompson, and also this history.

Notes: Property 6 assumes the tools do not strip the high bit from each byte. Such mangling was common years ago but is very uncommon now. Property 7 assumes the comparison is done treating the bytes as unsigned, but such behavior is mandated by the ANSI C standard for memcmp, strcmp, and strncmp.

Computing History at Bell Labs

2008-04-09T00:00:00-04:00

In 1997, on his retirement from Bell Labs, Doug McIlroy gave a fascinating talk about the “History of Computing at Bell Labs.” Almost ten years ago I transcribed the audio but never did anything with it. The transcript is below.

My favorite parts of the talk are the description of the bi-quinary decimal relay calculator and the description of a team that spent over a year tracking down a race condition bug in a missile detector (reliability was king: today you'd just stamp “cannot reproduce” and send the report back). But the whole thing contains many fantastic stories. It's well worth the read or listen. I also like his recollection of programming using cards: “It's the kind of thing you can be nostalgic about, but it wasn't actually fun.”

For more information, Bernard D. Holbrook and W. Stanley Brown's 1982 technical report “A History of Computing Research at Bell Laboratories (1937-1975)” covers the earlier history in more detail.

Corrections added August 19, 2009. Links updated May 16, 2018.

Transcript of “History of Computing at Bell Labs:”

Computing at Bell Labs is certainly an outgrowth of the mathematics department, which grew from that first hiring in 1897, G A Campbell. When Bell Labs was formally founded in 1925, what it had been was the engineering department of Western Electric. When it was formally founded in 1925, almost from the beginning there was a math department with Thornton Fry as the department head, and if you look at some of Fry's work, it turns out that he was fussing around in 1929 with trying to discover information theory. It didn't actually gel until twenty years later with Shannon.

1:10 Of course, most of the mathematics at that time was continuous. One was interested in analyzing circuits and propagation. And indeed, this is what led to the growth of computing in Bell Laboratories. The computations could not all be done symbolically. There were not closed form solutions. There was lots of numerical computation done. The math department had a fair stable of computers, which in those days meant people. [laughter]

2:00 And in the late '30s, George Stibitz had an idea that some of the work that they were doing on hand calculators might be automated by using some of the equipment that the Bell System was installing in central offices, namely relay circuits. He went home, and on his kitchen table, he built out of relays a binary arithmetic circuit. He decided that binary was really the right way to compute. However, when he finally came to build some equipment, he determined that binary to decimal conversion and decimal to binary conversion was a drag, and he didn't want to put it in the equipment, and so he finally built in 1939, a relay calculator that worked in decimal, and it worked in complex arithmetic. Do you have a hand calculator now that does complex arithmetic? Ten-digit, I believe, complex computations: add, subtract, multiply, and divide. The I/O equipment was teletypes, so essentially all the stuff to make such machines out of was there. Since the I/O was teletypes, it could be remotely accessed, and there were in fact four stations in the West Street Laboratories of Bell Labs. West Street is down on the left side of Manhattan. I had the good fortune to work there one summer, right next to a district where you're likely to get bowled over by rolling ?beads? hanging from racks or tumbling ?cabbages?. The building is still there. It's called Westbeth Apartments. It's now an artist's colony.

4:29 Anyway, in West Street, there were four separate remote stations from which the complex calculator could be accessed. It was not time sharing. You actually reserved your time on the machine, and only one of the four terminals worked at a time. In 1940, this machine was shown off to the world at the AMS annual convention, which happened to be held in Hanover at Dartmouth that year, and mathematicians could wonder at remote computing, doing computation on an electromechanical calculator at 300 miles away.

5:22 Stibitz went on from there to make a whole series of relay machines. Many of them were made for the government during the war. They were named, imaginatively, Mark I through Mark VI. I have read some of his patents. They're kind of fun. One is a patent on conditional transfer. [laughter] And how do you do a conditional transfer? Well these gadgets were, the relay calculator was run from your fingers, I mean the complex calculator. The later calculators, of course, if your fingers were a teletype, you could perfectly well feed a paper tape in, because that was standard practice. And these later machines were intended really to be run more from paper tape. And the conditional transfer was this: you had two teletypes, and there's a code that says "time to read from the other teletype". Loops were of course easy to do. You take paper and [laughter; presumably Doug curled a piece of paper to form a physical loop]. These machines never got to the point of having stored programs. But they got quite big. I saw, one of them was here in 1954, and I did see it, behind glass, and if you've ever seen these machines in the, there's one in the Franklin Institute in Philadelphia, and there's one in the Science Museum in San Jose, you know these machines that drop balls that go wandering sliding around and turning battle wheels and ringing bells and who knows what. It kind of looked like that. It was a very quiet room, with just a little clicking of relays, which is what a central office used to be like. It was the one air-conditioned room in Murray Hill, I think. This machine ran, the Mark VI, well I think that was the Mark V, the Mark VI actually went to Aberdeen. This machine ran for a good number of years, probably six, eight. And it is said that it never made an undetected error. [laughter]

8:30 What that means is that it never made an error that it did not diagnose itself and stop. Relay technology was very very defensive. The telephone switching system had to work. It was full of self-checking, and so were the calculators, so were the calculators that Stibitz made.

9:04 Arithmetic was done in bi-quinary, a two out of five representation for decimal integers, and if there weren't exactly two out of five relays activated it would stop. This machine ran unattended over the weekends. People would bring their tapes in, and the operator would paste everybody's tapes together. There was a beginning of job code on the tape and there was also a time indicator. If the machine ran out of time, it automatically stopped and went to the next job. If the machine caught itself in an error, it backed up to the current job and tried it again. They would load this machine on Friday night, and on Monday morning, all the tapes, all the entries would be available on output tapes.

Question: I take it they were using a different representation for loops and conditionals by then.

Doug: Loops were done actually by they would run back and forth across the tape now, on this machine.

10:40 Then came the transistor in '48. At Whippany, they actually had a transistorized computer, which was a respectable minicomputer, a box about this big, running in 1954, it ran from 1954 to 1956 solidly as a test run. The notion was that this computer might fly in an airplane. And during that two-year test run, one diode failed. In 1957, this machine called TRADIC, did in fact fly in an airplane, but to the best of my knowledge, that machine was a demonstration machine. It didn't turn into a production machine. About that time, we started buying commercial machines. It's wonderful to think about the set of different architectures that existed in that time. The first machine we got was called a CPC from IBM. And all it was was a big accounting machine with a very special plugboard on the side that provided an interpreter for doing ten-digit decimal arithmetic, including opcodes for the trig functions and square root.

12:30 It was also not a computer as we know it today, because it wasn't stored program, it had twenty-four memory locations as I recall, and it took its program instead of from tapes, from cards. This was not a total advantage. A tape didn't get into trouble if you dropped it on the floor. [laughter]. CPC, the operator would stand in front of it, and there, you would go through loops by taking cards out, it took human intervention, to take the cards out of the output of the card reader and put them in the ?top?. I actually ran some programs on the CPC ?...?. It's the kind of thing you can be nostalgic about, but it wasn't actually fun. [laughter]

13:30 The next machine was an IBM 650, and here, this was a stored program, with the memory being on drum. There was no operating system for it. It came with a manual: this is what the machine does. And Michael Wolontis made an interpreter called the L1 interpreter for this machine, so you could actually program in, the manual told you how to program in binary, and L1 allowed you to give something like 10 for add and 9 for subtract, and program in decimal instead. And of course that machine required interesting optimization, because it was a nice thing if the next program step were stored somewhere -- each program step had the address of the following step in it, and you would try to locate them around the drum so to minimize latency. So there were all kinds of optimizers around, but I don't think Bell Labs made ?...? based on this called "soap" from Carnegie Mellon. That machine didn't last very long. Fortunately, a machine with core memory came out from IBM in about '56, the 704. Bell Labs was a little slow in getting one, in '58. Again, the machine came without an operating system. In fact, but it did have Fortran, which really changed the world. It suddenly made it easy to write programs. But the way Fortran came from IBM, it came with a thing called the Fortran Stop Book. This was a list of what happened, a diagnostic would execute the halt instruction, the operator would go read the panel lights and discover where the machine had stopped, you would then go look up in the stop book what that meant. Bell Labs, with George Mealy and Glenn Hanson, made an operating system, and one of the things they did was to bring the stop book to heel. They took the compiler, replaced all the stop instructions with jumps to somewhere, and allowed the program instead of stopping to go on to the next trial. By the time I arrived at Bell Labs in 1958, this thing was running nicely.

16:36 Bell Labs continued to be a major player in operating systems. This was called BESYS. BE was the share abbreviation for Bell Labs. Each company that belonged to Share, which was the IBM users group, ahd a two letter abbreviation. It's hard to imagine taking all the computer users now and giving them a two-letter abbreviation. BESYS went through many generations, up to BESYS 5, I believe. Each one with innovations. IBM delivered a machine, the 7090, in 1960. This machine had interrupts in it, but IBM didn't use them. But BESYS did. And that sent IBM back to the drawing board to make it work. [Laughter]

17:48 Rob Pike: It also didn't have memory protection.

Doug: It didn't have memory protection either, and a lot of people actually got IBM to put memory protection in the 7090, so that one could leave the operating system resident in the presence of a wild program, an idea that the PC didn't discover until, last year or something like that. [laughter]

Big players then, Dick Hamming, a name that I'm sure everybody knows, was sort of the numerical analysis guru, and a seer. He liked to make outrageous predictions. He predicted in 1960, that half of Bell Labs was going to be busy doing something with computers eventually. ?...? exaggerating some ?...? abstract in his thought. He was wrong. Half was a gross underestimate. Dick Hamming retired twenty years ago, and just this June he completed his full twenty years term in the Navy, which entitles him again to retire from the Naval Postgraduate Institute in Monterey. Stibitz, incidentally died, I think within the last year. He was doing medical instrumentation at Dartmouth essentially, near the end.

20:00 Various problems intrigued, besides the numerical problems, which in fact were stock in trade, and were the real justification for buying machines, until at least the '70s I would say. But some non-numerical problems had begun to tickle the palette of the math department. Even G A Campbell got interested in graph theory, the reason being he wanted to think of all the possible ways you could take the three wires and the various parts of the telephone and connect them together, and try permutations to see what you could do about reducing side ?...? by putting things into the various parts of the circuit, and devised every possibly way of connecting the telephone up. And that was sort of the beginning of combinatorics at Bell Labs. John Reardon, a mathematician parlayed this into a major subject. Two problems which are now deemed as computing problems, have intrigued the math department for a very long time, and those are the minimum spanning tree problem, and the wonderfully ?comment about Joe Kruskal, laughter?

21:50 And in the 50s Bob Prim and Kruskal, who I don't think worked on the Labs at that point, invented algorithms for the minimum spanning tree. Somehow or other, computer scientists usually learn these algorithms, one of the two at least, as Dijkstra's algorithm, but he was a latecomer.

Another pet was the traveling salesman. There's been a long list of people at Bell Labs who played with that: Shen Lin and Ron Graham and David Johnson and dozens more, oh and ?...?. And then another problem is the Steiner minimum spanning tree, where you're allowed to add points to the graph. Every one of these problems grew, actually had a justification in telephone billing. One jurisdiction or another would specify that the way you bill for a private line network was in one jurisdiction by the minimum spanning tree. In another jurisdiction, by the traveling salesman route. NP-completeness wasn't a word in the vocabulary of ?...? [laughter]. And the Steiner problem came up because customers discovered they could beat the system by inventing offices in the middle of Tennessee that had nothing to do with their business, but they could put the office at a Steiner point and reduce their phone bill by adding to what the service that the Bell System had to give them. So all of these problems actually had some justification in billing besides the fun.

24:15 Come the 60s, we actually started to hire people for computing per se. I was perhaps the third person who was hired with a Ph.D. to help take care of the computers and I'm told that the then director and head of the math department, Hendrick Bode, had said to his people, "yeah, you can hire this guy, instead of a real mathematician, but what's he gonna be doing in five years?" [laughter]

25:02 Nevertheless, we started hiring for real in about '67. Computer science got split off from the math department. I had the good fortune to move into the office that I've been in ever since then. Computing began to make, get a personality of its own. One of the interesting people that came to Bell Labs for a while was Hao Wang. Is his name well known? [Pause] One nod. Hao Wang was a philosopher and logician, and we got a letter from him in England out of the blue saying "hey you know, can I come and use your computers? I have an idea about theorem proving." There was theorem proving in the air in the late 50s, and it was mostly pretty thin stuff. Obvious that the methods being proposed wouldn't possibly do anything more difficult than solve tic-tac-toe problems by enumeration. Wang had a notion that he could mechanically prove theorems in the style of Whitehead and Russell's great treatise Principia Mathematica in the early patr of the century. He came here, learned how to program in machine language, and took all of Volume I of Principia Mathematica -- if you've ever hefted Principia, well that's about all it's good for, it's a real good door stop. It's really big. But it's theorem after theorem after theorem in propositional calculus. Of course, there's a decision procedure for propositional calculus, but he was proving them more in the style of Whitehead and Russell. And when he finally got them all coded and put them into the computer, he proved the entire contents of this immense book in eight minutes. This was actually a neat accomplishment. Also that was the beginning of all the language theory. We hired people like Al Aho and Jeff Ullman, who probed around every possible model of grammars, syntax, and all of the things that are now in the standard undergraduate curriculum, were pretty well nailed down here, on syntax and finite state machines and so on were pretty well nailed down in the 60s. Speaking of finite state machines, in the 50s, both Mealy and Moore, who have two of the well-known models of finite state machines, were here.

28:40 During the 60s, we undertook an enormous development project in the guise of research, which was MULTICS, and it was the notion of MULTICS was computing was the public utility of the future. Machines were very expensive, and ?indeed? like you don't own your own electric generator, you rely on the power company to do generation for you, and it was seen that this was a good way to do computing -- time sharing -- and it was also recognized that shared data was a very good thing. MIT pioneered this and Bell Labs joined in on the MULTICS project, and this occupied five years of system programming effort, until Bell Labs pulled out, because it turned out that MULTICS was too ambitious for the hardware at the time, and also with 80 people on it was not exactly a research project. But, that led to various people who were on the project, in particular Ken Thompson -- right there -- to think about how to -- Dennis Ritchie and Rudd Canaday were in on this too -- to think about how you might make a pleasant operating system with a little less resources.

30:30 And Ken found -- this is a story that's often been told, so I won't go into very much of unix -- Ken found an old machine cast off in the corner, the PDP-7, and put up this little operating system on it, and we had immense GE635 available at the comp center at the time, and I remember as the department head, muscling in to use this little computer to be, to get to be Unix's first user, customer, because it was so much pleasanter to use this tiny machine than it was to use the big and capable machine in the comp center. And of course the rest of the story is known to everybody and has affected all college campuses in the country.

31:33 Along with the operating system work, there was a fair amount of language work done at Bell Labs. Often curious off-beat languages. One of my favorites was called Blodi, B L O D I, a block diagram compiler by Kelly and Vyssotsky. Perhaps the most interesting early uses of computers in the sense of being unexpected, were those that came from the acoustics research department, and what the Blodi compiler was invented in the acoustic research department for doing digital simulations of sample data system. DSPs are classic sample data systems, where instead of passing analog signals around, you pass around streams of numerical values. And Blodi allowed you to say here's a delay unit, here's an amplifier, here's an adder, the standard piece parts for a sample data system, and each one was described on a card, and with description of what it's wired to. It was then compiled into one enormous single straight line loop for one time step. Of course, you had to rearrange the code because some one part of the sample data system would feed another and produce really very efficient 7090 code for simulating sample data systems. By in large, from that time forth, the acoustic department stopped making hardware. It was much easier to do signal processing digitally than previous ways that had been analog. Blodi had an interesting property. It was the only programming language I know where -- this is not my original observation, Vyssotsky said -- where you could take the deck of cards, throw it up the stairs, and pick them up at the bottom of the stairs, feed them into the computer again, and get the same program out. Blodi had two, aside from syntax diagnostics, it did have one diagnostic when it would fail to compile, and that was "somewhere in your system is a loop that consists of all delays or has no delays" and you can imagine how they handled that.

35:09 Another interesting programming language of the 60s was Ken Knowlten's Beflix. This was for making movies on something with resolution kind of comparable to 640x480, really coarse, and the programming notion in here was bugs. You put on your grid a bunch of bugs, and each bug carried along some data as baggage, and then you would do things like cellular automata operations. You could program it or you could kind of let it go by itself. If a red bug is next to a blue bug then it turns into a green bug on the following step and so on. 36:28 He and Lillian Schwartz made some interesting abstract movies at the time. It also did some interesting picture processing. One wonderful picture of a reclining nude, something about the size of that blackboard over there, all made of pixels about a half inch high each with a different little picture in it, picked out for their density, and so if you looked at it close up it consisted of pickaxes and candles and dogs, and if you looked at it far enough away, it was a reclining nude. That picture got a lot of play all around the country.

Lorinda Cherry: That was with Leon, wasn't it? That was with Leon Harmon.

Doug: Was that Harmon?

Lorinda: ?...?

Doug: Harmon was also an interesting character. He did more things than pictures. I'm glad you reminded me of him. I had him written down here. Harmon was a guy who among other things did a block diagram compiler for writing a handwriting recognition program. I never did understand how his scheme worked, and in fact I guess it didn't work too well. [laughter] It didn't do any production ?things? but it was an absolutely immense sample data circuit for doing handwriting recognition. Harmon's most famous work was trying to estimate the information content in a face. And every one of these pictures which are a cliche now, that show a face digitized very coarsely, go back to Harmon's first psychological experiments, when he tried to find out how many bits of picture he needed to try to make a face recognizable. He went around and digitized about 256 faces from Bell Labs and did real psychological experiments asking which faces could be distinguished from other ones. I had the good fortune to have one of the most distinguishable faces, and consequently you'll find me in freshman psychology texts through no fault of my own.

39:15 Another thing going on the 60s was the halting beginning here of interactive computing. And again the credit has to go to the acoustics research department, for good and sufficient reason. They wanted to be able to feed signals into the machine, and look at them, and get them back out. They bought yet another weird architecture machine called the Packard Bell 250, where the memory elements were mercury delay lines.

Question: Packard Bell?

Doug: Packard Bell, same one that makes PCs today.

40:10 They hung this off of the comp center 7090 and put in a scheme for quickly shipping jobs into the job stream on the 7090. The Packard Bell was the real-time terminal that you could play with and repair stuff, ?...? off the 7090, get it back, and then you could play it. From that grew some graphics machines also, built by ?...? et al. And it was one of the old graphics machines in fact that Ken picked up to build Unix on.

40:55 Another thing that went on in the acoustics department was synthetic speech and music. Max Mathews, who was the the director of the department has long been interested in computer music. In fact since retirement he spent a lot of time with Pierre Boulez in Paris at a wonderful institute with lots of money simply for making synthetic music. He had a language called Music 5. Synthetic speech or, well first of all simply speech processing was pioneered particularly by John Kelly. I remember my first contact with speech processing. It was customary for computer operators, for the benefit of computer operators, to put a loudspeaker on the low bit of some register on the machine, and normally the operator would just hear kind of white noise. But if you got into a loop, suddenly the machine would scream, and this signal could be used to the operator "oh the machines in a loop. Go stop it and go on to the next job." I remember feeding them an Ackermann's function routine once. [laughter] They were right. It was a silly loop. But anyway. One day, the operators were ?...?. The machine started singing. Out of the blue. “Help! I'm caught in a loop.”. [laughter] And in a broad Texas accent, which was the recorded voice of John Kelly.

43:14 However. From there Kelly went on to do some speech synthesis. Of course there's been a lot more speech synthesis work done since, by 43:31 folks like Cecil Coker, Joe Olive. But they produced a record, which unfortunately I can't play because records are not modern anymore. And everybody got one in the Bell Labs Record, which is a magazine, contained once a record from the acoustics department, with both speech and music and one very famous combination where the computer played and sang "A Bicycle Built For Two".

?...?

44:32 At the same time as all this stuff is going on here, needless to say computing is going on in the rest of the Labs. it was about early 1960 when the math department lost its monopoly on computing machines and other people started buying them too, but for switching. The first experiments with switching computers were operational in around 1960. They were planned for several years prior to that; essentially as soon as the transistor was invented, the making of electronic rather than electromechanical switching machines was anticipated. Part of the saga of the switching machines is cheap memory. These machines had enormous memories -- thousands of words. [laughter] And it was said that the present worth of each word of memory that programmers saved across the Bell System was something like eleven dollars, as I recall. And it was worthwhile to struggle to save some memory. Also, programs were permanent. You were going to load up the switching machine with switching program and that was going to run. You didn't change it every minute or two. And it would be cheaper to put it in read only memory than in core memory. And there was a whole series of wild read-only memories, both tried and built. The first experimental Essex System had a thing called the flying spot store which was large photographic plates with bits on them and CRTs projecting on the plates and you would detect underneath on the photodetector whether the bit was set or not. That was the program store of Essex. The program store of the first ESS systems consisted of twistors, which I actually am not sure I understand to this day, but they consist of iron wire with a copper wire wrapped around them and vice versa. There were also experiments with an IC type memory called the waffle iron. Then there was a period when magnetic bubbles were all the rage. As far as I know, although microelectronics made a lot of memory, most of the memory work at Bell Labs has not had much effect on ?...?. Nice tries though.

48:28 Another thing that folks began to work on was the application of (and of course, right from the start) computers to data processing. When you owned equipment scattered through every street in the country, and you have a hundred million customers, and you have bills for a hundred million transactions a day, there's really some big data processing going on. And indeed in the early 60s, AT&T was thinking of making its own data processing computers solely for billing. Somehow they pulled out of that, and gave all the technology to IBM, and one piece of that technology went into use in high end equipment called tractor tapes. Inch wide magnetic tapes that would be used for a while.

49:50 By in large, although Bell Labs has participated until fairly recently in data processing in quite a big way, AT&T never really quite trusted the Labs to do it right because here is where the money is. I can recall one occasion when during strike of temporary employees, a fill-in employee like from the Laboratories and so on, lost a day's billing tape in Chicago. And that was a million dollars. And that's generally speaking the money people did not until fairly recently trust Bell Labs to take good care of money, even though they trusted the Labs very well to make extremely reliable computing equipment for switches. The downtime on switches is still spectacular by any industry standards. The design for the first ones was two hours down in 40 years, and the design was met. Great emphasis on reliability and redundancy, testing.

51:35 Another branch of computing was for the government. The whole Whippany Laboratories [time check] Whippany, where we took on contracts for the government particularly in the computing era in anti-missile defense, missile defense, and underwater sound. Missile defense was a very impressive undertaking. It was about in the early '63 time frame when it was estimated the amount of computation to do a reasonable job of tracking incoming missiles would be 30 M floating point operations a second. In the day of the Cray that doesn't sound like a great lot, but it's more than your high end PCs can do. And the machines were supposed to be reliable. They designed the machines at Whippany, a twelve-processor multiprocessor, to no specs, enormously rugged, one watt transistors. This thing in real life performed remarkably well. There were sixty-five missile shots, tests across the Pacific Ocean ?...? and Lorinda Cherry here actually sat there waiting for them to come in. [laughter] And only a half dozen of them really failed. As a measure of the interest in reliability, one of them failed apparently due to processor error. Two people were assigned to look at the dumps, enormous amounts of telemetry and logging information were taken during these tests, which are truly expensive to run. Two people were assigned to look at the dumps. A year later they had not found the trouble. The team was beefed up. They finally decided that there was a race condition in one circuit. They then realized that this particular kind of race condition had not been tested for in all the simulations. They went back and simulated the entire hardware system to see if its a remote possibility of any similar cases, found twelve of them, and changed the hardware. But to spend over a year looking for a bug is a sign of what reliability meant.

54:56 Since I'm coming up on the end of an hour, one could go on and on and on,

Crowd: go on, go on. [laughter]

55:10 Doug: I think I'd like to end up by mentioning a few of the programs that have been written at Bell Labs that I think are most surprising. Of course there are lots of grand programs that have been written.

I already mentioned the block diagram compiler.

Another really remarkable piece of work was eqn, the equation typesetting language, which has been imitated since, by Lorinda Cherry and Brian Kernighan. The notion of taking an auditory syntax, the way people talk about equations, but only talk, this was not borrowed from any written notation before, getting the auditory one down on paper, that was very successful and surprising.

Another of my favorites, and again Lorinda Cherry was in this one, with Bob Morris, was typo. This was a program for finding spelling errors. It didn't know the first thing about spelling. It would read a document, measure its statistics, and print out the words of the document in increasing order of what it thought the likelihood of that word having come from the same statistical source as the document. The words that did not come from the statistical source of the document were likely to be typos, and now I mean typos as distinct from spelling errors, where you actually hit the wrong key. Those tend to be off the wall, whereas phonetic spelling errors you'll never find. And this worked remarkably well. Typing errors would come right up to the top of the list. A really really neat program.

57:50 Another one of my favorites was by Brenda Baker called struct, which took Fortran programs and converted them into a structured programming language called Ratfor, which was Fortran with C syntax. This seemed like a possible undertaking, like something you do by the seat of the pants and you get something out. In fact, folks at Lockheed had done things like that before. But Brenda managed to find theorems that said there's really only one form, there's a canonical form into which you can structure a Fortran program, and she did this. It took your Fortran program, completely mashed it, put it out perhaps in almost certainly a different order than it was in Fortran connected by GOTOs, without any GOTOs, and the really remarkable thing was that authors of the program who clearly knew the way they wrote it in the first place, preferred it after it had been rearranged by Brendan. I was astonished at the outcome of that project.

59:19 Another first that happened around here was by Fred Grampp, who got interested in computer security. One day he decided he would make a program for sniffing the security arrangements on a computer, as a service: Fred would never do anything crooked. [laughter] This particular program did a remarkable job, and founded a whole minor industry within the company. A department was set up to take this idea and parlay it, and indeed ever since there has been some improvement in the way computer centers are managed, at least until we got Berkeley Unix.

60:24 And the last interesting program that I have time to mention is one by Ken Church. He was dealing with -- text processing has always been a continuing ?...? of the research, and in some sense it has an application to our business because we're handling speech, but he got into consulting with the department in North Carolina that has to translate manuals. There are millions of pages of manuals in the Bell System and its successors, and ever since we've gone global, these things had to get translated into many languages.

61:28 To help in this, he was making tools which would put up on the screen, graphed on the screen quickly a piece of text and its translation, because a translator, particularly a technical translator, wants to know, the last time we mentioned this word how was it translated. You don't want to be creative in translating technical text. You'd like to be able to go back into the archives and pull up examples of translated text. And the neat thing here is the idea for how do you align texts in two languages. You've got the original, you've got the translated one, how do you bring up on the screen, the two sentences that go together? And the following scam worked beautifully. This is on western languages. 62:33 Simply look for common four letter tetragrams, four letter combinations between the two and as best as you can, line them up as nearly linearly with the lengths of the two types as possible. And this very simple idea works like storm. Something for nothing. I like that.

63:10 The last thing is one slogan that sort of got started with Unix and is just rife within the industry now. Software tools. We were making software tools in Unix before we knew we were, just like the Molière character was amazed at discovering he'd been speaking prose all his life. [laughter] But then Kernighan and Plauger came along and christened what was going on, making simple generally useful and compositional programs to do one thing and do it well and to fit together. They called it software tools, made a book, wrote a book, and this notion now is abroad in the industry. And it really did begin all up in the little attic room where you [points?] sat for many years writing up here.

Oh I forgot to. I haven't used any slides. I've brought some, but I don't like looking at bullets and you wouldn't either, and I forgot to show you the one exhibit I brought, which I borrowed from Bob Kurshan. When Bell Labs was founded, it had of course some calculating machines, and it had one wonderful computer. This. That was bought in 1918. There's almost no other computing equipment from any time prior to ten years ago that still exists in Bell Labs. This is an integraph. It has two styluses. You trace a curve on a piece of paper with one stylus and the other stylus draws the indefinite integral here. There was somebody in the math department who gave this service to the whole company, with about 24 hours turnaround time, calculating integrals. Our recent vice president Arno Penzias actually did, he calculated integrals differently, with a different background. He had a chemical balance, and he cut the curves out of the paper and weighed them. This was bought in 1918, so it's eighty years old. It used to be shiny metal, it's a little bit rusty now. But it still works.

66:30 Well, that's a once over lightly of a whole lot of things that have gone on at Bell Labs. It's just such a fun place that one I said I just could go on and on. If you're interested, there actually is a history written. This is only one of about six volumes, this is the one that has the mathematical computer sciences, the kind of things that I've mostly talked about here. A few people have copies of them. For some reason, the AT&T publishing house thinks that because they're history they're obsolete, and they stopped printing them. [laughter]

Thank you, and that's all.

Using Uninitialized Memory for Fun and Profit

2008-03-14T00:00:00-04:00

This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improvements: some important operations change from linear to constant time.

Alfred Aho, John Hopcroft, and Jeffrey Ullman's 1974 book The Design and Analysis of Computer Algorithms hints at the trick in an exercise (Chapter 2, exercise 2.12):

Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(||V||²) time to initialize an adjacency matrix.

Jon Bentley's 1986 book Programming Pearls expands on the exercise (Column 1, exercise 8; exercise 9 in the Second Edition):

One problem with trading more space for less time is that initializing the space can itself take a great deal of time. Show how to circumvent this problem by designing a technique to initialize an entry of a vector to zero the first time it is accessed. Your scheme should use constant time for initialization and each vector access; you may use extra space proportional to the size of the vector. Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is dear, and the vector is sparse.

Aho, Hopcroft, and Ullman's exercise talks about a matrix and Bentley's exercise talks about a vector, but for now let's consider just a simple set of integers.

One popular representation of a set of n integers ranging from 0 to m is a bit vector, with 1 bits at the positions corresponding to the integers in the set. Adding a new integer to the set, removing an integer from the set, and checking whether a particular integer is in the set are all very fast constant-time operations (just a few bit operations each). Unfortunately, two important operations are slow: iterating over all the elements in the set takes time O(m), as does clearing the set. If the common case is that m is much larger than n (that is, the set is only sparsely populated) and iterating or clearing the set happens frequently, then it could be better to use a representation that makes those operations more efficient. That's where the trick comes in.

Preston Briggs and Linda Torczon's 1993 paper, “An Efficient Representation for Sparse Sets,” describes the trick in detail. Their solution represents the sparse set using an integer array named dense and an integer n that counts the number of elements in dense. The dense array is simply a packed list of the elements in the set, stored in order of insertion. If the set contains the elements 5, 1, and 4, then n = 3 and dense[0] = 5, dense[1] = 1, dense[2] = 4:

Together n and dense are enough information to reconstruct the set, but this representation is not very fast. To make it fast, Briggs and Torczon add a second array named sparse which maps integers to their indices in dense. Continuing the example, sparse[5] = 0, sparse[1] = 1, sparse[4] = 2. Essentially, the set is a pair of arrays that point at each other:

Adding a member to the set requires updating both of these arrays:

add-member(i):
    dense[n] = i
    sparse[i] = n
    n++

It's not as efficient as flipping a bit in a bit vector, but it's still very fast and constant time.

To check whether i is in the set, you verify that the two arrays point at each other for that element:

is-member(i):
    return sparse[i] < n && dense[sparse[i]] == i

If i is not in the set, then it doesn't matter what sparse[i] is set to: either sparse[i] will be bigger than n or it will point at a value in dense that doesn't point back at it. Either way, we're not fooled. For example, suppose sparse actually looks like:

Is-member knows to ignore members of sparse that point past n or that point at cells in dense that don't point back, ignoring the grayed out entries:

Notice what just happened: sparse can have any arbitrary values in the positions for integers not in the set, those values actually get used during membership tests, and yet the membership test behaves correctly! (This would drive valgrind nuts.)

Clearing the set can be done in constant time:

clear-set():
    n = 0

Zeroing n effectively clears dense (the code only ever accesses entries in dense with indices less than n), and sparse can be uninitialized, so there's no need to clear out the old values.

This sparse set representation has one more trick up its sleeve: the dense array allows an efficient implementation of set iteration.

iterate():
    for(i=0; i<n; i++)
        yield dense[i]

Let's compare the run times of a bit vector implementation against the sparse set:

Operation	Bit Vector	Sparse set
is-member	O(1)	O(1)
add-member	O(1)	O(1)
clear-set	O(m)	O(1)
iterate	O(m)	O(n)

The sparse set is as fast or faster than bit vectors for every operation. The only problem is the space cost: two words replace each bit. Still, there are times when the speed differences are enough to balance the added memory cost. Briggs and Torczon point out that liveness sets used during register allocation inside a compiler are usually small and are cleared very frequently, making sparse sets the representation of choice.

Another situation where sparse sets are the better choice is work queue-based graph traversal algorithms. Iteration over sparse sets visits elements in the order they were inserted (above, 5, 1, 4), so that new entries inserted during the iteration will be visited later in the same iteration. In contrast, iteration over bit vectors visits elements in integer order (1, 4, 5), so that new elements inserted during traversal might be missed, requiring repeated iterations.

Returning to the original exercises, it is trivial to change the set into a vector (or matrix) by making dense an array of index-value pairs instead of just indices. Alternately, one might add the value to the sparse array or to a new array. The relative space overhead isn't as bad if you would have been storing values anyway.

Briggs and Torczon's paper implements additional set operations and examines performance speedups from using sparse sets inside a real compiler.

Play Tic-Tac-Toe with Knuth

2008-01-25T00:00:00-05:00

Section 7.1.2 of the Volume 4 pre-fascicle 0A of Donald Knuth's The Art of Computer Programming is titled “Boolean Evaluation.” In it, Knuth considers the construction of a set of nine boolean functions telling the correct next move in an optimal game of tic-tac-toe. In a footnote, Knuth tells this story:

This setup is based on an exhibit from the early 1950s at the Museum of Science and Industry in Chicago, where the author was first introduced to the magic of switching circuits. The machine in Chicago, designed by researchers at Bell Telephone Laboratories, allowed me to go first; yet I soon discovered there was no way to defeat it. Therefore I decided to move as stupidly as possible, hoping that the designers had not anticipated such bizarre behavior. In fact I allowed the machine to reach a position where it had two winning moves; and it seized both of them! Moving twice is of course a flagrant violation of the rules, so I had won a moral victory even though the machine had announced that I had lost.

That story alone is fairly amusing. But turning the page, the reader finds a quotation from Charles Babbage's Passages from the Life of a Philosopher, published in 1864:

I commenced an examination of a game called “tit-tat-to” ... to ascertain what number of combinations were required for all the possible variety of moves and situations. I found this to be comparatively insignificant. ... A difficulty, however, arose of a novel kind. When the automaton had to move, it might occur that there were two different moves, each equally conducive to his winning the game. ... Unless, also, some provision were made, the machine would attempt two contradictory motions.

The only real winning move is not to play.

Crabs, the bitmap terror!

2008-01-09T00:00:00-05:00

Today, window systems seem as inevitable as hierarchical file systems, a fundamental building block of computer systems. But it wasn't always that way. This paper could only have been written in the beginning, when everything about user interfaces was up for grabs.

A bitmap screen is a graphic universe where windows, cursors and icons live in harmony, cooperating with each other to achieve functionality and esthetics. A lot of effort goes into making this universe consistent, the basic law being that every window is a self contained, protected world. In particular, (1) a window shall not be affected by the internal activities of another window. (2) A window shall not be affected by activities of the window system not concerning it directly, i.e. (2.1) it shall not notice being obscured (partially or totally) by other windows or obscuring (partially or totally) other windows, (2.2) it shall not see the image of the cursor sliding on its surface (it can only ask for its position).

Of course it is difficult to resist the temptation to break these rules. Violations can be destructive or non-destructive, useful or pointless. Useful non-destructive violations include programs printing out an image of the screen, or magnifying part of the screen in a lens window. Useful destructive violations are represented by the pen program, which allows one to scribble on the screen. Pointless non-destructive violations include a magnet program, where a moving picture of a magnet attracts the cursor, so that one has to continuously pull away from it to keep working. The first pointless, destructive program we wrote was crabs.

As the crabs walk over the screen, they leave gray behind, “erasing” the apps underfoot:

For the rest of the story, see Luca Cardelli's “Crabs: the bitmap terror!” (6.7MB). Additional details in “Crabs (History and Screen Dumps)” (57.1MB).