What are CustomTypes?

[ss2165]

Discussion started here:
#186 (comment)

It is unclear what data specifies a CustomType

[croyzor]

I'm thinking of the example compiler in the mlir docs, which adds a tensor type which is parameterised over some dimensions, i.e. Tensor<2 x 3>. This is an opaque type as far as mlir is concerned, yet it has some (attribute/parameter) arguments.

In the extensibility example in our docs, we have arrays of a fixed length which are written as Array<i>(T), I think it would be good to allow custom types to be this expressive, with the caveat that the arguments opaque types should be static.

When a plugin developer specifies types, they should be able to specify some type parameters, then when that type is put in the signature of a function, that signature specifies what the type parameters are. Be they from typeargs bound by the signature or constants.

Hence, when I declare the opaque type "Array", I write

types:
   - name: Array
      typeargs: [["size", !U64], ["data", !Type]]

I can then write a function signature like so:

args: n
inputs: [!Array n !u64]
outputs: [!Array n !Bool]

[acl-cqc]

Yes, this is what I meant (! syntax aside, i.e. just looking at the Rust implementation, not parsing from yaml or anything).

So looking here: https://github.com/CQCL-DEV/hugr/blob/43ae6bac774c39b3f513259530b9761261c1fc15/src/types/custom.rs#L13-L16

I think this "TypeRow" is wrong for a definition - that’d mean the params to a CustomType was a row like [Qubit, Int], and not allow saying that the type def wants “a type” as a parameter - e.g. if you try defining List as a CustomType. (I think this is what Conor would call a “kinding error”.)

So I think the fix parallels what #186 does with CustomOp and OpDef - we should split CustomType into two: maybe TypeDef (like OpDef, belongs to a resource, may be of a higher kind like * or * -> *) and CustomType (like CustomOp, sits in the SimpleType hierarchy: an instantiation of a TypeDef to kind * with concrete arguments - the arguments themselves may be types)

So the Resource contains TypeDefs, which have a List not a TypeRow; the SimpleType hierarchy contains the instantiation, which has a reference (by name, I think, rather than Arc**) to the CustomTypeDef, and a List (a bit like a List but that also allows passing in types).

** because we call OpType::signature() to get the Signature, so there's no good time to "edit" this to resolve names to Arc's; and because the type name (unlike the operation name) probably carries all the information we need - there's no query you can make on an opaque type besides name+arguments, whereas OpType's have signature() etc.

The question is then about the exact form / variants of TypeParam / TypeArgValue, see #186

[ss2165]

The (Op/Type)Def + Custom(Op/Type) analogy makes sense to me

[acl-cqc]

That is to say, I don't see why the same system shouldn't be used for both OpDef and TypeDef, but the TypeParam/TypeArgValue may not be it.

Parameters/arguments could be two separate lists

