Unify Term with Value, and add function pointers

[acl-cqc]

Preliminaries

• Add Term::CustomConst (wrapping a dyn CustomConst). Where CustomConst::get_type is t: Type, the Term has type Term::ConstType(t).
• Move Term to use Arc....only really required when we merge constants into Term, but a good step to get out of the way first
• Add Term::Adt (aka Term::Sum). Needs to contain both a SumType and the subterms (insufficient to determine the SumType). This has type Term::ConstType(Type::new_sum(tag, sum_type)) and type-checking (check_term_type) requires that each of the subterms has type Term::ConstType(t) for the appropriate t within the SumType.
• Parametrize Term<N>, although no uses of N until we add Term::FuncRef
  • Types (runtime types) contains Term<Void>, where enum Void {}
  • OpTypes might possibly start off with Term<Void> too, at least to make migration more phased
  • And we'll need to parametrize CustomConst by <N> too, and make it contain Terms....is there a phased approach where Term::CustomConst containing unparametrized CustomConsts containing Values is "OK"?
• Then add Term::FuncRef(N, Vec<Term<N>>) - where the N will identify a function - possibly also containing a cache of the (instantiated?) type of the function (presumably hidden in a struct, with N-specific factories, so we can check the cache is valid...details will become clear)
  • check_term_type will have to take Term<PolyFuncType>s. A Term<PolyFuncType>::FuncRef will have type (i.e., check_term_types against) Term::ConstType(Type::Function(....)) where the RHS Type::Function is the result of instantiating the LHS PolyFuncType with the type args (this might have been cached). This type means that the FuncRef is a recipe for producing runtime function pointers (which would be equivalent to LoadFunctioning it - however it will also support being called directly).
  • In the short term, if OpTypes store Term<Void>, we'll need an easy conversion method from Term<Void> to Term<PolyFuncType>. We'll expand on this below when we enable OpType's to actually store FuncRef's (there are no Term<Void>::FuncRef because that would contain a Void and there are no instances!).

For static function pointers

We need to interface this with the Hugr graph:

• Now we make OpTypes such as ExtensionOp and Call store Term<PolyFuncType>.
  • Note that OpType::Call is already kinda specialized for storing the contents of a Term::FuncRef internally; we could move to OpType::CallTerm storing a Term as target and involving check_term_type but I think the gain (deduplication of "type checking" code) is small.
• Any node whose type-args contain Term::FuncRef(....), gets a static in-port for each (that must have an edge from a FuncDecl/Defn matching the <FunctionType> - after instantiation with the type-args - maybe we store the PolyFuncType and/or cache).
  • That is, probably the OpType::static_input_port method (becomes ...s), and HugrView::static_source -> s similarly - hard to do with deprecation (maybe old method panics if >1 ?). Actually adding ports to the node (in the portgraph) is a separate thing, as at present (e.g. like changing the OpType).
  • So, I am hoping we can add an enum_dispatch method get_type_args (reads args for Call/LoadFunc/ExtensionOp) and then use this in some non-dispatched OpType::static_input_ports method (that takes the ports immediately after the value inputs in the signature). We might want to cache how many ports the OpType needs, or we might say, the cache of how many ports are allocated in portgraph is sufficient...
  • Methods on specific enum variants know their own get_type_args so can be correct, although I'd prefer if we can keep this info on port allocation within the impl of enum OpType rather than the individual ops.
• Functions/methods to translate (Vec<N>, Vec<Term<PolyFuncType>>) <-> Vec<Term<N>> (the right-to-left direction needs a Hugr, l2r might take a Hugr to verify types) - traverse the Vec<Term> producing/consuming the Vec<N> in the order in which Term::FuncRefs are encountered
  • Thus, we can define HugrView::get_args(&self, n: Self::Node) -> Vec<Term<Self::Node>> that gets the Vec<Term<PolyFuncType>> from the op, and a Vec<N> of static sources (function definitions), and converting them;
  • Also HugrMut::set_args(&mut self, n: Self::Node, args: Vec<Term<Self::Node>>) that performs reverse conversion, stores the Vec<Term<PolyFuncType>> in the op, and sets up edges (+portgraph ports) from the Vec<N>.
  • Similarly, substitution operates on ephemeral Term<N> and converts to/from Term<PolyFuncType>+separate-edges for storage in the Hugr
  • And check_term_type no longer needs to convert OpType type-args from Term<Void>
