Partial evaluation in Dart

[lukehutch]

const in Dart is only a halfway step to partial evaluation. There are a lot of things I have to compute in my Flutter app on startup that are not const according to Dart, but they will deterministically always return exactly the same result (e.g. a color table that is generated from some fixed number of entries in a const array that is provided in the source code). Having to pre-generate this sort of thing using a separate program, then incorporating it as a const table, is a pain.

Partial evaluation is complex, but Dart would benefit greatly from it. The user could indicate a CPU budget to the compiler for how much time to spend in partial evaluation, and/or parts of the program that should or should not be partially evaluated could be marked by the user using an annotation.

A major benefit of adding proper partial evaluation to the language is that type resolution becomes just another computation that is partially evaluated by the compiler. dynamic is the type of anything that cannot be partially evaluated, because the type quite literally depends upon some input, dynamically.

[gintominto5329]

something like c++'s constexpr?

I too, have many applications for this:

• class constructor wrapper functions
• in-class constructor's statements, following the : char

In many cases, I need dependence on a field, of the same class, example:

class ABC {
  const ABC(
    final ABC? previous,
  ) : id = ((previous != null)
            ? (1 + previous.id)
            : 0);

  final int id;
}

void main() { final a = ABC(null), b = ABC(a); }

CPU budget for the compiler

Please allow to turn this off, during compilation, because:

• A [released] software is run huge number of times, compared to the number of compilations
• Not every programmer would trade runtime perf, of a release build, for compilation-time

Since a few weeks, I was thinking of this limitation of dart, and today this arrived in the issue-tracker.

thanks

[lukehutch]

Just for completeness, I should mention that the GraalVM authors managed to get partial evaluation working for arbitrary languages. Which is a heroic effort! I'm not sure what lessons can be taken from that, but it's impressive work.

[Levi-Lesches]

Would macros help with this? You could generate your table in a macro:

@generateColorTable
external List<Color> allColors;

(it's been a while since I looked at the design docs, so that might not be the exact right syntax)

Then the table should be generated for you at compile time, using logic you define under generateColorTable.

[lukehutch]

It's not the generation of this table that I care about, it's the fact that what const is trying to achieve is much better achieved with partial evaluation (which is an extremely powerful language feature).

[Levi-Lesches]

Right but again, wouldn't macros be a more general solution for this more broader issue? Namely, executing some code at compile time instead of at runtime?

[lukehutch]

The point is that macros aren't even necessary if you have partial evaluation.

Since Dart can already figure out, transitively, what is const and what is not, based on only declarations, it is only a fairly small step to figure out what computed values are downstream of only const values, and then the compiler can opt to pre-compute those too. The resulting values become const after running these computations.

Macros of the form you cited disconnect the value declaration from the implementation. I don't think that's a step in the right direction.

[munificent]

Can you explain a little more concretely what you mean by "partial evaluation"?

[Reprevise]

From what I can gather, it's transforming declared const values into computed const values so the following would be possible, just running map at compile time instead of at runtime, though probably with a different syntax to be explicit about what's happening.

const numbers = <int>[1, 2, 3, 4, 5, 6, 7];
const halves = numbers.map((n) => n / 2);

Handy Wikipedia screenshot, of course:

It's also very possible that I explained this wrong but this is what I interpreted from the conversation. :)

[lukehutch]

@munificent Partial evaluation is one of the deepest results in all of programming language theory...

You trace the transitive closure of everything that depends upon variable inputs in the program, and everything that is left is const, or can be computed only from const values.

Then you specialize the program so that it becomes a function of only the variable inputs. Basically this takes each function in the program and "curries" it so that its only inputs are values that are derived from variable inputs.

Basically you are collapsing down any computation that will always produce the same result into a bunch of const values or lookup tables.

You can go further with this, and even for variable inputs, if you can determine the domain (range of values) of each variable input, and it's a finite set of values, then you can pre-compute the result for each of the inputs, and store the outputs as a lookup table.

The compiler can then have a knob that you can dial that the developer can turn to determine how much time is allowed for pre-computation during compilation, and how much space is allowed for storing the cached intermediate results. Obviously some programs will be much smaller after partial evaluation, but some may be bigger. Universally though, programs should run faster after partial evaluation.

Both tree-shaking and const in Dart are actually examples of partial evalutation, and if proper partial evaluation were in place, both of these features would come for free. Partial evaluation goes far beyond what these two things can do, however.

If you want to have your mind blown, learn about the Futamura projections:

https://en.wikipedia.org/wiki/Partial_evaluation

Basically if you take an interpreter, and fix the program input for a specific program that you want it to interpret, you end up compiling the program into an executable (you just compiled the program using an interpreter that was not designed to be a compiler!). If you partially evaluate (specialize) your partial evaluator, fixing the input to be the interpreter, then you turn the interpreter into a compiler. If you specialize your partial evaluator with itself as input, you produce a compiler that will compile any interpreter into an equivalent compiler.

Partial evaluation is a big part of GraalVM. It actually uses the first Futamura projection to turn an interpreter for any "guest language" into a compiler that can compile programs in that language into the "host language" (the language that is running the compiler). This allows close to perfect language interoperability, no matter the language:

https://www.graalvm.org/latest/graalvm-as-a-platform/language-implementation-framework/HostOptimization/

[lrhn]

Partial evaluation is basically Kleene's S-m-n theorem: For a program (function) taking m+n inputs and a given m inputs, there is a corresponding program taking n inputs which behaves as the original program would when given all m+n inputs.

Compilation is an example of that, an interpreter takes a program and one or more runtime inputs. A compiler is the specialization of the interpreter to it's program input.

If we can provide more inputs at compile time, we can possibly specialize the program more.

Partial evaluation is the goal of creating a fully specialized result, where as much of the program as possible has been evaluated at compile time.

The risk, as always, is that unrestricted compile time evaluation can take unbounded time and memory, and the specialized result can end up larger than the original program plus inputs, because the result is not a program, it's a runtime state that includes computed values. (Which may be another way to say that Kleene's S-m-n theorem might not apply directly to languages where values have identity and are mutable, or that has side effects, you can't necessarily create a program with the same behavior.)

Dart's current constant compilation restrictions ensure that the amount of created values is bounded by the original program size, and are computable in linear time. Also the values are simple to re-create from scratch at runtime, so we don't actually need to represent runtime values in the compiled result. That's the real reasons for why the restrictions are there.

[lukehutch]

@lrhn of course was able to describe this far more concisely than I was able to! +Thanks for pointing out the reasons for the current limitations.

I see so much potential for additional partial evaluation in Dart though. In addition to const, as I pointed out, tree-shaking is really just a limited form of partial evaluation. But even the Dart type system is an example of partial evaluation, and could be represented as such: the specializable part of the program is the set of all types that can be statically determined, and what is left (viz the program taking m inputs of the original m+n inputs) is the set of the dynamic types of the program which can only be evaluated at runtime.