Compilers For Free
Stuart, Tom
Partial evaluation is a powerful tool for timeshifting some aspects of a program's execution from the future into the present. Among other things, it gives us an automatic way to turn a general, abstract program into a faster, more specialized one. This math-free talk uses Ruby to explain how partial evaluation works, how it can be used to make programs go faster, and how it compares to ideas like currying and partial application from the world of functional programming. It then investigates what happens when you run a partial evaluator on itself, and reveals some surprising results about how these techniques can be used to automatically generate compilers instead of writing them from scratch.
 Good morning, everyone. Thanks for coming to this talk. I'm Tom Stewart. I'm going to talk about getting compilers for free. Although, actually, my agenda today is that I'm fascinated by programming, or to be more specific, I'm fascinated by meta-programming. It's something I'm really interested in. So let's talk about meta-programming. As Ruby programmers, we already intuitively understand the power of meta-programming, right, programs that write programs. So in Ruby, we've got things like instance eval and define method and method missing and all these kind of tools for making programs that grow new functionality at runtime that wasn't present in the static program that we started out with. Now, there's another thing that I find even more interesting than that, which still kind of counts as meta-programming, which is programs that manipulate representations of other programs, right, programs that operate on data, which itself represents a program, and then does something with that representation, like analyzes it, or evaluates it, or translates it, or transforms it. So this is kind of the world of compilers and interpreters and static analyzes, and I think it's really fascinating in a way it's kind of the purest or the most self-referential kind of software that you can write. So in this talk today, I'd like to make you look at programs differently. I don't have a complicated technical point to make. I just want to tell you a cool story and hopefully convince you that programs which manipulate other programs are interesting and hopefully kind of inspire you to find out some more about them. So I'm going to start out by just talking about something we're all familiar with, which is executing programs. So you write a program, right? You have a program written down that you want to run, and you have a machine that you can run that program on. So you put that program into the machine, and then you've got some inputs for that program, and those might be command line arguments or configuration files or standard input or whatever, and you feed all of those inputs into the machine that's got the program inside it, and the program executes on the machine, and it produces an output. I think we're all kind of familiar with how computers work, right? But that only works if the program that you wrote is written in a language that the machine kind of natively understands. So in terms of a real machine, that'll be, you know, the program has to be written in machine code. And if it's, if the program's written in a higher level language, then maybe you can run it on some kind of like virtual machine that understands that language specifically. But if your program's written in a language that's unfamiliar to the machine, then you're going to need an interpreter or a compiler to be able to execute it, right? So interpreters, how does an interpreter work? Well, very kind of roughly the way it works is it reads in some source code of the program you want to execute, and then it builds an abstract syntax tree by parsing that source code, and then it evaluates the program by walking over the abstract syntax tree and performing the instructions that it finds inside the tree. And this is basically how, you know, MRI pre-1.9 did its job, right? So I'm going to show you a little demo of how this works by just introducing this, a language that I'm going to call simple. It's just a toy language. Simple is like an abbreviation for a simple imperative language. This language is really straightforward. It looks a little bit like Ruby, but not exactly the same. Statements look like this. So simple's got expressions and statements unlike Ruby. It's got expressions like 19 plus 23. Expressions just evaluate to a value. It's also got statements like assignments. So a equals 19 plus 23 is a statement, and that statement is going to have, is going to modify the lexical environment. So when you evaluate a statement, it's going to update the bindings between variable names and their values. So the effect of executing that statement is that after the statement is executed, a has got the value 42, right? Some other statements, it's got sequencing in it. It's got conditionals in it. It's got while lips in it, right? Very basic language. It's not quite Ruby because it's got curly braces and stuff, but it's kind of close enough to Ruby that you've recognized what it's trying to do. So given that you're at RubyConf, you probably already know about this gem called treetop, which we can use to parse languages, like build parses. And I'm just going to very, very quickly show you how we can build a grammar for that simple language. The grammar for this language looks like this. You just write a file. You say this is a grammar for the simple language, and then you just need to write rules that explain what the syntax of each of the different kinds of statement and expression in your language look like. You can say a sequence is two statements separated by a semicolon, a while loop says while bracket and then a condition and then curly braces around the body of the while loop. An assignment looks like a variable name and an equals sign. There's some more rules there. Conditionals, binary expressions here, less than add and multiply. And then down at the bottom, you get to the atomic things like numbers and Booleans and variables, right? So I'm just going to scoop past that. But if you write a file like that that explains what your programming language looks like, you can use the tree top gem to load that grammar file, and it will generate you a parser class named after the grammar. And then I can instantiate that parser class and say, make me a new parser and then parse this string. And what tree top will do is give you back this big data structure called a concrete syntax tree or a parse tree. And this has got a lot of information in it about the exact sort of lexical structure of the string you gave it and how it breaks down into all its component parts. There's a lot of information in there that we're not very interested in. But that's a good start. We don't want a concrete syntax tree. We want an abstract syntax tree, which is a more useful representation of the structure of the statement we gave it. And we can make an abstract syntax tree. By first, we can declare a bunch of classes that we're going to use to instantiate to make the nodes of the abstract syntax tree. And I'm just going to use struct to do that. So I'm going to define a new class for each kind of, each different kind of expression and statement. And some of them, so all these binary expressions have got a left and a right sub-expression assignments. I've got the variable name and the expression that's being assigned to it and so on. Now going back to the grammar, in each of these rules that matches a particular kind of syntax, you can put some Ruby code in here and say, whenever I get one of these number nodes in the concrete syntax tree, I want to define a method on that called 2ast, which is arbitrary. I've made that up. And then when I call that, I want that to manufacture a new instance of the number class in this case. And that just needs to contain the integer version of the text string that was inside, you know, that was the number. I can define versions of those for, you know, the Booleans and variables. And each of these is just building a new instance of my custom abstract syntax tree classes, right? So looking at those, these are just three definitions of the same method on different kinds of concrete syntax tree node that will help me create one of these abstract syntax tree nodes, you know, from it. And similarly for things like these statements, I can go in and put, you know, put more of these method definitions in. These are mostly just recursively converting their sub-expressions or sub-statements into abstract syntax trees and then going them together with the right, the right kind of node class. So once I've done all of that work, I can get tree top to build me a concrete syntax tree and then I can call two AST on the root node and then that will recursively convert the whole thing into an abstract syntax tree, which is a nice data structure that's made up instances of classes that I defined, right? So this is saying that this statement here is, you know, a sequence of assignments and actually just to visualize that, you can see that this statement is a sequence of two assignments. The first assignment is assigning the number two to X and the second assignment is assigning the result of multiplying X and three to Y, right? So now I've got this abstract syntax tree, I can evaluate the abstract syntax tree by recursively walking over it. An easiest way to do that is just to define a method on all of the different kinds of node and then I can call the method on the root node and it will recursively, I can define it so it recursively walks over the tree. So again, just briefly, I'm going to define an evaluate method on each of those abstract syntax tree classes and the evaluate method is going to take an environment, which is the electrical environment, it's a hash that says what the value of each variable currently is. So if you're evaluating a number or a Boolean, it doesn't care what's in the environment, you always just get out the value that you stored inside that node. If you're evaluating a variable, then it looks in the environment and pulls out the variable with that name, right? So that means that I can, if I make a new number instance and evaluate that in an empty environment, I just get the original number back, same with Booleans. If I evaluate a variable Y in this particular environment that gives Y the value 11, then I'll get 11, whereas if I evaluate in a different environment that gives Y a different value, I get the different value out, right? So those are the simplest possible expressions to evaluate. These are the definitions of evaluate for those binary expressions and these just recursively evaluate their left and right sub expressions and then they perform the operation that corresponds to the kind of node that we've got. So if it's an add node, we add them, if it's multiply, we multiply them, if it's less than, we compare them with less than. So that means I can make something like a multiply expression X times Y and evaluate that inside this environment and I get the result 6. If I make a less than node instead that is X less than Y, the answer is true in that particular environment. And I can do that again for statements. I'm not going to go into any detail here, but for example, you can see that the, for assignment statements, oh, so statements don't return a value, they return the new environment. So when I do an assignment, for example, I recursively evaluate the expression inside the assignment and then I update the environment to have a new mapping from the variable name to the new value of that sub expression and so on for all of these, the rest of these things. You know, sequence kind of evaluates the first, you know, the first statement first to get an updated environment and then it evaluates the second statement in the updated environment to get the final environment and so on. So once I've done all of that stuff, I can now do things like when I evaluate an assignment that is X is assigned the value 1. If I start with an empty environment and I evaluate it, I get a new environment where X has got the value 1. If I do a sequence of assignments, X equals 1 and then X equals 2 in an empty environment, I end up with X equals 2 because that's kind of clobbered the first assignment. And the point of doing all this is so that I can chain things together and say, use the parser to parse this, this program and then evaluate the abstract syntax tree in an empty environment. So if I evaluate X equals 2, Y equals X times 3 in an empty environment, I get X is 2, Y is 6. That's like the result of my program. And I can do that with a, you know, a more sophisticated program that's got a while loop in it. So I can do that with a program that starts out X at 1 and it keeps multiplying it by 3 until the value becomes greater than 5 and then that finishes up with X being the value of 9. So that all works. It's all fairly straightforward. That's what an interpreter is, really. The point of an interpreter is that it provides what I'm calling single stage execution. And what I mean by that is you've got your interpreter and you provide a source program into the interpreter. And then in general, although we didn't do it in the case I just showed you, you will also be, also provide some input to the program. So if the interpreter is Ruby, you'll provide a Ruby program as the source and then the input will be whatever, standard input or command line arguments or whatever. So you provide all of that stuff to the interpreter and then the interpreter is what runs on the machine and then that produces the output. And of course here we're assuming that the interpreter is already written in a language that can run on the underlying machine. This doesn't need to be because we're using the interpreter to run the source program on the underlying machine, right? And this all happens at the same time. This is the single stage of program execution. That's what I'm calling runtime, that's what you would call runtime. So what about compilers? How are they different? Well, they're pretty similar, really. They work in a similar kind of way. They read some source code and then they build an abstract syntax tree by parsing the source code. But then they do a different thing, which is rather than perform the instructions they find in the abstract syntax tree, they generate some target code by walking over the abstract syntax tree and emitting some instructions as they find them. So I'm not going to, I don't have time to go into any detail of how to do this properly, but I am going to show you an example. So here's a version of, instead of having evaluate defined on those abstract syntax tree nodes, I could define a method called toJavascript. And this is just going to return a string which contains some JavaScript code that does whatever that node is supposed to do. The JavaScript code I'm generating here, rather than using real JavaScript variables and having to deal with all of JavaScript's like weird variable scoping stuff, I'm just turning every piece of, every simple program into a JavaScript function that takes an object that's got mappings of variable names to values and then kind of updates that environment. So or in this case, when you have expressions, like a number is going to turn into a function that just returns a constant number and a Boolean is going to return a constant Boolean and a variable is going to look up the variable in the environment. So this is a JavaScript variable and then it's going to look up the right value in that, in that JavaScript object. It's very quickly same for these kind of binary expressions. I just like recursively convert the left and right sub expressions to JavaScript and then add them together or multiply them together or whatever. And then, you know, don't try to read all this, but this is how for all of the statements, I'm really just generating the JavaScript syntax. So if turns into a JavaScript if and a sequence turns into kind of JavaScript sequencing and a while turns into a JavaScript while loop. So that's all pretty straightforward. And the point of doing that is so that I can take like this program that I showed you before, x equals 1 while x is left in 5, turn that into JavaScript and now that's kind of been compiled into an admittedly much longer JavaScript program. But this is a JavaScript program that does the same thing as the program I started with that was written in a different language. And so I can take that big JavaScript program, this is the same program formatted more nicely, and place it on the Node.js console and say, look, here's my program and then you probably can't see it at the bottom here. When I run this program in JavaScript, I get the result x is 9. So that compiler I just showed you is extremely stupid. It's not a good compiler, but it does let us execute those simple programs if our machine only understands JavaScript. So the difference between an interpreter and a compiler really is that a compiler provides two-stage execution. When you've got a compiler, you just give it the source program as input and then the compiler runs and it generates something that we usually call the target program. And then later on, at a different time, you can take the target program, which was just data when the compiler admitted it, and put the target program inside a machine and run it. And that's when you provide the input to your program and then your target program runs and you get the output out. So we've still achieved the same thing as with an interpreter, but now it's been kind of staged in two pieces. And the first piece is what we call compile time and the second piece is what we call run time. So the good news about compilers is that compiled programs run faster. Staging the computation like this removes the interpretive overhead at run time. And by interpretive overhead, I mean all of that faff of parsing the program and walking over the AST and deciding what you're going to do with it. That all gets done at compile time. And by the time the program runs, that work's already been done. And so if you're going to run the program a million times, it makes sense to do the interpreting stuff once and then just run the target code that doesn't have all of that kind of overhead. There are other kind of performance benefits that I'm not talking about in this talk, but for example, your compiler can use like clever data structures or clever optimizations to make the target program more and more efficient, especially if it knows about the underlying architecture of the machine and stuff like that. So that's the good news. The bad news is that compilation is just harder to do than interpretation. So there are a few reasons for that. First, you have to think about two times instead of one. You're not just, when you write an interpreter, you're just thinking, well, I'm running right now. I'm the interpreter. I'm going to do what that program says to do right now. When you're writing a compiler, you're thinking about compile time and run time. So in your head, you have to have this model of like, well, what am I doing now as the compiler? And then what's the target program going to do later when it actually gets executed? So that's harder. You also have to implement in two languages instead of one. With an interpreter, you're just implementing in the interpreter language. With that compiler I showed you, the compiler was implemented in Ruby, but what it did was generate some JavaScript code. So to write the compiler, I was actually writing in two programming languages, kind of intertwine, and that's harder to kind of get your head around. And also, in a very vague hand wave, you sense, compiling dynamic languages is fundamentally challenging. If you want to compile a language like Ruby or JavaScript or something, you can't, it's not enough to just look at the static program and then convert it into some kind of target program because the static program doesn't tell you everything about what might happen at run time, right? If you've got things like defined method and you can create new classes and things like that, it's just hard to write a compiler for languages that kind of, whether programs can change dynamically as they execute. So long story short, writing an interpreter is easier than writing a compiler, but interpreters are slower than compilers, right? Interpreters only run at one time. They only use one language, and they can be as dynamic as you like if the program changes when it runs, and that's fine because you can just change the abstract syntax tree as the program runs and the interpreter will just keep working. So ideally, we would just write interpreters for our programming languages, but unfortunately, they're slower, and so usually we end up writing compilers. So I want to tell you about a third kind of thing, which is like interpreters and compilers, and these are called partial evaluators. Now a partial evaluator is like a cross between an interpreter and a compiler. An interpreter kind of does this job of executing a program right now, and compilers do this job of generating a program now and then executing it later. Now partial evaluators kind of live in the middle, they're like a hybrid of these two things. They execute some of the code now and then leave the rest of it for execution later. So what that means is you give a partial evaluator your subject program it's called, you know, the program you want it to partially evaluate, and you give it some of the inputs for that program, and it evaluates only the parts of the program that depend on the inputs that you've provided. And then whatever's left afterwards is called the residual program. It's like what you have left, you know, if you like boil a liquid and you get a residue left over, this is kind of the residual program after you've done your partial evaluation. So what this looks like is instead of taking your subject program and running it directly on a machine and sort of providing an arbitrary number of inputs to your program, again like command line arguments or standard input or config files or whatever, and then executing it and getting an output. Again, this is like a single stage computation. What partial evaluation lets you do is kind of pick out part of this process, say like the first input being fed into the subject program, and kind of do it earlier. You can kind of time shift it into the past and say, well, this is the computation I ultimately want to do at some point in the future, but I want to do this part of it now and save the rest for later. So by time shifting this stuff into the past, that means you take the program and the input and instead of running this program, you treat it as data, treat it as input to a partial evaluator. So this is like a compiler or interpreter. It will read in a program and it will read in some of the input for that program. And then when you execute the partial evaluator, it will produce this residual program. And then later, you can take that residual program and run it on a machine and feed in the rest of the input to the original program. That will run and give you the final output. So the idea of a partial evaluator is it lets you kind of split a single stage execution into two stages by sort of time shifting the processing of some of the input from the future when you're going to run the program to the present. You can do some of the work earlier. So that's easy enough to say, but how do these partial evaluators work? Well, they work a lot like compilers and interpreters. They're just more complicated and I don't have time to show you how to build one in Ruby. But briefly what happens is you read in some source code just like an interpreter or a compiler. You build an abstract syntax tree just like an interpreter or a compiler. But then you read some of the inputs to that program. And once you've read some of the inputs to the program, you analyze the program, you walk over the abstract syntax tree, you do usually just a static analysis to find all of the places where the inputs that have been provided are used in the program. And once you've found those places, you can partially evaluate the program by going to all of those places where the inputs have been used and evaluating them and then putting like new code in to replace them with the results of the evaluation. And then once you've finished doing that, you've got this residual program that you can emit. So I can't really give you a whole program example in Ruby in the time I've got, but I just want to show you a really basic example to just kind of give you a feel of what's going on here. So just for demo purposes, I'm going to show you this on the level of an individual method. So imagine we've got a partial evaluator for Ruby and I've got this Ruby method, which is power. So this is raise x to the power of n. So if I passed in 3 as the value of n here, it's going to do x multiplied by power 2x and it's going to recursively multiply x by itself three times, right? So say that I've told my partial evaluator that I know that this method is going to be called with 5 as the first argument. So I know I'm going to be calling it with the value of n being 5. So what the partial evaluator is going to do is kind of start looking at this method and say, OK, so I know what the value of n is going to be. So I can find all of the other places where n is used. And by doing that, I can find all of the sub-expressions in this method that I can evaluate now. I don't have to wait to find out what the value of x is because these expressions are independent of the value of x. So once it's found those expressions, it can start like evaluating them and replacing them. So what we're going to do is instead of having this power method that takes two arguments, we're going to make a method called power 5 that only takes one argument x and the value of n is going to be like fixed in this method. So all of those instances of n, I'm just going to turn into 5. And then we can start partially evaluating this and saying, well, I can already tell you what the value of 5.0 is going to be. That's going to be false. And then once you've done that, you've now got a conditional here which you are able to accept by sort of propagating the information about what expressions are available. You can say, well, I know that this thing is just going to evaluate to this guy here, right, because it was if false. And now I've got this 5 minus 1. I can evaluate that to get 4. And then I can do some kind of, I can inline the body of this method here. If I know that I'm going to be calling power with 4 and x, then I can just get this code in here with 4 substituted for the value of n. And then you can just keep doing the same thing. You can say, well, 4.0 is going to be false. So that means that bit of the program is going to be x times power 4 minus 1. And that's going to be power 3x. And you can keep going. So 2, 1, 0. You keep generating more multiplied by x's. When you get down to 0, you get into this situation where now you're saying, if 0.0, which is going to evaluate to true, which means you're going to end up with 1 there. So just to tidy that up a bit, you end up with a definition of power 5. But it's just x multiplied by itself five times. And they're multiplied by 1. And actually, most partial evaluators will be smart enough to realize that if you've got something which is a number, and you multiply it by 1, then you can just get rid of that. So this is kind of the residual program that's left over after the partial evaluation. And you can see it's made of bits of the original program, just kind of like rearranged and stuck together in different ways. The partial evaluator hasn't made any new Ruby. It's just used all of the existing Ruby and kind of moved bits of it around and figured out what it should look like. And the point of doing this, of course, is that this version of power 5 should be faster. This doesn't make any recursive method calls. It just multiplies x by itself five times, whereas this thing has got every recursive call. You've got a new stack frame. It does a conditional, and then it does another multiplication and stuff like that. So this is like a better version of the original method, if you know that n is going to be 5. And just as a side note, this isn't the same thing as partial application, which you might be thinking about, which what partial application is, is when you've got a method like this, and you make a new method that just fixes one of the arguments to it. So I could define power 5 by just saying, well, call power with 5 as its first argument. And if I run that on the console, then that does work. Power 5 of 2 is 32, because that's 2 to the power of 5. But this new version of the method isn't any, isn't better than the original one. I mean, actually calling this is going to be slightly slower because you get another stack frame, there's another method execution going on there. Another way of doing this in Ruby is instead of defining a new method here, what I could do is turn this power method into a proc, and then I could use the curry method on it to turn it into a courage proc, and then I could call that with one argument, and that will return me a new proc, which when I call it with the second argument, it gives me a new value bet. So partial application is a little bit similar, but partial application is a technique that you do inside your program. You make new values, new function values in functional programming terms that allow you to fix the arguments to some of your other functions. But partial evaluation is something that happens from the outside of your program. It's like a source level transformation of your program that hopefully makes it faster and more specialized to particular input values. So I just wanted to note that there are a couple of useful applications of this technology. The main point of this is that you can take a general program and a partial evaluator that can specialize it for you for a fixed input. So this is kind of the best of both worlds. You can write a general program that is, you know, maximally general and can accept lots of different kinds of input, but then you can use a partial evaluator to produce a specialized version of it that has got all of the overhead involved in choosing what kind of thing you're dealing with, kind of baked out of it, and then you can run the specialized version of the program, which will hopefully be faster. So that's pretty good. Some of the things you could do with that, for example, if you've got a web server like Apache or Nginx, you know, that reads in a config file when it starts up, and the config file controls the execution of the web server. And you have to imagine that the web server is spending some of its execution cycles like checking stuff that it's been configured to do. And so in principle, what you could do is specialize the whole, you know, web server and give it just your config file as the input, and the partial evaluator will generate your new version of the web server that's designed just to run your config file, and hopefully all the overhead of reading the config file and checking config flags is not going to be part of the program anymore. It will have been partially evaluated away. Similarly, this is the classic example in the partial evaluation literature. It's like a ray tracer. If you had a three-dimensional scene and you wanted to fly a camera through it, then you might end up rendering a million frames with your ray tracer as the camera moves through the scene. But the scene's the same every time. So you could take a general ray tracer and specialize it with respect to a particular scene file, and the partial evaluator will generate you a new ray tracer that can only ray trace that scene. And then if you run that a million times, and each time you move the camera slightly, all of the overhead of building all of the polygons and stuff in the scene and, you know, figuring out what all the directives in the scene file mean and stuff like that will have gone away. And a third sort of slightly more practical but more questionable example is in Mac OS 10, the OpenGL pipeline is, bits of the OpenGL pipeline are written in LLVM intermediate language, and it has implementations of stuff which is implemented in hardware on some GPUs. So Apple ship all of the software implementations of all of the stuff that your GPU may or may not do in LLVM intermediate representation. And then when you actually run it on your machine and it can see what your GPU is capable of, all of the stuff that your GPU already does kind of gets partially evaluated away and it just runs on hardware, whereas all the features that your GPU doesn't have is kind of stay in the OpenGL pipeline written as software, right? So anyway, at the beginning, I promised you I was going to tell you a cool story. So here's the cool story. In 1971, this guy, Yoshihiko Futamura, realized something cool when he was working at Hitachi Central Research Laboratory. He was thinking about partial evaluation. He was thinking about how with partial evaluation, you have your inputs and your subject program and you get your output and you can use partial evaluation to timeshift that bit to do it earlier so that you get this residual program that you can run later. And he was thinking about that in the context of interpreters and thinking, well, an interpreter is just a computer program and it's just a program that I provide inputs to and then that program runs and then I get some output. I mean, one of the inputs happens to be a program, but it's basically just a box that takes two inputs and I get some output out. So what would happen if I used partial evaluation to timeshift some of this work if I did this part of the computation earlier so that I could do the rest of it later with a residual program? So here's what happens. If you treat the interpreter as data rather than executing it as a program, you feed the interpreter into a partial evaluator and you get this residual program out. So this is called partially evaluating the interpreter with respect to the source program. So this is an input to the interpreter. If you put both of them in the partial evaluator, you get a residual program out, right, which has done half of the work of the interpreter. And then at some later time, you can take that residual program, run it with the original input to that program and you get the output. So he was looking at this and thinking about it and so I'm saying, well, this thing I've got down here that reads in input and then produces output, like that's usually what we'd call the target program. This is a version of the source program that will execute directly on the underlying machine. So what I've got myself there is a target program. So that means that what I got out of the partial evaluator was a target program. So there's something up here which is read in a source program and it's generated a target program which I can run later. So what is this thing that I've got in the green box? Anyone? That's the compiler, right? So there's your compiler for free, no refunds. So that's pretty cool. How does that work? Does that, I mean, that seems like too good to be true, right? Let's just go through a quick example. So here's my simple interpreter written in Ruby. I've added some furniture, right? So the actual overall program that works as a simple interpreter is going to read in the source and the starting environment, the bindings and variables to their values from somewhere. It's going to somehow acquire the source code in the environment and it's going to use tree top to load the grammar and then it's going to instantiate the parser and then turn it into an abstract syntax tree and then let's say it's just going to print out the result of evaluating the original program in the environment we provided, right? So if we're going to do what Futenmaura suggested, we're going to feed this into a partial evaluator and we're going to give it the simple source program as like partial input and then we're going to evaluate as much of the program as we can and see what's left over. So that means that we're going to provide a particular source. So one way or another we're going to arrange that when this thing tries to read its source, it actually gets the string of a simple program. So this x equals 2, y equals x times 3 is just an arbitrary program. So firstly our partial evaluator can do some static analysis of this program. It can do some constant propagation and say, well, if source is going to be that guy, then actually this instance of source here is going to be that code and we don't even need source anymore. It's not mentioned anywhere. And now it knows what the value of this string is, it can partially evaluate all of this stuff. So this treetop loading the grammar and then building the AST by parsing this string and then calling to AST on it. We've already got all of the code to do that and now we've got all of the inputs to do that. I mean, I guess we're also assuming that the grammar is available. So assuming we just do all of that work, we end up with a program that looks like this, which is just the abstract syntax tree should be the result of parsing that program and turning it into an abstract syntax tree, which is the stuff I showed you before. So it's able to do all of this work up front because it knows what the source program is going to be. So all that this program does now is it reads in an environment from somewhere and then it constructs the abstract syntax tree, this literal one, and then it just calls evaluate on it with whatever the environment is. So what does calling evaluate on this abstract syntax tree do? Well, we've already got all the code to do that as well. That's already part of the interpreter. I haven't showed it all on this slide, but I'm assuming that we've got all of that stuff built into the simple grammar, right? So this is the abstract syntax tree that we've got. And each one of these nodes, each one of these instances of a syntax class has got a definition of evaluate on it. So if a sequence evaluate looks like evaluate the first statement in the environment and then use that as the input to evaluate in the second statement in the environment, these assignments have got definitions that say evaluate the expression and then update the environment with a mapping from the variable name to the value of evaluate on that expression. That multiply just says evaluate the left hand, expression evaluate the right hand one, multiply them together. And all of these things, like number and variable, just have these simple definitions that either just return their value or in this case just pulls the value out of the environment. So we've got all of the data in this abstract syntax tree and we've got all of the code. And actually the partial evaluator can boil all of this down to just a couple of lines of Ruby code, right? So firstly, all of these places where here we've got value and name and value. Well, we know that the value is 2 and we know that the name is x and we know that the value is 3 there. So all of those things can just be inlined in those definitions of those methods by the partial evaluator. And then all of these places where we're saying evaluate the expression, evaluate the left expression, evaluate the right expression, we know that they're going to be 2 and environment x and 3. So we can inline all of those things into these definitions here. And then again here we can see that the name is going to be x, the name here is going to be y and the result of evaluating this expression is going to be environment x times 3. So we can like inline all of that stuff. And then finally up here we can see, well, evaluate the first expression is just going to be this environment.merge x maps to 2 and this evaluate the second expression, the second statement sorry is going to be update the environment. It's a little bit tricky because the environment gets mentioned twice here. So what I'm going to need to do is, you know, the partial evaluator would be able to do this, just evaluate that first expression and assign it to a variable and then use that variable here. So I've kind of glossed over a lot of detail there, but you can see that all of the code and data that you need is there for the taking and it can all be boiled down. So the code I've ended up with just tidied up slightly is that, right? Calling evaluate on the root node of that abstract syntax tree is going to do this. The environment is the result of updating the environment with x is mapped to 2 and then we make a new environment where y is mapped to whatever the value of x is times 3. So back to this original thing here, when we call ast.evaluate with environment, we can replace all of this stuff with just that code that we just generated, right? So this is what we end up with. Reading the environment, make a new one by making x equal to 2 and then print out the result of merging in y is equal to whatever the value of x is times 3. And so comparing that to the simple program that we started with, that in a, like, I've waved my hands through all of that, but you can see that we've sort of compiled this simple program into Ruby now. We've got a Ruby program that does what this thing does. I mean, there's some machinery involving environments and stuff, but basically we've turned it into Ruby. But in order to do that, I didn't have to write any new Ruby. This thing here is just bits of the interpreter stuck together. And the partial evaluator has stuck together bits of source code from the interpreter in such a way that it's now a Ruby implementation of the program we started with. So that's kind of how you can compile stuff with partial evaluation. So this is the called the first Futimora projection, right? If you partially evaluate an interpreter with respect to some source code, you get a target program. So that's really good. Futimora was pretty pleased with himself when he realized that. So this is the picture I showed you before. But he was thinking about this. Specifically, he was thinking about the first part of this. And he was thinking, well, when I'm feeding an interpreter and a source program into the partial evaluator and getting a target program out later, I'm really just passing inputs into a program. So what would happen if I used partial evaluation to timeshift some of this and do it earlier? If I fed the interpreter into the partial evaluator first and got a residual program out that I could then feed the source program into. Would that work? So we tried that. Here's what happens. So treating the partial evaluator as input, you can feed the partial evaluator and the interpreter into the partial evaluator. And when that runs, you get a residual program out. When you've got the residual program, then later on, you can run that with the source program as input. And you get a target program out. And then later on, you can run the target program with the original input to the program as input and get some output out. So that makes sense. We've just split it apart with time again. But when he looked at this, he saw, well, what I've got here is that I've got a source program going into the residual program. And I get out the target program. So what is this residual program that I've got? Right. That's the compiler. So that means that what I got out of the thing here was a compiler. So that means that what I've got myself here is a compiler generator. So this means that if you've got any interpreter, you can feed it in. You can specialize. You can partially evaluate a partial evaluator with respect to that interpreter. And you can get a compiler for that language. So this is sort of a higher order version of what I showed you the first time. This gives you a mechanism for generating a compiler. And then you can feed any source program into it. You don't need to involve the partial evaluator at this point. You've just got a bona fide compiler that you can run. And it will compile your language. So that's really cool. That's called the second Futimora projection. If you partially evaluate a partial evaluator with respect to an interpreter, you get a compiler. So Futimora was pretty pleased with himself when he realized that. And he was thinking about this. And specifically, he was thinking about this first bit. And he was looking at this and thinking, well, really, this is really just feeding input into a program. So what would happen if I time-shifted this part of the execution and did it earlier so that I could get a residual program out and then I could feed the interpreter into it later to do what I'm doing here? So here's what happens if you do that. So you treat the partial evaluator as input. And so you feed the partial evaluator and the partial evaluator into the partial evaluator. And what you get out is a residual program. And then later on, you feed the interpreter into the residual program. And then that runs, and then you get a compiler. And then later on, you run the compiler with the source program as input, and then you get a target program. And then later on, you run the target program with input as input, and you get the output. But this thing here, the residual program that takes an interpreter and turns it into a compiler, is a compiler generator. So that means that what we've got out of the thing here was a compiler generator. So what's this thing we've got on the top? It's a compiler generator generator. So this is the third Futumora projection, right? If you partially evaluate a partial evaluator with respect to a partial evaluator, you get a compiler generator. And thankfully, we can't take it any further than that. Because if you did this again, you'd still be partially evaluating a partial evaluator with respect to a partial evaluator, right? So there are only three Futumora projections. So this is really cool. And this is why I wanted to tell you about this. I think it's funny and interesting and unusual. However, it doesn't mean that we don't need compiler writers anymore, right? Partial evaluation is a fully general technique for evaluating bits of computer programs. So it gets rid of the interpretive overhead of evaluating a program. But it doesn't do any of the clever stuff like inventing new data structures or optimizations or doing anything platform-specific. So we still need smart people to write compilers to make our programs go far. But this technique does remove some of the overhead of interpretation, right? It removes all of that stuff that involves parsing and generating code and all of that stuff. So if you're sufficiently interested in this, that you'd like to learn more, then there's a really interesting book called Partial Evaluation and Automatic Programme Generation, which is now available for free. So if you go to that URL there, you can download a copy of that. It's a really good textbook. I recommend it. So various bits of software that you may or may not be familiar with use techniques like this. So the JIT in LLVM and the bits of the PyPy tool chains, like R-Python and the VM and the JIT that underlie that, use some of these program specialization techniques. Rubinius sits on top of LLVM. So when you use Rubinius, stuff that's a little bit like this is happening. And there's a Ruby implementation called Topaz that sits on top of the PyPy tool chain and is a Ruby implementation that's written in Python. So if you use the Topaz Ruby implementation, then stuff like this is happening inside Topaz when you run your program. It happens at runtime rather than compile time. And quite aside from the partial evaluation stuff, Rubinius and JRuby are great because they are compilers that have got interesting and accessible implementations. So if you feel like you could become interested, sort of in the spirit of Max's keynote yesterday, if you feel like you want to get involved with stuff and you're interested in these kind of programs that generate programs, then you could do a lot worse than cracking open Rubinius or JRuby and having a look at how they work and maybe submitting a pull request or something. So much more generally than that. If you're generally interested in this sort of thing, I've written a book about all this sort of thing, which uses Ruby to go over all of these kinds of things and interpreters and compilers and the lambda calculus and cellular automata and type systems and stuff. So if you're interested, there's a book that you can read. There's a website for it. I rarely have given me a discount code so you can get 50% off if you use RubyConf as the discount code. That's all I wanted to say. Thanks very much. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you.
 Good morning, everyone.  Thanks for coming to this talk.  I'm Tom Stewart.  I'm going to talk about getting compilers for free.  Although, actually, my agenda today is that I'm fascinated by programming, or to be more  specific, I'm fascinated by meta-programming.  It's something I'm really interested in.  So let's talk about meta-programming.  As Ruby programmers, we already intuitively understand the power of meta-programming,  right, programs that write programs.  So in Ruby, we've got things like instance eval and define method and method missing  and all these kind of tools for making programs that grow new functionality at runtime that  wasn't present in the static program that we started out with.  Now, there's another thing that I find even more interesting than that, which still kind  of counts as meta-programming, which is programs that manipulate representations of other programs,  right, programs that operate on data, which itself represents a program, and then does  something with that representation, like analyzes it, or evaluates it, or translates it, or transforms  it.  So this is kind of the world of compilers and interpreters and static analyzes, and I  think it's really fascinating in a way it's kind of the purest or the most self-referential  kind of software that you can write.  So in this talk today, I'd like to make you look at programs differently.  I don't have a complicated technical point to make.  I just want to tell you a cool story and hopefully convince you that programs which manipulate  other programs are interesting and hopefully kind of inspire you to find out some more  about them.  So I'm going to start out by just talking about something we're all familiar with, which  is executing programs.  So you write a program, right?  You have a program written down that you want to run, and you have a machine that you can  run that program on.  So you put that program into the machine, and then you've got some inputs for that program,  and those might be command line arguments or configuration files or standard input or  whatever, and you feed all of those inputs into the machine that's got the program inside  it, and the program executes on the machine, and it produces an output.  I think we're all kind of familiar with how computers work, right?  But that only works if the program that you wrote is written in a language that the machine  kind of natively understands.  So in terms of a real machine, that'll be, you know, the program has to be written in  machine code.  And if it's, if the program's written in a higher level language, then maybe you can  run it on some kind of like virtual machine that understands that language specifically.  But if your program's written in a language that's unfamiliar to the machine, then you're  going to need an interpreter or a compiler to be able to execute it, right?  So interpreters, how does an interpreter work?  Well, very kind of roughly the way it works is it reads in some source code of the program  you want to execute, and then it builds an abstract syntax tree by parsing that source  code, and then it evaluates the program by walking over the abstract syntax tree and  performing the instructions that it finds inside the tree.  And this is basically how, you know, MRI pre-1.9 did its job, right?  So I'm going to show you a little demo of how this works by just introducing this, a  language that I'm going to call simple.  It's just a toy language.  Simple is like an abbreviation for a simple imperative language.  This language is really straightforward.  It looks a little bit like Ruby, but not exactly the same.  Statements look like this.  So simple's got expressions and statements unlike Ruby.  It's got expressions like 19 plus 23.  Expressions just evaluate to a value.  It's also got statements like assignments.  So a equals 19 plus 23 is a statement, and that statement is going to have, is going  to modify the lexical environment.  So when you evaluate a statement, it's going to update the bindings between variable names  and their values.  So the effect of executing that statement is that after the statement is executed, a  has got the value 42, right?  Some other statements, it's got sequencing in it.  It's got conditionals in it.  It's got while lips in it, right?  Very basic language.  It's not quite Ruby because it's got curly braces and stuff, but it's kind of close enough  to Ruby that you've recognized what it's trying to do.  So given that you're at RubyConf, you probably already know about this gem called treetop,  which we can use to parse languages, like build parses.  And I'm just going to very, very quickly show you how we can build a grammar for that simple  language.  The grammar for this language looks like this.  You just write a file.  You say this is a grammar for the simple language, and then you just need to write rules that  explain what the syntax of each of the different kinds of statement and expression in your  language look like.  You can say a sequence is two statements separated by a semicolon, a while loop says while bracket  and then a condition and then curly braces around the body of the while loop.  An assignment looks like a variable name and an equals sign.  There's some more rules there.  Conditionals, binary expressions here, less than add and multiply.  And then down at the bottom, you get to the atomic things like numbers and Booleans and  variables, right?  So I'm just going to scoop past that.  But if you write a file like that that explains what your programming language looks like,  you can use the tree top gem to load that grammar file, and it will generate you a parser  class named after the grammar.  And then I can instantiate that parser class and say, make me a new parser and then parse  this string.  And what tree top will do is give you back this big data structure called a concrete  syntax tree or a parse tree.  And this has got a lot of information in it about the exact sort of lexical structure  of the string you gave it and how it breaks down into all its component parts.  There's a lot of information in there that we're not very interested in.  But that's a good start.  We don't want a concrete syntax tree.  We want an abstract syntax tree, which is a more useful representation of the structure  of the statement we gave it.  And we can make an abstract syntax tree.  By first, we can declare a bunch of classes that we're going to use to instantiate to  make the nodes of the abstract syntax tree.  And I'm just going to use struct to do that.  So I'm going to define a new class for each kind of, each different kind of expression  and statement.  And some of them, so all these binary expressions have got a left and a right sub-expression  assignments.  I've got the variable name and the expression that's being assigned to it and so on.  Now going back to the grammar, in each of these rules that matches a particular kind  of syntax, you can put some Ruby code in here and say, whenever I get one of these number  nodes in the concrete syntax tree, I want to define a method on that called 2ast, which  is arbitrary.  I've made that up.  And then when I call that, I want that to manufacture a new instance of the number class  in this case.  And that just needs to contain the integer version of the text string that was inside,  you know, that was the number.  I can define versions of those for, you know, the Booleans and variables.  And each of these is just building a new instance of my custom abstract syntax tree  classes, right?  So looking at those, these are just three definitions of the same method on different  kinds of concrete syntax tree node that will help me create one of these abstract syntax  tree nodes, you know, from it.  And similarly for things like these statements, I can go in and put, you know, put more of  these method definitions in.  These are mostly just recursively converting their sub-expressions or sub-statements into  abstract syntax trees and then going them together with the right, the right kind of  node class.  So once I've done all of that work, I can get tree top to build me a concrete syntax  tree and then I can call two AST on the root node and then that will recursively convert  the whole thing into an abstract syntax tree, which is a nice data structure that's made  up instances of classes that I defined, right?  So this is saying that this statement here is, you know, a sequence of assignments and  actually just to visualize that, you can see that this statement is a sequence of two assignments.  The first assignment is assigning the number two to X and the second assignment is assigning  the result of multiplying X and three to Y, right?  So now I've got this abstract syntax tree, I can evaluate the abstract syntax tree by  recursively walking over it.  An easiest way to do that is just to define a method on all of the different kinds of  node and then I can call the method on the root node and it will recursively, I can define  it so it recursively walks over the tree.  So again, just briefly, I'm going to define an evaluate method on each of those abstract  syntax tree classes and the evaluate method is going to take an environment, which is  the electrical environment, it's a hash that says what the value of each variable currently  is.  So if you're evaluating a number or a Boolean, it doesn't care what's in the environment,  you always just get out the value that you stored inside that node.  If you're evaluating a variable, then it looks in the environment and pulls out the variable  with that name, right?  So that means that I can, if I make a new number instance and evaluate that in an empty  environment, I just get the original number back, same with Booleans.  If I evaluate a variable Y in this particular environment that gives Y the value 11, then  I'll get 11, whereas if I evaluate in a different environment that gives Y a different value,  I get the different value out, right?  So those are the simplest possible expressions to evaluate.  These are the definitions of evaluate for those binary expressions and these just recursively  evaluate their left and right sub expressions and then they perform the operation that corresponds  to the kind of node that we've got.  So if it's an add node, we add them, if it's multiply, we multiply them, if it's less  than, we compare them with less than.  So that means I can make something like a multiply expression X times Y and evaluate  that inside this environment and I get the result 6.  If I make a less than node instead that is X less than Y, the answer is true in that particular  environment.  And I can do that again for statements.  I'm not going to go into any detail here, but for example, you can see that the, for  assignment statements, oh, so statements don't return a value, they return the new environment.  So when I do an assignment, for example, I recursively evaluate the expression inside  the assignment and then I update the environment to have a new mapping from the variable name  to the new value of that sub expression and so on for all of these, the rest of these  things.  You know, sequence kind of evaluates the first, you know, the first statement first  to get an updated environment and then it evaluates the second statement in the updated  environment to get the final environment and so on.  So once I've done all of that stuff, I can now do things like when I evaluate an assignment  that is X is assigned the value 1.  If I start with an empty environment and I evaluate it, I get a new environment where  X has got the value 1.  If I do a sequence of assignments, X equals 1 and then X equals 2 in an empty environment,  I end up with X equals 2 because that's kind of clobbered the first assignment.  And the point of doing all this is so that I can chain things together and say, use the  parser to parse this, this program and then evaluate the abstract syntax tree in an empty  environment.  So if I evaluate X equals 2, Y equals X times 3 in an empty environment, I get X is 2, Y  is 6.  That's like the result of my program.  And I can do that with a, you know, a more sophisticated program that's got a while loop  in it.  So I can do that with a program that starts out X at 1 and it keeps multiplying it by  3 until the value becomes greater than 5 and then that finishes up with X being the value  of 9.  So that all works.  It's all fairly straightforward.  That's what an interpreter is, really.  The point of an interpreter is that it provides what I'm calling single stage execution.  And what I mean by that is you've got your interpreter and you provide a source program  into the interpreter.  And then in general, although we didn't do it in the case I just showed you, you will  also be, also provide some input to the program.  So if the interpreter is Ruby, you'll provide a Ruby program as the source and then the  input will be whatever, standard input or command line arguments or whatever.  So you provide all of that stuff to the interpreter and then the interpreter is what runs on the  machine and then that produces the output.  And of course here we're assuming that the interpreter is already written in a language  that can run on the underlying machine.  This doesn't need to be because we're using the interpreter to run the source program on  the underlying machine, right?  And this all happens at the same time.  This is the single stage of program execution.  That's what I'm calling runtime, that's what you would call runtime.  So what about compilers?  How are they different?  Well, they're pretty similar, really.  They work in a similar kind of way.  They read some source code and then they build an abstract syntax tree by parsing the source  code.  But then they do a different thing, which is rather than perform the instructions they  find in the abstract syntax tree, they generate some target code by walking over the abstract  syntax tree and emitting some instructions as they find them.  So I'm not going to, I don't have time to go into any detail of how to do this properly,  but I am going to show you an example.  So here's a version of, instead of having evaluate defined on those abstract syntax  tree nodes, I could define a method called toJavascript.  And this is just going to return a string which contains some JavaScript code that does  whatever that node is supposed to do.  The JavaScript code I'm generating here, rather than using real JavaScript variables  and having to deal with all of JavaScript's like weird variable scoping stuff, I'm just  turning every piece of, every simple program into a JavaScript function that takes an object  that's got mappings of variable names to values and then kind of updates that environment.  So or in this case, when you have expressions, like a number is going to turn into a function  that just returns a constant number and a Boolean is going to return a constant Boolean  and a variable is going to look up the variable in the environment.  So this is a JavaScript variable and then it's going to look up the right value in that,  in that JavaScript object.  It's very quickly same for these kind of binary expressions.  I just like recursively convert the left and right sub expressions to JavaScript and then  add them together or multiply them together or whatever.  And then, you know, don't try to read all this, but this is how for all of the statements,  I'm really just generating the JavaScript syntax.  So if turns into a JavaScript if and a sequence turns into kind of JavaScript sequencing and  a while turns into a JavaScript while loop.  So that's all pretty straightforward.  And the point of doing that is so that I can take like this program that I showed you  before, x equals 1 while x is left in 5, turn that into JavaScript and now that's kind of  been compiled into an admittedly much longer JavaScript program.  But this is a JavaScript program that does the same thing as the program I started with  that was written in a different language.  And so I can take that big JavaScript program, this is the same program formatted more nicely,  and place it on the Node.js console and say, look, here's my program and then you probably  can't see it at the bottom here.  When I run this program in JavaScript, I get the result x is 9.  So that compiler I just showed you is extremely stupid.  It's not a good compiler, but it does let us execute those simple programs if our machine  only understands JavaScript.  So the difference between an interpreter and a compiler really is that a compiler provides  two-stage execution.  When you've got a compiler, you just give it the source program as input and then the  compiler runs and it generates something that we usually call the target program.  And then later on, at a different time, you can take the target program, which was just  data when the compiler admitted it, and put the target program inside a machine and run  it.  And that's when you provide the input to your program and then your target program runs  and you get the output out.  So we've still achieved the same thing as with an interpreter, but now it's been kind  of staged in two pieces.  And the first piece is what we call compile time and the second piece is what we call  run time.  So the good news about compilers is that compiled programs run faster.  Staging the computation like this removes the interpretive overhead at run time.  And by interpretive overhead, I mean all of that faff of parsing the program and walking  over the AST and deciding what you're going to do with it.  That all gets done at compile time.  And by the time the program runs, that work's already been done.  And so if you're going to run the program a million times, it makes sense to do the  interpreting stuff once and then just run the target code that doesn't have all of that  kind of overhead.  There are other kind of performance benefits that I'm not talking about in this talk, but  for example, your compiler can use like clever data structures or clever optimizations to  make the target program more and more efficient, especially if it knows about the underlying  architecture of the machine and stuff like that.  So that's the good news.  The bad news is that compilation is just harder to do than interpretation.  So there are a few reasons for that.  First, you have to think about two times instead of one.  You're not just, when you write an interpreter, you're just thinking, well, I'm running right  now.  I'm the interpreter.  I'm going to do what that program says to do right now.  When you're writing a compiler, you're thinking about compile time and run time.  So in your head, you have to have this model of like, well, what am I doing now as the  compiler?  And then what's the target program going to do later when it actually gets executed?  So that's harder.  You also have to implement in two languages instead of one.  With an interpreter, you're just implementing in the interpreter language.  With that compiler I showed you, the compiler was implemented in Ruby, but what it did was  generate some JavaScript code.  So to write the compiler, I was actually writing in two programming languages, kind of intertwine,  and that's harder to kind of get your head around.  And also, in a very vague hand wave, you sense, compiling dynamic languages is fundamentally  challenging.  If you want to compile a language like Ruby or JavaScript or something, you can't, it's  not enough to just look at the static program and then convert it into some kind of target  program because the static program doesn't tell you everything about what might happen  at run time, right?  If you've got things like defined method and you can create new classes and things like  that, it's just hard to write a compiler for languages that kind of, whether programs can  change dynamically as they execute.  So long story short, writing an interpreter is easier than writing a compiler, but interpreters  are slower than compilers, right?  Interpreters only run at one time.  They only use one language, and they can be as dynamic as you like if the program changes  when it runs, and that's fine because you can just change the abstract syntax tree as  the program runs and the interpreter will just keep working.  So ideally, we would just write interpreters for our programming languages, but unfortunately,  they're slower, and so usually we end up writing compilers.  So I want to tell you about a third kind of thing, which is like interpreters and compilers,  and these are called partial evaluators.  Now a partial evaluator is like a cross between an interpreter and a compiler.  An interpreter kind of does this job of executing a program right now, and compilers do this  job of generating a program now and then executing it later.  Now partial evaluators kind of live in the middle, they're like a hybrid of these two  things.  They execute some of the code now and then leave the rest of it for execution later.  So what that means is you give a partial evaluator your subject program it's called, you know,  the program you want it to partially evaluate, and you give it some of the inputs for that  program, and it evaluates only the parts of the program that depend on the inputs that  you've provided.  And then whatever's left afterwards is called the residual program.  It's like what you have left, you know, if you like boil a liquid and you get a residue  left over, this is kind of the residual program after you've done your partial evaluation.  So what this looks like is instead of taking your subject program and running it directly  on a machine and sort of providing an arbitrary number of inputs to your program, again like  command line arguments or standard input or config files or whatever, and then executing  it and getting an output.  Again, this is like a single stage computation.  What partial evaluation lets you do is kind of pick out part of this process, say like  the first input being fed into the subject program, and kind of do it earlier.  You can kind of time shift it into the past and say, well, this is the computation I ultimately  want to do at some point in the future, but I want to do this part of it now and save  the rest for later.  So by time shifting this stuff into the past, that means you take the program and the input  and instead of running this program, you treat it as data, treat it as input to a partial  evaluator.  So this is like a compiler or interpreter.  It will read in a program and it will read in some of the input for that program.  And then when you execute the partial evaluator, it will produce this residual program.  And then later, you can take that residual program and run it on a machine and feed in  the rest of the input to the original program.  That will run and give you the final output.  So the idea of a partial evaluator is it lets you kind of split a single stage execution  into two stages by sort of time shifting the processing of some of the input from the future  when you're going to run the program to the present.  You can do some of the work earlier.  So that's easy enough to say, but how do these partial evaluators work?  Well, they work a lot like compilers and interpreters.  They're just more complicated and I don't have time to show you how to build one in  Ruby.  But briefly what happens is you read in some source code just like an interpreter or a compiler.  You build an abstract syntax tree just like an interpreter or a compiler.  But then you read some of the inputs to that program.  And once you've read some of the inputs to the program, you analyze the program, you  walk over the abstract syntax tree, you do usually just a static analysis to find all  of the places where the inputs that have been provided are used in the program.  And once you've found those places, you can partially evaluate the program by going to  all of those places where the inputs have been used and evaluating them and then putting  like new code in to replace them with the results of the evaluation.  And then once you've finished doing that, you've got this residual program that you  can emit.  So I can't really give you a whole program example in Ruby in the time I've got, but  I just want to show you a really basic example to just kind of give you a feel of what's  going on here.  So just for demo purposes, I'm going to show you this on the level of an individual method.  So imagine we've got a partial evaluator for Ruby and I've got this Ruby method, which  is power.  So this is raise x to the power of n.  So if I passed in 3 as the value of n here, it's going to do x multiplied by power 2x  and it's going to recursively multiply x by itself three times, right?  So say that I've told my partial evaluator that I know that this method is going to be  called with 5 as the first argument.  So I know I'm going to be calling it with the value of n being 5.  So what the partial evaluator is going to do is kind of start looking at this method  and say, OK, so I know what the value of n is going to be.  So I can find all of the other places where n is used.  And by doing that, I can find all of the sub-expressions in this method that I can evaluate now.  I don't have to wait to find out what the value of x is because these expressions are  independent of the value of x.  So once it's found those expressions, it can start like evaluating them and replacing them.  So what we're going to do is instead of having this power method that takes two arguments,  we're going to make a method called power 5 that only takes one argument x and the value  of n is going to be like fixed in this method.  So all of those instances of n, I'm just going to turn into 5.  And then we can start partially evaluating this and saying, well, I can already tell  you what the value of 5.0 is going to be.  That's going to be false.  And then once you've done that, you've now got a conditional here which you are able  to accept by sort of propagating the information about what expressions are available.  You can say, well, I know that this thing is just going to evaluate to this guy here,  right, because it was if false.  And now I've got this 5 minus 1.  I can evaluate that to get 4.  And then I can do some kind of, I can inline the body of this method here.  If I know that I'm going to be calling power with 4 and x, then I can just get this code  in here with 4 substituted for the value of n.  And then you can just keep doing the same thing.  You can say, well, 4.0 is going to be false.  So that means that bit of the program is going to be x times power 4 minus 1.  And that's going to be power 3x.  And you can keep going.  So 2, 1, 0.  You keep generating more multiplied by x's.  When you get down to 0, you get into this situation where now you're saying, if 0.0,  which is going to evaluate to true, which means you're going to end up with 1 there.  So just to tidy that up a bit, you end up with a definition of power 5.  But it's just x multiplied by itself five times.  And they're multiplied by 1.  And actually, most partial evaluators will be smart enough to realize that if you've  got something which is a number, and you multiply it by 1, then you can just get rid of that.  So this is kind of the residual program that's left over after the partial evaluation.  And you can see it's made of bits of the original program, just kind of like rearranged and stuck  together in different ways.  The partial evaluator hasn't made any new Ruby.  It's just used all of the existing Ruby and kind of moved bits of it around and figured  out what it should look like.  And the point of doing this, of course, is that this version of power 5 should be faster.  This doesn't make any recursive method calls.  It just multiplies x by itself five times, whereas this thing has got every recursive  call.  You've got a new stack frame.  It does a conditional, and then it does another multiplication and stuff like that.  So this is like a better version of the original method, if you know that n is going to be  5.  And just as a side note, this isn't the same thing as partial application, which you might  be thinking about, which what partial application is, is when you've got a method like this,  and you make a new method that just fixes one of the arguments to it.  So I could define power 5 by just saying, well, call power with 5 as its first argument.  And if I run that on the console, then that does work.  Power 5 of 2 is 32, because that's 2 to the power of 5.  But this new version of the method isn't any, isn't better than the original one.  I mean, actually calling this is going to be slightly slower because you get another  stack frame, there's another method execution going on there.  Another way of doing this in Ruby is instead of defining a new method here, what I could  do is turn this power method into a proc, and then I could use the curry method on it to  turn it into a courage proc, and then I could call that with one argument, and that will  return me a new proc, which when I call it with the second argument, it gives me a new  value bet.  So partial application is a little bit similar, but partial application is a technique that  you do inside your program.  You make new values, new function values in functional programming terms that allow you  to fix the arguments to some of your other functions.  But partial evaluation is something that happens from the outside of your program.  It's like a source level transformation of your program that hopefully makes it faster  and more specialized to particular input values.  So I just wanted to note that there are a couple of useful applications of this technology.  The main point of this is that you can take a general program and a partial evaluator  that can specialize it for you for a fixed input.  So this is kind of the best of both worlds.  You can write a general program that is, you know, maximally general and can accept lots  of different kinds of input, but then you can use a partial evaluator to produce a specialized  version of it that has got all of the overhead involved in choosing what kind of thing you're  dealing with, kind of baked out of it, and then you can run the specialized version of  the program, which will hopefully be faster.  So that's pretty good.  Some of the things you could do with that, for example, if you've got a web server like  Apache or Nginx, you know, that reads in a config file when it starts up, and the config  file controls the execution of the web server.  And you have to imagine that the web server is spending some of its execution cycles like  checking stuff that it's been configured to do.  And so in principle, what you could do is specialize the whole, you know, web server  and give it just your config file as the input, and the partial evaluator will generate your  new version of the web server that's designed just to run your config file, and hopefully  all the overhead of reading the config file and checking config flags is not going to be  part of the program anymore.  It will have been partially evaluated away.  Similarly, this is the classic example in the partial evaluation literature.  It's like a ray tracer.  If you had a three-dimensional scene and you wanted to fly a camera through it, then you  might end up rendering a million frames with your ray tracer as the camera moves through  the scene.  But the scene's the same every time.  So you could take a general ray tracer and specialize it with respect to a particular  scene file, and the partial evaluator will generate you a new ray tracer that can only  ray trace that scene.  And then if you run that a million times, and each time you move the camera slightly,  all of the overhead of building all of the polygons and stuff in the scene and, you know,  figuring out what all the directives in the scene file mean and stuff like that will have  gone away.  And a third sort of slightly more practical but more questionable example is in Mac OS  10, the OpenGL pipeline is, bits of the OpenGL pipeline are written in LLVM intermediate  language, and it has implementations of stuff which is implemented in hardware on some GPUs.  So Apple ship all of the software implementations of all of the stuff that your GPU may or may  not do in LLVM intermediate representation.  And then when you actually run it on your machine and it can see what your GPU is capable  of, all of the stuff that your GPU already does kind of gets partially evaluated away  and it just runs on hardware, whereas all the features that your GPU doesn't have is  kind of stay in the OpenGL pipeline written as software, right?  So anyway, at the beginning, I promised you I was going to tell you a cool story.  So here's the cool story.  In 1971, this guy, Yoshihiko Futamura, realized something cool when he was working at Hitachi  Central Research Laboratory.  He was thinking about partial evaluation.  He was thinking about how with partial evaluation, you have your inputs and your subject program  and you get your output and you can use partial evaluation to timeshift that bit to do it  earlier so that you get this residual program that you can run later.  And he was thinking about that in the context of interpreters and thinking, well, an interpreter  is just a computer program and it's just a program that I provide inputs to and then  that program runs and then I get some output.  I mean, one of the inputs happens to be a program, but it's basically just a box that  takes two inputs and I get some output out.  So what would happen if I used partial evaluation to timeshift some of this work if I did this  part of the computation earlier so that I could do the rest of it later with a residual  program?  So here's what happens.  If you treat the interpreter as data rather than executing it as a program, you feed the  interpreter into a partial evaluator and you get this residual program out.  So this is called partially evaluating the interpreter with respect to the source program.  So this is an input to the interpreter.  If you put both of them in the partial evaluator, you get a residual program out, right, which  has done half of the work of the interpreter.  And then at some later time, you can take that residual program, run it with the original  input to that program and you get the output.  So he was looking at this and thinking about it and so I'm saying, well, this thing I've  got down here that reads in input and then produces output, like that's usually what  we'd call the target program.  This is a version of the source program that will execute directly on the underlying machine.  So what I've got myself there is a target program.  So that means that what I got out of the partial evaluator was a target program.  So there's something up here which is read in a source program and it's generated a target  program which I can run later.  So what is this thing that I've got in the green box?  Anyone?  That's the compiler, right?  So there's your compiler for free, no refunds.  So that's pretty cool.  How does that work?  Does that, I mean, that seems like too good to be true, right?  Let's just go through a quick example.  So here's my simple interpreter written in Ruby.  I've added some furniture, right?  So the actual overall program that works as a simple interpreter is going to read in the  source and the starting environment, the bindings and variables to their values from somewhere.  It's going to somehow acquire the source code in the environment and it's going to use tree  top to load the grammar and then it's going to instantiate the parser and then turn it  into an abstract syntax tree and then let's say it's just going to print out the result  of evaluating the original program in the environment we provided, right?  So if we're going to do what Futenmaura suggested, we're going to feed this into a partial evaluator  and we're going to give it the simple source program as like partial input and then we're  going to evaluate as much of the program as we can and see what's left over.  So that means that we're going to provide a particular source.  So one way or another we're going to arrange that when this thing tries to read its source,  it actually gets the string of a simple program.  So this x equals 2, y equals x times 3 is just an arbitrary program.  So firstly our partial evaluator can do some static analysis of this program.  It can do some constant propagation and say, well, if source is going to be that guy, then  actually this instance of source here is going to be that code and we don't even need source  anymore.  It's not mentioned anywhere.  And now it knows what the value of this string is, it can partially evaluate all of this  stuff.  So this treetop loading the grammar and then building the AST by parsing this string and  then calling to AST on it.  We've already got all of the code to do that and now we've got all of the inputs to do  that.  I mean, I guess we're also assuming that the grammar is available.  So assuming we just do all of that work, we end up with a program that looks like this,  which is just the abstract syntax tree should be the result of parsing that program and  turning it into an abstract syntax tree, which is the stuff I showed you before.  So it's able to do all of this work up front because it knows what the source program is  going to be.  So all that this program does now is it reads in an environment from somewhere and then  it constructs the abstract syntax tree, this literal one, and then it just calls evaluate  on it with whatever the environment is.  So what does calling evaluate on this abstract syntax tree do?  Well, we've already got all the code to do that as well.  That's already part of the interpreter.  I haven't showed it all on this slide, but I'm assuming that we've got all of that stuff  built into the simple grammar, right?  So this is the abstract syntax tree that we've got.  And each one of these nodes, each one of these instances of a syntax class has got a definition  of evaluate on it.  So if a sequence evaluate looks like evaluate the first statement in the environment and  then use that as the input to evaluate in the second statement in the environment, these  assignments have got definitions that say evaluate the expression and then update the  environment with a mapping from the variable name to the value of evaluate on that expression.  That multiply just says evaluate the left hand, expression evaluate the right hand one,  multiply them together.  And all of these things, like number and variable, just have these simple definitions  that either just return their value or in this case just pulls the value out of the environment.  So we've got all of the data in this abstract syntax tree and we've got all of the code.  And actually the partial evaluator can boil all of this down to just a couple of lines  of Ruby code, right?  So firstly, all of these places where here we've got value and name and value.  Well, we know that the value is 2 and we know that the name is x and we know that the value  is 3 there.  So all of those things can just be inlined in those definitions of those methods by the  partial evaluator.  And then all of these places where we're saying evaluate the expression, evaluate the left  expression, evaluate the right expression, we know that they're going to be 2 and environment  x and 3.  So we can inline all of those things into these definitions here.  And then again here we can see that the name is going to be x, the name here is going to  be y and the result of evaluating this expression is going to be environment x times 3.  So we can like inline all of that stuff.  And then finally up here we can see, well, evaluate the first expression is just going  to be this environment.merge x maps to 2 and this evaluate the second expression, the second  statement sorry is going to be update the environment.  It's a little bit tricky because the environment gets mentioned twice here.  So what I'm going to need to do is, you know, the partial evaluator would be able to do  this, just evaluate that first expression and assign it to a variable and then use that  variable here.  So I've kind of glossed over a lot of detail there, but you can see that all of the code  and data that you need is there for the taking and it can all be boiled down.  So the code I've ended up with just tidied up slightly is that, right?  Calling evaluate on the root node of that abstract syntax tree is going to do this.  The environment is the result of updating the environment with x is mapped to 2 and  then we make a new environment where y is mapped to whatever the value of x is times  3.  So back to this original thing here, when we call ast.evaluate with environment, we  can replace all of this stuff with just that code that we just generated, right?  So this is what we end up with.  Reading the environment, make a new one by making x equal to 2 and then print out the  result of merging in y is equal to whatever the value of x is times 3.  And so comparing that to the simple program that we started with, that in a, like, I've  waved my hands through all of that, but you can see that we've sort of compiled this simple  program into Ruby now.  We've got a Ruby program that does what this thing does.  I mean, there's some machinery involving environments and stuff, but basically we've  turned it into Ruby.  But in order to do that, I didn't have to write any new Ruby.  This thing here is just bits of the interpreter stuck together.  And the partial evaluator has stuck together bits of source code from the interpreter in  such a way that it's now a Ruby implementation of the program we started with.  So that's kind of how you can compile stuff with partial evaluation.  So this is the called the first Futimora projection, right?  If you partially evaluate an interpreter with respect to some source code, you get a target  program.  So that's really good.  Futimora was pretty pleased with himself when he realized that.  So this is the picture I showed you before.  But he was thinking about this.  Specifically, he was thinking about the first part of this.  And he was thinking, well, when I'm feeding an interpreter and a source program into the  partial evaluator and getting a target program out later, I'm really just passing inputs  into a program.  So what would happen if I used partial evaluation to timeshift some of this and do it earlier?  If I fed the interpreter into the partial evaluator first and got a residual program  out that I could then feed the source program into.  Would that work?  So we tried that.  Here's what happens.  So treating the partial evaluator as input, you can feed the partial evaluator and the  interpreter into the partial evaluator.  And when that runs, you get a residual program out.  When you've got the residual program, then later on, you can run that with the source  program as input.  And you get a target program out.  And then later on, you can run the target program with the original input to the program  as input and get some output out.  So that makes sense.  We've just split it apart with time again.  But when he looked at this, he saw, well, what I've got here is that I've got a source  program going into the residual program.  And I get out the target program.  So what is this residual program that I've got?  Right.  That's the compiler.  So that means that what I got out of the thing here was a compiler.  So that means that what I've got myself here is a compiler generator.  So this means that if you've got any interpreter, you can feed it in.  You can specialize.  You can partially evaluate a partial evaluator with respect to that interpreter.  And you can get a compiler for that language.  So this is sort of a higher order version of what I showed you the first time.  This gives you a mechanism for generating a compiler.  And then you can feed any source program into it.  You don't need to involve the partial evaluator at this point.  You've just got a bona fide compiler that you can run.  And it will compile your language.  So that's really cool.  That's called the second Futimora projection.  If you partially evaluate a partial evaluator with respect to an interpreter, you get a compiler.  So Futimora was pretty pleased with himself when he realized that.  And he was thinking about this.  And specifically, he was thinking about this first bit.  And he was looking at this and thinking, well, really, this is really just feeding input  into a program.  So what would happen if I time-shifted this part of the execution and did it earlier so  that I could get a residual program out and then I could feed the interpreter into it  later to do what I'm doing here?  So here's what happens if you do that.  So you treat the partial evaluator as input.  And so you feed the partial evaluator and the partial evaluator into the partial evaluator.  And what you get out is a residual program.  And then later on, you feed the interpreter into the residual program.  And then that runs, and then you get a compiler.  And then later on, you run the compiler with the source program as input, and then you  get a target program.  And then later on, you run the target program with input as input, and you get the output.  But this thing here, the residual program that takes an interpreter and turns it into  a compiler, is a compiler generator.  So that means that what we've got out of the thing here was a compiler generator.  So what's this thing we've got on the top?  It's a compiler generator generator.  So this is the third Futumora projection, right?  If you partially evaluate a partial evaluator with respect to a partial evaluator, you get  a compiler generator.  And thankfully, we can't take it any further than that.  Because if you did this again, you'd still be partially evaluating a partial evaluator  with respect to a partial evaluator, right?  So there are only three Futumora projections.  So this is really cool.  And this is why I wanted to tell you about this.  I think it's funny and interesting and unusual.  However, it doesn't mean that we don't need compiler writers anymore, right?  Partial evaluation is a fully general technique for evaluating bits of computer programs.  So it gets rid of the interpretive overhead of evaluating a program.  But it doesn't do any of the clever stuff like inventing new data structures or optimizations  or doing anything platform-specific.  So we still need smart people to write compilers to make our programs go far.  But this technique does remove some of the overhead of interpretation, right?  It removes all of that stuff that involves parsing and generating code and all of that  stuff.  So if you're sufficiently interested in this, that you'd like to learn more, then there's  a really interesting book called Partial Evaluation and Automatic Programme Generation, which is  now available for free.  So if you go to that URL there, you can download a copy of that.  It's a really good textbook.  I recommend it.  So various bits of software that you may or may not be familiar with use techniques like  this.  So the JIT in LLVM and the bits of the PyPy tool chains, like R-Python and the VM and  the JIT that underlie that, use some of these program specialization techniques.  Rubinius sits on top of LLVM.  So when you use Rubinius, stuff that's a little bit like this is happening.  And there's a Ruby implementation called Topaz that sits on top of the PyPy tool chain and  is a Ruby implementation that's written in Python.  So if you use the Topaz Ruby implementation, then stuff like this is happening inside Topaz  when you run your program.  It happens at runtime rather than compile time.  And quite aside from the partial evaluation stuff, Rubinius and JRuby are great because  they are compilers that have got interesting and accessible implementations.  So if you feel like you could become interested, sort of in the spirit of Max's keynote yesterday,  if you feel like you want to get involved with stuff and you're interested in these  kind of programs that generate programs, then you could do a lot worse than cracking open  Rubinius or JRuby and having a look at how they work and maybe submitting a pull request  or something.  So much more generally than that.  If you're generally interested in this sort of thing, I've written a book about all this  sort of thing, which uses Ruby to go over all of these kinds of things and interpreters  and compilers and the lambda calculus and cellular automata and type systems and stuff.  So if you're interested, there's a book that you can read.  There's a website for it.  I rarely have given me a discount code so you can get 50% off if you use RubyConf as  the discount code.  That's all I wanted to say.  Thanks very much.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.
