static enough metaprogramming

[mraleph]

Proposal text has moved to PR: #4374

[rrousselGit]

I wonder what the performance overhead would be compared to what you could achieve using code-generation.

Is it safe to assume that raw Dart code would still be faster ; due to:

• not having to lookup type information
• the compiler being able to perform the usual optimisations (like how comparing List<int> is faster than comparing List<Object>)

[stereotype441]

At first glance, this sounds like a really cool idea. I'm curious to play around with it more and try to understand its uses and limitations.

To get the feeling of expressive power, implementation complexity and costs I have thrown together a very rough prototype implementation which can be found [here][konst-prototype-branch].

I'm very interested in looking at this! Did you forget to paste in the link?

[lrhn]

(Working my way through the proposal, so I might not have all the details yet.)

The example:

void bar<@konst T>(@konst T v) { }

for (@konst final v in [1, '2', [3]]) {
  invoke(bar, [v], types: [typeOf(v)]);
}

doesn't vibe with the

enhanced constant evaluation at compile time if the underlying compiler supports it.

goal. If the compiler doesn't support konst-evaluation, it would have to be able implement invoke and typeOf as runtime functions. (But I see that you say that: Every compilation tool-chain must support the functionality, the option is between doing it at compile-time and using runtime reflection. And the only thing preventing this from being full-fledged reflection is that every tool-chain will require that @konst-annotated arguments are actually available at compile-time.)

The reason you need the invoke may be that the loop is using the wrong abstraction level function.
It's treated as if it's iterating over values, which is why it has a static type of Object, but since the loop is expanded and the elements of the list is inserted into the body as expressions, it is really looping over expressions, not values.
If the entries are treated as expressions, with no given type, then substituting them into separate unrollings of bar(v)
doesn't have to assume that the static type of v is Object, and then you can get inference for each invocation.

But then it won't be able to have the same semantics if executed at runtime if the compiler doesn't do konst.
If that's a requirement, then this proposal is very limited in what it can do (it probably cannot touch any mutable global state, and can't rely on object identity).

This is a two-level language, like Scheme's quote/unquote, but it's omitting the quote on the list elements and the unquote in the body of the konst loop. That makes it harder to reason about.

