On Research (Part 1: An Impostor Is Born)

My research career began in the year 2000, when I nearly failed out of grad school.

I was in the middle of my third year of the PhD program in computer science at Carnegie Mellon University (CMU), and I had taken all of my required coursework except for the “Software Systems” course, which I finally took that spring semester of 2000. I only barely passed it — and probably shouldn’t have. Most of the course involved reading papers about operating systems and distributed systems design, papers which to my mathematically-oriented mind were often impossibly vague and informal. I couldn’t get much out of them. I also had no idea how to carry out the open-ended class project, because I had never done anything remotely resembling “systems programming”. I managed to squeak out a passing grade by pairing up with Kevin Watkins, a brilliant fellow grad student who at some point took over the project and did most of the work. (How ironic, then, that I am now a tenured faculty at the Max Planck Institute for Software Systems, and that I recently received a big grant to study the “logical foundations of safe systems programming”! So it goes.)

But as far as research was concerned, I had at that point done essentially none at all. For my first two and a half years at CMU, my advisor had been Peter Lee. Peter was a generously warm and comforting advisor. However, in my second year, he was mostly focused on his startup, Cedilla. (Peter has since gone on to become a Corporate Vice President at Microsoft Research.) Moreover, it turned out that what I needed was not comfort and assurance, but close hands-on guidance and firm deadlines. Because, you see, I had no idea what I was doing. I had no clue what it meant to do research. I flittered back and forth between various projects, some of which were glorified homework assignments, some extremely vague and open-ended. I was getting nowhere.

Realizing that things were not as they should be, I decided at the beginning of 2000 to look around for a different advisor and a more clearly defined project. I talked to several other professors in PL (programming languages), and the problem that seemed most interesting to me was one suggested by a brand new faculty member, Karl Crary: how to extend the ML programming language with recursive modules. ML has a very expressive “module system” — a sub-language for structuring large programs — but for a variety of technical reasons it prevents modules from being defined recursively, thus leading programmers to use unpleasant workarounds. This was a problem that had actually interested me from my first year, when I saw a talk at PLDI’98 by Matthew Flatt on his “units” system (a recursive module extension of the Scheme language), but I had never thought to pursue it. In the meantime, Karl, together with Bob Harper, had taken a very preliminary stab at the problem in their PLDI’99 paper, “What is a Recursive Module?”, which is arguably one of the most theoretical papers ever to appear in PLDI (not generally a theory-friendly conference). It’s an interesting paper, and it did introduce the novel concept of a “recursively dependent signature”, but as even the title suggests, the paper is much more about asking questions than it is about answering them. I took as my goal to flesh out the inchoate ideas of that paper into a more fully thought-out design.

Unfortunately, I still wasn’t getting (or even knowing that I needed to be seeking) much hands-on guidance from Bob and Karl, and by May 2000, I had made very little tangible progress. I received an e-mail from Peter while I was home for Passover vacation, not long before the end of the spring semester, informing me that, according to Bob and Karl, I was not in good standing. I would subsequently receive an “n-1” letter: a progress report from the CMU faculty after the semi-annual “Black Friday” meeting, indicating that I would have to produce a significant piece of research and write a paper about it by the end of the year, or else be ejected from the CMU grad program.

What on earth had just happened? One minute, I was embarking on a career in computer science research and just getting my feet wet (never mind that three years into the program was a bit late to be getting my feet wet). The next minute, I was being essentially told I was a failure.

This was the lowest point of my entire existence. I felt like a worthless piece of shit. That is a feeling you don’t soon forget. I certainly haven’t forgotten it — I relive it frequently, even now as a successful academic, although I’ve learned to mostly refrain from throwing small objects across the room and thinking suicidal thoughts in despair at my general shittiness and uselessness. I view myself as a reasonably smart person, but I always feel I’m in way over my head, surrounded by people much more talented than me, who work much harder than me, who actually know how to program, who actually understand type theory (which I’m supposed to be an expert in but I’m not), who actually know how computers work, who actually care about how computers work — people who are qualified to do research in computer science. Whereas I am not qualified: I am…an impostor.

