Tue, 15 Sep 1992 15:02:35 GMT

Related articles |
---|

Literature needed on recursive (union) types nico@dutiag.twi.tudelft.nl (1992-09-15) |

Re: Literature needed on recursive (union) types firth@sei.cmu.edu (1992-09-16) |

Re: Literature needed on recursive (union) types drw@euclid.mit.edu (1992-09-16) |

Newsgroups: | comp.compilers |

From: | nico@dutiag.twi.tudelft.nl (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 nico@dutiaa.twi.tudelft.nl -

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.