Polymorphism and Monomorphization

[acl-cqc]

This relates to guppy, also to #1556.

At the moment Guppy has less polymorphism than Hugr: users can declare functions that are polymorphic over type variables, but the kind of every type var is one of either AnyType, CopyableType or UnboundedNat. In contrast Hugr offers a wide space of kinds (aka TypeParams) - AnyType, CopyableType, BoundedNat, String, ExtensionSet, and List and Tuple of TypeParam(s) making an infinite set.

If current Guppy was the only language we cared about supporting, we could massively simplify Hugr by dropping support for typeparams beyond Guppy's 3. (#1405 would no longer be the case, the type-level stuff would be waaay short of what one might call a "language"!)

More likely is that we'll extend Guppy. Adding support for kinds ListOfType and ListOfCopyableType seems like something that'd be useful for end user programmers dealing with (arbitrary) tuples. Other cases may follow, noting we plan never to parametrize over "higher-order" kinds like Type -> Type.

Currently plans for compiling polymorphic functions in guppy lean towards monomorphization, i.e. guppy generates non-polymorphic Hugrs. Again, this suggests we might massively simplify the Hugr language(!); however, that route

• entails every frontend doing its own monomorphization, which seems like duplication of effort. (Ok, there will always be some cases where frontends must do their own monomorphization, but we might want to try to limit these cases to those involving types that definitely do not fit into Hugr, i.e. dependent types)
• restricts our options for compilation: it's extremely hard to un-monomorphize, whereas if we delay monomorphization until lower down the stack, we keep our options open (e.g. including dyn-like passing of vtables)

Instead we might ask: what facilities do we need in Hugr for "native Hugr polymorphism" to be usable by frontends? (Having frontends that monomorphize instead of using Hugr polymorphism seems the worst of all worlds - with a Hugr more complex than it needs to be, and frontends having to do more work.)

Looking at guppy, a major source of problems here are array comprehensions and initializations. For example, array(qubit() for _ in range(N)), where N is a statically-known type parameter. The monomorphization strategy involves generating N calls to qubit(), which seems poor.

So question to @doug-q: can LLVM initialize such an array (on stack) using a loop? E.g. via a new_uninitialized (or new_filled_with_poison) and then direct indexing?

And what does the Hugr look like here? Given the element type is not copyable, we need code to execute for each element, so possibilities:

• We could have new_uninitialized / new_poisoned in Hugr too, either
  • followed by loop + direct indexing - noting that inside the loop the type system does not protect us from indexing outside the array, although it shouldn't take "much" inspection to convince us it's ok (i.e. the frontend has the "proof" of safety but can't encode it into the Hugr)
  • or followed by map_array similar to the next option:
• We could have new_array taking a function. This could be a runtime (Value edge) pointer to a function (but not yet dynamically allocated / closure - that could follow later); or (following Allow custom ops with static constant input edges #1594) with a static edge to a function. We might also want to make this a fold, passing through some arbitrary (TypeParam::Type) state. Again this boils down to what hugr-llvm might be able to compile (@doug-q again)?

What about constant folding? Loop+direct-indexing seems unlikely to constant-fold unless we first determine the iteration count is small and then unroll; array_map and similar structures would require the fold impl to make a nested call/callback into the constant-folder to evaluate the argument Hugr (perhaps multiple times).

[doug-q]

So question to @doug-q: can LLVM initialize such an array (on stack) using a loop? E.g. via a new_uninitialized (or new_filled_with_poison) and then direct indexing?

Yes, no problem. This is the only way to create a new array in llvm, on the stack or anywhere.

e could have new_array taking a function. This could be a runtime (Value edge) pointer to a function (but not yet dynamically allocated / closure - that could follow later); or (following #1594) with a static edge to a function. We might also want to make this a fold, passing through some arbitrary (TypeParam::Type) state. Again this boils down to what hugr-llvm might be able to compile (@doug-q again)?

I don't see any problem here.

Looking at guppy, a major source of problems here are array comprehensions and initializations. For example, array(qubit() for _ in range(N)), where N is a statically-known type parameter. The monomorphization strategy involves generating N calls to qubit(), which seems poor.

We could provide a new_qubit_array<N>: [] -> Array<Qubit,N> op to support this very important case. I agree that the general solutions you outline look right, we should do them, but just providing this op takes solving the general problem much less urgent.