Yes, this is a well-known problem among academics (and other “high-achieving individuals” as Wikipedia puts it), known as “impostor syndrome”. What is so insidious about impostor syndrome is that, although it is a subjective distortion of reality, it is usually grounded in an accurate and honest perception of one’s own limitations. I am surrounded by people who are much more talented than me, who work much harder than me, who actually know how to program, who actually understand type theory, who actually know how computers work, who actually care about how computers work. It’s just that I have some other strengths that those people lack, which I fail to take account of because I am too focused on my failings, and I probably romanticize the talents of others out of proportion. In other words, the impostor syndrome is a natural consequence of the tendency of smart people to be self-critical, competitive, and a bit mad. These characteristics are correlated with creativity and accomplishment, and are thus admirable and beneficial in appropriate doses, but they can easily be abused like a drug, justifying inaction and hopelessness, and leading to a spiral of self-hatred and depression.

Fortunately, after receiving my “n-1” letter, I did not spiral into self-hatred and depression because I am blessed with a loving and supportive family. My mother came and stayed with me for several weeks that summer, and gave me the moral support I needed in order to focus on making steady, positive steps toward completing a piece of research. She also helped put me on a new exercise and physical training regimen, which enabled me to lose a lot of weight and feel better about myself in general. That was spectacularly good timing, given that I met my future wife Rose Hoberman later that fall.

By the end of the year, I had drafted my first paper:

Looking back at this paper now, I am struck by a few things:

1. The paper is the very definition of preliminary work, an exploration of ideas without a clearly useful result. I can’t tell you how many papers I’ve reviewed for POPL this summer, written by big-name established researchers, that fall into the same category! But at least it is thoughtful, scientifically rigorous, and even, dare I say it, mildly interesting. Hiding within it are the seeds of ideas (in particular, a way of dealing with something I eventually termed the “double vision” problem) that I would later explore in a much more satisfactory way. It was worth writing, and the writing — though not up to my present standards — is not half bad. I guess I was always a decent writer, if I do say so myself. Nevertheless, the paper was far too preliminary to be worth publishing, and it would remain unpublished.

2. Some people are inventors; they invent brilliant new ideas and solutions that are radically different from anything that came before. Generally speaking, that is not my style. I have invented a few clever things, but I view myself primarily as a consolidator. I like to take other people’s good (but often somewhat rough) ideas, to explain them more clearly, to clean them up and pare them down to their essence, to rescue them from the ad-hoc, kludgy trappings of their birth and unify them into more general and elegant conceptual frameworks so that their latent potential can be revealed. On many of my papers, I let my collaborators do most of the inventing, and my role is primarily to extract the key high-level ideas that make their inventions work and explain those ideas so that others can appreciate and build on them. (Whether I succeed at that is a different story.)

This personal style of mine is already evident in my first paper. The paper is basically attempting a more refined analysis of two approaches to the semantics of recursive modules that were described in Karl and Bob’s PLDI’99 paper, which they called “opaque” vs. “transparent” recursive modules. In their PLDI paper, “opaque” and “transparent” were presented as different points in the design space, both of which had major limitations. In the first half of my paper, I showed how both could be seen as instances of a more general unifying rule for recursive module typechecking, which I called the Fundamental Property of Recursive Modules. This was a kind of neat and non-obvious observation. Unfortunately, it didn’t really go anywhere.  The second half of my paper proposed a hand-wavy design for recursive modules, supposedly combining the best aspects of opaque and transparent recursive modules, but it’s an ad-hoc mess, and it leaves some of the most interesting parts of the problem (in particular, dealing with the interaction of recursive modules and data abstraction) for future work.

3. The title of the paper commits two cardinal sins: one of excessive sincerity, the other of shoddy salesmanship.

