2 ms·
The referential integrity dreamcompiler refers to isn't just for cycles in the structure, but for substructure sharing. Substructure sharing still occurs in a D
by kazinator 4y ago
The referential integrity dreamcompiler refers to isn't just for cycles in the structure, but for substructure sharing. Substructure sharing still occurs in a DAG, unless you rule it out also (e.g. with some strict one reference ownership model or whatever). In the absence of cycles, it is still useful to have a notation which says "these two objects in the DAG are actually the same node". If you implement that, the detection of cycles is almost free, because the assumption that a duplicate node appearing in the print is not a descendant of the previous one doesn't simplify the printing or reading algorithms very much.
In order to print this #1=(... #1#) you have to determine that the given object occurs inside itself. In order to print (#1=(whatever) #1#), you have to determine that the given object occurs later in a sibling expression. Knowing that #1# will not occur inside (whatever) doesn't help all that much with anything; it doesn't help you decide whether or not the #1= prefix needs to be printed.
If anything if the restrictions were reversed, it would be simpler: if the only substructure sharing that were allowed was backward references, that helps. Because then we know that the (whatever) object can only occur again inside (whatever), and not after it. To detect nothing but cycles, without caring about other sharing, we just have to maintain an object path across the recursion so that for every visited object we can ask "is this object already in the path from root to here?" If so we have a backreference.
The sibling case is harder. You can have situations like:
((((#1=(foo)))) (((#1#))))
Deep inside the left item in the list there is an object which occurs again deep in the right item. We need to put the objects we are visiting into a hash, which is pretty expensive.
> Just by making sure your primitives for constructing values don't permit cycles to be constructed.
But lambda calculus teaches us that if all we have is functions being passed to functions and binding arguments we can build a circular reference. See the middle word of the domain in the browser address bar. So you have to further dumb things down from there if you want to absolutely eliminate cycles in the object graph.
(You can have it so that you don't care about function-induced cycles (only the garbage collector does) by not having any printed notation or other API that traverses the internals of a function. The application can still build a graph using functions, but is "on its own" as far as providing its own functions for operating on it, and serializing it and whatnot.)