Re: Type inference without principal types

Jonathan Aldrich (jonal@cs.washington.edu) wrote:
> We are looking at adding type inference to Java from a software
> engineering perspective.  When using the existing Java type system
> unchanged, our planned inference algorithm does not yield principal types;
> this may make inference more challenging.
> What previous theoretical work is there on type inference in systems
> (especially object-oriented) without principal types? 

In Summer 1997, Nate Nystrom and I designed and implemented a type inference
algorithm for most of Java 1.1.3.  The algorithm is a combination of 
algorithms by 
  - Jens Palsberg, "Efficient Inference of Object Types", Information and 
    Computation 123(2):198-209, 1995.
  - Fritz Henglein, "Breaking through the $n^3$ Barrier: Faster Object Type
    Inference", The Fourth International Workshop on Foundations of
    Object-Oriented Languages, 1997.
  - Marcin Benke, "Efficient Type Reconstruction in the presence of 
    Inheritance", 1994.
Our type inferencer takes a program without any type annotations, and it
produces a Java program which can be compiled by the Java compiler.

Jens Palsberg