Literature needed on recursive (union) types (Nico Plat)
Tue, 15 Sep 1992 15:02:35 GMT

          From comp.compilers

Related articles
Literature needed on recursive (union) types (1992-09-15)
Re: Literature needed on recursive (union) types (1992-09-16)
Re: Literature needed on recursive (union) types (1992-09-16)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Nico Plat)
Organization: Compilers Central
Date: Tue, 15 Sep 1992 15:02:35 GMT
Keywords: types, design, question

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 -

Post a followup to this message

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