Epic: Metaprogramming

[jfecher]

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

Core Tasks for Noir 1.0

Beta 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

Bugs for Noir 1.0

Beta 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. Closures cannot be inlined in the comptime interpreter #4922
   bug +1
4. Optimize the elaborator #5194
   enhancement +1

Nice-to-haves for Noir 1.0+

Beta 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. Make compiler minimally re-entrant #4592
   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?