• Now we can have an OpType::LoadTerm that contains just a Term<PolyFuncType>; this supercedes OpType::LoadConstant and OpType::LoadFunction, and does not need OpType::Const, all three of which can then be deprecated
• Monomorphization: will need adjusting to use these magic get/set methods to do substitution but otherwise should just work

For BRAT evaluation

I think we don't actually need Term<PolyFuncType> within OpType here - we can probably stick with existing Const nodes etc. and with OpTypes storing Term<Void> ??? - instead we need to interface Term::FuncRef with constant-folding:

• Parametrize CustomConst by <N> and make impls (ListVal/ArrayVal/etc.) contain Term<N> rather than Value. A big + disruptive change! 😢
  • Add CustomConst<N>::map<M>(self, func: impl Fn(N) -> M) -> impl CustomConst<M> (Rust will not less us say Self<M>). Hopefully one method can do both conversion between Rust types and Term substitution.
  • For now make Value contain CustomConst<Void>
  • Note this would happen naturally if these were expressed as "custom constructors" in the Term language, so that might actually be the easiest way?? But I'm less confident about getting this right, so maybe best to do it later (sadly meaning we write code to throw away) unless we can figure this out and do it first.
  • Note that in order to avoid OpType::LoadTerm gaining static input edges, LoadTerm and other OpTypes must contain Term<Void> at this point...and Const nodes would contain Terms - of type Term::ConstType(...) and without any function pointers, so they are mappable to/from Values if necessary, but this is ugly. See section below.
• Redefine ConstantFoldPass to operate on Term<H::Node> rather than Value, and trait ConstFold to take/return Term<N> (method parametric over N) rather than Value.
  • Loading a constant (a Term<Void> essentially) requires conversion, but that's generally trivial
  • ConstantFoldPass currently converts PartialValue to Option<Value> to pass to trait ConstFold; instead, convert to Option<Term<H::Node>>
  • Thus, ConstantFoldPass can turn PartialValue::LoadedFunction into Some(Term::FuncRef) rather than None (note this is because trait ConstFold takes currently Value, which becomes Term, not PartialValue<Value/Term>. It is tempting to think that instead we could move trait ConstFold into hugr-passes and pass PV's into trait ConstFold, but this does not work for ListVal/ArrayVal/etc. which contain hugr-core Value (becoming Term) - these are also used for constants in the Hugr and it makes no sense to have PVs there.)

Unresolved: are these Goals Separable

BRAT evaluation requires passing around ListVals containing function pointers. These same ListVals can live inside OpType::Const / OpType::LoadTerm nodes, which we'd therefore want to give static inports for FuncRef's, proposed as work for "static function pointers". Can we do BRAT without the other? (Or, can we do static function pointer work without changing CustomConst to contain Term?) There may be some horrible hybrid where (maybe we don't have LoadTerm) and Value contains CustomConst<Void> i.e. no FuncRef's, but it's looking rather nasty.

(Rather, it would seem consistent to allow FuncRef's inside CustomConsts and accept that we cannot validate the node until the constant becomes non-opaque....this is one advantage of keeping static edges in the Hugr, rather than computing an ephemeral "static graph" from Term<Self::Node> - the latter would not be able to inspect opaque constants; we need to keep edges for such stored externally.)

Finally

After both the above, we can then deprecate Value too :)

[acl-cqc]

This would let us remove all monomorphization from the guppy compiler, given current type system (where we currently monomorphize in guppy to deal with e.g. float constants), and some future proposals (e.g. protocols).

However, Quantinuum/guppylang#1299 will take us in an opposite direction, to doing all monomorphization in the guppy compiler, and not using Hugr polymorphism at all. Hence, closing

[acl-cqc]

We might reconsider this after #2756 and related issues as it might be a lot less work then