First, it starts with the word “Toward”. This is an outright admission that the work is going somewhere but has not arrived there yet. Too honest, kid! It makes the reader think: “OK, well, call me back when you get there.”

Second, it claims it is aiming at a “practical theory”, which is a dead giveaway that the author is a pure theoretician yearning to have practical relevance. Saying your theory is “practical” is like saying your restaurant serves “world-famous pizza”. If your pizza is really world-famous, there’s no need to advertise that fact. Sadly, I would repeat the mistake a few years later when I tried and failed to publish a completely different paper called “Practical Type Theory for Recursive Modules”. As that title suggests, the later paper still wasn’t remotely practical, but at least I had dropped the “Toward”, thus staking a claim that I had arrived where I was going. (Spoiler alert: I hadn’t.) And even now, my web page says: “I am working toward a ‘realistic’ theory of modularity.” I’m not sure that “realistic theory” is any more convincing than “practical theory”, but at least I had the good sense to put ‘realistic’ in scare quotes.

The truth is that “practical theory” — with all the theoretician’s inadequate yearning that that implies — is what I do. I aim to build beautiful formal foundations for reasoning about real-world systems in all (or at least some) of their filthy complexity. I am not particularly interested in solving mathematical problems for their own sake, nor am I interested in practical impact for its own sake. This tends to put me at odds with almost everyone: to pure theoreticians, I am an unprincipled hacker working on short-term problems, while to unprincipled hackers I am a pie-in-the-sky pointy-headed theorist. Oh well — I can’t change who I am.  And obviously I think there’s some merit in trying to do “practical theory” or I wouldn’t be doing it.  More about that some other time.

In the end, my first paper was not a very successful effort, but it was enough of a non-failure to convince my advisors to let me keep my head. For that, I am eternally grateful. It would take another year, though, for me to actually prove my worth to them, and in a way no one could have predicted…

To be continued…


Great Moments in Bureaucracy (Part 1: A Fistful of Euros)

So, we drove Alma to the US Consulate in Frankfurt today to file for her US Passport. This proved, unsurprisingly, to be a bit challenging. We wouldn’t want just any old kid claiming to be a US citizen, now, would we?  But before I get ahead of myself…

