PL for SE, Part 1: “Programming Languages”

This is the first post in a Q&A series I’m doing for software engineers who are interested in getting into programming languages (PL) research. And it’s a great question to start with because it’s impossible to get into PL research if you don’t know what it is. The name really isn’t self-explanatory.

Q

@drin_montana writes:

Type systems, formal analysis and security related things are all I know of in PL research. What other types of research are under a PL PhD?


A

Any one-line summary of PL research is going to miss the mark, but here’s an attempt at one, anyways: PL research is about reasoning about programs. Sometimes we do the reasoning ourselves, sometimes we build algorithms or tools that do the reasoning automatically, and sometimes we make it easier for programmers to do the reasoning.

I once gave a quick summary along those lines to a machine learning researcher, who then responded “so basically, you guys solve the halting problem.”¹ I mean, basically. Pretty much anything interesting you could ever want to know about a program is undecidable. And yet PL is a thriving field. How?

Typically, we explore some trade-offs:

  1. We solve decidable sub-problems of an undecidable problem.
  2. We approximate a solution to an undecidable problem that mostly works in practice.
  3. We limit what we let the programmer do so that we can avoid solving the problem altogether. (This is often actually a really good solution.)

This explanation for sure falls short, though, so let’s get into some examples. I’ll walk through a small selection of topics I know about. I’m not going to pretend it’s an exhaustive list, and it’s definitely biased by the kinds of research I’m exposed to at UW. Also note that this list is constantly evolving, and that there’s some overlap with software engineering research—I’m not going to get into the distinction.

If you want to learn more about any of these topics or see what other kinds of PL research exist, I recommend checking out the programs for some big PL conferences (PLDI 2017 [not yet posted, but hopefully soon], POPL 2017, OOPSLA 2016).

Language Design & Implementation

What it is: This is probably what most people think we do: design and implement programming languages.² This often means developing new abstractions that help programmers express something that is difficult to express or avoid common mistakes. Sometimes it’s just a matter of combining and implementing existing abstractions the right way. It’s actually a pretty small part of PL research, but there are people who focus on it, and it intersects a lot with other kinds of PL research.

Recent example: Checked C is a project at Microsoft Research with the goal of making your life less miserable if you have to write C programs. In their words:

Checked C … adds checking to C to detect or prevent common programming errors such as buffer overruns, out-of-bounds memory accesses, and incorrect type casts.

Why you should care: You use these languages every day. No matter how awesome of a programmer you are, there are sometimes things you can’t express easily or mistakes that you’re likely to make. Researchers are trying to make your life easier.

Domain-Specific Languages

What it is: General-purpose programming languages (like C or Java) are great. But sometimes, you can get a lot more power by using a language that is specific to the problem you are solving (say, by using Mathematica for math, or SQL to query a database). Domain-specific languages (DSLs) are designed for these specific tasks.

Recent example: Luck is a language that makes it easier to write generators (which generate test inputs) for QuickCheck-style (automatic) testing.

Why you should care: You already do! DSLs are all around you. They’re often disguised as frameworks or libraries. You can view Spring MVC as a DSL. The same goes for mocking frameworks like Mockito.

Solver-Aided Languages

What it is: Solver-aided languages are (usually domain-specific) languages backed by constraint solvers. These languages let you leave some of the reasoning to a logic solver, so you can write high-level programs and have the logic solver prove your program correct (verification), generate correct code on the fly (angelic execution), or produce correct programs for you (synthesis).

Recent example: Rosette is a solver-aided language that makes it easy to write new solver-aided languages (pretty meta). One recent application of Rosette is a solver-aided language that helps programmers generate lots of different inputs for testing (kind of like Luck, but very different under the hood).

Why you should care: For all of the same reasons you care about DSLs and general-purpose programming languages, with the added bonus that constraint solvers are really good at the tedious things you don’t like wasting your time on. Imagine if all of the time you spent thinking about low-level details and writing boilerplate were freed up to spend just on the fun, creative stuff. Your job would be more fun; your code would be better.

Program Synthesis

What it is: An elaboration of the above, but not limited to its use in new languages. Basically, programming is hard, so let’s let our computers do some of the programming for us. Sometimes we give the computer a specification of what our program should do; sometimes we give it some examples and let it figure out the rest.

