type inference of recursive types

"Joel F. Klein" <jfklein@students.uiuc.edu>
1 Dec 1999 23:40:28 -0500

          From comp.compilers

Related articles
type inference of recursive types jfklein@students.uiuc.edu (Joel F. Klein) (1999-12-01)
Re: type inference of recursive types okrslar@informatik.uni-muenchen.de (Martin Okrslar) (1999-12-04)
| List of all articles for this month |

From: "Joel F. Klein" <jfklein@students.uiuc.edu>
Newsgroups: comp.compilers
Date: 1 Dec 1999 23:40:28 -0500
Organization: University of Illinois at Urbana-Champaign
Keywords: ML, types, analysis

I'm trying to add support for recursive types to a compiler whose language
is based on typed lambda calculus, sort of akin to ML. Does anyone have
pointers to literature on implementing type inference for recursive types?

An example of such a recursive type is as follows:
type A = {car:int, cdr=var ref A}

("var ref A" means a variable of an A-typed Java-style reference in this

but this would have to be distinguished from the cdr field of this type:
type B = {car:int, cdr=A}

that is, given f : A -> T and M : B, both the following lines would be
f M
f M.cdr

The ML approach to type inference with recursive types seems to be
through the use of constructors that disambiguate the type of recursive
terms. Being accustomed only to ML, I'm unfamiliar with the alternatives.

--Joel Klein

Post a followup to this message

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