[% setvar title type inference %]

This file is part of the Perl 6 Archive

Note: these documents may be out of date. Do not use as reference!

To see what is currently happening visit http://www.perl6.org/


type inference


  Maintainer: Steve Fink <steve@fink.com>
  Date: 1 Aug 2000
  Last Modified: 27 Aug 2000
  Mailing List: perl6-language@perl.org
  Number: 4
  Version: 2
  Status: Developing


Types should be inferred whenever possible


Removed static type declarations. That should be another RFC.


For large systems, and often for small ones, type checking is extremely valuable for optimization and error detection. It is particularly useful when trying to make global changes without introducing major errors by forgetting to update code. I propose that we create a type hierarchy, such as

         hash(T1 -> T2)
             object of class T

(This is just a sketch; there are many ways of skinning this cat.) Types will be inferred based on constants and operators. The inference process would assign a type or set of possible types to every node in the parse tree. Variables would not have a single type (unless explicitly constrained by a declaration); they would have a possibly different type after every assignment. So using the default rules

   1 $x = 3;
   2 $x .= "x";
   3 $h{$x} = \$x;
   4 $h{foo} = "bar";
   5 $x = f();

$x would have type number after line 1 and nonref after line 2. %h would have type hash(nonref -> ref(nonref)) after line 3. The effects of line 4 depend on the implementation. Possible results include hash(nonref -> scalar) and the union type hash(nonref -> ref(nonref)) union hash(nonref -> nonref). Line 5's effect depends on whether f()'s type is known. If not, then $x will have type any after line 5.

Note that so far, all existing programs will always typecheck successfully, so no burden has been placed on the programmer who does not want types. Also note that the linear, 1-pass process above is a dramatic oversimplification of a realistic type inference algorithm.


None required. The output of p52p6 may be run through the inferencer, but not even native Perl6 code will be required to make it through the type inferencer without errors.


Still being thought out. I'm hoping to use Ole Agesen's CPA (Cartesian Product Algorithm) to deal with functional polymorphism, and some variant of Plevyak and Chien's iterative algorithm to deal with the harder problem of data polymorphism.


There are several problematic constructs for type inferencing.


Ole Agesen. Concrete Type Inference : Delivering Object-Oriented Applications. PhD thesis, Department of Computer Science of Stanford University, Published by Sun Microsystem Laboratories (SMLI TR-96-52), 1996.

It's a long thesis, but it's by far the most clear description of type inferencing that I've found. He uses almost no formulas, and instead describes things in terms of graphs and pictures. He has a much shorter paper that summarizes his contributions that I haven't read yet.

John Plevyak, Andrew A. Chien. Iterative Flow Analysis. citeseer.nj.nec.com

They wrote a bunch of similar papers, I'm not sure which is best. Their stuff is tackling data polymorphism more directly, and I think that's the harder and more important problem for inferring types in Perl6.


Ken Fox gave some helpful advice and suggestions, particularly to avoid confusing static type checking with type inference.

Hildo Biersma had several useful comments that I've partly integrated and am partly still thinking about.