• Firstly a list of types - parameters are an enum {Simple, Classic} (I can't see how a linear type could be a valid parameter but not a classic type, as anything you can do with an arbitrary linear type you can also do with a classic one); arguments could then be a List (elements corresponding to Classic parameters must be SimpleType::Classics)
• Secondly a list of values - parameters are a List of ClassicType, arguments a list of ConstValue

We could combine these à la TypeParam/TypeArgValue, as having to write types before values is slightly restrictive, but separating them does fit quite neatly with the Rust types/structs/etc. that we have already.

[acl-cqc]

A argument for TypeParam and TypeArg is that the proposed alternative (List<enum { SimpleType, ClassicType }> + List<ClassicType) would not allow a declaration parameterized over an unspecified-length-list-of-types.

While that's not something that one can do in (say) Haskell, it is quite meaningful if the opaque type is implemented in python, say, by iterating over said list of types. So you could have a custom/opaque type def "ConvertibleTo" and instantiations (CustomTypes) ConvertibleTo<F64>, the probably-useless ConvertibleTo<>, and also things like ConvertibleTo<String, Int> (quite different from ConvertibleTo<Tuple<String,Int>>). This is kinda useful as we don't have a notion of intersection of types (no way to say that a single value is both of type ConvertibleTo<String> and of type ConvertibleTo<Int>)

This is, perhaps, a minor detail - I think the main thing here is that we need TypeDef+CustomType that parallel OpDef+CustomOp and they should be parameterized with the same mechanism (whatever that is).

[ss2165]

Broadly, I'm in favour of this simpler system - it makes it a lot clearer what the link between values/types/type arguments are.

One question thought, TypeParam/TypeArgValue makes restrictions on which ClassicTypes are valid as TypeParams, while this system would presumably allow any level but then validate input at runtime?

[ss2165]

the main thing here is that we need TypeDef+CustomType that parallel OpDef+CustomOp and they should be parameterized with the same mechanism (whatever that is).

👍

[acl-cqc]

Hmmm, we also need ResourceSets, so I'm heading towards:

enum TypeParam {
   Type, // Or "AnyType" or "SimpleType", perhaps
   ClassicType,
   ResourceSet,
   Value(ClassicType),
   List(Box<TypeParam>)
}

enum TypeArgValue {
   Type(hugr::types::simple::SimpleType),
   ClassicType(hugr::types::simple::ClassicType),
   ResourceSet(hugr::resource::ResourceSet),
   Value(hugr::ops::constant::ConstValue),
   List(Vec<TypeArgValue>)
}

This puts a lot of the work onto ConstValue which looks like it needs some updates (e.g., it does not provide a signature), but avoids needing a direct reference from TypeArgValue to CustomType.

[ss2165]

what is the signature of a ConstValue?

[acl-cqc]

Oh, crap. I think we do not want types indexed by a float? Then it becomes hard to check types for equality. I mean, we can just not define/derive Eq, but we need to check type A is equal to type B when we pass a value of type A into an operation expecting a B...

[acl-cqc]

So I think OpDef/CustomOp can use these enums, probably renamed from TypeParam/TypeArgValue to, oh, OpParam and OpArg; but TypeDef/CustomType will have their own more-restricted form (maybe just Type/ClassicType/Int/bool/List... bool<->Sum perhaps)

[cqc-alec]

C++ restricts non-type template params to so-called structural types. Do we need such a concept here?

[acl-cqc]

In the limit, we could have:

• WireTypes: Quantum or Classic, with lists, tuples, sums, etc. - this is the SimpleType we have now (just I'm wondering why it's called SimpleType, they are about the most general form of type we have. Perhaps because they don't include Resources?)
• Constant types: these are just the ClassicType we have now. Significantly, including float and opaque. I think it makes sense for operations to be able to take all of these as parameters, where all-of is inclusion but doesn't rule out taking other parameters too.
• Operation Parameters (statically known parameters to an operation): in fact I think these include all the constant types, as well as Type and ClassicType. Moreover, the most general thing would be to use the notion of Container again, allowing an operation to require (say) a variable-length list of (Type, Int) pairs: instantiations might be [(Int, 6), (Float, 3), (List<Int>, 2)] sort of thing - an example that demonstrates why separating out "type" arguments from "value" arguments (the latter could then be sent down Static edges) is not as expressive.
• Type Parameters (statically known arguments to a type definition that result in a type). If we say that declaring a type parameterized by a float should not be allowed (and ruling this out seems very sensible), type parameters include "Type" and "ClassicType" but do not include all constant parameters, specifically excluding Float

That is, writing each label in the colour of the lines bounding the space (around the label, that the label refers to):

[acl-cqc]

Or:

BasicType = Int | Opaque | ....
ClassicType = closure_under_containers (BasicType | Float) # also used for Constants
WireType = closure_under_containers (BasicType | Float | Quantum)
TypeParameterType = closure_under_containers(BasicType | "Type" | "ClassicType")
OperationParameterType = closure_under_containers(BasicType | Float | "Type" | "ClassicType")

[acl-cqc]

Pushed something like the above to #186, but will be good to refactor in the future

[acl-cqc]

However, further discussion, I think we conclude:

• Types and Defs should be parameterized by a fairly basic set: Type (e.g. Qubit), ClassicType (e.g. Int), Int (e.g. 6), ResourceSet (e.g. Quantum+Honeywell), List.
  • We specifically disallow parameterizing either on Float or Opaque (so no "floats less than 3", or ops whose type depends on a matrix) or anything Linear
  • For an example of a type parameterized by a ResourceSet, see GraphType ;-)
• Op's wanting constant data shall have to accept this via Static input(s); this is not possible for types

[cqc-alec]

... or anything derived from Float or Opaque such as lists of floats etc...

[acl-cqc]

Yes - but it's only the type that can't depend on that, the operation still can: you can parameterize by List, then compute a type that uses that list as the dimensionality of an arbitrary-rank tensor.

The big thing may be that we are ruling out TKET1-style ops parameterized by the angle they add, say. It's good to be clear what we are allowing, right? :)

[cqc-alec]

Yes agreed. I am wondering if it might be clearer to define (for type params) an explicit subclass of ClassicType that is allowed, along with containers thereof, rather than saying any ClassicType with specific exclusions.

[ss2165]

Side-note on TKET1 parameters, with context that I don't think going to any effort to support them in HUGR is that useful:

As @acl-cqc pointed out to me earlier, type parameters are only meaningful because they need to be specified on a node so that the signature of the node can be computed. The misc field is for other data that may specify the op, and therefore all uses of that op in any node, but it doesn't really interact with the HUGR. The floating rotation angle parameter does not affect the signature of the node in any way, so it can just go in misc.

[acl-cqc]

Yes agreed. I am wondering if it might be clearer to define (for type params) an explicit subclass of ClassicType that is allowed, along with containers thereof, rather than saying any ClassicType with specific exclusions.

I've pretty much done that, but will make an issue to refactor further so we can have proper containers. For example, List<Tuple<Type, Int>> is a good parameterization for "an arbitrary rank matrix where each row, column, etc., has a header" (and there's a type for row headers, a different type for column headers, and so on)

[acl-cqc]

Time to close discussion?