No explicit copy

[ss2165]

Explicit copy nodes lead to lots of difficulties. We found this with Tierkreis. The problems stem from the fact that there is some strong coupling between the source of the value and the copy node, which leads to special casing on copies. E.g. in the builder, if there is a state edge on a node, an output of which is then copied, the state edge either needs to move or be copied on to the copy node.

I propose instead changing to allowing multiple edges leaving a classical output port.

In the spec we use the copy for:

1. Defining linear types as those that cannot be copied. This can be done equivalently well by stating linear ports can only have one edge leaving them.
2. Defining discard as 0 copy. Instead state a port with no edges leaving it means discard. If this complicates replacement definition too much (in terms of "open graphs"), we can still use an explicit discard op.

In terms of implementation, this can be done by still using copy nodes in the underlying portgraph. By obscuring global PortIndex in the hugr interface (using instead (NodeIndex, PortOffset) to identify ports), we can map the source of edges leaving copy nodes to original output port.

[acl-cqc]

Not convinced. I realize copies lead to difficulties, but they also solve problems.

1. "Defining linear types as those that cannot be copied. This can be done equivalently well by stating linear ports can only have one edge leaving them" - at the moment ports don't know about linearity or not. (In the spec, ports = for value edges, whereas in the implementation, ports = all edges, but none know about linearity).
   a. We talked about should a node have both linear ports and nonlinear ports, and we didn't like having these extra classes of thing (an implementation concern perhaps but I think the implementation will get messier and more complicated). In contrast, the current scheme moves the decision re. linearity out to the question of what nodes are available, and polymorphic operations is something we are already thinking about elsewhere but can easily be kept at a higher level (i.e. not in portgraph).
   b. we also have the idea that portgraph/hugr atm don't really care what direction means. But linearity applies only in one direction, so now they must.
2. But now we have two mechanisms for discarding a value! (0 out-edges, plus discard node. Let's forget you could have many out-edges and discard all of them.) I suspect this means we should think harder - rather than "use a discard op" we may want a new mechanism altogether.

Another way of looking at it is that having a copy node is a great way of capturing all the issues with linearity into one place...maybe we should consider whether there are other ways around the builder problems etc. I note these problems are all with the implementation - so there is something to be said for making spec + implementation diverge on this front. However if the spec details all the API calls, does the presence/absence of copies not change any of these APIs? And, if we keep copies in the implementation, I guess that doesn't help solve the problems in the builder - so what other problems are there with copy nodes that we are thinking about?

[aborgna-q]

I don't like the idea of keeping the discard nodes. I think the replacement API should support connecting any number of wires to a input boundary port (including zero).

E.g. suppose that we replace a Const usage with multiple ones (say we are unrolling some loop), we'll need to attach n wires to that boundary port. Discard would be a weird edge case.

[ss2165]

The builder example I gave was the one that was closest to hand, I don't see much use in debating it one way or the other (any compromises needed for the builder are trivial against the broader scope of this question). My main motivation is that multiple edges from one port is the most natural way to capture the semantics of "produced once, used 0 or more times". It is the closest to SSA, which we will be going to and from.

But they also solve problems

I cannot see what problems they solve that are not implementation only.

1. a) Current spec: Types are either linear or classical. Ports have an associated type. Therefore the current spec already encodes linearity in ports. The copy node is redundant for this purpose. b) Hugr cares about direction - every edge has a meaning to the direction (dataflow/controlflow).
2. I wasn't suggesting two mechanisms, I was saying pick either "no edges from port" or "discard node", I wasn't advocating for one or the other here. Though I like @aborgna-q 's argument against discard nodes above.

[ss2165]

I forsee many problems in rewriting and analysis too, many pieces of logic that have some variation of "if copy node, go to source, then continue"

[ss2165]

For 1. b) I may have misunderstood.
Maybe you mean that inedges and outedges are symmetric so we have a lot of code/interface just parametrised by Direction? And this would break that symmetry, because the number of outgoing edges does not match the number of outgoing ports. I agree that this leads to a significant departure in the interface, but I'm not sure it's a bad departure.

[cqc-alec]

[I]f there is a state edge on a node, an output of which is then copied, the state edge either needs to move or be copied on to the copy node.

I don't follow here: why does the state (order) edge need to be copied to the copy node?

[cqc-alec]

Ah this is for adding intergraph edges, right.

[ss2165]

