Path-Sensitive

Let’s face it, programming books suck. Those general books on distributed systems or data science or whatever can be tomes for a lifetime, but, with few exceptions, there’s something about the books on how to write code in a language/framework/database/cupcake-maker, the ones with the animal covers and the cutesy sample apps, they just tend to be so forgettable, so trite, so….uneducational.

I think I’ve figured out why I don’t like them, and it’s not just that they teach skills rapidly approaching expiration. It’s their pedagogical approach. The teaching algorithm seems to be: write these programs where we’ve told you everything to do, and you’ll come out knowing this language/framework/database/cupcake-maker. Central to these books are the long code listings for the reader to reproduce. Here’s an example, from one of the better books in this category

class User < ApplicationRecord
  attr_accessor :remember_token
  before_save { self.email = email.downcase }
  validates :name,  presence: true, length: { maximum: 50 }
  VALID_EMAIL_REGEX = /\A[\w+\-.]+@[a-z\d\-.]+\.[a-z]+\z/i
  validates :email, presence: true, length: { maximum: 255 },
                    format: { with: VALID_EMAIL_REGEX },
                    uniqueness: { case_sensitive: false }
  has_secure_password
  validates :password, presence: true, length: { minimum: 6 }

  # …another 30 lines follows...
end

Traditionally, there are two ways to study a page like this:

1. Type out every line of code 
2. Copy+paste the code from their website, maybe play around and make small changes 

Approach #1 is a method that, like a lecture, causes the code to go from the author’s page to the reader’s screen without passing through the heads of either. The second is like trying to learn how to make a car by taking apart a seatbelt and stereo: you’re just toying with small pieces. Neither is a sound way to learn.

If you had an expert tutor, they wouldn’t teach you by handing you a page of code. Still, these books are what we have. How can we read them in a way that follows the principles of learning? Read on.

Mental Representations

According to K. Anders Ericsson in his book Peak, expertise is a process of building mental representations. We can see this because expert minds store knowledge in a compressed fashion. Musicians can memorize a page of music far faster than a page of random notes. Expert chess players told to memorize a board position will do much better than amateurs, but, when they make a mistake, they’ll misplace whole groups of pieces.

This is possible because music and chess positions have structure that makes them look very different from a page of random notes or a random permutation of pieces. Technically speaking, they have lower perplexity than random noise. So, even though there are 26 letters in the English alphabet, Claude Shannon showed that the information content of English is about 1 bit per letter: given a random prefix of a paragraph, people can guess the next letter about half the time.

This is why a programmer skilled in a technology can look at code using it and read through it like fiction, only pausing at the surprising bits, while the novice is laboring line-by-line. This is also why a smart code-completion tool can guess a long sequence of code from the first couple lines. With a better mental representation, understanding code is simply less work.

(How do these mental representations work? My officemate Zenna Tavares argues they are distribution-sensitive data structures.)

This is exactly what’s missing from the “just type out the code” approach: there’s nothing forcing your mind to represent the program as anything better than a sequence of characters. Yet being able to force your mind to do this would mean being able to learn concepts more rapidly. Here’s a 200 year-old idea for doing so.

The Benjamin Franklin Method

I don’t know what’s more impressive: that Benjamin Franklin became a luminary in everything from politics to physics, or that he did this without modern educational techniques such as schools, teachers, or StackOverflow. As part of this, he discovered a powerful method of self-study. I’ll let him speak for himself (or go read someone else’s summary).

About this time I met with an odd volume of the Spectator. It was the third. I had never before seen any of them. I bought it, read it over and over, and was much delighted with it. I thought the writing excellent, and wished, if possible, to imitate it. With this view I took some of the papers, and, making short hints of the sentiment in each sentence, laid them by a few days, and then, without looking at the book, try'd to compleat the papers again, by expressing each hinted sentiment at length, and as fully as it had been expressed before, in any suitable words that should come to hand. Then I compared my Spectator with the original, discovered some of my faults, and corrected them.

—Benjamin Franklin, Autobiography

This process is a little bit like being a human autoencoder. An autoencoder is a neural network that tries to produce output the same as its input, but passing through an intermediate layer which is too small to fully represent the data. In doing so, it’s forced to learn a more compact representation. Here, the neural net in question is that den of dendrons in your head.

K. Anders Ericsson likens it to how artists practice by trying to imitate some famous work. Mathematicians are taught to attempt to prove most theorems themselves when reading a book or paper --- even if they can’t, they’ll have an easier time compressing the proof to its basic insight. I used this process to get a better eye for graphical design; it was like LASIK.

But the basic idea, applied to programming books and streamlined, is particularly simple yet effective.

Here’s how it works:

Read your programming book as normal. When you get to a code sample, read it over

Then close the book.

Then try to type it up.

Simple, right? But try it and watch as you’re forced to learn some of the structure of the code.

It’s a lot like the way you may have already been doing it, just with more learning.

Big up-front planning phases are out. Rapid iteration is in. With all this movement towards agile, it’s increasingly tempting to throw out the idea of having a separate design doc for software in favor of just getting started and having self-documenting code.

And that is a fatal mistake.

Last week, I explained that we speak about program behavior at one of three levels: executions, code, and specification. Most knowledge about software design is contained in Level 3, the specification. The flipside: the information of a program’s design is largely not present in its code¹. I don’t just mean that you have to really read the code carefully to understand the design; I mean that there are many designs that correspond to the exact same code, and so recovering all the design information is actually impossible.