1. On Friday, we tried to take a passport photo of Alma.  The requirements of the passport photo are minimal: it just has to be 5x5cm, on a white background, with the head taking up between 25 and 35mm of the frame, and the eyes positioned between 28-35mm from the bottom of the photograph, and the infant facing straight ahead, eyes open, with a neutral expression, and both ears showing completely.  As we quickly learned, this is a nearly impossible set of constraints to satisfy, especially when your infant, upon being placed on her back, starts to squirm in every possible direction (if she is in a good mood.  We managed to take several hundred photos on my iPhone, out of which one (or possibly two) met all the qualifications.  It then took us another two days (and a few failed trips to the local DM store) to actually get the photo printed on glossy paper in the right dimensions, with the help of my student Georg and his own private photo printer.  The picture we ended up using is not the most glamorous photo of Alma (see below), but it’s a passport photo, so I guess that’s to be expected.  In any case, many of the other pictures we took were very cute, so this wasn’t an entirely pointless effort.

alma-passport2. We had to fill out multiple different forms (with totally redundant information on each form) in advance, and also bring evidence, above and beyond our US passports, proving that “we have been in the US for at least one day”.  I’m not sure who invented the one-day rule, but it’s a great rule: it is seemingly designed to make life as hard as possible for expats who have been away from the US too long and forgotten where they keep all their important papers, while simultaneously making said expats feel like idiots for not being able to prove they were in the US for even one day.  As for myself, I felt very smart because my birth certificate was sitting in my “Important Papers” folder (or maybe it was in the “black envelope” with other mysterious papers — I can’t remember).  But Rose couldn’t find any immediate evidence.  We had her mother email her a scanned copy of her birth certificate and college transcripts, and crossed our fingers.

IMG_15863. Today, we drove up from Saarbruecken to Frankfurt (about a 2.5-hour drive during rush hour).  This went very well: Alma slept basically the whole way.  When we got there, they warned us up front that their credit card machines broke.  Or they were not accepting credit cards today (“sorry for the inconvenience”).  Or something like that.  Despite the fact that we were told to bring a form with our credit card information on it.  What me worry?  I had brought $200 in cash!

IMG_1585Initially, things seemed to be going fine.  Everyone was pretty friendly.  But then the passport officer gave me the bill.  It turned out there was an extra charge of $100 for “Report of Birth Abroad”.  Report of Birth Abroad?  I’m the one reporting the birth, they should pay me!  And the website never mentioned any $100.  [UPDATE: Actually it does, under “Report of Birth Abroad”, but it was not clear to me that this was a separate charge on top of the US Passport Application.  OK, I’m an idiot.]  Anyway, this would have been fine, except that of course that $100, on top of the $105 I was expecting to pay, came to $205.  And all I had was $200.  Did they accept euros as well?  Yes!  Great — I had 5 euros in my wallet.  Problem solved.  I went to the cashier and presented her the money.  She was a very friendly-looking person, who said hello in a very friendly way, and proceeded to explain in a very friendly voice that this wouldn’t work.  They could not simply accept $200 and 5 euros to cover a $205 bill.  Before reading on, take a minute to see if you have any idea why that would be.

IMG_1548So you might have thought that the problem was they could only accept payment completely in dollars or completely in euros.  That was not the case.  They could accept payment with a combination of dollars and euros.  But: each individual charge on the bill could only be paid completely in dollars or completely in euros.  The minimum subcharge on the bill was $25 (for the passport book or something), so she could take $180 in payment for everything else, plus 23 euros for the passport book.  But I only had 5 euros in cash.  And Rose had already spent her remaining euros on buying a self-addressed envelope at the consulate for them to send us the passport in.  (As it turned out, she may have had enough change in her pockets, plus the spare change in the car, to cover the 23 euros, but we didn’t think of it at the time.)

IMG_15904. Of course, the consulate, in their non-credit-card-accepting state, did not have an ATM machine on the premises.  So I had to go out looking for an ATM.  I asked the security guards and they sent me to a gas station around the block, but the first gas station I found had no ATM, and the second one had an ATM that was broken.  The cashier there said (in English!) that she “hoped” there “might” be a working ATM at the gas station a kilometer or so down the road, but she wasn’t sure.  Eventually, after several U-turns, I found a gas station to get cash at, but at this point, I was getting nervous that the consulate was going to close for lunch.  (We had arrived at 10:30 and now it was close to 12.)  Fortunately, after this (at least) 45-minute detour, I made it back in time with a fistful of euros.  The place was almost deserted at this point, and it didn’t take long this time to get through security.  The cashier took our money, the passport officer had already approved all our paperwork, there were no problems with our passport photo or our corroborating documents, and so everything was over in a flash.  The officer then told us we could go file our paperwork for Alma’s social security card at door 26 down the hall.  If there wasn’t anyone there, he said we should ring the bell and someone would come.  We went there, there was no one there, and we rang the bell.  No one came.  The sign said their hours were Monday-Friday 8-11 AM.  It was now after 12.  We asked the security guard for help.  He went away for a few minutes, came back, and said everyone was “out to lunch”.  “Would they be back after lunch?” we asked.  “No, they don’t process any new paperwork after lunch.”

I think I now understand the true meaning of the phrase “out to lunch”.

On Science as Art

What do you know, man?  A stereo’s a stereo.  Art is forever!

— Cheech Marin, last line of Scorsese’s After Hours

We were having dinner the other night with Anusha Gummadi, the wife of a colleague of mine, and she asked me if I hoped my soon-to-be-born child would become a scientist. My kneejerk reaction was: “Hell, no! Science is what you do when you can’t get a real job — you know, as an artist.”

Now, although I was (as usual) being half-facetious, the immediacy and vehemence of my retort took me a bit by surprise. After all, I am a scientist, and I (mostly) really enjoy what I do. There are many excellent reasons to become a scientist: intellectual stimulation, impact on society, useful skill set offering increased chance of employment, etc. There are also excellent reasons not to become an artist, the most important one being that it is an extremely low-percentage occupation. Most artists, even the ones who are actually talented, barely manage to eke out a living. Only a very lucky few make a lucrative career in the arts, and in my experience there is only a weak correlation between success and talent.

And yet…I wasn’t entirely joking.

When I was a kid, I enjoyed math, but my heart was in the arts — music and film, primarily. If you had asked me what I wanted to do for a living when I was a teenager, I believe “composer” and “filmmaker” would have been at the top of the list. Indeed, when I was a pre-teen, I sang in the now-defunct New York City Opera Children’s Chorus (with a few bigger solo parts), and I also spent a lot of time tap-dancing. Some of my fondest memories as a child were taking the train up from Long Island to Manhattan with my mother, and then the subway down to the bowels of the New York State Theater in Lincoln Center, where we rehearsed La Boheme, Carmen, Tosca, and more in a windowless room with Mildred Hohner, the matriarchal coach of the children’s chorus. Or over to an underground loft space in Soho, where I learned about rhythm and jazz from the members of the American Tap Dance Orchestra. (I had my bar mitzvah there!) That loft space was only a few minutes’ walk from a bunch of arthouse theaters showing movies from everywhere in the world. My favorites were Film Forum and Theatre 80 St. Mark’s.

And yet I ended up as a professor in computer science. How did that happen? Well, I was good at song and dance, but not that good. And I never demonstrated any particular aptitude for what I really wanted to do, which was composition. I took piano lessons, but was too lazy to ever become proficient at the instrument. I enjoyed watching films and listening to music — the weirder, the better — but I didn’t have any particularly interesting ideas about films or music that I wanted to create. I wrote poetry, mainly in a sort of Dadaist vein, but I spent a lot more time thinking about what would be a good title for a movie/poem/whatever than what it would actually be about. In short, I was all style and no substance, and what little style I had had been more or less done to death in the 1920s.

So when I went to college (at NYU), I decided pragmatically to study math and computer science. I always loved math, computer science less so. I enjoyed the CS classes I had taken as a child and in high school, but they were pretty basic (literally: BASIC and Pascal programming). And I was very far from a computer nerd: my idea of fun, as I said, was singing, dancing, listening to weird classical music or offbeat films — definitely not hacking. Originally I just wanted to major in math, but my parents convinced me to study CS as well, mainly because it would improve my job opportunities.

Boy, was that a good call. I learned after a few years at NYU that (a) computer science was actually more interesting than I had thought, and (b) I was good at math, but not that good. I think what really hit point (b) home for me was when I ended up becoming friends with some Eastern European students (Yevgeniy Dodis and Ioana Dumitriu, among others), and they won the Putnam Competition (meaning they were top-5 finishers). For those who don’t know, the Putnam Competition is an annual North American undergraduate math competition. I don’t know how my friends prepared for it — all I know is that I got straight A’s in math, but when I took a look at past years’ Putnam questions, I had absolutely no clue where to begin. I’m sure if I looked at them now, I’d have the same reaction. Yevgeniy is now a professor in theoretical CS (crypto) at NYU, and Ioana is a professor in math at University of Washington. They are mathematicians, I am not.

As for point (a), I would credit two classes with getting me really excited about computer science. One was Alan Siegel’s graduate Algorithms course, which I took either in my first or second year of college. The other was Ben Goldberg’s graduate Programming Languages course, which I took in my third year. The Algorithms course was my first experience reasoning about programs mathematically (if not exactly formally). The PL course was my first experience with functional languages (SML and Scheme, and a little bit of Haskell). Both of these were truly eye-opening, and ultimately convinced me that I wanted to pursue graduate studies in computer science, studying PL or algorithms or both.

OK, fast-forward 18 years (I’ll discuss some of those years in a different post). I ended up doing research in programming language theory for a living. This has been incredibly rewarding, but clearly based on my answer to Anusha’s question, it’s not quite what I would choose to be doing if I could pick any career.

Well, join the club, Derek! Almost no one ends up living out their childhood fantasy. More to the point, I think there’s an extent to which I am living out my childhood fantasy.

What do I do? I get paid to think about whatever I want, so long as I eventually write my ideas up, convince a few of my peers that there is something exciting about the ideas, and then if I succeed at that, I have to present those ideas to an even broader audience in a talk at a conference. And thinking all by myself is really very tiring, you know, so I get to hire extremely bright people to think along with me, do most of the actual work for me, and then I get to help them figure out how to explain their hard work and their cool ideas to other people.

Basically, in cinematic terms, I get to be a cross between a screenwriter and an executive producer. This is pretty incredible. What science has done is to fix that core problem I had as a child when I was writing poems — all style and no substance — by providing the thematic content around which to spin interesting stories. And as a result, I’ve managed, pretty much accidentally, to make science work for me as a means of artistic expression, as an art form, or at least as close to an art form as I’ll probably ever get.

Of course you could argue that relatively few people who go into science end up becoming professors. This is true. However, the percentage is still far greater than the percentage of aspiring artists who make a career out of their art. (I don’t actually have any evidence to back this up: that would require too much actual science.)

This view of science as art pretty accurately reflects my perspective on CS research. Art can be simple or complex, art can be easy or hard to understand, but there should be something about it that touches you, something that is elegant, something distinctive. Similarly, a research paper can present a really simple and retrospectively obvious idea that anyone can make sense of, or it can present a challenging extension to a well-studied proof technique that only three people in the world understand — I’ve written papers of both sorts — but it should strive in either case to illuminate and inspire, to demonstrate an original and memorable way of thinking about the problem at hand. I would not say that I succeed in doing this all (or even most) of the time, but it is always my goal.

And this is what I look for when I read other people’s papers, too. Maybe it’s why I have such high standards, and a reputation for being a harsh critic: poorly written papers really bum me out. (Btw, this reputation is totally undeserved — for example, on a recent program committee on which I served, my average review score was one of the highest of any of the PC members.  Just saying.)

On the flip side, well-written papers bring me great joy. One that comes immediately to mind is the paper “Ribbon Proofs for Separation Logic” by Wickerson, Dodds, and Parkinson from ESOP’13. It presents a graphical (yet formally defined!) language in which to write separation-logic proof outlines, and the tool implementing this language produces gorgeous “ribbon proofs” of program correctness. Aside from being lucidly written, the paper lends a distinctive visual representation to the core ideas of separation logic. It’s a pretty literal example of science as art, and what can I say, it made me very happy.

Screen Shot 2014-12-31 at 6.21.09 PM

Anyway, getting back to my soon-to-be-born child and the important life lessons I hope to impart to them — umm, maybe I could misquote the Dread Pirate Roberts from The Princess Bride: “Have fun, kiddo. Create, explore, sleep well. You’ll most likely do science in the morning.”

Or even more simply: “As you wish.”

On Work-Life Balance (Part 1: Lamentations)

These poems date back to the early 2000s, in the first few years when Rose and I were living together.  I believe Rose wrote the first, I wrote the second (you can tell I was hot for Dorothy Parker at the time), and the third we wrote together.  But in honor of the sacrosanct rules of academic authorship, we’ll just maximize our publication counts and say we co-wrote all of them.

Waiting on Work:

I’ve been anxiously awaiting
a young working man named Derek.
The length of time he’s been away
is nothing if not barbaric.
But it’s slow-going, I understand,
for his research is most esoteric.

Lament IV:

My man is so brilliant,
his work so profound,
his mind so resilient,
he’s never around.

A Fine Head (I Hope):

At twenty his hair started thinning.
Before long there emerged a spot.
In the next years the baldness was winning.
Soon whatever hair had been was not.