Lint rule: `operation`s that don't manipulate quantum state can be `function`s instead

[minestarks]

trafficstars

We should add a rule to the linter that will emit a warning when an operation does not manipulate quantum state. The warning should suggest declaring the callable as a function instead.

Context:

In Q#, callables declared as operation can manipulate quantum state (allocate qubits, apply gates, call other operations etc) while callables declared as function must be pure functions and cannot manipulate state.

Currently, a callable such as the one below can be declared as an operation or function.

operation Add(a: Int, b: Int) : Int {
    return a + b;
}

function Add(a: Int, b: Int) : Int {
    return a + b;
}

Playground link

Since this is a pure function, function is a more appropriate designation for it.

Declaring the proper callable type not only helps prevent mistakes, it may also allow runtime capability analysis to run faster since the compiler can rely on the knowledge that functions don't manipulate quantum state.

---

CONTRIBUTORS PLEASE READ

Getting started

Welcome! Please take a look through our README to orient yourself in the repo and find instructions on how to build.

For this issue you'll want to have a working knowledge of Rust and compilers.

For documentation on how to add lints, see: https://github.com/microsoft/qsharp/blob/main/compiler/qsc_linter/src/lib.rs

For examples of existing lints, see:

https://github.com/microsoft/qsharp/blob/ed2a8fcab06acea8e2b8fcaf64f109bbd979f403/compiler/qsc_linter/src/lints/ast.rs#L10-L12

https://github.com/microsoft/qsharp/blob/ed2a8fcab06acea8e2b8fcaf64f109bbd979f403/compiler/qsc_linter/src/lints/hir.rs#L8

Testing

You can demonstrate that the lint works by running the playground locally (see the code example in the issue description).

Please add unit tests verifying the functionality you implemented.

Before you submit a pull request please run python ./build.py to ensure the project builds cleanly. See README for details.

Reviews

Once you have published your PR, the codeowners will automatically get tagged and we'll review shortly.

If you need clarification on an issue please tag @minestarks with your questions.

[Manvi-Agrawal]

@minestarks, what about functions that call operations? Is it in scope?

Eg: This is example from Old Katas where Oracle_Converter_Reference is a function.

operation ApplyMarkingOracleAsPhaseOracle_Reference (markingOracle : ((Qubit[], Qubit) => Unit is Adj + Ctl), qubits : Qubit[]) : Unit is Adj + Ctl {
        use minus = Qubit();
        within {
            X(minus);
            H(minus);
        } apply {
            markingOracle(qubits, minus);
        }
    }

   operation Oracle_Converter_Reference (markingOracle : ((Qubit[], Qubit) => Unit is Adj + Ctl)) : (Qubit[] => Unit is Adj + Ctl) {
        return ApplyMarkingOracleAsPhaseOracle_Reference(markingOracle, _);
    }

    function Oracle_Converter_Reference (markingOracle : ((Qubit[], Qubit) => Unit is Adj + Ctl)) : (Qubit[] => Unit is Adj + Ctl) {
        return ApplyMarkingOracleAsPhaseOracle_Reference(markingOracle, _);
    }

[minestarks]

@Manvi-Agrawal that got me scratching my head for a bit! But I figured it out.

The compiler should return an error for a function that calls an operation . So, that wouldn't really be in scope for this issue. To put it differently: an operation that calls another operation cannot be turned into a function, so a lint shouldn't be shown for it.

The code you shared is an example of partial application (https://github.com/microsoft/qsharp-language/blob/main/Specifications/Language/3_Expressions/Closures.md#partial-application). The function isn't calling the operation, it's "applying" one parameter and returning a new operation.

[Manvi-Agrawal]

Hi @minestarks , you mentioned in this issue that implementing this lint rule would pave the way for runtime capability analysis to run faster since the compiler can rely on the knowledge that functions don't manipulate quantum state. I am curious to know whether it requires an extra change or that logic is already implemented. If any additional changes are required, I would like to try those out. Could you please provide some pointers?