In that post, I talked a lot about the example of describing malloc and free, and how it’s quite possible to have a semantic-level notion of “freeing memory” that corresponds to absolutely nothing in the implementation. In this post, I give three more examples. The first discusses the problem of testing too much, and how the decision of what to test is in general unrecoverable from the code. The second is a question of coupling which cannot be answered from the code alone. The third shows how an identical comparison function may have different meanings in different contexts, with different expectations about how the code may evolve. None of these examples will cause your code to break, at least not today. What they will cause are the characteristic problems of bad design: fragile tests, and the risk of extra work and bugs tomorrow. The first two examples are based on real code I’ve encountered (or written!), which caused exactly those problems.

Let’s begin!

1) What should you test?

“Write the tests first,” say advocates of test-driven development, “and the code will follow.” Doing so forces you to think about what the code should do before writing it. What it doesn’t do is get you to separate the code’s goals from its implementation details.

So you update the code, a test fails, and you think “Oh. One of the details changed.” Should you update the test to compensate? If you tried to use TDD as a substitute for thinking about the design, then you probably will. Congratulations, you now have a fragile test. Writing tests in this fashion is mistake #7 in my booklet “7 Mistakes that Cause Fragile Code”.

Here’s some code and its test. Is this a good test?

Code (pseudo-Java):
public void postProfileUpdateToServer(User u, Profile p) {
  appState.saveCurrentState();
  HttpParams params = …;
  addProfileToParams(params, p);
  HttpResult res = httpClient.post(getPostUrlForUser(u), params);
  logger.logUpdateEvent(u, p); // calls appState.saveCurrentState()
  if (res.getResponseCode() != Http.HTTP_SUCCESS)
    scheduleRetry(u, this.updateBlock);
}

Test checkPostProfileUpdateToServerAssumeSuccess (pseudocode):
  Call postProfileUpdateToServer with user Bob,
       and his profile with address changed to 123 Mulberry St
  Check that httpClient.post was called once
  Check that its first argument was
               “www.website.com/callbacks/updateprofile/bob/”
               Check that the first parameter is the user’s E-mail address,
                  the second their mailing address,
                  and the third their preferred language
  Check that appState.saveCurrentState was called twice

( How do you check that httpClient.post was called? This is quite easy to do using a mocking framework such as Java’s Mockito. I quite recommend it, as a way to unit-test functionality purely in terms of how it’s defined using other operations. )

There are generally two ways to write bad tests. One is to miss cases and not be rigorous enough. This is what happens when developers chase code coverage without actually thinking about what they’re testing. A common blind spot is that a programmer will test what happens when a program goes right, but not test what happens when a server’s down, when it’s fed bad input, etc.

The other is to test too much and be too specific. Is it part of the design that postProfileUpdateToServer must call appState.saveCurrentState twice, and it chooses to do so once by calling logger.logUpdateEvent? I don’t know. The test assumes a certain order about the HTTP parameters, but does the Profile object guarantee it? If the Profile uses a hash table internally, then the order is arbitrary, and may change when upgrading the libraries. Then the test will fail when upgrading to a new version of Java. (This is why Go randomizes hash table iteration order; one of my colleagues built a tool that does the same for Java.) At the extreme, I’ve seen a very experienced programmer write tests like assert(MSG_CODE_UPLOAD_COMPLETE == 12), which, given that these constants are meant to encapsulate knowledge, kinda defeats the point of having them in the first place.

The code should not follow the tests, nor the tests the code. They should both follow the design.

2) Do these pieces of code know about each other?

One nice thing about understanding the design/specification level of code is that it gives us very clean definitions of formerly-fuzzy concepts like “this code knows about that code.” For now, stick with your intuition as you answer this question:

Here are three modules. Module 1 defines a “student” record. Module 2 defines an “employee” record, and creates them by turning students into student employees. Finally, module 3 uses employee records, namely by printing them.

Oh yeah, and this example is in pseudo-JavaScript, so there’s no notion of “type” other than “the set of stuff this function can return.” Here’s the code:

Module 1 :

function makeStudent(firstName, lastName) {
  return {firstName: firstName, lastName: lastName};
}

Module 2:

function makeStudentEmployee(student) {
  var e =  student.copy();
  e["employeeId"] = nextEmployeeId();
  return e;
}

Module 3:

function printEmployeeFirstName(employee) {
  console.log(employee["firstName"]);
}

So, Module 3 accesses the firstName field of the employee value, which is defined in Module 1. Now, the question is: does Module 3 know about Module 1. That is, does the description of what Module 3 does need to be written in terms of the description of what Module 1 does?

The answer is: it depends. If the documentation of Module 2 is “Returns a student employee record with firstName, lastName, and employeeId fields,” then the answer is a clear No; it’s just an implementation detail that it obtains a student-employee record by appending to a student record. If the documentation is “Returns a student record with an additional employeeId” field, then it really is the case that you can’t know what’s in the argument to printEmployeeFirstName without reading Module 1, and so modules 1 and 3 are very much coupled.

3) What does this code accomplish?

Quick! What does this line of code accomplish?

  return x >= 65;

Two possible answers:

1. x is an ASCII character which is already known to be alphanumeric; this code checks if it’s a letter. 
2. x is an age of a person; the code checks if the person is past the retirement age in the US. 

In both possible answers, the code is the same. I can probably find examples where the surrounding context is the same too. If this is just a standalone function lying in a Utils file somewhere, it makes absolutely no difference to the program which I use it for; I could even use it for both. But it makes a massive difference to the evolution of the program.

The former may need to be changed for internationalization, while the latter may need to be changed following changes in US laws. The former should live alongside other functionality related to character sets; the latter alongside code relating to people or company policies. And in the former case, since there’s a bunch of non-alphanumeric ASCII characters between “9” and “A”, some crazy-optimizing programmer could change it to “return x >= 64” and then optimize it to use bit-ops like “return (x >> 6)” with no effect on the program. In the latter, that might lead to a lot of erroneously-sent retirement benefits.

