Wed, 16 Sep 1992 17:19:30 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: | drw@euclid.mit.edu (Dale R. Worley) |

Organization: | MIT Dept. of Tetrapilotomy, Cambridge, MA, USA |

Date: | Wed, 16 Sep 1992 17:19:30 GMT |

Keywords: | types |

References: | 92-09-079 |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.