Epic: Metaprogramming MVP

[jfecher]

Proposal: https://hackmd.io/Tkzo_ryvTsWMPESmWHPiZw?view

Core Tasks for Noir 1.0

Preview Give feedback

1. Add quote expressions for metaprogramming #4586
   enhancement +1
2. Add compile-time evaluator for metaprogramming #4587
   enhancement +1
3. Add comptime modifier for variables/functions which only exist at compile-time #4588
   enhancement +1
4. Make the compiler re-entrant #4589
   enhancement +1
5. Implement unquoting of code values #4590
   enhancement +1
6. Allow splicing of Code values into other Code values #4591
   enhancement +1
7. Add Hir -> Ast conversion #4796
   enhancement +1
8. comptime globals #4916
   enhancement +1
9. Mutable comptime globals #4917
   enhancement +1
10. Call generic functions in a comptime context #4924
    enhancement +1
11. Handle trait dispatch in the comptime interpreter #4925
    enhancement +1
12. Interleave compiler passes #4953
    enhancement +1
    
13. Create Functor Ast to control interleaving #4954
    enhancement +1
    
14. Create an Elaborator #5146
    enhancement +1
    
15. Add flag to print out program after comptime expressions have been evaluated #5168
    enhancement +1
    
16. Separate functions from comptime functions in the type system #5201
    enhancement +1
17. Run comptime code when a type definition is annotated with a comptime function #5255
    enhancement +1
    
18. Add query functions on TypeDefinition #5285
    enhancement +1
19. Add the ability to quote token streams #5284
    enhancement +1
20. Allow extra arguments on attribute functions #5473
    enhancement +1
21. Support variable argument count for attributes #5476
    enhancement +1
22. Apply attributes to a trait #5477
    enhancement +1
23. Add TraitConstraint as a comptime type #5480
    enhancement +1
24. Add Quoted::as_trait_constraint method #5481
    enhancement +1

Bugs for Noir 1.0

Preview Give feedback

1. Calling closures in the comptime interpreter is incorrect #4879
   bug +1
2. Hir -> Ast pass losses full names of variables #4915
   bug +1
3. Optimize the elaborator #5194
   enhancement +1
4. Non-comptime local functions silently fail in a comptime context #5333
   bug +1
5. ICE when using a comptime let variable in runtime code #5388
   bug +1
   
6. Add handling of format strings to the comptime interpreter #5482
   enhancement +1
7. Cannot run macros within comptime code #5575
   bug +1
   

Nice-to-haves for Noir 1.0+

Preview Give feedback

1. Add a derive attribute with support for (de)serialize macros on existing complex types #3379
   0 of 1
   aztec.nr enhancement +2
2. Closures cannot be inlined in the comptime interpreter #4922
   bug +1
3. Make compiler minimally re-entrant #4592
   enhancement +1
4. Add unquote method to stdlib #5478
   enhancement +1
5. Add a compile-time hashmap type #5479
   enhancement +1

[jfecher]

Current goal is to get a vertical slice of metaprogramming working to support deriving a trait impl of a simple type on a simple trait like Default:

comptime fn derive_default(typ: TypeDefinition) -> Quoted {
    let generics: [Quoted] = typ.generics();
    assert(generics.is_empty(), "derive_default: Deriving Default on generic types is currently unimplemented");

    let type_name: Type = typ.as_type();
    let fields: [(Quoted, Type)] = typ.fields();
    
    let fields: Quoted = fields.map(|(name, _)| quote { $name : Default::default(), })
        .join();

    quote {
        impl Default for $type_name {
            fn default() -> Self {
                Self { $fields }
            }
        }
    }
}

#[derive_default]
struct Foo {
    x: Field
}

// Expected output:
//
// impl Default for Foo {
//     fn default(this: Self) -> Self {
//         Foo {
//             x: Default::default(),
//         }
//     }
// }

Required unimplemented features:

