[This is the second in an occasional series of posts explaining what I do in my “day job” as a computer science PhD student. The idea is to write a series of posts of increasing specificity, but all aimed at a general mathematical audience. Previous posts in the series can be found here: Part 0.]

In the zeroth post in this series, I explained what it is that computer scientists actually study—not computers, but computation. And since research is always driven by questions, I gave a list of questions that can be asked about computation. My research, broadly speaking, falls within the scope of two of those questions: What are different ways of describing a computational process? and How can information be structured to make computational processes easier to write, more efficient, or more beautiful? In this post, I’ll flesh out the first of those two questions; next time I’ll tackle the second.

What are different ways of describing a computational process?

My “subfield” within computer science is programming languages. A programming language is a system for describing computational processes—which (usually) can then be carried out by a computer. There are many, many different programming languages: Java, C, C++, C#, Python, Perl, Ruby, Scala, Clojure, Lisp, Racket, F#, Go, R, J, Haskell, OCaml, Prolog, Agda, and Coq, to name just a few. (Remember Coq?) LaTeX (used for typesetting, especially for documents involving mathematics) is actually a programming language. Mathematica and Maple each have their own built-in programming language. PostScript is a programming language for describing computations to be carried out by printers. Javascript is a programming language for describing computations to be carried out by your web browser.¹ And this is really just the tip of the iceberg. Wikipedia’s list of programming languages has over six hundred entries—and those are only the “notable” ones!

So what does it look like to study programming languages? Is it like being an entomologist—collecting, studying, describing, cataloging, and comparing lots of different languages? Well… no. That could be interesting from a historical or sociological point of view—what sorts of programming languages do people invent? Why do some become popular and others languish in obscurity? etc.—but not really from a technical or mathematical point of view. Collecting butterflies is interesting because we didn’t create them, so there’s a lot we don’t know about them; there might even be some kinds we haven’t discovered yet! But the same isn’t true of programming languages.

Instead, it’s more like being an explorer—mapping out new mathematical territory in order to create new programming languages² (or add new features to existing ones) which allow thinking at a higher level, help prevent certain kinds of mistakes, and so on. In a way, it’s really about inventing new ways to think, and mathematics is at the very heart of the process.

As a simple but far-reaching example of the interplay between mathematics and inventing new ways to describe computational processes, consider the task of taking a list of integers and adding one to each number in the list. For example, if we start with the list we want to end up with the list . In many languages this computational process can be described something like this:

int i;
for (i = 0; i < n; i++) {
    list[i] = list[i] + 1;
}

Essentially, this says to let take on all the values from up to (where we’re assuming is the length of the list), and for each value of , to add one to the value at position in the list.

If you have written this kind of program before, this probably makes sense to you. If you haven’t, you might be kind of confused and disappointed (or at least, you should be!). My description of the computational process in English was elegant and succinct: “adding one to each number in the list”. But the above program seems to have introduced lots of extra confusing details. What’s this thing? Why does it start at instead of ? Why do we have to mention list[i] twice? And so on.

But there’s a new mathematical idea which can help: functions which take other functions as arguments. We often define functions like ; why not something like ? This might seem strange… but then again, perhaps it is not so strange after all. For example, if you know some calculus, note that differentiation is exactly such a function-of-functions: the differentiation operator takes a function as input and produces another function (its derivative) as output! There is a mathematical theory describing these sorts of generalized functions, called the lambda calculus—which, I should point out, was created about a decade before the first electronic digital computers (in the early 1930’s), but is now used as the basis for many programming languages.

Here’s how you would describe our example computational process in Haskell:

map (+1) list

That’s it! (+1) is a function which adds one, that is, it takes a number as input and outputs one more than that number. map is a function which takes two arguments: the second argument is a list, and the first argument is another function which describes some computational process which should be applied to every element of the list. So this mathematical idea of functions taking other functions as arguments turns out to bear practical fruit in designing languages for describing computational processes. This Haskell code is an almost direct transliteration of my English description, with only a bit of reordering: “add one” (+1) “to each number in” (map) “the list” (list).

And that’s my research in a nutshell: taking mathematical ideas and turning them into new ways of describing computation. In future installments I’ll explain what that really looks like in more detail.