Meanwhile, if you were trying to prove the correctness of a program that used this function, the proof environment would not be convinced that Bob is eligible for retirement benefits just because that function returned “true” until you tell it exactly what this function is meant to do.

If you just think about the code, then the letter ‘A’ is the same as the retirement age. So focus on the design.

Credit to Ira Baxter for this example.

Writing Better Code

I gave you three examples of situations where it’s impossible to recover design information from the code alone. For the tests, there’s no solution other than to have the design written somewhere separately, so you can know whether the order of HTTP parameters is stable, or whether to rely on the number of times saveState is called. For the code examples, it’s actually quite possible to change the code so that it only corresponds to one design. For that unclear case of coupling, if you want to make it clear that modules 1 and 3 are separate, have module 2 create records with explicit fields. For that retirement age check, just write it as “return x >= RETIREMENT_AGE”. Even if RETIREMENT_AGE and ASCII_A (usually spelled just 'A') have the exact same runtime values (for now), they represent different concepts. They are not interchangeable in the design, nor in a formal proof.

This gives rise to my first rule of writing good code:

Jimmy Koppel’s rule of good code #1: Make the design apparent in the code (Embedded Design Principle).

Sounds simple, but it’s quite vague and subtle until you’ve really internalized how code is derived from a design. I’ve given multiple workshops exploring different aspects of this idea, especially around coupling.

Some things are better left unsaid

In statistics, we used to think that, if you had enough data, you could learn anything. Then the causal inference guys came along and showed us that, actually, even with infinite data, there can be many processes that generate the same observations. If you just collect data about what days there was rain in town and what days your lawn was muddy, you can’t tell the difference between a universe in which rain causes mud and one where mud causes rain. You need to know something more.

Software design is the same way: there can be many designs that correspond to the exact same code. Those who speak of “self-documenting code” are missing something big: the purpose of documentation is not just to describe how the system works today, but also how it will work in the future and across many versions. And so it’s equally important what’s not documented.

Acknowledgments

Thanks to Alan Pierce, Alex Reece, and Tej Chajed for comments on earlier drafts of this post.

1 Note that I am considering text in a source file, namely comments and variable names, as part of the documentation, not part of the code. A long comment explaining the structure and guarantees of your program is absolutely a form of specification.

Have you ever stopped to consider what it means for a program to be wrong? I mean, really stopped to consider? Like, “it’s wrong if it crashes — but what if the crash conditions are only hypothetically achievable — but wait…”. Let’s get to the bottom of this. Here’s a first try:

Definition #1

A program is wrong if it runs and produces a wrong result.

So I put my bread in the toaster, and, instead of giving me a piece of toast, it gives me a rhinoceros. Not what I wanted. Definitely a bug (err, mammal).

Programs can still usually produce the correct result but be wrong. So I get a new toaster, and I’ve never had a problem with it. Then I find out that, if I put in a thin slice of Bavarian rye when there’s a full moon out, and I’ve used the toaster exactly twice in the last 24 hours, then it will fry its circuits. Sounds like a bug. So we amend it into a 2nd definition.

Definition #2

A program is wrong if there exists some environment, sequence of events, or other “input” under which it produces a wrong result.

It’s still possible for the code to be wrong.

How? Simple. Let’s say somewhere in that toaster, it sums all the elements of an array — but it accidentally goes over by one. Memory error? Well, it’s written in C, so it just adds on whatever is in the next address in memory. That address is a byte which is always 0 for whatever reason, so it gets the right answer every time.

The code is still wrong. It may never fail, but the reasoning for why the code should work has a hole: what should have been a simple argument of reading an array now depends on complex assumptions about the compiler and memory layout, as well as a whole-program check that that byte is always 0. And that hole can cause an actual failure in future versions of the program: someone rearranges the fields in a structure, and code that should never have been affected starts failing.

We reach our third definition:

Definition #3

A program is wrong if the reasoning for why it should be correct is flawed.

Progress! We’ve gone from a clear and simple definition to one that’s handwavy and impossible to use. Actually, it’s quite rigorous, but I’ll have to teach you some concepts from formal verification to make it more concrete.

All three definitions are correct to use at different times. This forms one of my core teachings: that, when we talk about programs, we speak at one of three levels. These three levels are:

• Level 1: Runtime. The runtime level deals with specific values and a specific environment from a single execution of the program. A lot of debugging is done at the runtime level.
• Level 2: Concrete Implementation/Code. At the level of the concrete implementation, we think about what the current implementation could do when given arbitrary inputs and an arbitrary environment. Behaviors that cannot happen are not considered, even if it requires global reasoning to rule them out. A lot of implementation work is done at the code level.
• Level 3: Design/Logic: At the level of logic, we consider the abstract specification of each unit of a program. When using other units, we only consider the guarantees made by the spec, and assume they may be replaced at any time with a different implementation. Many programs which are correct when viewed at the concrete implementation level are not correct when viewed at the logical level, because they rely on behavior which is not guaranteed to hold in all future versions. We call this an error of modular reasoning, because functions with such errors lack a desirable property: the ability to argue that the function is correct only from the function’s code and from the contracts of the function's dependencies, without need to even glance at the dependencies. Most software design is done at the level of logic.

I’ve met programmers who confuse the runtime and concrete implementation/code levels, but not many. The runtime and code levels are concrete enough: you see the runtime level by running under a debugger and inspecting the stack, while you see the concrete implementation level just by reading the code and thinking about what could happen. But most programmers have a much harder time getting that there even is a logical level, and I’ve seen much confusion come from when one programmer is talking about what a component is guaranteed to do, and the other is talking about what it happens to do. Most programmers will be taught the difference between interface and implementation at a high-level. But very few get to see the full details of what defines an “interface” beyond just “list of functions.” That can only be seen when doing formal verification, where a program’s properties and assumptions are written just as concretely as its source code. In everyday development, all that structure and reasoning is still there; it’s just scattered across documentation, comments, and programmers’ heads.