• Query functions on TypeDefinition: generics, as_type, and fields
• Quoted type for quoted, unparsed raw token streams. I think this is necessary to quote code fragments like quote { $name : Default::default(), } which is only valid in the context of struct initialization. I've chosen this name to avoid confusion with crypto tokens that Tokens or TokenStream may cause.
  • Additionally, to support this and make unquoting easier into arbitrary locations of quoted values, I'd like to move from an AST representation of quoted values to a token stream. This will ensure we can combine values like quote { $name : Default::default(), } where $name is spliced in despite us not knowing what grammar rule it should be part of (is it an identifier? an expression?).
  • Quoted token streams will be the new default type of quoted values with alternate types like quote Type { ... } or quote TopLevelItem { ... } only being used to force a quoted value into a particular shape so that specific methods can be called on it. TypeDefinition is the only type with methods on it above but we can imagine similar methods on a Type value which would be meaningless on unparsed Quoted values.
  • Notably, quoting the impl as a token stream avoids us needing to rework the parser to make our top level statement parser recursive since at parse time we'd only be parsing a token stream here.
  • The token stream ends when the matching } is found.
  • We avoid actually parsing Quoted values until they're expanded into a macro's call site: either a top level statement or an expression. When this happens, we parse the token stream and issue an error if we cannot parse into a top level statement or an expression.
• Some helper functions like join to join a slice of quoted values into one:

fn join(slice: [Quoted]) -> Quoted {
    let mut ret = quote {};
    for element in slice {
        // Since quoted values are token streams, we do not need (or want) a `;` separator.
        ret = quote { $ret $element };
    }
    ret
}

• Finally, it is optional but would be very useful to get generic functions like map working in the interpreter. The work around for this is writing a monomorphic version of map for Quoted values.

Edit: We used to have a Code type for quoted code. Maybe we should use that name over Quoted?

[jfecher]

Next goal is getting the full derive macro working from the Comptime Grimoire:

#[derive(Default, Eq, Cmp)]
struct MyStruct { my_field: u32 }


type DeriveFunction = fn(StructDefinition) -> Quoted

comptime mut global HANDLERS: HashMap<TraitConstraint, DeriveFunction> = HashMap::new();

comptime fn derive(s: StructDefinition, traits: [Quoted]) -> Quoted {
    let mut result = quote {};
    
    for trait_to_derive in traits {
        let handler = HANDLERS.get(trait_to_derive);
        assert(handler.is_some(), f"No derive function registered for `{trait_to_derive}`");
        
        let trait_impl = handler.unwrap()(s);
        result = quote { $result $trait_impl };
    }
    
    result
}

comptime fn derive_via(t: TraitDefinition, f: Quoted) {
    HANDLERS.insert(t.as_constraint(), unquote!(f));
}

#[derive_via(derive_do_nothing)]
trait DoNothing {
    fn do_nothing(self);
}

comptime fn derive_do_nothing(s: StructDefinition) -> Quoted {
    let typ = s.as_type();
    let generics = s.generics().join(quote {,});
    quote {
        impl<$generics> DoNothing for $typ {
            fn do_nothing(self) {
                // Traits can't tell us what to do
                println("something");
            }
        }
    }
}

Features we still need to do this:

• Add extra arguments to annotations
• Variable argument count for annotations
• Apply annotations to a trait & TraitDefinition type
• unquote method in stdlib. It can be simple: fn unquote(q: Quoted) -> Quoted { q } since applying the ! on a macro automatically unquotes anyway.
• A usable compile-time HashMap type. The existing constrained one is slow (but maybe usable enough?).
• TraitConstraint type which implements Hash and Eq.
• Quoted::as_trait_constraint
• Format strings

[jfecher]

This issue is subject to feature creep particularly since there's no set amount to comptime functions or functionality we should support. As a result, after my above comment on features we need to complete a general derive macro is complete I'm going to consider this issue as a whole completed as well.

Any remaining issues we can keep as separate bugs / feature requests.

[jfecher]

#5667 has been merged so I'm closing this issue now.

With PR, all issues linked here except #5201 have been implemented.