An example of substituability test that is recursive
john.r.rose at oracle.com
Thu Jan 31 19:43:33 UTC 2019
On Jan 31, 2019, at 10:41 AM, forax at univ-mlv.fr wrote:
> yes, i creates a DAG that will be too long to traverse :(
> you basically, DDOS yourself if you do a ==.
The complexity is exponential in depth, and
can be more than linear in heap allocation,
because of the risk of repeat traversals.
A worklist algorithm could make use of the
secret implementation identity of heap nodes
to push the complexity back down to heap
allocation size. A portable algorithm could
not. This is one more bit of evidence it should
be a system intrinsic rather than a vanilla library
More information about the valhalla-spec-observers