yes sorry, was very lazy with the example

[acl-cqc]

I'd like to see some elaboration/enumeration of the other problems whose existence is implied by "e.g. in the builder, if there is a state edge".

I wonder if that one might be solved by constructing a copy node (in the builder) for every non-linear port, and then eliding copy1's in finish ?

[aborgna-q]

From the implementation side, I think we can have a nice interface if we allow logical multiports.

The main annoyance I see is having to modify the underlying ports (let's call them physical ports) each time we connect or disconnect a classical wire. Now that we have port capacities however, this cost is reduced (although it still requires shifting the following physical ports, and updating the links).

We have to redefine Wire to avoid unexpected invalidations, and take some care to avoid linear scans on a node's port, but I think this is doable and performance may not suffer too much (vs having more nodes).

[aborgna-q]

I'm assuming that we keep the "no unconnected ports" on the the underlaying portgraph, but that may also change to avoid unnecessary shifting.

[ss2165]

Is this a different suggestion to "map HUGR output ports to underlying portgraph copy nodes if there is more than one edge"? Because in terms of modifying port capacity that seems identical to the current case

[aborgna-q]

Ah, yes. I was thinking about adding the new nodes directly. If we use underlaying copy nodes then everything should work without much modifications.

[ss2165]

in fact I think this makes it more natural to avoid changing capacity - because you can have an interface for specifying how many copies you want when creating the node.

[aborgna-q]

Like an add_op_with_linear_capacity? Makes sense.

[ss2165]

A nice side-effect is that const, def, declare don't have a special cased "variable number of ports all of the same type" rule, they just have one outport.

[acl-cqc]

So initially I thought that, due to difficulties in (I think) (Builder) implementation, the proposal was to change the spec (and even perhaps keep the implementation the same) - that didn't seem the right approach.

I am somewhat neutral on the spec. I note the spec came after the implementation, i.e. following Lukas' implementation-focused work in Hack Month! (We did at that time consider having two kinds of port, non/linear, but decided it looked like too many levels of indirection in the implementation and rather ugly.) If the implementation can be made nicer by changing the idea of copy nodes, maybe the spec should once again follow after the implementation is settled. Clearly it seems that Agustin and others have ideas on how the new implementation could look - are these spelled out in more detail anywhere?

One property that we don't really capitalize on at the moment is that the only nodes that have variable-output-arity have no other outputs of that kind. Indeed, excluding dataflow nodes, they have no other outputs (e.g. def, const, declare) - annoyingly dataflow nodes have variable-arity-state plus value outputs, but they retain having only one variable-arity port, so maybe that helps. At present the only node with a variable-arity value output (i.e., copy) then has no other outputs...?

Oh, and CFG nodes have variable-arity inputs....

[ss2165]

summary of chat with @acl-cqc and @aborgna-q

• copy node at port graph level but not at hugr makes sense
• Spec does not need to refer to copy nodes at all - neither does the serialized format
• need to think careful about interface/symmetry:
• for efficient mutation may need a handle to i'th copy (underlying copy node outport)
• CFG nodes can have multi-in-port - should generic interface be "bundles" of edges per port?
• How much better can interfaces be in high-assumption regions? (e.g. linear/no-copy regions can have 1-1 port-to-edge interfaces)

[zrho]

A potential solution to building graphs conveniently when using explicit copy nodes would be a method that, when given a port, does the following:

• If the port is already connected, then insert a copy node, relink the port to the input of the copy node, and link the left output of the copy to the input port that was previously connected. Then return the right output of the copy.
• If the port is not connected yet, return it.
  This could be adjusted to avoid building trees of copies and instead build one big one.

If we want copying to be more implicit, there is options:

• Build something on top of portgraph that models both nodes and hyperedges as the nodes of an inner portgraph.
• Adjust the portgraph to be a hypergraph. That is possible without affecting performance in the single connection case but the API will be weirder. This might be a bit weird from a circuit rewriting perspective.

[aborgna-q]

We're testing that idea, with a hopefully not-too-weird multiport wrapper on the Hugr side.
We can then hide the copy nodes from the API, and create them on-demand.

The port indices remain the same, but there is also a SubPort(PortIndex, PortIndex) when we need to identify the specific copy ports.
This adds some indirection, but it may not be too bad since we'll be normally working with the operations rather than the copy nodes.

[aborgna-q]

Spec updated in #108
Implementation Issue: #109