(j3.2006) more on J32031 equivalence of circular types

[Michael Ingrassia]

>Mike gets into an infinite loop

No, that was Aleks who gets into an infinite loop.   I'm not even
trying to run an algorithm, just trying to understand what answer the
standard specifies that an algorithm would get.  The question isn't
"why do implementations get into infinite loops" -- I don't know that any
of them do -- but "does the standard say A and B have the same type or not".
Bill has it exactly -- the standard seems to say only that A and B have the
same type if they have the same type.

>I don't think you have any choice but to say "Aha! I've been here so
>they must be the same"

I find this statement curious.  Since the standard doesn't spell out an
algorithm, how does it foreclose some of the possible choices in an algorithm?

You've spelled out an algorithm, and you may not have any other reasonable
choices in your algorithm when you come full circle.  But it's easy to spell out
different algorithms, e.g.
	o In the first case, you try to show 
		that the types of A and B are different
	o So you start doing a simultaneous recursive traversal of both
		type systems' graphs
	o If you arrive at anything different in the traversal, you
	     quit and say "I was right, they're different!"
	o If you finish traversing the graphs by visiting every vertex without
             saying "I was right!", you quit and say "My goal was wrong, they're the
             same type after all"
In this case when you arrive at types you've visited, it makes sense to
quit and say "I was right, they're different".  I don't see that the
standard rules out this algorithm.

As for Bill's question (is this only a theoretical concern), I ran the Sun
compiler on the sample program and we accept it without errors, which is
evidence that we treat A's type and B's type as the same.  Maybe others
want to check their compilers.

 	--Michael I.