(The substitution into loops is also worrisome, take @konst var ctr = 0; for (@konst var i in [++ctr, ++ctr]) { print("${i} == ${i} < $ctr"); }. If the loop is actually unrolled by substituting the expression with a side-effect into the body more than once, then this behaves very differently than if run at runtime. A more viable subsititution would be to convert for (@konst var i in [expr1, ..., exprN]) { body[i]; } into

{
var i$0 = expr1;
var i$1 = expr2;
...
var i$N = exprN;
{
  body[i$0];
}
// ...
{
  body[i$N];
}

What if we had quote and unquote functions defined in dart:metaprogramming, which captures a value and its static type as an Expr<T> which has an R unquote<R>(R Function<X>(X) use); function to unpack itself.
Then you'd write this as:

void bar<@konst T>(@konst T v) { }

for (@konst final v in [quote(1), quote('2'), quote([3])]) {
  v.unquote(<T>(o) => bar<T>(o));
}

Still would't work the same if executed at runtime.

Would be:

@konst
class Expr<T> {
  final T value;
  Expr(@konst this.value);
  @konst
  R unquote<R>(R Function<X>(X value) use) => use(value);
}
Expr<T> quote<T>(T value) => Expr<T>(value);

(Or just call the class Quote.)

[lrhn]

I worry about the field-reflection because it doesn't say what a "field" is.

If it's any getter, then this is probably fine.

If it distinguishes instance variables from getters, then it's almost certainly not fine. That'd be breaking the abstraction of the class, and of its superclasses.

Which also means that if you do:

for (@konst final field in TypeInfo.of<T>().fields) 
      if (!field.isStatic) field.name: field.getFrom(value)

you'll probably also need a && field.name != 'hashCode' && field.name != 'runtimeType' guard.
Which sucks, but so does breaking abstraction.

(Can you see private fields? If you are in the same library?)

[aam]

I have thrown together a very rough prototype implementation which can be found [here][konst-prototype-branch].

Can you fix the link?

FWIW: the review would be more complete if you also consider Julia's metaprogramming as a source of ideas.

[TekExplorer]

Wouldn't it be simpler to simply expand access to const, and (less simply) just give access to reflection there and only there?
like:

// figure out how to mark this as constant in all ways.
external T constInvoke<const F extends Function>(F fn, posParams, namedParams, {List<Type> typeArguments}) const;

const Object? toJson<T>(T object) {...}
// could be a modifier like async
Object? toJson<T>(T object) const {
  if ((T).annotations.hasCustomToJson) {
    // ...
  }
  return switch (object) {
    null || String() || num() || bool() => object,
    _ => toJsonMap(object),
  };
}
Map<String, Object?> toJsonMap<T>(T object) const {
  return <String, Object?>{
    // probably break this out more to check for annotations and such.
    for (final field in (T).fields) field.name: constInvoke(toJson, [field.of(object)], typeArguments: [field.type])
  };
}

and possibly have const? for potentially constant vs must be constant.

after all, there are often classes (read: annotations) that arent ever supposed to not be const.

[schultek]

But that does not solve the problem. Type arguments and normal values are separated in Dart - which means you can't invoke a generic function with the given Type value as type argument, even if Type value is a compile time constant.

Wouldn't it be an option to allow exactly that, instead of adding the "wonky" invoke function?

So

void bar<@konst T>(@konst T v) { }

for (@konst final v in [1, '2', [3]]) {
  final t = typeOf(v);
  bar<t>(v);
}

would be allowed since the generic parameter is a compile time constant?

void bar<@konst T>(@konst T v) { }

for (@konst final v in [1, '2', [3]]) {
  final t = typeOf(v);
  bar<t>(v);
}

While reading this program, I cannot easily see that the for block executes in comptime. Even if the compiler can somehow figure this out (not clear how), for the reader it looks quite baffling.
It should be

comptime for (final v in [1, '2', [3]]) {
  final t = typeOf(v);
  bar<t>(v);
}
// more general form:
comptime { 
  for (final v in [1, '2', [3]]) {
    final t = typeOf(v);
    bar<t>(v);
  }
  // other stuff executed in comptime
  //...
}

[julemand101]

To get the feeling of expressive power, implementation complexity and costs I have thrown together a very rough prototype implementation which can be found [here][konst-prototype-branch].

I'm very interested in looking at this! Did you forget to paste in the link?

I think the link should have been: https://github.com/mraleph/sdk/tree/static_enough_reflection. At least that branch matches this proposal and have a recent commit related to this topic: mraleph/sdk@d594629

[mraleph]

RE: @rrousselGit

I wonder what the performance overhead would be compared to what you could achieve using code-generation.

The performance overhead at which stage and at which mode? If we are talking about runtime performance for the code compiled with toolchain which supports @konst then hard written (or generated code) and @konst should have very similar performance characteristics. Though the comparison is very nuanced here:

1. On one side, there are no type information lookups or anything like that in the final code. If you use @konst type arguments the final code will be fully specialized for specific types. This is the level of optimization which is not easily achievable in Dart today (sans manual function cloning). In some occasions it can be faster - because it replaces type parameters with concrete types and removes const associated with reified type parameters.

2. On another side, you need to be about levels of abstraction. You might be encouraged to create helpers (e.g. see my example fromJson implementation which defines listFromJson helper). In code written by hand (or generated via a code generator) you will create the same helper but it will most likely be generating a code snippet to be used inline inside bigger chunk of code. This means generated code would have less levels of abstractions for compiler to chew through. It is not unsurmountable - but it is a difference to be aware off.

   // @konst approach
   FieldType _valueFromJson<@konst FieldType>(Object? value) {
     // ...
     if (fieldType.instantiationOf<List>() case final instantiation?) {
       final elementType = instantiation.typeArguments.first.type;
       return invoke<FieldType>(
             listFromJson,
             [value as List<Object?>],
             typeArguments: [elementType],
           );
     }
     // ...
   }
   
   List<E> _listFromJson<@konst E>(List<Object?> list) {
     return <E>[for (var v in list) _valueFromJson<E>(v)];
   }
   
   // Instantiating _valueFromJson<List<A>> yields:
   
   List<A> _valueFromJson$ListA(Object? value) {
     return _listFromJson$A(value as List<Object?>);
   }
   
   A _listFromJson$A(List<Object?> value) {
     return <E>[for (var v in list) _valueFromJson$A(v)];
   }
   
   // Levels of abstractions are still present.

   // Codegeneration approach (pseudocode)
   String genValueFromJson(String varName, Info info) {
     // ...
     if (info.isList) {
       return genListFromJson(varName, info.elementType);
     }
     // ...
   }
   
   String genListFromJson(String varName, Info info) {
     return '<${info.typeName}>[for (var v in list) ${genValueFromJson('v', info)}]';
   }
   
   // Running code generator you will end up with a snippet:
   // (abstractions are kinda automatically erased)
   
   <A>[for (var v in list) A.fromJson(v)]

I'm very interested in looking at this! Did you forget to paste in the link?

@stereotype441 @aam I have fixed the link now. It was included but I marked it incorrectly in the references section. Don't look to much at the prototype though - it is very hodgepodge. I am implemented just enough to get my samples running.

RE: @lrhn

since the loop is expanded and the elements of the list is inserted into the body as expressions, it is really looping over expressions, not values.

That's not what the proposal proposes. Please see above (emphasis added):

When @konst is applied to loop iteration variables it instructs the compiler to expand the loop at compile time by first computing the sequence of values for that iteration variable, then cloning the body for each value in order and substituting iteration variable with the corresponding constant.

So no expression business - you substitute variable with a constant value. This guarantees the following property: if @konst evaluation succeeds, then executing the same code using reflection will have the exact same behavior.

I do have an interest in AST based metaprogramming, but this proposal is explicitly not about it, because you can't avoid expanding AST templates.

Regarding the second comment about fields vs getters.

1. I don't see any reason to pretend that fields and getters are the same when accessing this information reflectively. They quack the same - but they are not the same in the text of the program. I don't agree that they should be seen in the same way at this level of introspection. Neither dart:mirrors nor analyzer model tries to pretend that they are the same. Yes, this might change behavior of the function when user changes field to getter or other way around. And yes, I think this is a correct capability to have - reflection gives you access to the program structure at a more precise level.
2. Regarding inherited fields: I think¹ you probably need explicit supertype chain walk. TypeInfo.fields only gives you fields of this exact type, not those of its superclass.
3. Re-privacy: we can choose to both restrict and allow access to private fields. e.g. I think it is okay to say that field.getFrom(o) errors if current library does not have access to the field.

RE: @TekExplorer

Wouldn't it be simpler to simply expand access to const,

I think you are missing one crucial piece: fromJson and toJson are not constant functions themselves and they can't be computed in compile time. Usually you give them objects that are only know in runtime. This means you can't just say toJson() const and call it a day. toJson which can only be called on a constant object is not very useful.

These functions are partially² constant - if some arguments (e.g. specifically T) are know in compile time then you can produce a version of toJson and fromJson specialized for that T.

That being said there is actually a way to make this model work, but it is not going to be pretty. You need to manually split constant and non-constant part of the toJson and fromJson computations. You can for example do something like:

typedef JsonMap = Map<String, Object?>;

/// Make serializer for T - this is constant part.
JsonMap Function(T) toJsonImpl<T>() const {
  final write = (JsonMap map, T o) {};
  for (final field in T.fields) {
    final previous = write;      
    write = (JsonMap map, T o) {
      previous(map, o);
      map[field.name] = field.getFrom(o);
    };
  }

  return (o) {
    final m = <String, Object?>{};
    writer(m, o);
    return m;
  };
}

class A {
  JsonMap toJson() => (const toJsonImpl<A>())(this);
}

But this has a bunch of draw-backs:

• It requires developer to expect compiler to perform a bunch of optimizations
  to arrive to the specialized code e.g. the chain of write callbacks needs to
  be fully inlined and compiler needs to fold field.name and field.getFrom
  accesses. If optimizations don't happen you end up with code which performs bad
  and potentially has bad code size (because full specialization is required to
  erase reflective metadata). That's why expectations around compile time expansion
  and specialization are encoded directly into semantics of @konst. If that's
  the case developer can reason about the code they get in the end (and they also
  get an error if compiler can't fully specialize the code).

• Significant mental gymnatics is required to arrive to this. Splitting the code
  into constant and non-constant part is inconvenient: consider toJson(this) vs
  (const toJsonImpl<A>())(this). To make matters worse correctly structuring
  your const part is non-trivial, e.g. you might be tempted to write

  JsonMap Function(T) toJsonImpl<T>() const {
    final fields = T.fields;
    return (o) => {
        for (var field in fields)
          field.name: field.getFrom(o),
      };
  }

  But this expects even more from the compiler: it now needs to unroll the
  loop to specialize the code and eliminate reflective metadata. That's why
  @konst has special provisions for loops for example.

RE: @schultek

I should rewrite the section about invoke a bit. It is not just for passing
type parameters around. You also need to be able to express invoking functions
with constructed argument lists. Consider: fromJson case which needs to
invoke constructor with named parameters.

I think invoke can be avoided only if we supported some form of spread
(...) into function arguments (including spread into type parameters).

Another reason to add invoke is that I would like to avoid any changes to
the Dart language itself. I think it makes this much simpler feature to ship.

Footnotes

1. Reflection APIs (and JSON example) does not try to be complete or precise - they serve to illustrate the approach. ↩

2. partially constant is not a real term, I just want to draw a parallel with partial evaluation ↩

[lrhn]

Ack, I did misunderstand how konst-loops work.

They are only over constant values (or at least "konstant values"), in which case duplicating the value is not an issue.

I don't see any reason to pretend that fields and getters are the same when accessing this information reflectively.

It's definitely possible to allow reflection only on instance variables, and not getters, but it means the code using reflection may change behavior, or even break, if someone changes a variable to a getter or vice versa, or adds implementation details like an int? _hashcodeCache;.

I'll absolutely insist that the breaking change policy says that reflection is not supported by any platform class unless it's explicitly stated as being supported. If someone complains that their code breaks in Dart 3.9.0 because I changed late final int foo = _compute(); to final int? _foo; int get foo => _foo ??= _compute();, they will not be allowed to block the change.
(Which likely also means lints and opt-in markers to ensure that no internal code depends on reflection of types that are not guaranteed to support it. Effectively it must be an opt-in feature. Might as well make it one from the start, so a class must be annotated as @reflectable to be allowed to be reflected.)

Also means that you can't reflect anything if all you have is an abstract interface type. It's all getters.
You can only reflect a concrete class type.

Accessing inherited fields explicitly through a TypeInfo.superClass makes sense. You'd want such a property too, then. Or rather, the declared superclass (the one in the extends clause), not the actual super-class. I expect that mixin applications counts as part of the class declaration, even if they are technically superclasses.
(Which is also not guaranteed to be stable over time, the superclass of an object can change without its API changing.)

Re-privacy: we can choose to both restrict and allow access to private fields. e.g. I think it is okay to say that field.getFrom(o) errors if current library does not have access to the field.

I don't believe "current library" is a viable or useful distinction.
It makes it impossible to rely on helper functions to do the actual invocation if those helper functions are in a different library.
The getFrom function is a konst function, so you can't tear it off, but you can pass the field object to another konst function and invoke it in there, perhaps a helper function in another library.

Map<String, Object?> getAllFields<@konst T>(@konst List<FieldInfo<T, Object?>> fields, T receiver) => 
    {for (@konst f in fields) f.name: f.getFrom(receiver)};

If there are some fields you can only access from "the same library", this helper function won't work.

If the implementation performs reflection at runtime, it would implement getFrom as a function which just accesses the actual getter on the argument object. That function can't see where it's called from.
(And don't say "look on the stack"! 😉)

I would at least make it possible to not get private members, and having to opt in to it. (But if a class needs to opt in to being reflectable to begin with, they could choose which kind of reflectable to allow, and maybe even for which individual fields. As long as the default @reflectable is a good default, like all non-private instance variables, you won't need to write more in most cases.)

So, the crux is that anything marked with @konst (when supported) is computed/expanded away at compile-time so that there is nothing @konst left. If a function has a parameter marked @konst (including this), it must be invoked at compile-time, and that argument (or all arguments?) is konst-evaluated too, and the body is effectively inlined at the call point. The function cannot be invoked at runtime, because it doesn't exist at runtime.
A konst for/in is over a konst list, and is unrolled.
It'll be a compile-time error if something is used in a way that would prevent konst-evaluation.
(And konst evaluation can't access any mutable global state.)

It's not a languge feature because the same code can be evaluated at runtime. It just requires some reflective functionality from the runtime system, but which can still only be invoked with values that could be known at compile-time.

Still don't understand why you need to use weird @K-words in

Map<String, Object?> getAllFields<@konst T>(@konst List<FieldInfo<T, Object?>> fields, T receiver) => 
    {for (@konst f in fields) f.name: f.getFrom(receiver)};

where you could write quite legibly

comptime Map<String, Object?> getAllFields<T>(List<FieldInfo<T, Object?>> fields, T receiver) => 
    {for (f in fields) f.name: f.getFrom(receiver)};

Also: in zig, the variable declared as const can be set in comptime, but it's still available in runtime. The meaning of @konst, on the other hand, is unclear: if you declare @konst x, will it be available in runtime?

The concept of comptime was formalized in zig after years of bikeshedding. If you try to borrow just some parts of it, you may eventually realize why you needed other parts, too 😄