Re: Literature needed on recursive (union) types

nico@dutiag.twi.tudelft.nl (Nico Plat) writes:
      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?


When evaluating predicates that involve recursively looking inside
circular structures, you always get into this sort of problem. I suspect
that the solutions are standardized, and all are ugly.


For instance, the type equivalence relationship in the Algol 68 type
system has this problem. The solution in the Algol 68 Revised Report is
that every time you start recursively testing a sub-problem, you check
whether you are already inside an evaluation of that sub-problem, and if
so, exit immediatly, reporting True. (This gives you the most-lenient
interpretation of the problem, i.e., the greatest fixed point.) (The
first Algol 68 report didn't notice this problem, and its type-equivalence
algorithm is non-computable.)


You could also accumulate a table of all types mentioned in the system and
then parallely compute IsSubType for all of them. This probably doesn't
work very well for your problem, but it's simple if you're computing an
equivalence relation like the Algol 68 type equivalence problem: Put all
types in one class. Then, based on what the type classes are at the
moment, split each class into subclasses which are distinguishable because
their 'components' are in different classes. When the process stabilizes,
you have the coarsest equivalence relation that is compatible with the
equivalencing rules.


Dale Worley Dept. of Math., MIT drw@math.mit.edu
--

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