Recent example: Cassius synthesizes CSS. This probably doesn’t need any motivation to anyone who has ever written a website, but if you’d like some, the talk intro has a nice example.

Why you should care: You may have unknowingly used synthesis tools already (for example, Flash Fill, an Excel feature that fills in spreadsheets from examples). If you haven’t, they will be coming your way soon. I think this is really going to be the future of programming. It doesn’t mean you’ll be out of a job—it just means you’ll be able to spend more time on the things that really matter. So think about any programming task that you find mundane or unnecessarily difficult, something you wish you could just throw at your computer and have it do for you. Synthesis is here to help you with that.

Verification

What it is: Proving programs correct. According to common wisdom there are “two kinds” of verification, but nobody agrees on what those “two kinds” are. Some say the split is automatic/manual: Is the tool reasoning, or is the programmer using the tool to reason? Others say it is classical/constructive: What assumptions does the tool’s underlying logic make? In reality, these are more like axes, so you’ll see automatic-classical, automatic-constructive, and manual-constructive (probably not manual-classical, but who knows, and there are way more than just two flavors of logic).

Recent example: Neutrons verified a radiotherapy system (and found bugs in the process). In the past, programming bugs in (unverified) radiotherapy machines actually poisoned patients from radiation overdoses.

Why you should care: If you write code that’s important in any way, you probably want it to be correct. Even if your bugs don’t physically harm customers, they might impact customer security and privacy. Testing gives you some weak guarantees, but imagine the peace of mind of knowing your program is correct. (It also means getting paged less often.)

Testing

What it is: Sometimes you really don’t need full guarantees that your programs are correct, so you write some tests. Writing good tests is hard, though. Testing research aims to make that easier, usually through automation (whether partial or full), but sometimes through new abstractions (as in Luck, which we talked about earlier). The meat of this is software engineering research, but testing papers still show up in PL conferences.

Recent example: PBNJ makes it easier to write mock objects. It uses constraint solvers under the hood.

Why you should care: Oh, I’m sure you already care. I remember scoping out projects with my TPM and setting aside an equal amount of time for testing and writing code in some cases. Should you really spend that much time writing tests? Sometimes you have to, but you probably shouldn’t have to.

Static Program Analysis

What it is: Sometimes you don’t quite want to prove things correct, but you also don’t want to just run a bunch of tests and call it a day. There are a lot of topics that fall in between the two approaches, and I’m not going to write about all of them, but static program analysis is a really big one worth mentioning. Basically, static program analysis approximates your program in some way, then proves some properties about the approximation. You can use this to find bugs, but for even very simple bugs (like divide by zero) you’ll typically have at least one of two problems: Sometimes your analysis will report bugs that aren’t really bugs, or sometimes it will fail to report some bugs. That’s usually OK, though.

Recent example: FindBugs is an analysis tool that finds bugs in Java programs. I’ve seen it actually used in industry.

Why you should care: I think I’ve motivated the “bugs suck” angle a lot, so here’s another reason: Every time you compile a general-purpose language, the compiler is already doing this for you and using it to optimize your code. This is why you don’t have to think about all of the low-level optimizations you learned about in undergrad that make your code fast but messy. The compiler makes your code fast, but you never have to see the mess.

Type Systems / Type Theory

What it is: This is way down in “core PL,” and focuses on reasoning about the type systems that programming languages use. Type systems are really a way of limiting what the programmer can do so we can better reason about our programs. Ideally you want a type system that is expressive enough to do everything you want to do (imagine writing Java code without being able to make a List of Integers). But as you make your type system more expressive, it may be harder to reason about or require extra programmer effort.

Not-so-recent example: I’m going a little older here, since it takes a while for type theory results to reach the real world (but trust me, they do). It’d be great to automatically infer types without the programmer ever having to write them. It turns out this is undecidable for a pretty simple language. But! (OK, if you can’t tell, I really like this stuff.) By placing just a few restrictions on the type system, it’s actually decidable. ML and older versions of Haskell both use this result.

