Compilers For Free
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 50 | |
| Author | ||
| License | CC Attribution - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/37466 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Producer | ||
| Production Place | Miami Beach, Florida |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
FreewareCompilerCompilerComa BerenicesComputer programMetaprogrammierungFreewareComputer programmingGoodness of fitSoftwareInstance (computer science)Point (geometry)CountingCompilerSelf-referenceRight angleRepresentation (politics)Run time (program lifecycle phase)Functional programmingInterpreter (computing)MetaprogrammierungPresentation of a groupFluid staticsWritingPower (physics)Software testingProgrammer (hardware)XMLComputer animation
01:50
Computer programFormal languageVirtual machineComputer programmingRight angleVirtual machineFormal languageParameter (computer programming)Configuration spaceComputer fileNeuroinformatikHigh-level programming languageInterpreter (computing)CompilerPosition operatorForceFreewareSource codeTerm (mathematics)Film editingAbstractionStandard deviationLatent heatMachine codeFunction (mathematics)outputLevel (video gaming)
02:50
Source codeAbstract syntax treeFormal languageExpressionSystem callSound effectAbstract syntax treeDemo (music)Statement (computer science)ProgrammschleifeIntegrated development environmentVariable (mathematics)Right angleComputer programmingFormal languageNetwork topologyClosed setSource codeBitInterpreter (computing)Imperative programmingProcess (computing)19 (number)Point (geometry)Keyboard shortcutWebsiteCondition number2 (number)
04:15
Recurrence relationFormal grammarUsabilityExecution unitFormal languageGamma functionSequenceStatement (computer science)Right angleCondition numberVariable (mathematics)Term (mathematics)Boolean algebraFormal grammarParsingFormal languageNumberState of matterBinary codeExpressionGreatest elementAtomic numberRule of inferenceDifferent (Kate Ryan album)Condition numberSign (mathematics)Variable (mathematics)WebsitePoisson-KlammerNetwork topologyProgramming languageData structureColor confinementInformationInequality (mathematics)2 (number)Loop (music)Statement (computer science)Boolean algebraSequenceRight angleSocial classParsingLecture/Conference
05:17
Structural loadParsingParsingStrutNumberBoolean algebraVariable (mathematics)MultiplicationSequenceExpressionRegulärer Ausdruck <Textverarbeitung>Abstract syntaxParsingString (computer science)QuicksortRepresentation (politics)SyntaxbaumAbstract syntax treeConnectivity (graph theory)Structured programmingInformationData structureStatement (computer science)Spring (hydrology)Simplex algorithmAbstractionFreewareNetwork topologySocial classMereologyDifferent (Kate Ryan album)ExpressionMachine codeRevision controlNumberRight angleInstance (computer science)SequenceRule of inferenceIntegerRootBoolean algebraVariable (mathematics)Complex (psychology)Formal grammarExtreme programmingCASE <Informatik>RecursionPoint (geometry)Force
07:18
Variable (mathematics)NumberBoolean algebraIntegrated development environmentMultiplicationNetwork topologyAbstract syntaxResultantAbstract syntax treeStatement (computer science)SequenceRootNumberIntegrated development environmentGoodness of fitInterpreter (computing)Social classSign (mathematics)Reading (process)Different (Kate Ryan album)Instance (computer science)Operator (mathematics)Right angleBoolean algebraHash functionExpressionMultiplication signBinary multiplierProgram flowchart
08:48
Variable (mathematics)MultiplicationInequality (mathematics)SequenceIntegrated development environmentNumberParsingParsingExpressionMultiplication signIntegrated development environmentStatement (computer science)Direction (geometry)ResultantSign (mathematics)MappingComputer programmingSequenceParsingLoop (music)Abstract syntax treeInterpreter (computing)CNNPoint (geometry)Open setLevel (video gaming)Arithmetic meanSingle-precision floating-point format
10:26
Source codeInterpreter (computing)Single-precision floating-point formatFormal languageVirtual machineCASE <Informatik>Computer programmingRight angleMultiplication signoutputSource codeLevel (video gaming)Function (mathematics)Standard deviationRun time (program lifecycle phase)CircleCompilerFreewareLine (geometry)Parameter (computer programming)Impulse responseSimilarity (geometry)Internet service provider
11:19
CompilerSource codeAbstract syntax treeMachine codeFunction (mathematics)NumberVariable (mathematics)Boolean algebraMultiplicationJava appletAbstract syntaxString (computer science)Source codeComputer programmingAbstract syntax treeBinary codeRevision controlMappingObject-oriented programmingMultiplication signVariable (mathematics)NumberFunctional programmingRight angleSequenceReal numberMachine codePoint (geometry)Boolean algebraProcess (computing)Mortality rateExpressionScripting languageRecursionIntegrated development environmentDescriptive statisticsBit rateStatement (computer science)Asynchronous Transfer ModeCASE <Informatik>Java appletFilm editingLogical constant
12:59
ParsingParsingFunction (mathematics)Computer programCompilerSource codeComputer programmingFormal languageScripting languageJava appletCompilerDescriptive statisticsResultantVideo game consoleGreatest elementProcess (computing)Interpreter (computing)Source codeDifferent (Kate Ryan album)outputVirtual machineRight anglePosition operatorMultiplication signLevel (video gaming)Keyboard shortcutHand fanCompilerOverhead (computing)Goodness of fit2 (number)
14:22
Overhead (computing)Computer programMathematical optimizationComputer programmingData structureRun time (program lifecycle phase)Programming languageFormal languageInterpreter (computing)Mathematical optimizationMultiplication signCompilerComputer architectureMathematicsOverhead (computing)Machine codeCompilerVirtual machineGoodness of fitRight angleDisk read-and-write headAbstract syntax treeNeuroinformatikFluid staticsSocial classDynamical systemCompiler constructionProcess (computing)Interrupt <Informatik>NP-hardRegular graphBit ratePerformance appraisal
16:51
Interpreter (computing)Partial derivativeCompilerCompilerPerformance appraisalInterpreter (computing)Right angleProcess (computing)Computer programmingCompilerWeightMachine codeHybrid computerMereologyoutputVideo gameLiquidResidual (numerical analysis)MomentumPartial derivativeMultilaterationComputer animationDiagram
17:22
outputInterpreter (computing)MereologyPartial derivativeResidual (numerical analysis)Performance appraisalQuicksortCompilerLevel (video gaming)Interpreter (computing)outputPoint (geometry)Virtual machineMereologyResidual (numerical analysis)MultilaterationComputer programmingBoiling pointComputer fileNeuroinformatikLiquidPartial derivativeMultiplication signConfiguration spaceFunction (mathematics)NumberStandard deviationShift operatorRevision controlLine (geometry)System callHeegaard splittingParameter (computer programming)Process (computing)State of matterSingle-precision floating-point format
18:54
Process (computing)InformationInterpreter (computing)Abstract syntax treeSource codeoutputComputer programMachine codeCompilerSource codeComputer programmingInterpreter (computing)Abstract syntaxLevel (video gaming)Abstract syntax treeProcess (computing)Multiplication signoutputSingle-precision floating-point formatHeegaard splittingQuicksortMachine codeResultantReading (process)Power (physics)Video gameCompilerPartial derivativePerformance appraisalProgrammer (hardware)Impulse responseMathematical analysis
20:02
Power (physics)Revision controlSource codeParameter (computer programming)Point (geometry)outputExpressionInterpreter (computing)System callFunctional programmingBitLevel (video gaming)InformationQuicksortInstance (computer science)Power (physics)Performance appraisalMultiplication signPartial derivativeMachine codeNumberBinary multiplierResidual (numerical analysis)Cartesian coordinate systemComputer programmingTransformation (genetics)MultiplicationDemo (music)MereologyRight angleTotal S.A.Video game consoleProduct (business)Matching (graph theory)Term (mathematics)Data storage deviceFrame problemSubstitute goodLine (geometry)
24:22
outputServer (computing)Graphics processing unitCartesian coordinate systemPerformance appraisalPoint (geometry)FlagImplementationComputer programmingoutputPartial derivativeOverhead (computing)Computer fileServer (computing)Computer hardwareRevision controlPolygonConfiguration spaceDemosceneWeb 2.0Right angleFrame problemDirection (geometry)Different (Kate Ryan album)MereologyRay tracingInterpreter (computing)Graphics processing unitSource codeSubsetArithmetic meanMultiplication signQuicksortBitCycle (graph theory)Intermediate languageMacro (computer science)Bit rateOpen setVirtual machineSystem callSoftwareGame controller
27:04
Source codeInterpreter (computing)Residual (numerical analysis)Partial derivativeComputer programmingMultiplication signValuation (algebra)Interpreter (computing)Shift operatorPartial derivativeBitoutputFunction (mathematics)QuicksortResidual (numerical analysis)NeuroinformatikCuboidMereologySource codeRevision controlPerformance appraisalGreen's functionFreewareVirtual machineContext awarenessRight angleOnline helpImpulse responseCompilerMeeting/Interview
29:21
ParsingParsingStructural loadIntegrated development environmentVariable (mathematics)NumberSequenceMultiplicationAbstract syntax treeComputer programmingSource codePerformance appraisalMachine codeInterpreter (computing)Right angleVariable (mathematics)Abstract syntaxPropagatorLetterpress printingFormal grammarPartial derivativeoutputInstance (computer science)ResultantMereologyMathematical analysisParsingIntegrated development environmentReading (process)String (computer science)Multiplication signParsingKeyboard shortcutSineNetwork topologyWave packetImpulse responseFreewareSocial classLocal ringType theorySlide rule
31:35
SequenceIntegrated development environmentVariable (mathematics)NumberMultiplicationResultantSource codeMappingMultiplication signLine (geometry)ExpressionNumberIntegrated development environmentStatement (computer science)outputRootMachine codeAbstract syntax treeRight angleInstance (computer science)Social classBitQuicksortOrder (biology)Performance appraisalComputer programmingPartial derivativeCASE <Informatik>Interpreter (computing)ImplementationCompilerBoiling pointProjective planeCoroutineSign (mathematics)2 (number)SequenceDirection (geometry)
34:47
Axonometric projectionSource codeInterpreter (computing)Partial derivativeComputer programResidual (numerical analysis)CompilerRight angleInterpreter (computing)Computer programmingSource codeoutputMereologyPerformance appraisalFunction (mathematics)Revision controlResidual (numerical analysis)Multiplication signCompilerPartial derivativeFormal languageMechanism designQuicksortOrder (biology)ResultantProjective planeValuation (algebra)Point (geometry)Program flowchart
36:45
Interpreter (computing)Axonometric projectionCompilerPartial derivativeResidual (numerical analysis)Source codePerformance appraisal2 (number)Projective planePartial derivativeCompileroutputSource codeComputer programmingInterpreter (computing)MereologyBitFunction (mathematics)Programmer (hardware)Connectivity (graph theory)QuicksortDependent and independent variablesResidual (numerical analysis)
38:12
Axonometric projectionData structureComputing platformFormal languageExploit (computer security)Latent heatCompilerProjective planePartial derivativePerformance appraisalCompilerComputer programmingOverhead (computing)Direction (geometry)Arithmetic meanLatent heatCompiler constructionData structureInterpreter (computing)Computing platformMathematical optimizationBitMachine codeParsingSoftwareAutomatic programmingRight angleElectric generator
39:16
Computer programTeilauswertungJust-in-Time-CompilerChainImplementationCompilerComputer programmingPartial derivativeCompilerInterpreter (computing)Just-in-Time-CompilerOpen setImplementationChainAutomatic programmingQuicksortRun time (program lifecycle phase)BitMaxima and minimaSoftwareAutomatonSystem programmingType theoryMultiplication signLine (geometry)Programmer (hardware)CalculusMassLecture/Conference
40:40
Machine codeDiscounts and allowancesVideoconferencingCellular automatonInterpreter (computing)WebsiteCompilerType theoryDiscounts and allowancesSystem programmingMachine codeQuicksortLambda calculus
Transcript: English(auto-generated)
00:00
Good morning everyone. Thanks for coming to this talk.
00:22
I'm Tom Stewart. I'm gonna talk about, well, I'm gonna 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.
00:41
OK. As Ruby programmers, we're already kind of intuitively, we already intuitively understand the power of meta-programming, right. Programs that write programs. So let's, 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 run time that wasn't, like, present in the static program
01:01
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
01:22
world of compilers and interpreters and static analyzers. 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
01:42
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 gonna 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
02:02
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 those inputs into the machine that's got the program inside it, and the program executes on the machine and it produces some output. I think
02:20
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. 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.
02:41
But, if your program's written in a language that's unfamiliar to the machine, then you're gonna 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
03:00
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 gonna show you a little demo of how this works by just introducing this, a language that I'm gonna call Simple.
03:21
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. The 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
03:42
19 plus 23 is a statement. And that statement is gonna have, is gonna modify the lexical environment. So when you evaluate a statement, it's gonna 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, you know, it's got sequencing
04:02
in it. It's got conditionals in it. It's got while loops 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 recognize 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 parsers. And I'm just gonna
04:21
very, very quickly show you how we can build a grammar for, 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. So I can say a sequence is two statements separated by a semicolon, a while loop says
04:41
while bracket and then a condition and then, you know, curly braces around the body of the while loop and 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 kind of the atomic things like numbers and booleans and variables, right. So I'm
05:00
just gonna scoot past that, but you, if you write a file like that that explains what your programming language looks like, you can use the Treetop 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 Treetop will do is give you back this big data structure called a concrete syntax tree or a parse tree, and this has got
05:22
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 like a more useful representation of the structure of the statement we gave it. And we can make an abstract syntax
05:41
tree by first we can declare a bunch of classes that we're gonna use to instantiate to make the nodes of the abstract syntax tree, and I'm just gonna use struct to do that. So I'm gonna 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 have got the variable name and the expression that's being assigned to it and so
06:00
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 abstract, in the concrete syntax tree, I want to define a method on that called to-ast, 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
06:21
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
06:42
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 growing them together with the right, the right kind of node class. So once I've done all of that work, I
07:01
can get treetop 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 out of 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
07:20
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. And the 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
07:41
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 gonna define an evaluate method on each of those abstract syntax tree classes, and the evaluate method is gonna take an environment, which is the lexical environment, it's a hash that says what the value of each variable currently is. So if you're evaluating a number or
08:02
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
08:23
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
08:41
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 six. 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
09:02
statements. I'm not gonna 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
09:21
on for all of these, the rest of these things. You know, sequence kind of evaluates the first, you know, the, 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 one, if I start
09:41
with an empty environment and I evaluate it, I get a new environment where x has got the value one. If I do a sequence of assignments, x equals one and then x equals two in an empty environment, I end up with x equals two, 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
10:01
an empty environment. So if I evaluate x equals two, y equals x times three in an empty environment, I get x is two, y is six. That's like the way you do that with a, you know, a more sophisticated program that's got a while loop in it. This is just a little program that starts out x at one, and it keeps multiplying it by three until the value becomes greater than five, and then that finishes up with x being the value of nine.
10:22
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 this, 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, we'll also be,
10:41
also provide some input to the program. So if the interpreter is IR, 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
11:02
can run on the underlying, 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, is what you would call runtime. So what about compilers? How are they different? Well, they're
11:20
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 gonna, I don't have time
11:41
to go into any detail of how to, how to do this properly, but I am gonna show you an example. So here's a version of, instead of having two, instead of having evaluate defined on those abstract syntax tree nodes, I could define a method called toJavaScript, and this is just gonna return a string which contains some JavaScript code that does whatever that node is supposed to do. The, the JavaScript code
12:01
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, in this case, when you have expressions, like a
12:21
number is gonna turn into a function that just returns a constant number, and a boolean's gonna return a constant boolean, and a variable's gonna look up the variable in the environment, so this is a JavaScript variable, and then it's gonna look up the right value in that, in that JavaScript object. Just very quickly, same for these kind of binary expressions, I just like recursively convert the left and right sub-expressions to JavaScript
12:41
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 an 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
13:00
I can take, like, this program that I showed you before, x equals one while x is less than five, 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 paste it in on the
13:23
say, look, here's my program, and then you probably can't see at the bottom here, when I run this program in JavaScript I get the result x is nine. 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, right.
13:42
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
14:00
was just data when the compiler emitted 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.
14:22
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, like, deciding what you're gonna do with it. That all gets done at compile time, and by the time the program runs,
14:41
that work's already been done, and so if you're gonna 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
15:01
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've read in a program, and I'm gonna do what that program says to do right now.
15:21
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 gonna 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
15:42
it did was generate some JavaScript code. So to write the compiler, I was actually writing in two programming languages kind of intertwined, and that's harder to kind of get your head around. And also, in a very vague hand wavy 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
16:00
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 runtime, right. If you've got things like define method and you can create new classes and things like that, it's just hard to write a compiler for languages that kind of, where the programs can change dynamically as they execute. So, long story short, writing an interpreter is
16:21
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
16:43
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
17:01
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.
17:21
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 boil a liquid and you get a residue
17:41
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
18:01
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, this is the computation I ultimately want to do at some point in the future, but I want to do this
18:20
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'll read in a program, and it'll read in some of the input for that program, and then when you execute the partial evaluator,
18:41
it'll 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
19:01
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 like, 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,
19:21
just like an interpreter or a compiler. You build an abstract syntax tree just like an interpreter or a compiler. And, 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
19:41
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, you know, I can't really give you a whole program example in Ruby
20:02
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 gonna show you this on the, on the, on the level of an individual method. So imagine we've got, 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, if I passed in three as the value of n here,
20:21
it's gonna do x multiplied by power two x, and it's gonna recursively multiply x by itself three times, right. So say that I've told my partial evaluator that I know that this method is gonna be called with five as the first argument. So I know I'm gonna be calling it with the value of n being five. So what the partial evaluator's gonna do is kind of start looking at this
20:41
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, 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
21:00
and replacing them. So what we're gonna do is, instead of having this power method that takes two arguments, we're gonna make a method called power five that only takes one argument, x, and the value of n is gonna be, like, fixed in this method. So all of those instances of n, I'm just gonna turn into five, and then we can start partially evaluating this and saying, well, I can already tell you what the value of five
21:21
dot zero is gonna be. That's gonna be false. And then once you've done that, you've now got a conditional here, which you are able to, so by sort of propagating the information about what expressions are available, you can say, well, I know that this thing is just gonna evaluate to this guy here, right, because it was if false. And now I've got this five minus one, I can evaluate that to get four.
21:40
And then I can do some kind of, I can inline the body of this method here. If I know that I'm gonna be calling power with four and x, then I can just get this code in here with four substituted for the value of n. And then you can just keep doing the same thing. You can say, well, four dot zero is gonna be false, so that means that bit of the program is gonna be x times power four minus one, and that's gonna be power three x,
22:00
and you can keep going, so, you know, two, one, zero. You keep generating more multiplied by x's. When you get down to zero, you get into this situation where now you're saying if zero dot zero, which is gonna evaluate to true, which means you're gonna end up with one there. So just to tidy that up a bit, you end up with a definition of power five that is just x multiplied by itself five times and then multiplied by one.
22:20
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 one, 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.
22:42
It's just used all of the existing Ruby and kind of moved bits of it around and figured out, like, what it should look like. And the point of doing this, of course, is that this version of power five should be faster. You know, this doesn't make any recursive method calls. It just multiplies x by itself five times, whereas this thing has got, like, every recursive call, you've got a new stack frame,
23:00
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 gonna be five. 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 five
23:21
by just saying, well, call power with five as its first argument, and if I run that on the console, then that does work. You know, power five of two is 32, because that's two to the power of five. But this new version of the method isn't any, isn't better than the original one. I mean, actually calling this is gonna be slightly slower because you get another stack frame, there's another method execution going on there.
23:40
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 curried 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'll give me a new value back. So partial application is a little bit similar, but partial application is a technique
24:01
that you do inside your program. You make new values, new function values, in sort of 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 sort of faster and more specialized to particular input values.
24:21
So I just wanted to note that there are a couple of, like, useful applications of this technology. The main point of this is that you can take a general program and a partial evaluator 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
24:41
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 is, 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, that's pretty good. Some of the things you could do with that, for example, if you've got a web server
25:01
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 you could specialize the whole, you know, web server and give it just your config file as the input,
25:22
and the partial evaluator will generate you a 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 gonna be part of the program anymore. It would 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
25:42
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,
26:02
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, in Mac OS 10, the OpenGL pipeline is,
26:23
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,
26:42
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, gets partially evaluated away, and it just runs on hardware, whereas all the features that your GPU doesn't have just kind of stay in the OpenGL pipeline written as software, right.
27:01
So anyway, at the beginning, I promised you I was gonna 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
27:22
and you get your output, and you can use partial evaluation to time shift that bit to do, to 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,
27:41
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 time, to sort of time shift 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?
28:01
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, this is called kind of partially evaluating the interpreter with respect to the source program. So this is an input to the interpreter, you put both of them in the partial evaluator, you get a residual program
28:20
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, you know, 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, that reads an input,
28:41
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, 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
29:00
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? Right. That's the compiler, right? So there's your compiler for free. No, no refunds. So that, that's pretty cool. How does that work? Does that, I mean, that seems like too good to be true, right?
29:20
Let's just go through a quick example. So here's my, 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 gonna read in the source and the starting environment, the bindings and variables to their values, from somewhere. It's gonna somehow acquire the source code in the environment, and it's gonna
29:41
use treetop to load the grammar, and then it's gonna, it's gonna make, it's gonna instantiate the parser and then turn it into an abstract syntax tree, and then let's say it's just gonna print out the result of evaluating the original program in the environment we provided, right. So if we're gonna, if we're gonna do the, what Futamura suggested, we're gonna take, we're gonna feed this into a partial evaluator, and we're gonna give it the simple source
30:02
program as like partial input, and then we're gonna evaluate as much of the program as we can and see what's left over. So that means that we're gonna provide a particular source, so one way or another we're gonna arrange that when this thing tries to read its source, it actually gets the string of a simple program, say, so this x equals two, y equals x times three is just an arbitrary program.
30:20
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 gonna be that guy, then actually this instance of source here is gonna 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
30:41
the AST by parsing this string and then calling to AST on it, that's, 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 this, 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
31:01
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's 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.
31:23
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
31:41
definition of evaluate on it. So for sequence, evaluate looks like evaluate the first statement in the environment and then use that as the input to evaluate 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 evaluating
32:01
that expression. That multiply just says evaluate the left hand, says expression evaluate the right hand one, multiply them together, and all of these things like number, 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,
32:20
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 two and we know that the name is x and we know that the value is three 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
32:40
evaluate the expression, evaluate the left expression, evaluate the right expression, we know that they're gonna be two and environment x and three, so we can inline all of those things into these definitions here, and then again here we can see that the name is gonna be x, the name here is gonna be y, and the result of evaluating this expression is gonna be environment x times three, so we can like
33:00
inline all of that stuff, and then finally up here we can see, well, evaluate the first expression is just gonna be this environment dot merge x maps to two, and this evaluate the second expression, the second statement, sorry, is gonna be update the environment, it's a little bit tricky because the environment gets mentioned twice here, so what I'm gonna need to do is, you know, the partial evaluator would
33:21
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 gonna do this. The
33:41
environment is the result of updating the environment with x is mapped to two, and then we make a new environment where y is mapped to whatever the value of x is times three. So going back to this original thing here, when we call ast dot 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
34:00
one by making x equal to two, and then print out the result of merging in y is equal to whatever the value of x is times three. And so comparing that to the simple program that we started with, that, in a very, 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
34:21
Ruby program that does what this thing does. I mean there's, 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
34:41
of the program we started with. So that's kind of how you can compile stuff with partial evaluation. So this is called the first Futamura projection, right. If you partially evaluate an interpreter with respect to some source code, you get a target program. So that's really good. Futamura was pretty pleased with himself when he realized
35:01
that. So this is the picture I showed you before. 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 time shift
35:20
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's input, you can feed the partial evaluator and the interpreter into the partial evaluator, and
35:40
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, right? So that makes sense, that's just, we've just split it apart with more, you know, with time again. But when he looked at this, he thought, well what's
36:01
what I've got here is that I've got a source program going in 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, right? 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
36:20
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.
36:40
You've just got a bonafide compiler that you can run and it will compile your language. So that's really cool. That's called the second Futamura projection. If you partially evaluate a partial evaluator with respect to an interpreter, you get a compiler. So Futamura was pretty pleased with himself when he realized that. And he was thinking about this, and specifically he was thinking about this first bit.
37:03
And he was thinking about 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
37:20
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
37:40
a compiler, and then later on you run the compiler with the source program as input, and then you get a 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 got out of the thing here was
38:00
a compiler generator. So what's this thing we've got on top? It's a compiler generator generator! So this is the third Futamura projection, right? If you partially evaluate a partial evaluator with respect to a partial evaluator, you get a compiler generator, and thankfully
38:21
we can't take it any further than that, because if you did this again, you'd just be, you'd still be partially evaluating a partial evaluator with respect to a partial evaluator, right? So there are only three Futamura 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 like unusual. However, it doesn't mean that we don't need compiler writers anymore, right?
38:41
Partial evaluation is a fully general technique for evaluating bits of computer programs. So it gets rid of the interpretive overhead of the, of the, of evaluating a program. But it doesn't do any of the clever stuff like inventing new data structures or optimizations or doing anything kind of platform specific. So we still need smart
39:00
people to write compilers to make our programs go fast. 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
39:20
partial evaluation and automatic program generation, which is, which is now available for free. So I've, if you go to that URL there, you can download a copy of that. It's a really good textbook. I recommend it. Also, various bits of software that you may or may not be familiar with use techniques like this. So like, the JIT in LLVM and the bits of the PyPy tool chains,
39:40
like R Python and the VM and the JIT that underlie that, use some of these kind of 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
40:00
Topaz Ruby implementation, then kind of stuff like this is happening inside Topaz when you run your program. It happens at run time rather than compile time. And, quite aside from the partial evaluation stuff, Rubinius and JRuby are great because they are compilers that have got like interesting and accessible implementations. So if you feel like you could
40:20
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, you know, submitting a pull request or something. So much more generally than that, if you're generally interested in this sort of thing,
40:40
I've written a book about all this sort of thing, which uses Ruby to go over all 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.
41:00
That's all I wanted to say. Thanks very much.