Open AccessMaking Type Inference Practical
Author(s) -
Nicholas Oxhøj,
Jens Palsberg,
Michael I. Schwartzbach
Publication year - 1992
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v21i385.6618
Subject(s) - computer science , inference , type inference , programming language , theoretical computer science , graph , source code , annotation , object (grammar) , inheritance (genetic algorithm) , constraint (computer aided design) , time complexity , algorithm , artificial intelligence , mathematics , biochemistry , chemistry , geometry , gene
We present the implementation of a type inference algorithm for untyped object-oriented programs with inheritance, assignments, and late binding.The algorithm significantly improves our previous one, presented at OOPSLA'91, since it can handle collection classes, such as {\bf List}, in a useful way. Also, the complexity has been dramatically improved, from exponential time to low polynomial time. The implementation uses the techniques of incremental graph construction and constraint template instantiation to avoid representing intermediate results, doing superfluous work, and recomputing type information. Experiments indicate that the implementation type checks as much as 100 lines pr. second. This results in a mature product, on which a number of tools can be based, for example a safety tool, an image compression tool, a code optimization tool, and an annotation tool. This may make type inference for object-oriented languages practical.