Type parameterizations

Q# supports type-parameterized operations and functions. The Q# standard libraries make heavy use of type-parametrized callables to provide a host of useful abstractions, including functions like Mapped and Fold that are familiar from functional languages.

To motivate the concept of type parameterizations, consider the example of the function Mapped, which applies a given function to each value in an array and returns a new array with the computed values. This functionality can be perfectly described without specifying the item types of the input and output arrays. Since the exact types do not change the implementation of the function Mapped, it makes sense that it should be possible to define this implementation for arbitrary item types; we want to define a factory or template that, given the concrete types for the items in the input and output array, returns the corresponding function implementation. This notion is formalized in the form of type parameters.

Concretization

Any operation or function declaration may specify one or more type parameters that can be used as the types, or part of the types, of the callable's input or output, or both. The exceptions are entry points, which must be concrete and cannot be type-parametrized. Type parameter names start with a tick (') and may appear multiple times in the input and output types. All arguments that correspond to the same type parameter in the callable signature must be of the same type.

A type-parametrized callable needs to be concretized, that is, it must be provided with the necessary type arguments before it can be assigned or passed as argument, such that all type parameters can be replaced with concrete types. A type is considered to be concrete if it is one of the built-in types, a struct type, or if it is concrete within the current scope. The following example illustrates what it means for a type to be concrete within the current scope, and is explained in more detail below:

    function Mapped<'T1, 'T2> (
        mapper : 'T1 -> 'T2,
        array : 'T1[]
    ) : 'T2[] {

        mutable mapped = new 'T2[Length(array)];
        for (i in IndexRange(array)) {
            set mapped w/= i <- mapper(array[i]);
        }
        return mapped;
    }

    function AllCControlled<'T3> (
        ops : ('T3 => Unit)[]
    ) : ((Bool,'T3) => Unit)[] {

        return Mapped(CControlled<'T3>, ops); 
    }

The function CControlled is defined in the Microsoft.Quantum.Canon namespace. It takes an operation op of type 'TIn => Unit as argument and returns a new operation of type (Bool, 'TIn) => Unit that applies the original operation, provided a classical bit (of type Bool) is set to true; this is often referred to as the classically controlled version of op.

The function Mapped takes an array of an arbitrary item type 'T1 as argument, applies the given mapper function to each item, and returns a new array of type 'T2[] containing the mapped items. It is defined in the Microsoft.Quantum.Array namespace. For the purpose of the example, the type parameters are numbered to avoid making the discussion more confusing by giving the type parameters in both functions the same name. This is not necessary; type parameters for different callables may have the same name, and the chosen name is only visible and relevant within the definition of that callable.

The function AllCControlled takes an array of operations and returns a new array containing the classically controlled versions of these operations. The call of Mapped resolves its type parameter 'T1 to 'T3 => Unit, and its type parameter 'T2 to (Bool,'T3) => Unit. The resolving type arguments are inferred by the compiler based on the type of the given argument. We say that they are implicitly defined by the argument of the call expression. Type arguments can also be specified explicitly, as is done for CControlled in the same line. The explicit concretization CControlled<'T3> is necessary when the type arguments cannot be inferred.

The type 'T3 is concrete within the context of AllCControlled, since it is known for each invocation of AllCControlled. That means that as soon as the entry point of the program - which cannot be type-parametrized - is known, so is the concrete type 'T3 for each call to AllCControlled, such that a suitable implementation for that particular type resolution can be generated. Once the entry point to a program is known, all usages of type parameters can be eliminated at compile-time. We refer to this process as monomorphization.

Some restrictions are needed to ensure that this can indeed be done at compile-time as opposed to only at run time.

Restrictions

Consider the following example:

    operation Foo<'TArg> (
        op : 'TArg => Unit,
        arg : 'TArg
    ) : Unit {

        let cbit = RandomInt(2) == 0;
        Foo(CControlled(op), (cbit, arg));        
    } 

Ignoring that an invocation of Foo will result in an infinite loop, it serves for the purpose of illustration. Foo invokes itself with the classically controlled version of the original operation op that has been passed in, as well as a tuple containing a random classical bit in addition to the original argument.

For each iteration in the recursion, the type parameter 'TArg of the next call is resolved to (Bool, 'TArg), where 'TArg is the type parameter of the current call. Concretely, suppose Foo is invoked with the operation H and an argument arg of type Qubit. Foo will then invoke itself with a type argument (Bool, Qubit), which will then invoke Foo with a type argument (Bool, (Bool, Qubit)), and so on. Clearly, in this case Foo cannot be monomorphized at compile-time.

Additional restrictions apply to cycles in the call graph that involve only type-parametrized callables. Each callable needs to be invoked with the same set of type arguments after traversing the cycle.

   function Bar<'T1,'T2,'T3>(a1:'T1, a2:'T2, a3:'T3) : Unit{
       Bar<'T2,'T3,'T1>(a2, a3, a1);
   }