A system of "Interfaces"

[ss2165]

Take as use case "hashability" of a type. For a given type T we can define the interface Hashable as

Hashable(T) {
    hash(T) -> (usize,);
}

And have for example standard library methods

insert<K, V: Hashable>(k: K, v: V) -> ();

So the proposal is:

• A HUGR concept of "interface" which means "a set of function with given names with given signatures that must be defined on a type"
• Ability to define interfaces and implementations of interfaces in extensions
• Ability to constrain type parameters by interfaces
• Validation time ability to check a type implements an interface

Is this overly complicated to be worthwhile? I suspect it gives us a large degree of flexibility for compile-team reasoning over generic operations without losing type safety and being too generic.

[acl-cqc]

Discussion yesterday we thought perhaps we did not need to add anything (/much) to Hugr:

• Passing tuples still seems a "preferred" way to do this, especially in cases where the implementation is likely to differ across the Hugr (e.g. Maps with different key types)
• Other cases we could push custom types and operations out to an extension; the Hugr could then be loaded in with a variety of different extension implementations.
  • There is no static checking of "will this Extension (implementation) satisfy the signatures required by this Hugr" here. You check by loading the Hugr + Extension and validating.
  • However, in a database of multiple extension implementations, we could define some notion of Extension-signature and check things that way. (E.g. one extension considered definitive for validation, but with no actual implementation; and then a tool to check other extensions against that one.)
    • After all, implementation of ops defined in extensions may be deferred to the tooling!
  • (Proposed by @doug-q) We might want to add the ability to define extension aliases ("using extension X as Y") locally across Hugr-subgraphs
  • We'd also want Guppy to be able to "compile" down to an extension (i.e. one where operations were implemented by providing Hugrs)

However, I am wondering if we have missed something here. Rather than the extension mechanism, can we not just use linking? Hugrs can declare both types and functions (to be defined by another Hugr linked in). The only things that the extension mechanism adds on top of this are (a) ops implemented by binary not Hugr, and (b) more flexible (binary-computed) type "schemes". I'm not sure I hear anything that says we need either of these?

[ss2165]

Thanks for the write-up

On linking, I'm pretty sure how this is Guppy does it at the moment, it just declares all the functions it needs on these types and assumes they will be linked in. @mark-koch is that correct?

[mark-koch]

it just declares all the functions it needs on these types and assumes they will be linked in

Yes pretty much. The problem is that we will need some sort of dynamic dispatch. I don't think we can achieve this just with linking?

[mark-koch]

Here are my thoughts. From a Guppy perspective, I would like users to be able to write something like this:

@guppy.protocol
class Hashable:
    def __hash__(self) -> int: ...

# Now we can define multiple types that implement the Hashable protocol

@guppy
def foo(x: Hashable) -> int:
    # Dispatches to the correct implementation for the argument
    h = hash(x)

Below are the different compilation options we have discussed.

Option 1: Passing implementations as extra arguments

The Hashable protocol is not represented in Hugr. Instead, we turn foo into a genric function forall T. T, (T -> int) -> int that takes the __hash__ implementation as an extra argument. If the protocol has more functions, we could package them up in a tuple.

Advantages

No extra complexity added to the Hugr spec

Disadvantages

• With this approach, we cannot handle things like list[Hashable] were each list element might require a different implementation
• The resulting Hugr will be a lot harder to understand. Once we have multiple protocols that extend and depend on each other, I think a considerable part of the Hugr representation will just be concerned with unpacking, repacking, and shuffling these functions around.
• Related: If we go ahead and turn even Qubit into a protocol, then circuits would become very hard to work with.

Option 2: Generating Extensions

Morally, we can think of interfaces as existential types / dependent tuples, e.g. Hashable = (T :: Type, T -> int). This is not representable in Hugr's type system, however we could add an extension that provides:

• An opaque type Hashable
• An injection op ToHashable :: T, (T -> int) -> Hashable
• An op __hash__ :: Hashable -> int

This makes Hashable isomorphic to the existential type described above. In particular, the extension binary can implement it as such.

Advantages

• The resulting Hugrs are easier to understand since ops still have meaningful names
• The resulting extension will be fairly simple
• No custom validation code needed

Disadvantages

• These ToHashable ops will pop up all over the place, in particular, they require the protocol implementation as input.
• If we want to call a function that expects a list[Hashable] and we've got a list[int], we would need to map ToHashable over the list in order to pass it to the function. In general, we will need (nested) fmap over all container types.

Remark: Extending protocols

We probably also want to allow users to extend protocols:

@guppy.protocol
class Hashable(Equatable):  # Hashable extends Equatable
    def __hash__(self) -> int: ...

In this case, the Hashable extension would need to provide an extra op HashableToEquatable :: Hashable -> Equatable. However, this will get hairy once we get into multiple inheritance territory (diamond problem).