Statements at different levels do not mix. So if the proposed client/server protocol says the client should send a request twice and discards the first result (a Level 3/design-level statement), and the designer tells you it’s because there are three different kinds of request handlers in the codebase, and Bob’s sometimes gets it wrong the first time (a Level 2/implementation-level statement), you should get confused. You should be as confused as if someone wanted to call a file or write to a function.

Isn’t our goal to deliver working software to customers, and so correctness at the concrete implementation level is all that’s important? No, our goal is to be able to continue to deliver working software far into the future. The logical level is all about how modular are the interactions between the components of your software, and that’s important if you care at all about having different versions of those components, like, say, if you wanted to rewrite one of them tomorrow. Joel Spoelsky relates how the original Sim City had a use-after-free error. At the concrete implementation/code level, this was totally fine, since freed memory in DOS was valid until the next malloc, and so the program worked. At the logical level, this was a defect, because the spec for free says you need to act as if memory gets eaten by a dragon as soon as you free it, and any future free implementation may actually eat it. Sure enough, once Windows 3.1 rolled around with a new memory manager, SimCity would start crashing. Microsoft had to add a special case to check if SimCity was running and switch to a legacy memory manager if so.

People sometimes tell me about how software is so easy and you can just have an idea and make it and it’s so cheap because there’s nothing physical to build. Hogwash. Software is a domain where we make decisions that can’t be undone and have to be supported for all eternity. The HTTP “referer” is forever misspelled, and that SimCity special-casing code is still there 30 years later.

This is why it’s important to get programs right at the logical level, making it so you can argue each component is correct independently of the rest of the program, even if the overall program passes all your testing and meets external requirements.

And, lesson for API designers: This is why it’s important to make your APIs conform as strictly to the spec as possible, at least in Debug mode. This all could have been avoided if DOS’s free were to deliberately zero-out the memory.

I now have two years experience teaching engineers a better understanding of how to avoid complexity, improve encapsulation, and make code future-proof. But ultimately, that knowledge all stems from this single master insight: the most important parts of our craft deal not with code, but with the logic underneath. The logical layer may be hidden, but it’s not mystic: we have over 40 years of theory behind it; see the postscript below for a taste of the details. When you learn to see the reasoning behind your system as plainly as the code, then you have achieved software enlightenment.

Next time: why this implies keeping design and implementation separate.

Postscript: Technical Details

I could speak a book on harmony and composition, but you’d learn more from listening to a song and seeing the sheet music. Similarly, I could ramble on about reasoning and assumptions, but to truly understand it, you need to see the objects under study. The three levels deal with different views of a program: executions, code, and specifications. Each corresponds to its own kind of reasoning.¹ Let’s bring in the math!

Level 1: Traces and states

The objects of study of Level 1, the runtime level, are traces and states. A trace is a sequence of events that occurred in a program execution. A trace looks something like this:

Traces can be very high level, like which microservices get run, or very low level, involving instruction scheduling on the CPU. They tell you exactly what happened, and give the information to construct the current state.

The state is a collection of cells with their current value. It looks like this:

