Noir Closures Implementation Progress

[alexvitkov]

I'm opening this as central place to track progress on closures and related features as well as to discuss them.

I'm looking for input on the two big points at the bottom (arrays of closures & handling of incompatible closure types), as there are a few question marks that we should get sorted out.

Basic

• Rewrite closures to regular function accepting environment structs - feat: Initial work on rewriting closures to regular functions with hi… #1959

• Closures can be used as return values. - feat: add syntax for specifying function type environments #2357

• Support mutable captures.

• Handle returning closures that use internal mutable variables, e.g:

fn make_counter() -> fn() -> Field {
    let x = &mut 0;
    || {
         *x = *x + 1;
         *x
    }
}

I have implemented this locally, but in some cases (including the one above) it generates code that triggers this bug: #2316

• stdlib - The signatures of higher-order functions in the stdlib will need to be changed to work with closures. We can do a lot of that with the environment capture syntax we added fn[env](args) -> ret, or we can wait until we have Fn traits.

• Introduce traits for callable objects such as closures (i.e. Fn).
  Blocked on missing traits features

Arrays of Incompatible Closure Closures

We could transparently handle arrays of closures with different environments by rewriting them to tuples. Iterating over them can be implemented by unrolling the loop during monomorphization. One problem with this idea is calling a function at an index not known at compile time, we may have to introduce hidden branching to handle it.

• Support arrays of closures by treating them as tuples.

• Unroll loops over closure arrays in the monomorphization pass in order to be able to instantiate the callee for the correct environment types.

Handling of Incompatible Closure Types

• Settle the language design question regarding expressions involving incompatible closure types. This problem arises in two situations:
  • if/match statements where the different branches return closures with different environment types.
  • functions returning closures where different exit paths may return closures with different environment types.

The current implementation treats these as compile-time errors, but this may be surprising for many users. As a minimum, we must document this limitation in the Noir manual.

Alternatively, we can rewrite such expressions to hidden enum types than can capture all alternative closure environment types. Later, when the closure is used, Noir will emit hidden branching code to handle every possible case.

This functionality will be complex to implement as the hidden branching must also be applied at call-sites that accept closures as parameters. In the presence of multiple closure parameters, we’ll need nested branching. Performing such transformations behind the scenes may be highly controversial because it can lead to an explosion in the number of required constraints for otherwise simple and innocently looking programs, so perhaps the users will benefit from doing the harder work of rewriting their closure-based code to avoid the use of incompatible closure types.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[jfecher]

  fn make_counter() -> fn() -> Field {
    let mut x = 0;
    || {
         x = x + 1;
         x
    }
}

I think this could should produce an error that x was captured by copy and not by reference, so it is immutable. If we wanted to capture a mutable variable we'd need to do:

fn make_counter() -> fn() -> Field {
    let x = &mut 0;
    || {
         x = x + 1;
         x
    }
}

stdlib - The signatures of higher-order functions in the stdlib will need to be changed to work with closures. We can do a lot of that with the environment capture syntax we added fnenv -> ret, or we can wait until we have Fn traits.

I'm all for doing this sooner rather than later. It's a small change so let's do this after #2383

As for both Arrays of Incompatible Closure Closures and Handling of Incompatible Closure Types, I'd say these are unnecessary for your work on implementing closures. However, these could be useful in the long term. I just don't see them as being implemented soon since it entails a lot of implicit generic managing and corner cases.

[Savio-Sou]

Is the work ongoing? Or should we break the remaining tasks into standalone Issues?

[jfecher]

@Savio-Sou we can mark this as complete with

Introduce traits for callable objects such as closures (i.e. Fn).
Blocked on missing traits features

Being the only remaining feature to break out into a separate issue. I'm not exactly sure we need it though considering we have syntax for closure types already: fn[Env](Params) -> Ret.