Add anonymous functions to Q#

[wsgac]

It is frequently convenient to express functional concepts using one-off functions or operations. For simple cases, such as an existing operation with certain arguments fixed, partial operation with _ is sufficient. However, sometimes one wishes to express more complex computation, hence the need for anonymous functions (lambdas).

To keep the overhead to a minimum, it should probably follow the existing C# syntax for lambdas, i.e. (arguments) => (body). So, an example use could be something like: q => CNOT(qs[0], q).

[bettinaheim]

Yes, that's definitively on our roadmap. There are a couple of immediate things we need to prioritize, but this is by far the most requested language feature currently. Thanks for filing it!
Would you be interested in contributing to it's specification and/or implementation?

[wsgac]

Interested? Absolutely :)! Though I will sure need some guidance first. I've noticed that the Q# compiler is written in F# - I should be able to handle that. But I'd appreciate any hints about where to start.

[bettinaheim]

Awesome!
This is a larger task that breaks down into a couple of main pieces:

• specification
• parsing support
• verification support
• syntax tree simplification (such that the runtime does not need to provide support for lambdas)

For language features we will want a proper spec before they are officially included in a release (i.e. merged back to master). We have a pretty good idea on how the feature should look like, but haven't gotten around to writing down the corresponding proposal. I'm happy to work with you to produce that, or I am also happy to take care of that if you prefer. To get an idea of what questions we consider for language features I'll post an empty outline/template below.
My apologies that I haven't gotten around to setting up a public language design repo that makes our process transparent.

If you would like to focus on contributing to the implementation instead I suggest I walk you through it as we go. A good place to get started is the parser. @wsgac Does that sound like a good start or would you like to be involved in formulating the proposal?

[bettinaheim]

And here is roughly the outline that we follow for new language features:

Proposal

TODO:
Insert a short outline for what the proposal is.

Justification

TODO:
Explain why this modification to the Q# language is needed or desireable.
Explain both the benefit of the proposed modification as well as briefly summarize the benefits of the chosen mechanism opposed to other ways of achieving a similar functionality.

Description

TODO:
Describe the proposal and how it ties in with other aspects of the Q# language in more detail.
Provide general information about the relevant mechanisms and their role in Q#, and how the proposal relates to them.

Current Status

TODO:
Describe all aspects of the current version of Q# that will be impacted by the proposed modification.
Describe in detail the current behavior or limitations that make the proposed change necessary.
Describe how the targeted functionality can be achieved with the current version of Q#.
Refer to the examples given below to illustrate your descriptions.

Examples

Example 1:
TODO: insert title and caption

// TODO: 
// Insert code example that illustrates what is described above.
// Comment your code to further elaborate and clarify the example.

TODO:
Add more examples following the structure above.

Proposed Modification

TODO:
Describe how the proposed modification changes the behavior and/or syntax described in Current Status.
Describe in detail how the proposed modification is supposed to behave how it is supposed to be used.
Describe in detail any impact on existing code and how to interpret all new language structures.
Refer to the code examples below to illustrate your descriptions.

Examples

Example 1:
TODO: insert title and caption

// TODO: 
// Insert code example that illustrates what is described above.
// Comment your code to further elaborate and clarify the example.

TODO:
Add more examples following the structure above.

Implementation

TODO:
Describe how the made proposal could be implemented and why it should be implemented in this way.
Be specific regarding the efficiency, and potential caveats of such an implementation.
Based on that description a user should be able to determine when to use or not to use the proposed modification and how.

Timeline

TODO:
List any dependencies that the proposed implementation relies on.
Estimate the resources required to accomplish each step of the proposed implementation.

Further Considerations

TODO:
Provide any context and background information that is needed to discuss the concepts in detail that are related to or impacted by your proposal.

Related Mechanisms

TODO:
Provide detailed information about the mechanisms and concepts that are relevant for or related to your proposal,
as well as their role, realization and purpose within Q#.

Impact on Existing Mechanisms

TODO:
Describe in detail the impact of your proposal on existing mechanisms and concepts within Q#.

Anticipated Interactions with Future Modifications

TODO:
Describe how the proposed modification ties in with possible future developments of Q#.
Describe what developments it can facilitate and/or what functionalities depend on the proposed modification.

Alternatives

TODO:
Explain alternative mechanisms that would serve a similar purpose as the proposed modification.
For each one, discuss what the implications are for the future development of Q#.

Comparison to Alternatives

TODO:
Compare your proposal to the possible alternatives and compare the advantages and disadvantages of each approach.
Compare in particular their impact on the future development of Q#.

Raised Concerns

Any concerns about the proposed modification will be listed here and can be addressed in the Response section below.

Response

[anfelor]

I could imagine working on this. Would it be sensible to just transform an anonymous function

operation SomeOp() {
  let z = ..;
  ..
  ..  (x => f(x) + z) ..
}

into

function SomeOp_anon1(z, x) {
  return f(x) + z;
}
operation SomeOp() {
  let z = ..;
  ..
  ..  SomeOp_anon1 ..
}

where z is a placeholder for some number of variables (the types of which I could find in a context)?

On a related note, I've been unable to find a formal language spec for Q#. Is it based on some Hindley-Milner style type system or something c#-like hand-rolled?

[bettinaheim]

@anfelor
You mentioned "I could imagine working on this." Cool!
We've been talking about a reasonable first version for this kind of feature, though we haven't had the time yet to fully write it all down. I believe it would be reasonable to support this by adding the corresponding additions to the SyntaxTree data structures, as well as a compilation step to do the lifting both for lambdas and partial applications. We have recently added some infrastructure around that, though there is still some more work to do there. @anfelor Let me know if you are still interested in contributing, and we can figure out how to best coordinate this feature.

[anfelor]

@bettinaheim Unfortunately, the new semester started in Germany this week and so I might not have a lot of time anymore. Still, I could try to make some progress as time allows.

[bettinaheim]

@anfelor @wsgac
I am happy to say that we now have a repository for the Q# language design. This feature is captured by this issue on the language repo.