Why you should care: You probably don’t want your type system holding you back when you write programs. But you also probably don’t want your programs mysteriously failing at runtime because of a simple type error that you could have prevented ahead of time. Type theory research gets very abstract very quickly, but ultimately it still does reach you (sometimes decades later) in the form of more expressive languages and more reliable programs.


  1. At the time, I was working with Byron Cook‘s group at Amazon. Byron Cook is well-known for literally solving the halting problem (in practice).^
  2. Often the first question we get when we say we study programming languages is, “what language?” ^

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

How to Take an Industry Break

“Grad school or industry?” God, who knows. You haven’t even finished college yet. How the hell are you supposed to know what you want to do with the rest of your life? Research sounds fun – maybe you’ve done a bit already – but grad school is a big commitment. And you have an offer from that company you interned with. It was a fun internship! The money sure sounds nice right now. Plus, you could really use a break.

It probably seems like everyone else knows exactly what they want right now. It’s not true. I promise. This was me in 2011. I see it all the time in students I mentor.

The reality is that it’s really scary to decide what to do with the rest of your life right now. You’re young and you have few priors.

Everyone is sure in retrospect. It’s easy to look back and rewrite your story so it’s consistent.¹ But probably most of us were unsure.

I’m not going to tell you what to do. That’s your job. But here’s the beautiful thing: You don’t need to figure it out right now. It turns out there’s no real way to go wrong in computer science.

Let’s say you go to grad school. You get a stipend (enough to get by). Two years in, you decide you hate it. Guess what? You just got a free masters degree. Drop out. Don’t stay because it’s What Someone Like Me Would Do™. Snag a cushy software gig. Make some extra cash with your new degree.

Now let’s say you go to industry. Two years in, you think boy, I really would like my Ph.D. Well, you can still do that.² Apply to grad school. Quit your job.³ Grad school will be fun with your newfound certainty, savings, and perspective.

But make it easy to change your mind. It’s OK to change your mind! If you only do something because past-you wanted to do it, you’ll be miserable. Set yourself up to go back to school.

Well, that’s neat and all, but how do I actually do that?

Good question, strawman student!


Before You Leave

Talk to your professors.

They probably seem kind of intimidating right now, but they are your best allies. If there’s a class you like a lot, get to know your professor. Go to office hours. Ask her about research.

Do research.

I remember feeling like I didn’t know enough to do research. This is silly; research is discovery. You learn from it. Talk to professors and grad students about doing research. I recommend working with a grad student on an existing project rather than doing a thesis. Better incentives. More guidance.

Try to publish something.

In undergrad, I was so scared of the publication process that I never submitted my research anywhere. Try to get your work published, even if it’s just to a workshop. Worst case, you learn how the process works. Best case, you strengthen your application a lot.

Tell your professors you’re planning to go to grad school.

If there’s one thing adults love, it’s younger people saying “I want to be you when I grow up.” Your professors will be happy to hear that you want to get your Ph.D. They might not believe you. That’s fine. Some may offer to help. Again, your professors are your best allies.

Identify professors for recommendations.

Think ahead of time about who will write you good recommendation letters. If you’re not sure, you can test the waters. For example, senior year, I applied to give the graduation speech, and the associate dean of my college told me my recommendations were great. This made my choice easy later on.

Get the GRE out of the way.

It’s really annoying to study for a test and take a test when you’re working full-time. Get it out of the way before you graduate. Your scores last five years!


After You’re Gone

Stay in touch with your professors.

If you email your professor like “hey, remember me? I want a recommendation letter” and they haven’t heard from you in the last n years, they might say no or write a weak letter. Make it easy for them. Stay in touch.

Again, your professors are your best allies, so you want to maintain connections with them. The payoff can be huge (think, getting you in touch with professors at your favorite school, helping you with your application).

Since every student I mentor thinks this is an extremely awkward thing to do, here are a few excerpts from emails I sent to my professors while in industry:

I’ve decided that  I’m going to go back to school two years from now.  One thing I noticed is that I dork out about PL as much as I dork out about theory, which is weird because I had always assumed I’d only want to go back for theory. So suddenly I’m not sure what I want to do specifically. I don’t know exactly what I’m expecting in response to this, but any information that I can use to make a decision would be super helpful. And I honestly don’t know how these decisions work; do I need to know what I want to do before I get to school, or can I make that decision once I am already there? You were always pretty enthusiastic about me going to grad school so I figure you’re a good person to contact.

