Skip to content
Hallway
0:00 / 0:00

#partialevaluation#futamuraprojections#ruby

Ruby Conf 2013 - Compilers For Free by Tom Stuart

Confreaks

42K subscribers • 74 videos on Hallway • Conference channel

YouTube
  • Recommended by 2 people: 2 in engineering communities.
  • A classic. People kept recommending it from 2014 to 2023.
  • Presented by Tom Stuart, author of Understanding Computation

Intermediate. Assumes working knowledge.

6.5K views12 years ago2 recommendations

Programming languagesSystems programmingCompilers and interpretersFunctional programming

Tom Stuart explains partial evaluation and the Futamura projections, showing how to automatically generate a compiler from an interpreter.

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. Help us caption & translate this video! amara.org/v/FG55/

Why it's here

2 people recommend this

What people say. Highly recommended for its clear explanation of the Futamura projections and how interpreters can be turned into compilers.

Moments people linked to

u/raiphin r/ProgrammingLanguages • Recommends

On “Can an interpreted language be faster than a compiled language?”

Consider watching compilers for free. The presenter shows a completely generic technique which can **convert** ***any*** **interpreter into a compiler**. It's a hugely important computer science discovery from 1971 that relatively few know about. If you can't handle the full 40 minutes, watch the first couple minutes till you've had your fill then jump to the 35 minute mark.
4View on Reddit

u/daverin r/ProgrammingLanguages • Recommends

On “Theory about interpreters”

I wholeheartedly recommend the book titled Understanding Computation by Tom Stuart. Here's a great talk he did on some of the ideas in the book as well: [video Also, Lisp in Small Pieces is great.
2View on Reddit

u/raiphin r/ProgrammingLanguages • Recommends

On “Distinguishing an Interpreter from a Compiler”

Ah, I just refreshed my memory by watching it again. It was *not* fun for me this time around until the tiny bit about projections. That disappointment/surprise motivated me to find earlier comments I'd written about it, and it turns out that while I must have watched it again just a couple years ago, and remembered it all as fun, the bit that mattered is at the *end* of the video: > More fundamentally, as Tom Stuart puts it, it's all just how you choose to do evaluation and when. He explains this in a fun fast paced 40 minute "Compilers for free" video, in which he builds an interpreter, a transpiler, a compiler, an evaluator, and then introduces a partial evaluator, and -- the bit that's…
2View on Reddit

u/raiphin r/ProgrammingLanguages • Recommends

On “Distinguishing an Interpreter from a Compiler”

Ah, even better, from my first comment about it in this sub (9 years ago; how time flies!): > Here's a link that starts about two thirds of the way through a video about partial evaluation and the cool thing Doctor Futamura realized in 1971. > > At the point I've linked the presenter is a few seconds from the end of explaining that he's NOT talking about mere "partial application" (eg currying). Next, he spends a couple minutes discussing some "useful applications" of partial evaluation (eg speeding up a raytracer). Then comes a 10 minute exposition of "Futamura's Three Projections".
2View on Reddit

u/raiphin r/ProgrammingLanguages • Recommends

On “{compiler, interpreter} = ?”

The following might be interesting to some readers... Here's a link that starts about two thirds of the way through a video about partial evaluation and the cool thing Doctor Futamura realized in 1971. At the point I've linked the presenter is a few seconds from the end of explaining that he's NOT talking about mere "partial application" (eg currying). Next, he spends a couple minutes discussing some "useful applications" of partial evaluation (eg speeding up a raytracer). Then comes a 10 minute exposition of "Futamura's Three Projections".
1View on Reddit

u/raiphin r/ProgrammingLanguages • Mentions

On “Can an interpreted language be faster than a compiled language?”

> A JIT-compiler exists at some middle-ground between an AOT-compiler and an interpreter, but if we include the extremes, Imo it's perfectly reasonable to classify a JIT as at one end (an interpreter) or at the other (a compiler). It's also reasonable to say there are a spectrum of solutions for getting from source code to running code, which can include multiple "interpreters" and "compilers" working in concert. But there's not just two ends and a middle. Even sticking with JITs, a method JIT is a very different evaluation staging strategy than a tracing JIT. More fundamentally, as Tom Stuart puts it, it's all just how you choose to do evaluation and when. He explains this in a fun fast…
3View on Reddit

u/abstractcontrolin r/compsci • Mentions

On “What are potential disadvantages of functional programming? For which areas does functional programming work best and for which ones not?”

By splitting the program into statically known terms such as constants and dynamic terms whose values can only be determined during runtime, it is possible to aggressively optimize the program by doing as much possible at compile time. Compilers already do this, and when it is done automatically compile-time program specialization is called partial evaluation. When it is done in a user directed manner it is called staging. By taking responsibility for having the compiler terminate, which is the main issue in both partial evaluation and staging, it is possible to make the program vastly more efficient. An example of the language that has it would be Scala via its LMS library. Scala LMS…
2View on Reddit