home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1560 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  2.2 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!psuvax1!rutgers!faatcrl!iecc!compilers-sender
  2. From: nico@dutiag.twi.tudelft.nl (Nico Plat)
  3. Newsgroups: comp.compilers
  4. Subject: Literature needed on recursive (union) types
  5. Keywords: types, design, question
  6. Message-ID: <92-09-079@comp.compilers>
  7. Date: 15 Sep 92 15:02:35 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: nico@dutiag.twi.tudelft.nl (Nico Plat)
  10. Organization: Compilers Central
  11. Lines: 39
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. Dear all,
  15.  
  16. I have the following problem:
  17.  
  18. Suppose I have a language with union types. A union type is a type 
  19. denoting those values that are a member of at least one of its
  20. component types. So, suppose I have a type definition T = nat | bool
  21. (The '|' symbol is the type constructor for union types), then 1, 2, 3,
  22. 4, etc. would be values of T, but <false> and <true> as well. 
  23.  
  24. The problem arises when trying to determine subtype relations between
  25. recursive union types. I want to define a relationship
  26. `IsSubType (T1, T2)', which yields true if (all the components of) T1
  27. are subtypes of (at least one of) the components of T2. 
  28.  
  29. Consider the two type definitons
  30.  
  31.     T1 = nat | nat X T1        { 'X' denotes a product type }
  32.     T2 = real | real X T2
  33.  
  34. IsSubType (nat, real) is defined to be true, and therefore it is easy
  35. to see that IsSubType (T1, T2) should be true as well. The obvious
  36. implementation does not work, however, because a recursive call to
  37. IsSubType (T1, T2) is made when examing the second component, and then
  38. we have infinite recursion. For this particular class of example a fix
  39. could be found, but they can be made much more complex.
  40.  
  41. Does anyone know of literature dealing with this kind of problem?
  42.  
  43. Thanks for your time,
  44.  
  45. - Nico Plat                                                           -
  46. - Delft University of Technology                                        -
  47. - Fac. of Techn. Math. and Informatics                                    -
  48. - P.O. Box 356, NL-2600 AJ Delft, The Netherlands                          -
  49. - Phone +31-15784433 Fax +31-15787141 E-mail nico@dutiaa.twi.tudelft.nl      -
  50. -- 
  51. Send compilers articles to compilers@iecc.cambridge.ma.us or
  52. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  53.