If you’re cringing at how awkward this email is, good. Me too. But this professor responded with the name of the professor who is now my advisor and told me he’d be in town for a conference in the field I’m now studying and got me in touch with professors at in the lab I currently work with. Awkward is OK. This is computer science. Though I wouldn’t recommend saying you “dork out.”

My team at work does a series of technical talks. My manager wants me to do one on FindBugs, since I got kind of excited when I saw that we were actually using it during our build process. I’m willing to do this but I’ve never given a technical talk before. I’m wondering if you have any advice. The talks are generally 30 minutes to an hour, which makes it hard to go into any real detail. The audience is all technical, mostly software engineers. They are all extremely bright people with strong backgrounds in computer science, but it’s a safe assumption that most of them probably don’t know anything about static analysis. Please let me know if you have any ideas or resources.

The feedback was useful. The talk went well. This professor learned I was still interested in PL.

 

I’m just wondering if you’re doing OK in the aftermath of Boston. I knew a lot of people out there and I know a lot of runners who are in the same position. All 18 members of my current club who were there as well as all 12 members of my old club who were there are safe and unharmed. I hope you are doing well.
This professor and I are both runners. So we chat about running sometimes. In this case, I reached out as a friend to make sure he was OK. This is also a thing you can do. Fun fact: Professors are people, too.

Nowadays, there’s also social media, provided your accounts are Safe For Academia. This doesn’t mean you need to always talk about computers, but keep things reasonable if you’re going to add your professors on Facebook (if you know them well) or Twitter (you can do this for pretty much anyone).

Go to conferences!

Pick a field you like. Google the top conferences in that field. Sign up for one every year or two. You might be able to get your employer to pay for this. Go to the talks that sound interesting. Skip the ones that sound boring (hang out in the hallways and talk to people). Talk to your old professors there. Talk to new people. Don’t worry about sounding dumb. If you’re not even in grad school yet, nobody will expect you to know anything.

Conferences are fun. You’ll learn about the latest research. You’ll meet people. Maybe they’ll remember you when they’re on your admissions committee in n years.

Power play: Find a professor whose work you find interesting, read his work before the conference, go to a talk for a paper he’s on, write down a question during the talk, then approach him casually in the hallway and ask him the question after the talk.

Keep up with the latest research.

Even if you can’t go to conferences, find the papers that are accepted to those conferences and read a few every year. Don’t worry if you don’t understand them at all. That’s normal.

Get involved with your local research group.

This is another really awkward thing to do, but if there’s a research group at your local university doing work that you think is cool, you can reach out to them and see if they have group lunches or social events or reading groups or talks that you can go to. Just mention that you’re planning to apply in n years and are currently in industry.

Also, you should actually talk to people while you’re there. I went to a theory talk by a UW grad student before I applied and was too scared to actually talk to anyone. Then I just sort of silently left. #MissingThePoint

Get help with your application.

If you’re close with any professors and grad school friends, don’t be scared to ask them for help with your application. They’ll give you good advice. Also, they won’t judge you if you say something stupid. You probably will. That’s fine.

Don’t get used to industry income.

It’s nice to spend some money for fun things, but saving is a good way to ensure that fear of a grad school stipend (which is honestly not bad in this field) doesn’t keep you from returning to school. As a bonus, you’ll be able to afford luxuries like an infinite supply of Jimmy John’s during your first deadline.


  1. Academics call this “writing a research paper.”^
  2. Every professor ever will tell you that you’re only dumb enough to go to grad school when you’re still in college, but I’m a constructive proof that this isn’t true.^
  3. You should probably actually get accepted to a school before you do this.^
  4. It is actually awkward. And I am actually awkward. So there’s that.^

 

Flip your NSF Rejection

I spent the last few days of March in 2015 refreshing TheGradCafe and my email inbox. I get push notifications for my email, so I’m not sure why I bothered refreshing it. I guess I was hoping it’d make things go faster. It didn’t.

One night, FastLane went down for maintenance. Posters on TheGradCafe noted that this had happened last year shortly before notifications had come out. I stayed up and waited for a few hours, but nothing happened, so I went to sleep. When I woke up, I saw this:

2015 NSF Graduate Research Fellowship Program Application Notification

Please be an award, please be an award, please be a-