{ p=Profile(name=”Bob”, id=42, …), 
  this=NetworkClient(socket=..., baseUrl=”http://mywebsite.com/api/”),
  __messages_output=[“Initializing MyApp version 5”, “Welcome, Bob!”, …],
  …
}

Most often, the state just consists of values in memory, though it can be helpful to also include pieces of the environment, or a list of what’s already been output or sent over the wire.

Any statement that can be phrased in terms of specific traces and states is a runtime-level statement. These constructs should be familiar to programmers: printouts let you view fragments of a trace, while a debugger lets you observe the current state.

The corresponding manner of automated reasoning is ground reasoning. Ground reasoning means reasoning only about concrete values with no quantifiers. So, suppose I have this code:

1:       left = x - 10;
2:       if (left < 0)
3:         left = 0;
4:       right = min(x+10, 100);
5:       print(right);

Say I know from the printout that right=50 in a given trace, and I want to know whether it’s possible that the branch on line 3 executed. I could answer this question by asking a solver to find a satisfying assignment for the following formula:

left<0 ∧ (left=x-10 
         ∧ right=(if x+10<=100 then x+10 else 100)
         ∧ right=50)

Level 2: Code

The object of study of Level 2, the level of concrete implementation, is the code. Yes, code, the stuff you work with every day. Any statement that can be phrased in terms of the code, but not a specific trace or state, is a code-level statement. Let’s look at the following example, which computes a damage bonus in a hypothetical game:

public double computeDamageBonus(int creature1AttackSkill,
                                 int creature1ArmorPiercing,
                                 int creature2DefenseSkill) {

  int adjDefense = creature2DefenseSkill - creature1ArmorPiercing;

  if (adjDefense <= 0) {
    return 10;
  }

  double factor = (double)creature1AttackSkill / 
                     (creature2DefenseSkill - creature1ArmorPiercing);

  if (factor > 10)
    return 10;
  else
    return factor;
}

By picking specific inputs to this function, it will yield a trace and a sequence of states. But this program encodes an exponentially large number of possible traces and states. At the runtime level, we can ask “Did this execution experience a division-by-zero error?” At the concrete implementation level, we can ask “Is there any execution of this function that experiences a division-by-zero error?”

The corresponding manner of reasoning is first-order logic. This means we can write down formulas that say “for all inputs X, does this property hold?” or “does there exist an input Y, such that this function crashes?” What we can’t do is quantify over other functions. Here’s a first-order formula that states that the computeDamageBonus function can never have a division-by-zero error:

∀creature1AttackSkill, creature1ArmorPiercing, creature2DefenseSkill.
  (adjDefense = creature1ArmorPiercing - creature2DefenseSkill∧
  ¬(adjDefense ≤ 0))
    ⇒ creature1ArmorPiercing - creature2DefenseSkill ≠ 0

Level 3: Specifications

The object of study of Level 3, the layer of logic, is the specification. I also call this the design level, because most software engineering terms, such as modularity and encapsulation, can only be defined in terms of the logic and specification. There are many, many ways of writing specifications, but a popular one is the Hoare triple: preconditions and postconditions. Here’s one for malloc:

malloc(n)
Pre: n > 0
Post: retval ≠ NULL ⇒ alloc(retval, n)

At the concrete implementation level, we could ask questions about a specific implementation of malloc, like “How much memory overhead does it use?” At the logical level, we can ask questions about all possible implementations of malloc, like “does this program have a memory error?”

The corresponding manner of reasoning is higher-order logic. Higher-order logic is like first-order logic, but we can now quantify over functions. First, let’s translate the spec above²:

MallocSpec(m) = ∀n. n > 0 ⇒ m(n) ≠ NULL ⇒ alloc(m(n), n)

Now, if we hypothetically had a formal specification for the PlaySimCity function, a spec that it works for any implementation of malloc would look something like

∀m. MallocSpec(m) ⇒ SimCitySpec(m, PlaySimCity)

And that, my friends, is modularity reduced to a formula.

A really big thing about specifications is that they can involve properties which do not appear in the code at all. We defined malloc in terms of this alloc predicate, which has no intrinsic meaning other than “stuff returned by malloc.” But what this does is let us relate malloc to other operations. We can give the act of dereferencing pointer x  a precondition ∃a,n. a≤x<a+n ∧ alloc(a,n), and give the free(x) function a spec that destroys the predicate alloc(x,n). Now, having a proof of alloc(a, n) when reasoning about the program means “this memory was returned by malloc, with no intervening free” — exactly our intuitive notion of memory being allocated!

What we’ve shown here is that “this memory is allocated” is a specification-level notion which is independent of the code. And indeed, there may be nothing within the program to indicate that a piece of memory has been allocated.  It’s possible that being allocated corresponds to some internal data structure of the memory manager, but it’s also possible that your code will be compiled for a machine with infinite memory.

Now I can state exactly in what sense the SimCity code was wrong: A precondition of dereferencing a pointer is that the pointer is to allocated memory. They tried to dereference a pointer without meeting that precondition, i.e.: no proof of alloc(a,n). So, their code ran fine for one implementation of malloc, but, as they sadly learned, not for all of them.

When designing software, I always recommend trying to think in pure concepts, and then translate that into the programming language, in the same way that database designers write ER diagrams before translating them into tables. So whether you’re discussing coupling or security, always think of the components of your software in terms of the interface, its assumptions and guarantees, and mentally translate them into formulas like the ones above. So much becomes clearer when you do, for logic is the language of software design.

Acknowledgments

Thanks to Elliott Jin and Jonathan Paulson for comments on drafts of this post.

1 Don’t get too hung up on the analogies between the levels of software and the modes of reasoning; there are plenty of exceptions. For instance, much of the progress in program analysis/verification/synthesis research comes from finding all sorts of tricks to encode more complicated problems into a form that can be solved by ground reasoning, since we have good solvers. This likely isn’t going to be too relevant to you unless you work in programming tools.
2 I am lying slightly in this example — the kind of logical formula I gave is really just meant for pure functions. To handle malloc properly, we’d want to use separation logic.

Around the time I started grad school, I applied for a few prestigious fellowships. Winning is determined by several factors. Some are just an application, while some have a follow-up interview, but the applications all get scored on a rubric that looks roughly like this:

• 50%: Past research
• 30%: Letters of recommendation
• 10%: Transcript
• 10%: Personal Essays

Naturally, I proceeded to pour massive amounts of time into the essays, letting it consume much of my free time for the month of October.

Getting that Fellowship will really help me have a successful graduate career. Writing better essays will help me get the Fellowship. Therefore, to the extent that I care about having a successful graduate career, I should be willing to work hard on those essays.

But if the real goal is a successful graduate career, then at some point shouldn’t I put those essays down and do something else, like reading a few papers or practicing public speaking?

This, I dub the Partial Control Fallacy. It’s where, if there’s some outcome you want, and you only control a couple factors that affect that outcome, you decide how much to try to improve those factors as if you were actually improving the entire outcome. It’s closely connected to the 80/20 principle: it’s when you only have control over that last 20%, but you pretend it’s the whole thing and work on it accordingly. It’s when the 80/20 principle would suggest doing nothing at all.

Here are some more examples:

• Trying to get any competitive award that’s judged mostly by your past. The best college application is stellar grades and some good awards, the best resume is a great network and lots of success stories, and the best pitch to VCs is a rock-solid business.
• Thinking really hard about what to say to that cute guy or girl across the room. Most of what happens is determined before you open your mouth by what they’re looking for and whether they’re attracted to you.
• Worrying about small optimizations when writing code, like avoiding copying small objects. Most of good performance comes from the high-level design of the system.

I think I’ve been guilty of all three of these at one point or another. I don’t want to think about how much time I spent on my Thiel Fellowship application and preparing for my YCombinator interview. Meanwhile, most people who get into either don’t spend much time at all.

In parallel computing, there’s a concept called Amdahl’s law. If your program takes t steps to run, and you can make s steps faster by a factor of f (say, by splitting them across multiple processors), then the new speed is t-s+s/f, for a speedup of t/(t-s+s/f). Therefore, if you optimize those s steps extremely hard and split them across infinite cores, the best speedup you’ll get is t/(t-s).

Applying that to the above, and you can see that, if I worked infinitely hard on my essays, I could only make my apps 11% better versus not doing anything at all. (At least to the extent that it really does follow that rubric, even if I submit a blank essay.)

Sometimes, that outcome is all you care about it, in which case you’re perfectly justified in trying to eke out every advantage you can get. If you’re in a massively competitive field, like sports or finance, where there’s a really big difference between being #1 and being #2 at some narrow thing, then, by all means, go get that last 1%. Wake up early, get that 7th computer monitor, rinse your cottage cheese. But if you’re putting this kind of effort into something because it’s your terminal goal — well, you’re not doing this for anything else, are you?

I think the solution to this fallacy is always to think past the immediate goal. Instead of asking “How can I get this Fellowship,” ask “How can I improve my research career.” When you see the road ahead of you as just a path to your larger mission, something that once seemed like your only hope now becomes one option among many.

Thanks to Nancy Hua, Melody Guan, and Ryan Alweiss for comments on earlier versions of this post.

It’s a sunny day in Santa Cruz, and Alice is showing Bob her new app:

Alice: This is Frosttly, my new on-demand delivery service for cupcakes. 

Bob: Cool! How does it work?

Alice: It’s based on the Uber and Google Maps APIs. Whenever, you press this button, it texts one of our Cupcake Delivery Specialists your current location and summons an Uber so they can bring you cupcakes. 

Bob: Wait; there’s got to be more to it than that. 

Alice: Naturally, this is just a prototype. The final version will integrate directly into the order system for a specialized cupcake kitchen, and will feature sophisticated order tracking and highly optimized routing of deliveries. It’s fully functioning though. Go ahead; try it. 

Bob presses the button, and hears Alice’s phone vibrate in the other room 

Bob: Wow, it works! I can’t wait to get my cupcakes.

If you’ve ever been to a hackathon, you might have seen plenty of conversations like this. Elsewhere, Billy is showing Alyssa his prototype of a new dessert: he poured confectioners sugar over an antique dinnerware set to create something light and fluffy with a rustic feel (the final version will also have chocolate and goji berries). Billy’s concoction is much closer to a final product than Alice’s cupcake service without cupcakes, and may have even taken more work than her handful of lines of code. Yet still I’d be surprised if I saw anyone calling a pile of sugar a prototype dessert. What makes one a prototype but not the other? The resolution is simple: there’s no such thing as a prototype app.

A few years ago, my working definition of a prototype was simple; you build enough of your plan to get a sense of what the final version looks like and show you could build the whole thing. The prototype of my app for playing arbitrary card games was a screen where you could drag-and-drop rectangles. The prototype of my game mod used hand-crafted assembly to make changes. This breaks down when you stop to think: what aspect exactly are you trying to figure out?

Some people walk into Jesse Schell’s Game Design class expecting an easy time, and are shocked to find themselves pulling multiple all-nighters for a class where getting a 100% on everything is only enough for a B. But those that persevere find themselves with new worldviews on everything from sleep to applied probability theory, and learn why there’s no such thing as a prototype app. As Schell states in his book “The Art of Game Design,” a prototype is defined not by the product it steps towards, but by the question it’s intended to answer. And depending on the question, the form of the prototype can be very surprising.

So, what’s a prototype for Tetris? You mean: something to figure out how the blocks mechanic works in practice? Get a friend to cut some shapes out of paper and start sliding them down a grid. It might not make for the best Tetris experience, but it takes about 15 minutes to get going, and it’s enough to start getting a feel for how the shapes work together.

The team for the game “Prince of Persia: Sands of Time” wanted to figure out how the acrobatics in the game would work. Their prototype was just a few animations of different moves, plus a bit of imagination.

Designing the gameplay for a new first-person shooter? Try flashlight tag. Designing the atmosphere? The prototype is also called “concept art.”

And for hardware? Nintendo showed us the difference between design and technological prototypes in 2005 when they unveiled the slick look of the Wii while having modified Gamecubes running behind their demo booths

It gets even more interesting once you leave the realm of games. Jeff Hawkins of Palm prototyped the user experience of the Palm Pilot by carrying around a block of wood in his shirt pocket. He would frequently take it out to “check his schedule” or “look up a contact.” Whenever someone suggested a new feature in a meeting, he would take it out and ask them where it would fit. Meanwhile, I told a friend at an assistive robotics startup, that, while their current project does serve the purpose of a technological prototype, he could build a prototype to test the value proposition much faster by simply going to his grandparents’ house and pretending to be a robot.

Prototypes and MVPs

Like everything else in Lean Startup, the idea of a “minimum viable product” has been passed around the Valley in a game of telephone until its meaning is perhaps less than that of the three words stuck together.

A minimum viable product is a very special kind of prototype, one that tests the two key factors behind a startup’s success, what Eric Ries calls the value hypothesis and the growth hypothesis. Typically, this constrains the MVP to more resemble the actual product, but not necessarily. In 2008, Dropbox hit a key milestone on the path to their MVP when they released a video demonstrating their product. Tens of thousands joined the waiting list. So actually, the minimum viable product was the video itself: they had already proven that lots of people (growth hypothesis) want what they’re building (value hypothesis).

Similarly, the MVP doesn’t need to work internally at all like the final product. Lean Startup contains a couple examples of this: the ingredient-delivery and meal-planning service “Food on the Table” started with the CEO making deliveries to one woman, and didn’t even try to add automation until forced to. Alice’s app may not be a technical prototype of anything other than the ability to send texts, but if she can do enough behind-the-curtain work to get real users and see how they respond, it’s enough for a perfectly fine MVP.

Unpacking the Confusion

Prototypes for design questions, engineering challenges, usability, market. Demos for users, investors, the press. Why do people seem to want to combine them all into one mythical “prototype?” To show they can build it? Surely they realize that, for a typical web app, the answer to “Can I make this?” is usually “Yes” if not “Yes, but why?” And why is it weird to prototype an RPG game’s combat system with pen and paper, when many of them are just digitized versions of physical predecessors?

I think it’s simply a case of a more general phenomenon. The best way to learn to play a song may first involve drills with nary a bar from the final piece. The charity that makes you feel great and does a lot of good may actually be two charities. When you learn to identify what things you want, it’s often best to get them separately. So let’s lay rest to the idea of a prototype app. Forget about about prototyping your product as a whole. Find the underlying questions, and answer them.

Thanks to Jonathan Paulson, Amy Quispe, Nancy Hua, Michael Poon, and Melody Guan for comments on earlier drafts of this post.

You’re in high school, trying to get into a good college. You know what you must do: do well in classes, score highly on the SAT, and be active in extracurriculars — and do it better than everyone else.

Actually, I have a different suggestion: train with a friend for the USA Biology Olympiad, score highly in the first two rounds of exams, and qualify for the national training camp and then the national team.

Only a handful of people can follow that strategy. But anyone who could play the standard high-school achievement game and have a good shot at getting into MIT or Stanford could instead play the Olympiad game and have a great one. The USABO is disproportionately high-utility compared to how competitive it is. It comes with a free trip to a national training camp where you receive intense training in biology and bond with a few dozen other top high-schoolers. There are vast swaths of America, including lots of high schoolers studying hard for the SAT, who have never heard of USABO. And yet there are communities where training for Olympiads is such a well-known option that it barely counts as a strategy.

My friend who did this and got into all her colleges didn’t do so by playing the standard high school game better than her competitors, but by stumbling into a different game entirely. In doing so, she could do things the others couldn’t. I think this a fairly common pattern: a lot of what’s involved in making it to the top of anything is not being better at things than other people, but outright being able to do things they can’t. In business, they call it a “competitive advantage.” Peter Thiel calls it a “secret”. For personal life, I like to call it a “source of power.”

The “other people can’t” is the big part. As a source of power percolates into society, it loses its power as an advantage, although whether you should stop doing it depends on whether its value is external or innate. As an example of the former, 200,000 people compete in the American math Olympiad qualifier rounds each year, so training for the math Olympiad is not such a good move for most people. It’s prestigious, but only in proportion to how competitive it is. In economic terms, the free lunch has been eaten. Meanwhile, when Benjamin Franklin was working in London, saving up to open his own print shop, he found it easier than most to be frugal due to his insight that strong beer does not grant physical strength. They nicknamed him the “water American.” Nowadays, his insight is common knowledge, but that doesn’t make it less effective. Instead, it becomes the new bar.

As a warning, I found when writing this that a lot of examples of sources of power I used or wanted to use would strike a lot of people as weird, but it would take a lot of space to justify them. This is inevitable in retrospect: if it’s considered normal, it’s no longer a source of power. I also noticed while writing this that a lot of my examples focus around high school or college. I think that’s largely because life tends to diverge afterwards, and the examples become much more niche.

Discovering Sources of Power

How can you learn about new opportunities before other people suck them dry? How can you find ways of being better before they become background knowledge? While CEOs often spend much of their time looking for a leg up on the competition, I think there’s enough sources of power and few enough people looking for them that simply trying is enough. In fact, sources of power are sufficiently exploitable that there are many algorithms for finding them with high success probability.

Often, they’re hidden in plain sight, waiting for anyone to read. For a basic example, right now a degree in computer science is a ticket to a decent life. Right now, the meta-skill of “study things that are valuable and will be in demand” is sufficiently uncommon that you can raise your expected earnings (or, dare I say, life outcome) significantly just by following it. Look at the distribution of college majors if you’re not sure. I think the same further applies to specializing in hot-but-difficult subfields like natural language processing or security. Right now, CMU’s Plaid Parliament of Pwning is winning tens of thousands of dollars from application security competitions every year, while only a handful of other American universities have a team at all. More broadly, this idea also applies to entering STEM in general.

This is basically staying ahead of the demand curve. When it comes to personal skills, demand is slow to propagate, and you can gain a lot simply by being faster. Since knowing that you can raise your earnings by becoming a programmer or moving to North Dakota doesn’t cause everyone to instantly become a programmer or move to North Dakota, it will remain exploitable for anyone who wants for quite some time.

It’s interesting to think about trying to be even more ahead of the demand curve by making a big bet and training in what will be hot. This involves predicting the future. But, in life as in stocks, the winner is often not someone who knows what will happen, but someone who figured out slightly more than everyone else. And, for predicting the future, not many are trying. Along these lines, I was surprised when I learned that several prominent companies in the mobile space — in particular AdMob, acquired by Google for $750 million, and Flurry, whose software runs in over 100,000 apps — were actually founded in 2005 or 2006, before the iPhone’s announcement ushered in the modern mobile era. I think a lot of people knew the mobile revolution was coming, although perhaps not that it would be so fast. The people bold enough to actually act on that prediction were in a very good spot when it happened. I’m hoping to do something similar for program analysis.

From Who You Know to What You Know

A lot of the above could perhaps be summarized to find ways to be effective. The interesting part is how people find sources of power. One way is to invent it yourself, whether by finding a loophole, noticing a trend, or doing science. While there are a few places where it’s clear that investigating it may result in disproportionately better capabilities, this can run out of steam pretty fast. It may be possible to gain vitality by eating better, but the reward curve of doing nutrition research probably more resembles climbing the corporate ladder. Most often, the way to find a source of power is to hear of it from other people.

I think it’s a pretty simple effect. People with similar interests like to cluster, but people who also really care about improving will cluster further. They might be able to invent one or two sources of power on their own, but then they share it with the people around them — who also have a secret or two. The effect compounds, with the benefits from sharing ideas dwarfing the loss of exclusivity. Just as IBM found their above-average testers becamedozens of times better when grouped together, what you get are communities that collectively have and share the best ways of doing things. So the way to get good at something is to simply find the right community and join it.

So, for example, you’ve probably heard weight-loss advice from everyone from talk show hosts to your neighbor. This suggests that you can do better by talking to bodybuilders, who can control exactly which day they’ll hit their goal.

But this strategy can be easier said than done. The problem is not the joining: these communities are rarely exclusionary. The problem is the finding: every community wants to seem like them. They get drowned out in the noise.

In 9th grade, I attended a local programming contest. I spent a morning running floppy disks to the judges, and left with a full belly and $500 — I had won by a sizable margin. I immediately went home and Googled for more high school programming contests. I found a pen-and-paper competition in which you answer multiple-choice questions about the BASIC programming language.

I often wonder how my life would have been different if I had instead discovered the USA Computing Olympiad.

For another example, it’s well-known that to get stronger you need to push your muscles to their limits — and specifically their strength limits, rather than their endurance limits. There are vast swaths of the Internet where everyone understands what implications this has for training, with plenty shouting it at the top of their lungs. But if you look around for advice on “how to get fit,” you’re perhaps more likely to find advice to do lots of crunches, or warnings that weights might make you look like a steroid junkie. One journalist described crossing this gap as “I somehow bumbled my way into a parallel universe of American fitness, one in which men know exactly how to get strong.”

Passing It On

As we’ve seen, while sources of power with intrinsic value may merely descend from insight to platitude over time, the externally-valued have a shelf life. Perhaps the big warning from this is for those wishing to help others be successful, especially parents. As Paul Graham wrote, parents are like generals always fighting the last war. I remember seeing a teenager on CollegeConfidential complaining that their parents wanted them to stay home all summer and study for the SAT. Perhaps that would be a rational choice in their home countries, where college admissions were and still are based on grueling exams. Yet here the most advanced standardized math test for college admissions is the Math SAT Subject Test, where it’s possible to miss 7/50 questions and still get a perfect score. Meanwhile, my own mother had occasional aspirations of being a “white tiger,” and would often cajole me during my hacking sessions to “stop playing Java” and go study for the SAT.

This realization — that all these secrets and sources of power I’ve spent so much effort finding might backfire when I try to pass them on — is what scares me. I imagine becoming a parent telling my children to train for Olympiads, not knowing that that’s become advice about as good as spending a summer studying for the SAT.

I think the defense is to recognize the phenomenon but go a meta-level up. Why are people at the top of one field often very good at another? Is it merely grit and intelligence? Just as there’s a meta-skill of finding sources of power, I think there’s a skill of finding and recognizing the people with the genuine secrets, versus the posers and people out to get your money. I believe there’s a way to recognize genuine competence that transcends fields (related concept). That’s a topic in and of its own.

So, find your sources of power, but pass on the meta-skill of finding them. To get your children into college, help them find the new secrets.

And, of course, that’s assuming college admissions are still worth obsessing over.

Thanks to Jonathan Paulson, Amy Quispe, Jessica Su, and Nancy Hua for comments on earlier drafts of this post.

I like doing things right.

When I wanted to make infographics for my paper, I spent hours picking out the best graphics program that I’d use for years to come (why waste time learning the wrong one?). When I was dieting, I didn’t want to buy new clothes until I hit my target weight. And so, when I decided to create a blog, I knew it would have to be the Best Blog. I would need to get a great design, put it on a great domain, and fill it with the sharpest posts consisting only of things I’ve thought about at least 3 years.

Oh and in case I started to get other ideas, my new blogging inspiration is Christopher Olah, who will often spend a month on a post complete with 3D animations of folding surfaces, and then get it on the front page of Hacker News.

In “The Lean Startup,” Eric Ries discusses the concepts of large-batch vs. small-batch thinking. A father and a daughter race trying to mail a hundred letters. The daughter, having recently learned about the assembly line in history class, first carefully first folds a hundred messages, then stuffs them in a hundred envelopes, and continues licking, stamping, and mailing each in batch. The father does everything one at a time: folding, stuffing, and sending each letter before beginning by next.

Who wins? The father, by the power of author fiat. But also by flexibility. No need to invest in table space. And what if the messages didn’t fit in the envelopes? The daughter would fold all 100 before finding out.

I admit it. I’m naturally a large-batch thinker. I live life as if every step I’m aiming myself like a rocket bound for Pluto. I study the long-term impact of software design decisions, decisions that, more often that most people realize, cannot be undone. And so it feels unnatural to remind myself that I can change my mind later.

Last year, I wrote an essay telling the story of my startup and my ensuing decision to go to grad school, and posted it privately on Facebook. People loved it. Friends I hadn’t spoken to in years E-mailed me to say how much it touched them.

It took two months to write, and was out of date by the time I finished.

I don’t want to go through life only saying things good enough to shout from the rooftops, or only doing things that I’d display on my resume. One of the most inspiring recent blog posts on research was written by Phillip Guo on an iPhone during a coffee break. That’s skill, and it didn’t come from spending two months on each post.

Words on the Internet may be written in ink, but that doesn’t mean that my persona is. I don’t need to pick the title I’ll be using for eternity. I don’t have to pick my life’s writing topics. I don’t need to pick the writing style I’ll forever be known for. I don’t even have to attach it to my domain name.

So, this is my first blog. It’s not the platonic blog, but it exists.