Compilers_For_Free_0_47.png Compilers_For_Free_48_95.png Compilers_For_Free_96_143.png Compilers_For_Free_144_191.png Compilers_For_Free_192_239.png Compilers_For_Free_240_287.png Compilers_For_Free_288_407.png Compilers_For_Free_408_731.png Compilers_For_Free_732_2747.png Compilers_For_Free_2748_2879.png Compilers_For_Free_2880_4295.png Compilers_For_Free_4296_6371.png Compilers_For_Free_6372_6623.png Compilers_For_Free_6624_7211.png Compilers_For_Free_7212_7343.png Compilers_For_Free_7344_8531.png Compilers_For_Free_8532_9179.png Compilers_For_Free_9180_11651.png Compilers_For_Free_11652_16967.png Compilers_For_Free_16968_17039.png Compilers_For_Free_17040_18875.png Compilers_For_Free_18876_19103.png Compilers_For_Free_19104_25271.png Compilers_For_Free_25272_25355.png Compilers_For_Free_25356_27659.png Compilers_For_Free_27660_28355.png Compilers_For_Free_28356_36539.png Compilers_For_Free_36540_36671.png Compilers_For_Free_36672_38783.png Compilers_For_Free_38784_40595.png Compilers_For_Free_40596_40691.png Compilers_For_Free_40692_40967.png Compilers_For_Free_40968_41147.png Compilers_For_Free_41148_50723.png Compilers_For_Free_50724_52091.png Compilers_For_Free_52092_52439.png Compilers_For_Free_52440_52667.png Compilers_For_Free_52668_53627.png Compilers_For_Free_53628_55139.png Compilers_For_Free_55140_55355.png Compilers_For_Free_55356_55775.png Compilers_For_Free_55776_57311.png Compilers_For_Free_57312_58895.png Compilers_For_Free_58896_59003.png Compilers_For_Free_59004_59603.png Compilers_For_Free_59604_59771.png Compilers_For_Free_59772_60947.png Compilers_For_Free_60948_61019.png Compilers_For_Free_61020_61763.png Compilers_For_Free_61764_61811.png Compilers_For_Free_61812_61859.png Compilers_For_Free_61860_61907.png Compilers_For_Free_61908_61955.png Compilers_For_Free_61956_62003.png Compilers_For_Free_62004_62051.png Compilers_For_Free_62052_62099.png Compilers_For_Free_62100_62147.png Compilers_For_Free_62148_62195.png Compilers_For_Free_62196_62303.png Compilers_For_Free_62304_62313.png
Good morning, everyone. Thanks for coming to this talk. I'm Tom Stewart. I'm going to talk about getting compilers for free. Although, actually, my agenda today is that I'm fascinated by programming, or to be more specific, I'm fascinated by meta-programming. It's something I'm really interested in. So let's talk about meta-programming. As Ruby programmers, we already intuitively understand the power of meta-programming, right, programs that write programs. So in Ruby, we've got things like instance eval and define method and method missing and all these kind of tools for making programs that grow new functionality at runtime that wasn't present in the static program that we started out with. Now, there's another thing that I find even more interesting than that, which still kind of counts as meta-programming, which is programs that manipulate representations of other programs, right, programs that operate on data, which itself represents a program, and then does something with that representation, like analyzes it, or evaluates it, or translates it, or transforms it. So this is kind of the world of compilers and interpreters and static analyzes, and I think it's really fascinating in a way it's kind of the purest or the most self-referential kind of software that you can write. So in this talk today, I'd like to make you look at programs differently. I don't have a complicated technical point to make. I just want to tell you a cool story and hopefully convince you that programs which manipulate other programs are interesting and hopefully kind of inspire you to find out some more about them. So I'm going to start out by just talking about something we're all familiar with, which is executing programs. So you write a program, right? You have a program written down that you want to run, and you have a machine that you can run that program on. So you put that program into the machine, and then you've got some inputs for that program, and those might be command line arguments or configuration files or standard input or whatever, and you feed all of those inputs into the machine that's got the program inside it, and the program executes on the machine, and it produces an output. I think we're all kind of familiar with how computers work, right? But that only works if the program that you wrote is written in a language that the machine kind of natively understands. So in terms of a real machine, that'll be, you know, the program has to be written in machine code. And if it's, if the program's written in a higher level language, then maybe you can run it on some kind of like virtual machine that understands that language specifically. But if your program's written in a language that's unfamiliar to the machine, then you're going to need an interpreter or a compiler to be able to execute it, right? So interpreters, how does an interpreter work? Well, very kind of roughly the way it works is it reads in some source code of the program you want to execute, and then it builds an abstract syntax tree by parsing that source code, and then it evaluates the program by walking over the abstract syntax tree and performing the instructions that it finds inside the tree. And this is basically how, you know, MRI pre-1.9 did its job, right? So I'm going to show you a little demo of how this works by just introducing this, a language that I'm going to call simple. It's just a toy language. Simple is like an abbreviation for a simple imperative language. This language is really straightforward. It looks a little bit like Ruby, but not exactly the same. Statements look like this. So simple's got expressions and statements unlike Ruby. It's got expressions like 19 plus 23. Expressions just evaluate to a value. It's also got statements like assignments. So a equals 19 plus 23 is a statement, and that statement is going to have, is going to modify the lexical environment. So when you evaluate a statement, it's going to update the bindings between variable names and their values. So the effect of executing that statement is that after the statement is executed, a has got the value 42, right? Some other statements, it's got sequencing in it. It's got conditionals in it. It's got while lips in it, right? Very basic language. It's not quite Ruby because it's got curly braces and stuff, but it's kind of close enough to Ruby that you've recognized what it's trying to do. So given that you're at RubyConf, you probably already know about this gem called treetop, which we can use to parse languages, like build parses. And I'm just going to very, very quickly show you how we can build a grammar for that simple language. The grammar for this language looks like this. You just write a file. You say this is a grammar for the simple language, and then you just need to write rules that explain what the syntax of each of the different kinds of statement and expression in your language look like. You can say a sequence is two statements separated by a semicolon, a while loop says while bracket and then a condition and then curly braces around the body of the while loop. An assignment looks like a variable name and an equals sign. There's some more rules there. Conditionals, binary expressions here, less than add and multiply. And then down at the bottom, you get to the atomic things like numbers and Booleans and variables, right? So I'm just going to scoop past that. But if you write a file like that that explains what your programming language looks like, you can use the tree top gem to load that grammar file, and it will generate you a parser class named after the grammar. And then I can instantiate that parser class and say, make me a new parser and then parse this string. And what tree top will do is give you back this big data structure called a concrete syntax tree or a parse tree. And this has got a lot of information in it about the exact sort of lexical structure of the string you gave it and how it breaks down into all its component parts. There's a lot of information in there that we're not very interested in. But that's a good start. We don't want a concrete syntax tree. We want an abstract syntax tree, which is a more useful representation of the structure of the statement we gave it. And we can make an abstract syntax tree. By first, we can declare a bunch of classes that we're going to use to instantiate to make the nodes of the abstract syntax tree. And I'm just going to use struct to do that. So I'm going to define a new class for each kind of, each different kind of expression and statement. And some of them, so all these binary expressions have got a left and a right sub-expression assignments. I've got the variable name and the expression that's being assigned to it and so on. Now going back to the grammar, in each of these rules that matches a particular kind of syntax, you can put some Ruby code in here and say, whenever I get one of these number nodes in the concrete syntax tree, I want to define a method on that called 2ast, which is arbitrary. I've made that up. And then when I call that, I want that to manufacture a new instance of the number class in this case. And that just needs to contain the integer version of the text string that was inside, you know, that was the number. I can define versions of those for, you know, the Booleans and variables. And each of these is just building a new instance of my custom abstract syntax tree classes, right? So looking at those, these are just three definitions of the same method on different kinds of concrete syntax tree node that will help me create one of these abstract syntax tree nodes, you know, from it. And similarly for things like these statements, I can go in and put, you know, put more of these method definitions in. These are mostly just recursively converting their sub-expressions or sub-statements into abstract syntax trees and then going them together with the right, the right kind of node class. So once I've done all of that work, I can get tree top to build me a concrete syntax tree and then I can call two AST on the root node and then that will recursively convert the whole thing into an abstract syntax tree, which is a nice data structure that's made up instances of classes that I defined, right? So this is saying that this statement here is, you know, a sequence of assignments and actually just to visualize that, you can see that this statement is a sequence of two assignments. The first assignment is assigning the number two to X and the second assignment is assigning the result of multiplying X and three to Y, right? So now I've got this abstract syntax tree, I can evaluate the abstract syntax tree by recursively walking over it. An easiest way to do that is just to define a method on all of the different kinds of node and then I can call the method on the root node and it will recursively, I can define it so it recursively walks over the tree. So again, just briefly, I'm going to define an evaluate method on each of those abstract syntax tree classes and the evaluate method is going to take an environment, which is the electrical environment, it's a hash that says what the value of each variable currently is. So if you're evaluating a number or a Boolean, it doesn't care what's in the environment, you always just get out the value that you stored inside that node. If you're evaluating a variable, then it looks in the environment and pulls out the variable with that name, right? So that means that I can, if I make a new number instance and evaluate that in an empty environment, I just get the original number back, same with Booleans. If I evaluate a variable Y in this particular environment that gives Y the value 11, then I'll get 11, whereas if I evaluate in a different environment that gives Y a different value, I get the different value out, right? So those are the simplest possible expressions to evaluate. These are the definitions of evaluate for those binary expressions and these just recursively evaluate their left and right sub expressions and then they perform the operation that corresponds to the kind of node that we've got. So if it's an add node, we add them, if it's multiply, we multiply them, if it's less than, we compare them with less than. So that means I can make something like a multiply expression X times Y and evaluate that inside this environment and I get the result 6. If I make a less than node instead that is X less than Y, the answer is true in that particular environment. And I can do that again for statements. I'm not going to go into any detail here, but for example, you can see that the, for assignment statements, oh, so statements don't return a value, they return the new environment. So when I do an assignment, for example, I recursively evaluate the expression inside the assignment and then I update the environment to have a new mapping from the variable name to the new value of that sub expression and so on for all of these, the rest of these things. You know, sequence kind of evaluates the first, you know, the first statement first to get an updated environment and then it evaluates the second statement in the updated environment to get the final environment and so on. So once I've done all of that stuff, I can now do things like when I evaluate an assignment that is X is assigned the value 1. If I start with an empty environment and I evaluate it, I get a new environment where X has got the value 1. If I do a sequence of assignments, X equals 1 and then X equals 2 in an empty environment, I end up with X equals 2 because that's kind of clobbered the first assignment. And the point of doing all this is so that I can chain things together and say, use the parser to parse this, this program and then evaluate the abstract syntax tree in an empty environment. So if I evaluate X equals 2, Y equals X times 3 in an empty environment, I get X is 2, Y is 6. That's like the result of my program. And I can do that with a, you know, a more sophisticated program that's got a while loop in it. So I can do that with a program that starts out X at 1 and it keeps multiplying it by 3 until the value becomes greater than 5 and then that finishes up with X being the value of 9. So that all works. It's all fairly straightforward. That's what an interpreter is, really. The point of an interpreter is that it provides what I'm calling single stage execution. And what I mean by that is you've got your interpreter and you provide a source program into the interpreter. And then in general, although we didn't do it in the case I just showed you, you will also be, also provide some input to the program. So if the interpreter is Ruby, you'll provide a Ruby program as the source and then the input will be whatever, standard input or command line arguments or whatever. So you provide all of that stuff to the interpreter and then the interpreter is what runs on the machine and then that produces the output. And of course here we're assuming that the interpreter is already written in a language that can run on the underlying machine. This doesn't need to be because we're using the interpreter to run the source program on the underlying machine, right? And this all happens at the same time. This is the single stage of program execution. That's what I'm calling runtime, that's what you would call runtime. So what about compilers? How are they different? Well, they're pretty similar, really. They work in a similar kind of way. They read some source code and then they build an abstract syntax tree by parsing the source code. But then they do a different thing, which is rather than perform the instructions they find in the abstract syntax tree, they generate some target code by walking over the abstract syntax tree and emitting some instructions as they find them. So I'm not going to, I don't have time to go into any detail of how to do this properly, but I am going to show you an example. So here's a version of, instead of having evaluate defined on those abstract syntax tree nodes, I could define a method called toJavascript. And this is just going to return a string which contains some JavaScript code that does whatever that node is supposed to do. The JavaScript code I'm generating here, rather than using real JavaScript variables and having to deal with all of JavaScript's like weird variable scoping stuff, I'm just turning every piece of, every simple program into a JavaScript function that takes an object that's got mappings of variable names to values and then kind of updates that environment. So or in this case, when you have expressions, like a number is going to turn into a function that just returns a constant number and a Boolean is going to return a constant Boolean and a variable is going to look up the variable in the environment. So this is a JavaScript variable and then it's going to look up the right value in that, in that JavaScript object. It's very quickly same for these kind of binary expressions. I just like recursively convert the left and right sub expressions to JavaScript and then add them together or multiply them together or whatever. And then, you know, don't try to read all this, but this is how for all of the statements, I'm really just generating the JavaScript syntax. So if turns into a JavaScript if and a sequence turns into kind of JavaScript sequencing and a while turns into a JavaScript while loop. So that's all pretty straightforward. And the point of doing that is so that I can take like this program that I showed you before, x equals 1 while x is left in 5, turn that into JavaScript and now that's kind of been compiled into an admittedly much longer JavaScript program. But this is a JavaScript program that does the same thing as the program I started with that was written in a different language. And so I can take that big JavaScript program, this is the same program formatted more nicely, and place it on the Node.js console and say, look, here's my program and then you probably can't see it at the bottom here. When I run this program in JavaScript, I get the result x is 9. So that compiler I just showed you is extremely stupid. It's not a good compiler, but it does let us execute those simple programs if our machine only understands JavaScript. So the difference between an interpreter and a compiler really is that a compiler provides two-stage execution. When you've got a compiler, you just give it the source program as input and then the compiler runs and it generates something that we usually call the target program. And then later on, at a different time, you can take the target program, which was just data when the compiler admitted it, and put the target program inside a machine and run it. And that's when you provide the input to your program and then your target program runs and you get the output out. So we've still achieved the same thing as with an interpreter, but now it's been kind of staged in two pieces. And the first piece is what we call compile time and the second piece is what we call run time. So the good news about compilers is that compiled programs run faster. Staging the computation like this removes the interpretive overhead at run time. And by interpretive overhead, I mean all of that faff of parsing the program and walking over the AST and deciding what you're going to do with it. That all gets done at compile time. And by the time the program runs, that work's already been done. And so if you're going to run the program a million times, it makes sense to do the interpreting stuff once and then just run the target code that doesn't have all of that kind of overhead. There are other kind of performance benefits that I'm not talking about in this talk, but for example, your compiler can use like clever data structures or clever optimizations to make the target program more and more efficient, especially if it knows about the underlying architecture of the machine and stuff like that. So that's the good news. The bad news is that compilation is just harder to do than interpretation. So there are a few reasons for that. First, you have to think about two times instead of one. You're not just, when you write an interpreter, you're just thinking, well, I'm running right now. I'm the interpreter. I'm going to do what that program says to do right now. When you're writing a compiler, you're thinking about compile time and run time. So in your head, you have to have this model of like, well, what am I doing now as the compiler? And then what's the target program going to do later when it actually gets executed? So that's harder. You also have to implement in two languages instead of one. With an interpreter, you're just implementing in the interpreter language. With that compiler I showed you, the compiler was implemented in Ruby, but what it did was generate some JavaScript code. So to write the compiler, I was actually writing in two programming languages, kind of intertwine, and that's harder to kind of get your head around. And also, in a very vague hand wave, you sense, compiling dynamic languages is fundamentally challenging. If you want to compile a language like Ruby or JavaScript or something, you can't, it's not enough to just look at the static program and then convert it into some kind of target program because the static program doesn't tell you everything about what might happen at run time, right? If you've got things like defined method and you can create new classes and things like that, it's just hard to write a compiler for languages that kind of, whether programs can change dynamically as they execute. So long story short, writing an interpreter is easier than writing a compiler, but interpreters are slower than compilers, right? Interpreters only run at one time. They only use one language, and they can be as dynamic as you like if the program changes when it runs, and that's fine because you can just change the abstract syntax tree as the program runs and the interpreter will just keep working. So ideally, we would just write interpreters for our programming languages, but unfortunately, they're slower, and so usually we end up writing compilers. So I want to tell you about a third kind of thing, which is like interpreters and compilers, and these are called partial evaluators. Now a partial evaluator is like a cross between an interpreter and a compiler. An interpreter kind of does this job of executing a program right now, and compilers do this job of generating a program now and then executing it later. Now partial evaluators kind of live in the middle, they're like a hybrid of these two things. They execute some of the code now and then leave the rest of it for execution later. So what that means is you give a partial evaluator your subject program it's called, you know, the program you want it to partially evaluate, and you give it some of the inputs for that program, and it evaluates only the parts of the program that depend on the inputs that you've provided. And then whatever's left afterwards is called the residual program. It's like what you have left, you know, if you like boil a liquid and you get a residue left over, this is kind of the residual program after you've done your partial evaluation. So what this looks like is instead of taking your subject program and running it directly on a machine and sort of providing an arbitrary number of inputs to your program, again like command line arguments or standard input or config files or whatever, and then executing it and getting an output. Again, this is like a single stage computation. What partial evaluation lets you do is kind of pick out part of this process, say like the first input being fed into the subject program, and kind of do it earlier. You can kind of time shift it into the past and say, well, this is the computation I ultimately want to do at some point in the future, but I want to do this part of it now and save the rest for later. So by time shifting this stuff into the past, that means you take the program and the input and instead of running this program, you treat it as data, treat it as input to a partial evaluator. So this is like a compiler or interpreter. It will read in a program and it will read in some of the input for that program. And then when you execute the partial evaluator, it will produce this residual program. And then later, you can take that residual program and run it on a machine and feed in the rest of the input to the original program. That will run and give you the final output. So the idea of a partial evaluator is it lets you kind of split a single stage execution into two stages by sort of time shifting the processing of some of the input from the future when you're going to run the program to the present. You can do some of the work earlier. So that's easy enough to say, but how do these partial evaluators work? Well, they work a lot like compilers and interpreters. They're just more complicated and I don't have time to show you how to build one in Ruby. But briefly what happens is you read in some source code just like an interpreter or a compiler. You build an abstract syntax tree just like an interpreter or a compiler. But then you read some of the inputs to that program. And once you've read some of the inputs to the program, you analyze the program, you walk over the abstract syntax tree, you do usually just a static analysis to find all of the places where the inputs that have been provided are used in the program. And once you've found those places, you can partially evaluate the program by going to all of those places where the inputs have been used and evaluating them and then putting like new code in to replace them with the results of the evaluation. And then once you've finished doing that, you've got this residual program that you can emit. So I can't really give you a whole program example in Ruby in the time I've got, but I just want to show you a really basic example to just kind of give you a feel of what's going on here. So just for demo purposes, I'm going to show you this on the level of an individual method. So imagine we've got a partial evaluator for Ruby and I've got this Ruby method, which is power. So this is raise x to the power of n. So if I passed in 3 as the value of n here, it's going to do x multiplied by power 2x and it's going to recursively multiply x by itself three times, right? So say that I've told my partial evaluator that I know that this method is going to be called with 5 as the first argument. So I know I'm going to be calling it with the value of n being 5. So what the partial evaluator is going to do is kind of start looking at this method and say, OK, so I know what the value of n is going to be. So I can find all of the other places where n is used. And by doing that, I can find all of the sub-expressions in this method that I can evaluate now. I don't have to wait to find out what the value of x is because these expressions are independent of the value of x. So once it's found those expressions, it can start like evaluating them and replacing them. So what we're going to do is instead of having this power method that takes two arguments, we're going to make a method called power 5 that only takes one argument x and the value of n is going to be like fixed in this method. So all of those instances of n, I'm just going to turn into 5. And then we can start partially evaluating this and saying, well, I can already tell you what the value of 5.0 is going to be. That's going to be false. And then once you've done that, you've now got a conditional here which you are able to accept by sort of propagating the information about what expressions are available. You can say, well, I know that this thing is just going to evaluate to this guy here, right, because it was if false. And now I've got this 5 minus 1. I can evaluate that to get 4. And then I can do some kind of, I can inline the body of this method here. If I know that I'm going to be calling power with 4 and x, then I can just get this code in here with 4 substituted for the value of n. And then you can just keep doing the same thing. You can say, well, 4.0 is going to be false. So that means that bit of the program is going to be x times power 4 minus 1. And that's going to be power 3x. And you can keep going. So 2, 1, 0. You keep generating more multiplied by x's. When you get down to 0, you get into this situation where now you're saying, if 0.0, which is going to evaluate to true, which means you're going to end up with 1 there. So just to tidy that up a bit, you end up with a definition of power 5. But it's just x multiplied by itself five times. And they're multiplied by 1. And actually, most partial evaluators will be smart enough to realize that if you've got something which is a number, and you multiply it by 1, then you can just get rid of that. So this is kind of the residual program that's left over after the partial evaluation. And you can see it's made of bits of the original program, just kind of like rearranged and stuck together in different ways. The partial evaluator hasn't made any new Ruby. It's just used all of the existing Ruby and kind of moved bits of it around and figured out what it should look like. And the point of doing this, of course, is that this version of power 5 should be faster. This doesn't make any recursive method calls. It just multiplies x by itself five times, whereas this thing has got every recursive call. You've got a new stack frame. It does a conditional, and then it does another multiplication and stuff like that. So this is like a better version of the original method, if you know that n is going to be 5. And just as a side note, this isn't the same thing as partial application, which you might be thinking about, which what partial application is, is when you've got a method like this, and you make a new method that just fixes one of the arguments to it. So I could define power 5 by just saying, well, call power with 5 as its first argument. And if I run that on the console, then that does work. Power 5 of 2 is 32, because that's 2 to the power of 5. But this new version of the method isn't any, isn't better than the original one. I mean, actually calling this is going to be slightly slower because you get another stack frame, there's another method execution going on there. Another way of doing this in Ruby is instead of defining a new method here, what I could do is turn this power method into a proc, and then I could use the curry method on it to turn it into a courage proc, and then I could call that with one argument, and that will return me a new proc, which when I call it with the second argument, it gives me a new value bet. So partial application is a little bit similar, but partial application is a technique that you do inside your program. You make new values, new function values in functional programming terms that allow you to fix the arguments to some of your other functions. But partial evaluation is something that happens from the outside of your program. It's like a source level transformation of your program that hopefully makes it faster and more specialized to particular input values. So I just wanted to note that there are a couple of useful applications of this technology. The main point of this is that you can take a general program and a partial evaluator that can specialize it for you for a fixed input. So this is kind of the best of both worlds. You can write a general program that is, you know, maximally general and can accept lots of different kinds of input, but then you can use a partial evaluator to produce a specialized version of it that has got all of the overhead involved in choosing what kind of thing you're dealing with, kind of baked out of it, and then you can run the specialized version of the program, which will hopefully be faster. So that's pretty good. Some of the things you could do with that, for example, if you've got a web server like Apache or Nginx, you know, that reads in a config file when it starts up, and the config file controls the execution of the web server. And you have to imagine that the web server is spending some of its execution cycles like checking stuff that it's been configured to do. And so in principle, what you could do is specialize the whole, you know, web server and give it just your config file as the input, and the partial evaluator will generate your new version of the web server that's designed just to run your config file, and hopefully all the overhead of reading the config file and checking config flags is not going to be part of the program anymore. It will have been partially evaluated away. Similarly, this is the classic example in the partial evaluation literature. It's like a ray tracer. If you had a three-dimensional scene and you wanted to fly a camera through it, then you might end up rendering a million frames with your ray tracer as the camera moves through the scene. But the scene's the same every time. So you could take a general ray tracer and specialize it with respect to a particular scene file, and the partial evaluator will generate you a new ray tracer that can only ray trace that scene. And then if you run that a million times, and each time you move the camera slightly, all of the overhead of building all of the polygons and stuff in the scene and, you know, figuring out what all the directives in the scene file mean and stuff like that will have gone away. And a third sort of slightly more practical but more questionable example is in Mac OS 10, the OpenGL pipeline is, bits of the OpenGL pipeline are written in LLVM intermediate language, and it has implementations of stuff which is implemented in hardware on some GPUs. So Apple ship all of the software implementations of all of the stuff that your GPU may or may not do in LLVM intermediate representation. And then when you actually run it on your machine and it can see what your GPU is capable of, all of the stuff that your GPU already does kind of gets partially evaluated away and it just runs on hardware, whereas all the features that your GPU doesn't have is kind of stay in the OpenGL pipeline written as software, right? So anyway, at the beginning, I promised you I was going to tell you a cool story. So here's the cool story. In 1971, this guy, Yoshihiko Futamura, realized something cool when he was working at Hitachi Central Research Laboratory. He was thinking about partial evaluation. He was thinking about how with partial evaluation, you have your inputs and your subject program and you get your output and you can use partial evaluation to timeshift that bit to do it earlier so that you get this residual program that you can run later. And he was thinking about that in the context of interpreters and thinking, well, an interpreter is just a computer program and it's just a program that I provide inputs to and then that program runs and then I get some output. I mean, one of the inputs happens to be a program, but it's basically just a box that takes two inputs and I get some output out. So what would happen if I used partial evaluation to timeshift some of this work if I did this part of the computation earlier so that I could do the rest of it later with a residual program? So here's what happens. If you treat the interpreter as data rather than executing it as a program, you feed the interpreter into a partial evaluator and you get this residual program out. So this is called partially evaluating the interpreter with respect to the source program. So this is an input to the interpreter. If you put both of them in the partial evaluator, you get a residual program out, right, which has done half of the work of the interpreter. And then at some later time, you can take that residual program, run it with the original input to that program and you get the output. So he was looking at this and thinking about it and so I'm saying, well, this thing I've got down here that reads in input and then produces output, like that's usually what we'd call the target program. This is a version of the source program that will execute directly on the underlying machine. So what I've got myself there is a target program. So that means that what I got out of the partial evaluator was a target program. So there's something up here which is read in a source program and it's generated a target program which I can run later. So what is this thing that I've got in the green box? Anyone? That's the compiler, right? So there's your compiler for free, no refunds. So that's pretty cool. How does that work? Does that, I mean, that seems like too good to be true, right? Let's just go through a quick example. So here's my simple interpreter written in Ruby. I've added some furniture, right? So the actual overall program that works as a simple interpreter is going to read in the source and the starting environment, the bindings and variables to their values from somewhere. It's going to somehow acquire the source code in the environment and it's going to use tree top to load the grammar and then it's going to instantiate the parser and then turn it into an abstract syntax tree and then let's say it's just going to print out the result of evaluating the original program in the environment we provided, right? So if we're going to do what Futenmaura suggested, we're going to feed this into a partial evaluator and we're going to give it the simple source program as like partial input and then we're going to evaluate as much of the program as we can and see what's left over. So that means that we're going to provide a particular source. So one way or another we're going to arrange that when this thing tries to read its source, it actually gets the string of a simple program. So this x equals 2, y equals x times 3 is just an arbitrary program. So firstly our partial evaluator can do some static analysis of this program. It can do some constant propagation and say, well, if source is going to be that guy, then actually this instance of source here is going to be that code and we don't even need source anymore. It's not mentioned anywhere. And now it knows what the value of this string is, it can partially evaluate all of this stuff. So this treetop loading the grammar and then building the AST by parsing this string and then calling to AST on it. We've already got all of the code to do that and now we've got all of the inputs to do that. I mean, I guess we're also assuming that the grammar is available. So assuming we just do all of that work, we end up with a program that looks like this, which is just the abstract syntax tree should be the result of parsing that program and turning it into an abstract syntax tree, which is the stuff I showed you before. So it's able to do all of this work up front because it knows what the source program is going to be. So all that this program does now is it reads in an environment from somewhere and then it constructs the abstract syntax tree, this literal one, and then it just calls evaluate on it with whatever the environment is. So what does calling evaluate on this abstract syntax tree do? Well, we've already got all the code to do that as well. That's already part of the interpreter. I haven't showed it all on this slide, but I'm assuming that we've got all of that stuff built into the simple grammar, right? So this is the abstract syntax tree that we've got. And each one of these nodes, each one of these instances of a syntax class has got a definition of evaluate on it. So if a sequence evaluate looks like evaluate the first statement in the environment and then use that as the input to evaluate in the second statement in the environment, these assignments have got definitions that say evaluate the expression and then update the environment with a mapping from the variable name to the value of evaluate on that expression. That multiply just says evaluate the left hand, expression evaluate the right hand one, multiply them together. And all of these things, like number and variable, just have these simple definitions that either just return their value or in this case just pulls the value out of the environment. So we've got all of the data in this abstract syntax tree and we've got all of the code. And actually the partial evaluator can boil all of this down to just a couple of lines of Ruby code, right? So firstly, all of these places where here we've got value and name and value. Well, we know that the value is 2 and we know that the name is x and we know that the value is 3 there. So all of those things can just be inlined in those definitions of those methods by the partial evaluator. And then all of these places where we're saying evaluate the expression, evaluate the left expression, evaluate the right expression, we know that they're going to be 2 and environment x and 3. So we can inline all of those things into these definitions here. And then again here we can see that the name is going to be x, the name here is going to be y and the result of evaluating this expression is going to be environment x times 3. So we can like inline all of that stuff. And then finally up here we can see, well, evaluate the first expression is just going to be this environment.merge x maps to 2 and this evaluate the second expression, the second statement sorry is going to be update the environment. It's a little bit tricky because the environment gets mentioned twice here. So what I'm going to need to do is, you know, the partial evaluator would be able to do this, just evaluate that first expression and assign it to a variable and then use that variable here. So I've kind of glossed over a lot of detail there, but you can see that all of the code and data that you need is there for the taking and it can all be boiled down. So the code I've ended up with just tidied up slightly is that, right? Calling evaluate on the root node of that abstract syntax tree is going to do this. The environment is the result of updating the environment with x is mapped to 2 and then we make a new environment where y is mapped to whatever the value of x is times 3. So back to this original thing here, when we call ast.evaluate with environment, we can replace all of this stuff with just that code that we just generated, right? So this is what we end up with. Reading the environment, make a new one by making x equal to 2 and then print out the result of merging in y is equal to whatever the value of x is times 3. And so comparing that to the simple program that we started with, that in a, like, I've waved my hands through all of that, but you can see that we've sort of compiled this simple program into Ruby now. We've got a Ruby program that does what this thing does. I mean, there's some machinery involving environments and stuff, but basically we've turned it into Ruby. But in order to do that, I didn't have to write any new Ruby. This thing here is just bits of the interpreter stuck together. And the partial evaluator has stuck together bits of source code from the interpreter in such a way that it's now a Ruby implementation of the program we started with. So that's kind of how you can compile stuff with partial evaluation. So this is the called the first Futimora projection, right? If you partially evaluate an interpreter with respect to some source code, you get a target program. So that's really good. Futimora was pretty pleased with himself when he realized that. So this is the picture I showed you before. But he was thinking about this. Specifically, he was thinking about the first part of this. And he was thinking, well, when I'm feeding an interpreter and a source program into the partial evaluator and getting a target program out later, I'm really just passing inputs into a program. So what would happen if I used partial evaluation to timeshift some of this and do it earlier? If I fed the interpreter into the partial evaluator first and got a residual program out that I could then feed the source program into. Would that work? So we tried that. Here's what happens. So treating the partial evaluator as input, you can feed the partial evaluator and the interpreter into the partial evaluator. And when that runs, you get a residual program out. When you've got the residual program, then later on, you can run that with the source program as input. And you get a target program out. And then later on, you can run the target program with the original input to the program as input and get some output out. So that makes sense. We've just split it apart with time again. But when he looked at this, he saw, well, what I've got here is that I've got a source program going into the residual program. And I get out the target program. So what is this residual program that I've got? Right. That's the compiler. So that means that what I got out of the thing here was a compiler. So that means that what I've got myself here is a compiler generator. So this means that if you've got any interpreter, you can feed it in. You can specialize. You can partially evaluate a partial evaluator with respect to that interpreter. And you can get a compiler for that language. So this is sort of a higher order version of what I showed you the first time. This gives you a mechanism for generating a compiler. And then you can feed any source program into it. You don't need to involve the partial evaluator at this point. You've just got a bona fide compiler that you can run. And it will compile your language. So that's really cool. That's called the second Futimora projection. If you partially evaluate a partial evaluator with respect to an interpreter, you get a compiler. So Futimora was pretty pleased with himself when he realized that. And he was thinking about this. And specifically, he was thinking about this first bit. And he was looking at this and thinking, well, really, this is really just feeding input into a program. So what would happen if I time-shifted this part of the execution and did it earlier so that I could get a residual program out and then I could feed the interpreter into it later to do what I'm doing here? So here's what happens if you do that. So you treat the partial evaluator as input. And so you feed the partial evaluator and the partial evaluator into the partial evaluator. And what you get out is a residual program. And then later on, you feed the interpreter into the residual program. And then that runs, and then you get a compiler. And then later on, you run the compiler with the source program as input, and then you get a target program. And then later on, you run the target program with input as input, and you get the output. But this thing here, the residual program that takes an interpreter and turns it into a compiler, is a compiler generator. So that means that what we've got out of the thing here was a compiler generator. So what's this thing we've got on the top? It's a compiler generator generator. So this is the third Futumora projection, right? If you partially evaluate a partial evaluator with respect to a partial evaluator, you get a compiler generator. And thankfully, we can't take it any further than that. Because if you did this again, you'd still be partially evaluating a partial evaluator with respect to a partial evaluator, right? So there are only three Futumora projections. So this is really cool. And this is why I wanted to tell you about this. I think it's funny and interesting and unusual. However, it doesn't mean that we don't need compiler writers anymore, right? Partial evaluation is a fully general technique for evaluating bits of computer programs. So it gets rid of the interpretive overhead of evaluating a program. But it doesn't do any of the clever stuff like inventing new data structures or optimizations or doing anything platform-specific. So we still need smart people to write compilers to make our programs go far. But this technique does remove some of the overhead of interpretation, right? It removes all of that stuff that involves parsing and generating code and all of that stuff. So if you're sufficiently interested in this, that you'd like to learn more, then there's a really interesting book called Partial Evaluation and Automatic Programme Generation, which is now available for free. So if you go to that URL there, you can download a copy of that. It's a really good textbook. I recommend it. So various bits of software that you may or may not be familiar with use techniques like this. So the JIT in LLVM and the bits of the PyPy tool chains, like R-Python and the VM and the JIT that underlie that, use some of these program specialization techniques. Rubinius sits on top of LLVM. So when you use Rubinius, stuff that's a little bit like this is happening. And there's a Ruby implementation called Topaz that sits on top of the PyPy tool chain and is a Ruby implementation that's written in Python. So if you use the Topaz Ruby implementation, then stuff like this is happening inside Topaz when you run your program. It happens at runtime rather than compile time. And quite aside from the partial evaluation stuff, Rubinius and JRuby are great because they are compilers that have got interesting and accessible implementations. So if you feel like you could become interested, sort of in the spirit of Max's keynote yesterday, if you feel like you want to get involved with stuff and you're interested in these kind of programs that generate programs, then you could do a lot worse than cracking open Rubinius or JRuby and having a look at how they work and maybe submitting a pull request or something. So much more generally than that. If you're generally interested in this sort of thing, I've written a book about all this sort of thing, which uses Ruby to go over all of these kinds of things and interpreters and compilers and the lambda calculus and cellular automata and type systems and stuff. So if you're interested, there's a book that you can read. There's a website for it. I rarely have given me a discount code so you can get 50% off if you use RubyConf as the discount code. That's all I wanted to say. Thanks very much. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you.
take the program and the input and instead of some of the input from the future when you're going to run the program to the present. You can to build one in Ruby. But briefly what happens is it can start like evaluating them and replacing method on it to turn it into a courage proc, and similar, but partial application is a technique hopefully makes it faster and more specialized to you can take a general program and a partial evaluation. He was thinking about how with then turn it into an abstract syntax tree and and a source program into the partial evaluator evaluation is a fully general technique for to write compilers to make our programs go far. Ruby to go over all of these kinds of things and