Build in support for integer limits on Repeat-statements

[swernli]

Suggestion

Q#'s repeat-statement should have built-in support for integer limits. This would allow a developer to specify the maximum number of loops that will be executed without needing to use a mutable count variable. This upper limit could be very between different loops, and could be determined at runtime by inputs, classical computation, or even quantum results. Having an integer limit would assist in the transformation of repeat-statements into forms that are compatible with execution capabilities of current hardware. Even beyond current capabilities, having a convenient construct for limiting the number repeats is handy syntax to capture a pattern where such a limit is needed but the current loop number is not needed in the repeat body.

This suggestion lines up with the possibility mentioned in the "Target-Specific Restrictions" section of the Repeat-Statement specification page: "Execution on quantum hardware can potentially be supported in the future by imposing a maximum number of iterations."

Considerations

In the current repeat-statement syntax, supporting an integer limit is possible via a mutable variable. This can be done either by counting down:

mutable limit = 10;
repeat {
    DoWork(q0);
}
until (M(q0) == Zero or limit <= 1)
fixup {
    Reset(q0);
    set limit = limit - 1;
}

or by counting up:

let limit = 10;
mutable count = 0;
repeat {
    DoWork(q0);
}
until (M(q0) == Zero or count >= limit - 1)
fixup {
    Reset(q0);
    set count = count + 1;
}

Note the subtleties in constructing the limit part of the conditional: in order to ensure that the loop stops after the 10th run the user must remember that the condition is a success/termination condition and a continuation condition (making it different from both while-loop and for-loop integer conditions), and be careful to remember whether they are zero indexing their limit or one indexing (these examples choose one indexing so that limit is a clear value that corresponds to the number of loops performed, with the trade-off being the need to use limit <= 1 and count >= limit - 1 for the conditions respectively). The developer may also decide to move the update of the mutable variable into the body of the repeat block instead of the fixup block, which has the subtle distinction of affecting what the variable value will be after termination, especially if the repeat terminated due to a different clause of the condition and/or the mutable variable is used after the execution of the repeat-statement.

For cases where the current loop count is not needed and a simple limit would suffice, these examples could use new syntax that provides the limit as a parameter to the repeat keyword. This allows the developer to skip the decision points of defining a mutable variable, updating that variable, and correctly crafting the right terminating condition. This syntax could look like this:

repeat (10) {
    DoWork(q0);
}
until (M(q0) == Zero)
fixup {
    Reset(q0);
}

This would ensure that loop is executed at most 10 times, and is clear syntax without the overhead of either author or readers of the code needing to consider the increment or termination pattern chosen.

It's also worth considering allowing a repeat loop that does not have an until condition if a limit is specified. This would essentially be an anonymous form of a for loop:

repeat (10) {
    DoWork(q0);
};

One way to think of this capability is that is akin to using a break in a for-loop for a language that supports that. Using repeat (<Int>) establishes the fixed loop while the until (<Condition>) is the early termination condition. Thus, an alternative consideration could be a break keyword that would allow such an early termination of a for-loop, though that has been called out as not part of the original intent of the for-loop in Q# (see here), and could confuse the role of for-loops as the predictable length loop construct.

Context

As part of exploring this option, I have been working on a prototype compiler rewrite step that transforms a repeat-statements into a recursive callable. This recursion can be unlimited or incorporate a fixed limit. With the fixed limit, recursive versions of repeat-statements can be interpreted as a fixed depth nested conditional structure that has a better chance of successfully translating into existing hardware instructions.

Examples

See above in the Considerations section.

Affidavit (please fill out)

Please add ticks by placing a cross in the box:

• [x] I have searched both open and closed suggestions and proposals on this site and believe this is not a duplicate.
• [x] I believe that the spirit of this suggestion is aligned with the design principles and general vision for Q#.

Please tick all that apply:

• [x] This is not a breaking change to the Q# language design
• [x] I or my organization would be willing to help implement and/or test this

[swernli]

Here are some updates to the idea, based on ongoing conversation regarding limited loops...

• Should we use this as a springboard to simple infinite loop syntax? The idea of a repeat-statement without an until to quickly and directly capture the idea of an infinite loop is an interesting one, but given some of the other directions the design may go in, it might not fit anymore with this proposal and should probably be separated out and discussed on its own.

• Should we adopt something like -1 to mean no limit or infinite loop? After discussing this, we realized that having a magic number for special capabilities is bad, and if the integer limit is a parameter to a callable, now it needs to make its way into the documentation as well. Instead, we should definitively establish that the syntax takes a non-negative integer, that way it corresponds directly with the concept of the limit on the number of repetitions. This has some implications about the type system, see below for further discussion.

• Does this syntax require a new type that captures unsigned integers? This does seem to be the case, given our discussion of -1 above. If negative numbers are not valid for this new syntax, then this becomes a source of runtime error without also being able to use a type that expresses that restriction. To be able to provide the right compile/design time feedback, we need a way to express an unsigned integer, which should be captured in its own proposal and linked to this one.

• Should we tie this to the introduction of an Option type to capture unlimited repeat? Having something lik e an Option<Int> could better capture the intent of supplying a limit or leaving it to be without limit, but given that we don't have this in the language yet it might be best to figure out an approach that doesn't rely on it. It also doesn't solve the problem of a signed integer on its own (see above), so would need to be taken in conjunction with that. Alternatively, we can leave the idea of an unlimited repeat as its own syntax by clearly separating the limited repeat as a distinct statement (see below).

• Do we need a new keyword to more clearly identify the limited repeat? This was a big source of discussion, and the consensus afterwards seems to be yes. A new keyword clearly identifies the limit and clarifies some of the syntax. This could further provide a way for the new repeat to stand on its own without using the repeat keyword. One idea that was proposed was upto which can either be used with repeat:

  repeat upto (10) {
  DoWork();
  }
  until (CheckCondition());

  or perhaps on it's own:

  upto (10) {
  DoWork();
  }
  until (CheckCondition());

  thereby creating a new statement type.

[bamarsha]

• This does seem to be the case, given our discussion of -1 above. If negative numbers are not valid for this new syntax, then this becomes a source of runtime error without also being able to use a type that expresses that restriction. To be able to provide the right compile/design time feedback, we need a way to express an unsigned integer, which should be captured in its own proposal and linked to this one.

Note that arrays have the same problem, since the length of an array is a natural number. new T[n] will fail at runtime if n < 0, and currently the proposal in #48 keeps that behavior for the new [x, size = n] syntax. It might make sense to change that if we do want an unsigned type though.