Literature needed on recursive (union) types

Dear all,


I have the following problem:


Suppose I have a language with union types. A union type is a type
denoting those values that are a member of at least one of its
component types. So, suppose I have a type definition T = nat | bool
(The '|' symbol is the type constructor for union types), then 1, 2, 3,
4, etc. would be values of T, but <false> and <true> as well.


The problem arises when trying to determine subtype relations between
recursive union types. I want to define a relationship
`IsSubType (T1, T2)', which yields true if (all the components of) T1
are subtypes of (at least one of) the components of T2.


Consider the two type definitons


T1 = nat | nat X T1 { 'X' denotes a product type }
T2 = real | real X T2


IsSubType (nat, real) is defined to be true, and therefore it is easy
to see that IsSubType (T1, T2) should be true as well. The obvious
implementation does not work, however, because a recursive call to
IsSubType (T1, T2) is made when examing the second component, and then
we have infinite recursion. For this particular class of example a fix
could be found, but they can be made much more complex.


Does anyone know of literature dealing with this kind of problem?


Thanks for your time,


- Nico Plat -
- Delft University of Technology -
- Fac. of Techn. Math. and Informatics -
- P.O. Box 356, NL-2600 AJ Delft, The Netherlands -
- Phone +31-15784433 Fax +31-15787141 E-mail nico@dutiaa.twi.tudelft.nl -
--

Return to the comp.compilers page.
Search the comp.compilers archives again.