Your application for the 2015 National Science Foundation (NSF) Graduate Research Fellowship Program has been evaluated. We regret to inform you that you were not selected to receive a fellowship in this year’s competition.

I’d gone into the application cycle pretty optimistic. Maybe I just wasn’t cut out for this research thing.

I got my first taste of academic rejection. Mostly reasonable and constructive academic rejection, but back then, it read like this:

This applicant has a very good academic record and rich relevant work experiences which are helpful for the proposed research. But all reference letters are from the same institution. … Also this application hasn’t any publication.

The proposed is an interesting idea but is needing more development. The questions seem a little naive. It is a research direction worth pursuing.

The research proposal is a bit rough and would be improved by better placing within the context of more existing work. While the letter writers are enthusiastic about the student, they collectively do not add many comments about their support for her specific research plan.

Just kidding, it actually read like this:

WHY HAVEN’T YOU PUBLISHED ANYTHING YET? 

YOU HAVE NO IDEA WHAT YOU’RE DOING.

THIS IS AWFUL. WHY DID YOU EVEN SUBMIT THIS? 

On TheGradCafe, the other rejected folk were posting their reviews. E / E / VG / VG / VG / VG. E / E / E / VG / E / VG. E / E / VG / VG / G / G. And there was a double poor just staring at me. Clearly, grad school wasn’t my thing.

This year, I got the NSF. There was no magical transformation in between the two years. I worked just as hard both years. But this year, I did better work. For those of you looking to flip your computer science NSF GRFP application, I’d like to share some advice.

Generate Lots of Bad Ideas

I remember emailing my undergrad professor the first time I applied and asking how people think of ideas. We chatted a bit and he sent me some papers. I didn’t really understand any of them. I thought of something on my own that sounded kind of interesting, chatted with a friend, and decided to take that direction because it sounded cool and I didn’t feel like generating more ideas.

I had one idea. It wasn’t really a great idea. Most of my ideas are bad. Most of most people’s ideas are bad. But bad ideas aren’t actually bad! Bad ideas are great. They’re ideas. Don’t filter them out too early. In your long list of ideas you think suck, there’s probably one that’s actually good. So write down the whole list.

This of course doesn’t help much if your list is empty. And it’s totally fine if that’s true. So I’m going to take this classic advice a step further and share some ways to actually think of ideas.

How to Generate Ideas

If you’re in industry, look around you for problems. There are plenty of problems. There are plenty of things that are unnecessarily hard. Builds take forever and always break. Developers spend as much time writing unit tests as code. Then they wait 24 hours for code reviews. Bugs regress. Developers get paged. Everything is broken, always.

Every time you find something that’s hard that you think would be easier in an ideal world, write it down. Send it to yourself in an email. Whatever. Anything to keep a list running. Later on, think about ways to solve these problems with computer science. These are research problems!

If you’re in academia, read current work. Go to talks. Talk to people about their ideas. Talk to people about the almost-ideas you have that sound really stupid that you don’t think should actually be ideas. Eat lunch with your research group. Eat lunch with other research groups. Absorb as much as you can.

Write down all of the questions you have after reading papers or attending talks. Ask those questions. Write down the answers. Ask questions about those answers. Always ask questions. I personally hate asking questions during a talk, but find that most people are willing to talk about the same questions either immediately after the talk or later in the day. Look for existing work that tackles those questions, read that work, and then (you guessed it) ask more questions about that work, too.

Oh, and all of this still applies if you’re an undergrad. Grad students don’t bite. We love undergrads who are interested in our research areas. They’re free labor impressionable get ’em hooked while they’re young! bright young minds.

Why not mix the two? If you’re in industry, hang out with your local university’s research group. Attend their talks. Show up to their reading groups. This might feel weird, but you’re probably welcome. If you’re in academia, talk to your friends in industry (make some if you don’t have any) about the problems they have. You’ll probably end up with something high in both broader impacts and intellectual merit.

Get Peer Feedback

Generating ideas is the fun part. You don’t have to worry about how stupid your ideas actually are, because they’re allowed to be stupid. You just have to have them. The scary part is actually pursuing an idea. If you think the idea is dumb, it feels awful to bounce it off of your peers, let alone your professors.

But here’s the secret: Nobody is judging you. Nobody’s going to go, “oh man, did you hear Talia’s idea today? It was so dumb.” People are mostly reasonable.