Option 3: Dynamic dispatch in Extension

A slightly different take on the extension idea is to use dynamic dispatch in the extension instead of passing implementations to the ToHashable function on each use. This means that __hash__ can fail at runtime if no implementation is found.

To make dynamic dispatch work we have some options:

• Store a vtable in every Guppy object
• Register protocol implementations in the extension. This requires explicit annotations when a user-defined type implements a protocol (so would be more like an ABC rather than a protocol)
• The extension knows about all Guppy types and functions
• ... ?

Note that we still need a ToHashable op to satisfy the Hugr type system, but it can be a noop that just casts the type. The benefit is we can also cast (nested) containers without any performance cost.

Advantages

• Resulting Hugrs are less noisy since we don't need the implementation wires
• Solves the list[Hashable] problem

Disadvantages

• Less validation guarantees and can fail at runtime (but frontends should guarentee that this never happens)
• Required extension is more complex

Option 4: Native Hugr support

Something along the lines @ss2165 suggested above.

[acl-cqc]

So we need to be clear about what level of "dynamic" dispatch is required. If we mean - the target function is statically known (during compilation), then either the proposal of abstracting over extensions or that of linking with another Hugr is sufficient, and leads to both simple Hugrs (no massive tuples) and simple Hugr specification.

In particular, I think "Qubit" is likely to fall into this category. How many programs are likely to want multiple kinds of Qubit? At the same time?? (Maybe we should work through a Tierkreis program that manipulates both optical-Qubit and atomic-spin-Qubit "circuits" in the same TierkreisGraph, but of course, only runs each on its own H/W. I don't think this will be too difficult.)

However, if what you want is lists of hashables - well, my overall thought here is that we are trying to shoehorn an object-oriented language into a lower-level IR. We could make Hugr OOP, but do we seriously want to? The "fun" you are talking about with vtables is exactly what C++ compilers, amongst others, do when compiling an object-oriented program down to a lower-level, non-OOP, language like C/C--/etc. That OOP involves a lot of complexity of function-passing etc. - well it does, because that is what is really going on under the scenes, and at some level, that has to become obvious!

(And, that in an object-oriented language, every value is an existential is the true horror of OOP, again best kept obvious rather than swept under the carpet? As Conor says, "anyone who isn't afraid of subtyping doesn't really understand it"...)

The ideal for Hugr would seem to be, we allow standard Hugr to be a "low-level" non-OOP IR; and then there is some object-orientation Extension which enables doing the awkward stuff. This looks like it corresponds to Option 2, and if I look at the disadvantages there, they don't seem too bad to me:

• Yes ToHashable requires the appropriate type/conversion, but only in places that are abstracted over T; if T is concrete, then the conversion (T -> Int) is statically known.
• mapping over container types seems very reasonable. Treating a list[int] as a list[Hashable] seems quite dangerous (subtyping, mutation). Typically functions operating on such a list might say fn foo[T <: Hashable])(items: List[T]) -> ... whereupon you pass a function-tuple (aka vtable, really) for the (type) parameter T.

Lastly, it seems to me that the "rules" for translating OOP into Hugr might well change as we refine the exact semantics (Conor's comment springs to mind again - we should not expect to get these right first time). I think that's an argument for keeping these outside core Hugr so that core Hugr doesn't have to change when the semantics do.

[acl-cqc]

Extension 3 is fine too. The tuple/vtable is looked up by the extension rather than being passed around, so maybe this saves some tuple-passing. Guppy's own static analysis should be enough to ensure we never fail to find an expected vtable at runtime - in some sense this static analysis is much the same as what you'd do to figure out what explicit tuple/vtable's to pass in option 2, just that you don't record the results in the Hugr. (So the Hugr looks simpler.)

However, note you'll have to store some Run-Time Type Information with each object (in option 3) so that you have something from which to find the vtable. I'd say it was an open question whether that RTTI was easier to work with / more compact than just storing the vtable itself...

[doug-q]

A variation of Option 2:

An extension provides an op: __hash__<t: Type>: [t] -> [int]

It could also provide a custom type dyn_Hashable (analgous to Hashable in option 2 and conversion ops.

The extension provides some way to "declare" "instances" of the "Hashable" "type class".

Perhaps this is inside-hugr, maybe with additional feature, or maybe by requiring exactly one CustomConst of opaque type TypeClassInstance<"Hashable",t: Type>" for each type twhich instantiates ahash` op. Perhaps this could be in the extension's static data. Perhaps instances are loaded into the extension in rust before it is added to a registry.

This pushes complicated instance composition into the type class registry. When this extension is lowered it can be implemented with whatever dynamic dispatch, or no dynamic dispatch, the lowering is free to do whatever it wants.

The extension should validate the hugr that all calls to __hash__ are on types with valid instances. I think this would require additional validation hooks.