08-245r1
To: J3
From: Van Snyder, originally from Michael Ingrassia
Subject: Public Comment J32031
Date: 2008 August 14
----------------------------------------------------------------------
Commenter: Robert Corbett
Subject: "equivalence of circular types"
The draft Fortran standard allow circular type
definitions (see Section 4.5.3). Type
equivalence for derived types that do not have
the SEQUENCE property or the BIND attribute is
trivial, they are equivalent only if they are
defined by the same derived-type definition.
For type that have the SEQUENCE property or
the BIND attribute, type equivalence is
defined in terms of a hybrid of structural
equivalence and name equivalence. This hybrid
condition is easier to test than pure
structural equivalence, but harder to test than
pure name equivalence. Like other definitions
of type equivalence based on structural
equivalence, the definition of the equivalence
of two circular types is tricky. The draft
Fortran standard avoids this problem by not
defining what it means for two circular types
to be equivalent.
Consider the program
MODULE MOD
TYPE T1
SEQUENCE
INTEGER I
TYPE(T2), POINTER :: P
END TYPE
TYPE T2
SEQUENCE
INTEGER I
TYPE(T1), POINTER :: P
END TYPE
END
PROGRAM MAIN
USE MOD, ONLY: T3 => T1, T4 => T2
TYPE T1
SEQUENCE
INTEGER I
TYPE(T2), POINTER :: P
END TYPE
TYPE T2
SEQUENCE
INTEGER I
TYPE(T1), POINTER :: P
END TYPE
TYPE(T1) :: X
TYPE(T3) :: Y
Y%I = 1
NULLIFY(Y%P)
X = Y
END
The types T1 and T2 defined in the module might or
might not be equivalent to the types T1 and T2 defined
in the main program depending on the definition of type
equivalence for types with circular definitions.
Because the standard does not provide such a definition,
implementors have had to supply their own definitions.
I have found three distinct definitions implemented by
different compilers.
In the case of the example given above, Sun Fortran
considers the types T1 and T2 defined in the module to be
equivalent to the types T1 and T2 defined in the main
program. A compiler from another vendor considers them
to be different and produces the error message
fortcom: Error: testa.f, line 32: An assignment of
different structure types is invalid. [Y]
X = Y
............^
compilation aborted for testa.f (code 1)
when it tries to compile the code above.
I know two ways to precisely define structural equivalence
of circular types. One is to give an algorithm for testing
type equivalence. The other is to define type equivalence
in terms of equivalence classes. Either approach will be
considerably long and more complicated than the definition
of derived-type equivalence given in the draft standard.
----------------------------------------------------------------------
J3 response:
The definition in paragraph 2 of subclause 4.5.2.4 is unambiguous, even
though it is recursive in the case of recursive types ("... have type
parameters and components that agree in order, name and attributes").
The obvious recursive graph-traversal algorithm that determines that
the two collections of recursive types in the example are equivalent
might have exponential time complexity, but that is a different
question.
J3 chooses not to change the description of equivalence of recursive
sequence types. Although transforming the definition of equivalence into
an efficient algorithm is difficult, J3 chooses clarity over a detailed
but extensive and opaque description.