!!Con West 2020 - Vaibhav Sagar: Compilers for nothing, executables for free!

So I have a problem. And my problem is that I use Vim. (laughter) And to get Vim to do anything remotely fancy or customize it to my needs, I need a vimrc. And every time Vim lags with a large file or it’s just a bit slower than I would like, I keep thinking how like… I don’t really need my Vim to handle every possible vimrc. I just need it to handle the vimrc that I have. There’s a whole bunch of functionality in Vim that I don’t use.

00:56 - There’s a whole tab engine, for example, that I just don’t care about. The only tab settings I use for my tab length are 4. Why does it need to handle a tab length of 3? Who uses tab length of 3? This is the kind of code I would imagine is inside Vim. Like… Someone set the tab length to 4. Handle it and set the number of spaces accordingly. So I kept thinking about… Wouldn’t it be cool if I could take Vim and take my vimrc and jam my vimrc into Vim and do a whole bunch of unrolling and inlining and take out the stuff I would never use? So at the end of the day, it would be smaller because it doesn’t have stuff I don’t use and faster because it doesn’t have stuff I don’t use.

01:38 - Right? The idea of doing this in general is called partial evaluation. So favorite example of this is: You think of a program as taking static input and dynamic input. Static input is essentially known in advance before the program starts executing and dynamic input is only known once the program starts executing, to produce some output. A favorite example is anything with a configuration file. I use Vim, but emacs has the same problem. Your web servers.

02:06 - So wouldn’t it be cool if we could actually take the program, take the static input, and jam it in, like I was describing, and do simple transformations like inline constants and unroll loops? What does that look like? Going back to the example I had earlier, if the tab length is not used anywhere else, I can just do that. Right? And that saves me a variable lookup and it saves me, like, allocating space that’s not needed and all that other fun stuff. That’s constant inlining. And what about loop unrolling? Again, same code. If I know I’m gonna insert a space four times, why don’t I just insert a space four times? Pretty straightforward, I think. At the end of this, I would have something called a residual program.

02:48 - You can think of this as evaporating away all the parts of the program I don’t need. It behaves exactly the same as my original program on that static input but it’s faster. The program that would do this is called a specialiser. A specialiser takes a program and static input, jams the static input into the program, inlines, unrolls, does some other simple program transformations, and gives me a residual program that can take the dynamic input and produce the same output that the original program would have produced given the static and dynamic input. We call these programs specialisers and say in the terminology a specialiser is a specialised program with respect to some input.

03:25 - So let’s take a slight detour and talk about interpreters versus compilers. So Python, for example, is a language that’s usually interpreted. An interpreter usually looks at instructions one and one and interprets them, changes a state, and performs some action in the outside world. And these programs are relatively simple to write but they’re also slow. Because you have to essentially consider each instruction one at a time. In contrast, we have languages like C, which are typically compiled. A compiler will kind of look at a whole source program, do a whole bunch of work, and generate another program that’s usually in a different language. And these are harder to write, because you have to handle two different languages at once, but the output they produce is usually faster. So wouldn’t it be nice if we could have both? Something that’s both simple to write, as well as fast enough for our purposes? So a researcher called Yoshiko Futamura was thinking about these things in the early ‘80s. Because what he wanted was he wanted to write software in BASIC, not the fastest language, interpreted, but wanted the output to be fast, like Fortran. But he didn’t want to write Fortran.

04:29 - Then he was thinking about this, so if I take an interpreter and specialise an interpreter with respect to some source program and do inlining and unrolling, and get a residual program which is a cut down version of the interpreter that only knows how to do things that the source program knows how to do, which can take dynamic input it needs and produce some output. But this program, the residual program, does not have any dependency on the old interpreter and runs by itself. So we’ve created a standalone program. That’s pretty cool. We’ve compiled it somehow. Without involving a compiler. So he thought about this some more. He thought… Okay. Let’s take this one step further. What if you specialized the specialiser itself with respect to an interpreter? You take a specialiser and jam an interpreter into it and do a whole bunch of inlining and unrolling and at the end you can take source code that the interpreter knows how to interpret and output a standalone executable just like in step one. Essentially we’ve made a compiler, because that’s what a compiler does. A compiler takes some source code for a program and outputs a standalone executable.

05:35 - So say the Python interpreter is written in C and we have a specialiser who knows how to specialise C, it takes a Python interpreter and outputs something that can then take Python source code and output a standalone executable. This is cool. Final trivial step. What if you specialise a specialiser? You take a specialiser, another specialiser, jam one specialiser into the other, do a bunch of inlining and unrolling and at the end you have a cool program that can take any interpreter that is written in a language that a specialiser knows how to specialise and output an equivalent compiler. Sp we’ve made a compiler compiler. That’s pretty cool. Pretty cool. So why would someone want to do this? In the ‘80s, when Yoshika Futamura came up with these ideas, people were like… Let’s write general purpose specialisers, but it turned out they’re very difficult to write. Not easy programs to write. And the speedups provided were not as fast as people were hoping for.

06:27 - Still, the idea of specialisation gives us an interesting insight into the difference between an interpreter and a compiler. Because a specialiser isn’t either, but it sits somewhere in between. The fact that you can use a specialiser to turn an interpreter into a compiler is pretty cool. It means it allows you, instead of writing a compiler, which is sometimes hard and error prone and tedious to write by hand, to just write an interpreter, which is relatively straightforward and a specialiser, and jam them together and get a compiler for free. So this is also important when it comes to correctness, because compiler bugs are pretty frustrating, and if you didn’t have to worry about that at all, that would be pretty great.

07:08 - And so far, I’ve avoided the use of the word “optimisation”, but has what we’ve been doing been optimisation? I would argue yes. You have to statically analyze a program and do loop unrolling and constant lining. This is a good way to think about what optimisation is. So this is a good entry point into learning about those things if you’re curious. So I mentioned in the ‘80s this idea didn’t go anywhere, but in the present day, we have things like PyPy, Truffle/Graal, LLVM, and other things whose entire value proposition is that if you write your language a certain way, you can get a just- in-time compiler for free.

07:37 - What is a just-in-time compiler but a second Futamura projection? It lazily partially evaluates parts of your program and turns things that were previously interpreted into things that are now compiled and also just gives you these programs. I would still like this specialised Vim. It would make me very happy. That’s essentially all I have. Here are some resources. There’s the original paper here. There’ll be a link to my slides shortly. The Wikipedia page is always good. There’s a much longer talk which in some ways this talk is a summary of called compilers for free which goes into details and gives you a sample language to talk about. But I think that talk is either 30 minutes or an hour long. So we didn’t really have enough time for that. There’s a textbook by people who did some interesting research into partial evaluation and were like… Here’s all this stuff for free. Some other resources.

08:30 - And finally this really interesting talk about a fourth Futamura projection, going even further than the three we’ve just covered. So this is all I want you to take away from this talk. And there are my slides. .