Allow higher order functions to be called with closures, and to return closures

[alexvitkov]

Problem

Setting this up to track progress on closures.

The immediate goal is to:

• Allow calling higher order functions with closures as arguments
• Allow functions to return closures

This will be done by making higher-order functions implicitly generic over their function arguments. The bulk of the work will be done during monomorphization -- ideally I'd like to do as much as possible during type-checking (and spent quite a bit of time trying), but as things stand right now doing it during mono requires fewer major changes.

I've split the work into a multiple PR's that I'll be submitting over the course of this week/next week.

There are a few cases we may wish to support that will need further consideration:

• Reassigning a mutable function variable to a closure with different environment:
• Arrays of functions with elements of closure types

Happy Case

Closures work in most places where regular functions and lambdas do

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[jfecher]

This will be done by making higher-order functions implicitly generic over their function arguments.

This sounds like potentially quite a bit of work. Especially with the goal of extending this to work while reassigning functions to mutable variables and enabling arrays of heterogenous closures as well. Wouldn't it be easier to stick closer to rust's approach first and keep raw functions and closures incompatible with each other? We could add a temporary syntax for closure types just so they can be used: fn[Env](Param1, ..., ParamN) -> Ret which does not unify with fn(Param1, ..., ParamN) -> Ret (unless Env ~ ()). That way when traits are added we can add the Fn trait to abstract over both.

Making every user-defined type and function implicitly generic over any closure types could work but seems like a larger change initially. We don't need to go with the above approach but it's another option to consider since you mentioned spending quite a bit of time trying the implicit generic approach.

[alexvitkov]

To be honest I haven't spent much time thinking about this Fn trait approach, since I was under the impression that higher order functions have to be callable with closures -- with the trait approach they'd all need to be rewritten to work for all Fn implementors.

I've got the implicit generic approach in a working state for both calling functions with closures and functions returning closures, although it's uglier than I would like as it requires overridding a bunch of types during monomorphization (for adding environments to function types everywhere they're used), which would be avoided with Fn traits.

I could submit a PR, but if the long/mid-term goal is to have Fn traits, it's probably too massive of a change for something temporary. For the time being I'll take a look at how far along generic traits are, and see if I can easily whip up a Fn on top of what the guys have going

[alexvitkov]

@jfecher I've sent a PR for the implicit generic approach https://github.com/noir-lang/noir/pull/2357

Even if later on we decide to go with Fn traits, it basically requires 100% of Rust traits to work (generic traits + where clause + type declarations in the trait) and we're not quite there yet.

I think it's worth it to have working closures in the meantime, since without being able to pass them to a function they're all but useless. Once we have solid traits, implementing Rust's Fn should be pretty easy and we can get rid of this, if we decide to.

This PR covers only calling functions with closure args, after that a few more changes will be required to handle functions returning closures, I've kept them out of this PR to keep it a bit more readable