What is kind and meta?

[Kesanov]

I am trying to understand the algorithm from your source code and I am not able to figure out how does the kind and meta tag work. Could you maybe describe it in few sentences?

I would be keen to write thorough documentation to your source code, after I get full understanding of it...

[VictorTaelin]

We have plans to document exactly how this works. Plus the source code could use much better variable names and comments, so reading it may be harder than necessary, sorry about that. But, answering: kind is just the tag of the node. Each node has a tag, which is used to determine which (of the two) reduction rules to apply. Nodes with equal tags annihilate themselves, nodes with different tags duplicate themselves. Sometimes I also call it "color".

Meta is more complicate to explain, because you must understand how the algorithm works. The reduce() function can be seen as a machine walking through the graph. That machine is always between two nodes (i.e., it sits at the middle of a wire). It keeps 3 pointers: prev, which points to the last port it passed through (on the previous-node), next, which points to the next port it will pass through (on the next-node), and back, which points to the port it passed through to get to the previous node (on the previous-previous node).

The reason the back pointer is necessary is that, when the algorithm walks from a port with index 0 to another port with index 0, it triggers a rewrite() rule between the 2 nodes it is walking through (previous-node and next-node). After that, the machine is literally outside of the graph, because that region has been rewritten! To go back to the graph, it must use the back pointer, which points to the last node it walked through that is still part of the graph, i.e., the port on the previous-previous-node which was used to access the previous-node. Then the prev pointer is updated to that port, and the next pointer to what that port is pointing to. Now the machine is technically on the wire between the previous-previous-node and some other node. But what about back? Now back should point to the previous-previous-previous node, but you don't have that information! That is what meta is for. As you walk through the graph, you annotate each node with the port you used to enter it. That breadcrumb is called meta, which is always 0, 1 or 2. meta is stored on the rightmost 2 bits of the kind of the node (so there are only 2^30 kind). That allows you to set back to the port pointed by the meta port on the previous-previous-node.

Confusing, right? Even worse, I believe the names prev and next are reversed on this implementation. Hopefully it will be better when we clean up the code, and document it with images.