Talk to your peers about your ideas. Talk to your professors about your ideas. Go back to your peers and talk to them about your ideas some more. Then go back to your professors. Write a really shitty first draft. Bounce it off of everyone who’s willing to read it. Get feedback. Refine your draft. Get more feedback. Send it to your professors. Get more feedback. Exchange essays with other people from your year who are applying. Exchange feedback.

But Talia, what if my peers give me negative feedback?

Better them than your reviewers. Don’t turn in a draft.

My first year, I was too scared to get any feedback ahead of time, so I sent in what I had. This year, I got feedback from several people in my lab, including two students who had won the NSF the year before. Some of it was really bad! But nobody decided I was stupid because the first draft of my research proposal wasn’t good.

Two students in my lab won the NSF this year; the two of us had exchanged essays with each other and given each other feedback. I believe that one of the reasons UW is so successful at winning NSF fellowships is that feedback among peers is highly encouraged.

Don’t be Scared

Once you think an idea is good, there’s a terrifying moment when you search through existing work and you’re like oh god, what if someone already had this idea that I really love, and they’ve already done it better than I ever could? 

Well, what are your options?

If you don’t look for existing work, one of your reviewers will know about it already. It will show up in your reviews. Ignorance doesn’t help.

If you find existing work that does exactly what you want, that’s great! That means that you had an idea that landed a publication. It was a good idea. Read the papers. Ask questions about the papers. Maybe you can do it better, or maybe you can find a new idea from those questions.

If you only find related work, you should still read all of those papers and mention them. They’ll help you refine your idea and make a good case that you’ve actually put a lot of thought into your proposal.

Looks like there’s only one way to lose.

Write for the Busy Reader

Your reviewer is probably juggling three commitments on the job and also has a family and friends and a life outside of reviewing NSF applications. So when you’re writing you should strategically use bold and italics. Get the reviewers to notice exactly what you want them to notice.

Tell your reader as clearly as possible how you’re addressing broader impacts and intellectual merit

My first year, I wrote a really nice personal statement that read beautifully if you had like thirty minutes to sit down and actually read it. Nobody did. I was profoundly surprised when my reviewers missed the broader impacts in my personal statement. This year, I added some nice headers: MENTORSHIP – BROADER IMPACTSTEACHING – BROADER IMPACTSRESEARCH – INTELLECTUAL MERIT. Nobody missed it this time.

Tell a Consistent Story

One of my professors emailed me the first year and asked me to send my materials so that he could give me a recommendation that was consistent with my story. I was too scared to actually do this. I think at first I gave him a high-level overview, then maybe eventually I caved and sent it but I think I sent it with a disclaimer that was longer than my actual research proposal. Whoops.

I don’t know why, but for some reason I thought that the professor who had helped me get that far would suddenly decide I wasn’t worth it anymore after reading my bad proposal. This was silly. It bit me in my reviews:

The research proposal seems to be in an early stage would benefit from being better placed within the context of existing work. The application could be strengthened by having a consistent message between the student and advisor. The collective letters of support do not provide strong support of the specific research goals. A more comprehensive package that reinforces the intellectual merit and shows more faculty support on the research contributions would make this proposal more competitive with others.

Even if my proposal had sucked, if I’d at least kept my professors on the same page, I’d have had a much stronger application!

This year, I sent my full application materials to everyone as soon as they were in reasonable shape. Then I sent the final materials before I submitted them. My story was consistent. Reviewers noticed. Your professors aren’t psychic.

Learn from your Mistakes

Which brings me to my final point. You’re going to get rejected a lot in academia. That’s what everyone tells me, at least. It’s good practice. Sometimes you’ll get rejected for stupid reasons. But most of the time you can learn from it.

The NSF does you a huge favor by releasing the reviews to you. Some of them probably aren’t useful, but I’m willing to bet there’s some useful information in there. You can sit there and beat yourself up over negative comments, or you can honestly look at them and figure out how you can strengthen your application next year.

Or, if you’re like me, you can beat yourself up a little, save them to a document, buy a pint of ice cream, eat it, and come back a few days later with a fresh mind. Then you can read them and figure out exactly how you’re going to win the NSF next year.

Go get it!