Dr. Futamura's Projection Machine: From Interpreters to Compilers through a Marvelous Device

Partial evaluation is a fascinating technique to specialize programs that has a number of applications; it dates back at least to the 1970s, but it has even deeper roots in computational theory. Recently, the buzz around the term has increased, as the GraalVM project has become mainstream in the industry; in fact, one ingredient to the “secret sauce” of this polyglot platform is partial evaluation: Futamura projections make it possible to derive optimized compilers from a high-level interpreter definition. In this talk, we will learn more about the theory behind GraalVM’s compiler: the three Futamura projections. Come and see how deep the rabbit hole goes!

Transcript

3. Copyright © 2018, Oracle and/or its affiliates. All rights reserved. | Confidential – Oracle Internal/Restricted/Highly Restricted !5 standalone Automatic transformation of interpreters to compilers Engine integration native and managed https://gotober.com/2018/sessions/650/graalvm-run-programs-faster-anywhere
4. Copyright © 2018, Oracle and/or its affiliates. All rights reserved. | !9 https://gotober.com/2018/sessions/650/graalvm-run-programs-faster-anywhere
6. The performance of many dynamic language implementations suffers from high allocation rates and runtime type checks. This makes dynamic languages less applicable to purely algorithmic problems, despite their growing popularity. In this paper we present a simple compiler optimization based on online partial evaluation to remove object allocations and runtime type checks in the context of a tracing JIT. We evaluate the optimization using a Python VM and find that it gives good results for all our (real-life) benchmarks.
7. The performance of many dynamic language implementations suffers from high allocation rates and runtime type checks. This makes dynamic languages less applicable to purely algorithmic problems, despite their growing popularity. In this paper we present a simple compiler optimization based on online partial evaluation to remove object allocations and runtime type checks in the context of a tracing JIT. We evaluate the optimization using a Python VM and find that it gives good results for all our (real-life) benchmarks.
9. Most high-performance dynamic language virtual machines duplicate language semantics in the interpreter, compiler, and runtime system. This violates the principle to not repeat yourself. In contrast, we define languages solely by writing an interpreter. The interpreter performs specializations, e.g., augments the interpreted program with type information and profiling information. Compiled code is derived automatically using partial evaluation while incorporating these specializations. This makes partial evaluation practical in the context of dynamic languages: it reduces the size of the compiled code while still compiling all parts of an operation that are relevant for a particular program. When a speculation fails, execution transfers back to the interpreter, the program re-specializes in the interpreter, and later partial evaluation again transforms the new state of the interpreter to compiled code.
10. Most high-performance dynamic language virtual machines duplicate language semantics in the interpreter, compiler, and runtime system. This violates the principle to not repeat yourself. In contrast, we define languages solely by writing an interpreter. The interpreter performs specializations, e.g., augments the interpreted program with type information and profiling information. Compiled code is derived automatically using partial evaluation while incorporating these specializations. This makes partial evaluation practical in the context of dynamic languages: it reduces the size of the compiled code while still compiling all parts of an operation that are relevant for a particular program. When a speculation fails, execution transfers back to the interpreter, the program re-specializes in the interpreter, and later partial evaluation again transforms the new state of the interpreter to compiled code.
11. We implement the language semantics only once in a simple form: as a language interpreter written in a managed high-level host language. Optimized compiled code is derived from the interpreter using partial evaluation. This approach and its obvious benefits were described in 1971 by Y. Futamura, and is known as the first Futamura projection. To the best of our knowledge no prior high-performance language implementation used this approach.
12. We implement the language semantics only once in a simple form: as a language interpreter written in a managed high-level host language. Optimized compiled code is derived from the interpreter using partial evaluation. This approach and its obvious benefits were described in 1971 by Y. Futamura, and is known as the first Futamura projection. To the best of our knowledge no prior high-performance language implementation used this approach.
13. We implement the language semantics only once in a simple form: as a language interpreter written in a managed high-level host language. Optimized compiled code is derived from the interpreter using partial evaluation. This approach and its obvious benefits were described in 1971 by Y. Futamura, and is known as the first Futamura projection. To the best of our knowledge no prior high-performance language implementation used this approach.
15. https://codon.com/compilers-for-free
17. Programs and Programming Languages
18. Programs • We call a program a sequence of instructions that can be executed by a machine. • The machine may be a virtual machine or a physical machine • In the following, when we say that a program is evaluated, we assume that there exists some machine that is able to execute these instructions.
19. Program Evaluation • Consider a program P, with input data D; • when we evaluate P over D it produces some output result R. D R P
20. f(k, u) = k + u 3 4 7 k + u
21. Interpreters • An interpreter I is a program • it evaluates some other given program P over some given data D, and it produces the output result R. P D R I • We denote this with I(P, D)
22. f(k, u) = k + u Instructions add x y sub x y mul x y ... write(D) while(has-more-instructions(P)): instr ← fetch-next-instruction(P) switch(op(instr)): case ’add’: x ← read() y ← read() result ← x + y write(result) case . . .
23. Compilers • Let be P a program that evaluates to R when given D; • A compiler C translates a source program P into an object program C(P) that evaluated over an input D still produces R P C C(P) C(P) D R • We denote this with C(P)(D)
24. f(k, u) = k + u sum: lea eax, [rdi+rsi] ret
25. $ cat example.ml print_string "Hello world!\n" $ ocaml example.ml Hello world! $ ocamlc example.ml $ ./a.out Hello world!
26. C(P)(D) = I(P, D)
27. Partial Evaluation
28. Partial Evaluation (intuition) Let us have a computation f of two parameters k, u f(k, u) • Now suppose that f is often called with k = 5; • f5(u) := “f by substituting 5 for k and doing all possible computation based upon value 5” • Partial evaluation is the process of transforming f(5, u) into f5(u)
31. This is Currying! I Know This! • Not exactly! In functional programming currying or partial applicationa is f5(u) := f(5, u) let f = (k, u) => k * (k * (k+1) + u+1) + u*u; let f5 = (u) => f(5, u); • In a functional programming language this usually does not change the program that implements f a Although, strictly speaking they are not synonyms, see https://en.wikipedia.org/wiki/Currying
32. Simplification let f = (k, u) => k * (k * (k+1) + u + 1) + u * u; by fixing k = 5 and simplifying: let f5 = (u) => 5 * (31 + u) + u * u;
33. Rewriting function pow(n, k) { if (k <= 0) { return 1; } else { return n * pow(n, k-1); } } function pow5(n) { return pow(n, 5); }
34. Rewriting function pow(n, k) { if (k <= 0) { return 1; } else { return n * pow(n, k-1); } } function pow5(n) { return n * pow(n, 4); }
35. Rewriting function pow(n, k) { if (k <= 0) { return 1; } else { return n * pow(n, k-1); } } function pow5(n) { return n * n * pow(n, 3); }
36. Rewriting function pow(n, k) { if (k <= 0) { return 1; } else { return n * pow(n, k-1); } } function pow5(n) { return n * n * n * n * n; }
37. Rewriting function pow(n, k) { if (k <= 0) { return 1; } else { return n * pow(n, k-1); } } function pow5(n) { return n * n * n * n * n; } In compilers this is sometimes called inlining
38. Rewriting and Simplification • Rewriting is similar to macro expansion and procedure integration (β-reduction, inlining) in the optimization technique of a compiler. • Often combined with simplification (constant folding)
39. Projection Projection The following equation holds for fk and f fk(u) = f(k, u) (1) we call fk a projection of f at k
40. Partial Evaluator A partial computation procedure may be a computer program α called a projection machine, partial computer or partial evaluator. α(f, k) = fk (2)
41. Partial Evaluator k u f(k, u) f
42. Partial Evaluator k u f(k, u) f
43. Partial Evaluator k u f(k, u) f fk α
44. Partial Evaluator function pow(n, k) { if (k <= 0) { return 1; } else { return n * pow(n, k-1); } } let pow5 = alpha(pow, {k:5}); // (n) => n * n * n * n * n;
45. Examples The paper presents: • Automatic theorem proving • Pattern matching • Syntax analyzer • Automatically generating a compiler
46. Examples The paper presents: • Automatic theorem proving • Pattern matching • Syntax analyzer • Automatically generating a compiler
47. Interpreters and Compilers (reprise) • An interpreter is a program • This program takes another program and the data as input • It evaluates the program on the input and returns the result I(P, D) • A compiler is a program • This program takes a source program and returns an object program • The object program processes the input and returns the result C(P)(D)
48. Partial Evaluation of an Interpreter P D R I
49. Partial Evaluation of an Interpreter P D R I
50. Partial Evaluation of an Interpreter P D R I IP α
51. First Equation of Partial Computation (First Projection) D R IP • That is, by feeding D into IP, you get R; • in other words, IP is an object program. I(P, D) = C(P)(D) α(I, P) = IP IP = C(P) (4)
52. f(k, u) = k + u (add x y) write(D) while(has-more-instructions(P)): instr ← fetch-next(P) switch(op(instr)): case ’add’: x ← read() y ← read() result ← x + y write(result) case . . .
53. f(k, u) = k + u (add x y) write(D) while(has-more-instructions(P)): instr ← fetch-next(P) switch(op(instr)): case ’add’: x ← read() y ← read() result ← x + y write(result) case . . . ...but this interpreter executes on a machine!
54. sum: lea eax, [rdi+rsi] ret
55. Partial Evaluation of an Interpreter P D R I IP α
56. Partial Evaluation of an Interpreter I P IP α
57. Partial Evaluation of the Partial Evaluation of an Interpreter I P IP α
58. Partial Evaluation of an Interpreter I P IP α αI α
59. Second Equation of Partial Computation (Second Projection) P IP αI αI(P) = IP (5) • but IP, evaluated on D gives R
60. Second Equation of Partial Computation (Second Projection) P C(P) αI αI(P) = IP (5) • but IP, evaluated on D gives R • then IP is an object program (P = C(P))
61. Second Equation of Partial Computation (Second Projection) P C(P) αI αI(P) = IP (5) • but IP, evaluated on D gives R • then IP is an object program (P = C(P)) • αI transforms a source program P to IP (i.e., C(P))
62. Second Equation of Partial Computation (Second Projection) P C(P) C αI(P) = IP (5) • but IP, evaluated on D gives R • then IP is an object program (P = C(P)) • αI transforms a source program P to IP (i.e., C(P)) • then αI is a compiler
64. Partial Evaluation of the Partial Evaluation of an Interpreter I P IP α αI = C α
65. Partial Evaluation of the Partial Evaluation of an Interpreter α I αI = C α
66. Partial Evaluation of the Partial Evaluation of an Interpreter α I αI = C α
67. Partial Evaluation of the Partial Evaluation of the Partial Evaluation of an Interpreter α I αI = C α αα α
68. Third Equation of Partial Computation (Third Projection) I αI = C αα αα(I) = αI (6) • αα is a program that given I, returns αI = C • αI transforms a source program to an object program • αI is a compiler • αα is a compiler-compiler (a compiler generator) which generates a compiler αI from an interpreter I
70. Partial Evaluation of the Partial Evaluation of an Interpreter α I αI = C α
71. Partial Evaluation of the Partial Evaluation of an Interpreter α I αI = C α
72. Partial Evaluation of the Partial Evaluation of the Partial Evaluation of an Interpreter α I αI = C α αα α
73. Projection of α at α α α αα α
74. Projection of α at α α α αα α
75. Projection of α at α α α αα α αα α
76. Fourth Equation of Partial Computation αα(α) = αα α αα αα • αα(I) = αI = C is a compiler for the language interpreter I; thus: αα(I) = αI = C αα(I)(P) = IP = C(P) • I is an interpreter • but at the beginning we said it could be any program • so, what is αα?
77. What is αα ? αα(I) = αI = C αα(α) = αα = C(α) • αα is a “compiler” for the “language α” ! • In other words, by finding αα we can generate fk for any f, k ! αα(f)(k) = fk (Fourth Equation) • That is, αα is a partial evaluation compiler (or generator). • However, the author notes, at the time of writing, there is no way to produce αα from α(α, α) for practical α’s.
78. GraalVM
80. We implement the language semantics only once in a simple form: as a language interpreter written in a managed high-level host language. Optimized compiled code is derived from the interpreter using partial evaluation. This approach and its obvious benefits were described in 1971 by Y. Futamura, and is known as the first Futamura projection. To the best of our knowledge no prior high- performance language implementation used this approach.
81. We implement the language semantics only once in a simple form: as a language interpreter written in a managed high-level host language. Optimized compiled code is derived from the interpreter using partial evaluation. This approach and its obvious benefits were described in 1971 by Y. Futamura, and is known as the first Futamura projection. To the best of our knowledge no prior high- performance language implementation used this approach.
82. We believe that a simple partial evaluation of a dynamic language interpreter cannot lead to high-performance compiled code: if the complete semantics for a language operation are included during partial evaluation, the size of the compiled code explodes; if language operations are not included during partial evaluation and remain runtime calls, performance is mediocre. To overcome these inherent problems, we write the interpreter in a style that anticipates and embraces partial evaluation. The interpreter specializes the executed instructions, e.g., collects type information and profiling information. The compiler speculates that the interpreter state is stable and creates highly optimized and compact machine code. If a speculation turns out to be wrong, i.e., was too optimistic, execution transfers back to the interpreter. The interpreter updates the information, so that the next partial evaluation is less speculative.
83. We believe that a simple partial evaluation of a dynamic language interpreter cannot lead to high-performance compiled code: if the complete semantics for a language operation are included during partial evaluation, the size of the compiled code explodes; if language operations are not included during partial evaluation and remain runtime calls, performance is mediocre. To overcome these inherent problems, we write the interpreter in a style that anticipates and embraces partial evaluation. The interpreter specializes the executed instructions, e.g., collects type information and profiling information. The compiler speculates that the interpreter state is stable and creates highly optimized and compact machine code. If a speculation turns out to be wrong, i.e., was too optimistic, execution transfers back to the interpreter. The interpreter updates the information, so that the next partial evaluation is less speculative.
85. https://twitter.com/larsr h/status/1227956746104266753
86. References • W¨ urthinger et al. 2017, Practical Partial Evaluation for High-Performance Dynamic Languages, PLDI’17 • ˇ Selajev 2018, GraalVM: Run Programs Faster Anywhere, GOTO Berlin 2018 • Bolz et al. 2011, Allocation Removal by Partial Evaluation in a Tracing JIT, PEPM’11 • Stuart 2013, Compilers for Free, RubyConf 2013 • Cook and L¨ ammel 2011, Tutorial on Online Partial Evaluation, EPTCS’11