Is "Map" core or extension? What about Hashable & constraints?

[acl-cqc]

In the current codebase, Map(ClassicType,T) is a T for both T=ClassicType and T=SimpleType. However, there are issues with this:

• We would like to have operations like insert<K,V>(map: Map<K,V>, key: K, value: V) -> Map<K,V>. However, this can't parameterize over all key types K because types like Float can't be hashed.
• Ideally, we'd also like to define Map as a CustomType in the higher-order/Tierkreis extension. However, this will conflict with the previous goal.

We can solve the first by defining a subset of ClassicTypes that are Hashable, excluding Float. However, there is a further issue here - are Opaque types hashable? Trivially one can hash their serialized representation, but for a Map to work, this must be consistent with equality, which means opaque types must not have any notion of equality other than equality of serialized representations. Obviously all this is internal to the extension (operations), so the Hugr could gloss over it and declare all opaque types hashable. Or none. Or allow opaque types to declare whether they are hashable or not....

Moving the Map type out into an extension is possible but then either

1. We move the hashable constraint out into the extension too....which sounds like it requires the Hugr to support some general notion of type constraints (resources can declare new constraints; and can, presumably, declare interfaces for new types to meet constraints from other resources). This is all getting a bit baroque and OTT.
2. Or, we have a "Hashable" constraint in the core, which is not used in the core, only in the library. This is a bit ugh.

If we want to allow CustomTypes to optionally implement Hashable, then there are two mechanisms which we could allow:

1. The extension has to register custom binary code
2. Hashable CustomType's are hashed by hashing their serialized representation.

I note there is some commonality between Hashable and whether the type is a valid parameter to an OpDef or TypeDef, see #198. So, if we went with a Hashable constraint in core, and CustomTypes declaring whether they are hashable or not, then we could allow hashable CustomTypes to be used as parameters to OpDef/TypeDef, which is neat. This might then lead us to Resource YAML something like:

types:
  - name: MyList
    args: [["element", Type]]
    hashable: [element] # i.e., only if element is.
    # "hashable: []" thus means "always hashable"; and no "hashable" means it isn't

A final idea that I recall is that "the Map type doesn't care whether its elements are hashable - only the operations (get, put) do". There is some sense in this, but I'm not sure it solves (m)any of the problems...

[cqc-alec]

So what about:

• Move Map into an extension (it does seem a bit specialized for core IR).
• But, define a notion of Hashable in the core spec.
• And use this notion (in the core) to specify types that are valid op and type parameters.

[acl-cqc]

Yes, I'm liking this. We'd have Hashable $\subset$ Classic $\subset$ Simple (where Quantum = Simple $\setminus$ Classic), which is a much simpler venn diagram than this one

[acl-cqc]

Also, regarding the YAML - we need some mechanism for specifying whether a custom type is classic (copyable), too (#222). So the hashable: [x,y] might generalize to classic: [x,y] too. (I presume we'd prefer classic to copyable but that's kind of what it is?)

[acl-cqc]

hashable: [x,y] might generalize to classic: [x,y]

This still isn't right. I think all the type arguments being hashable is a minimum for the constructed type being hashable. Maybe all we need is "hashable_if_args_are_hashable: bool" (being true/false) and similarly for classic_if....

[acl-cqc]

Hmmm, whether Graphs are hashable is an interesting question. But clearly it doesn't depend upon whether their input/output types are hashable or not!

[cqc-alec]

Right. In general, they are not. For example a graph may contain a Const node outputting a float.

It may be possible to define a subclass of hashable graphs, which would at least require that each of its operations is hashable. I don't know how useful this would be.