A Framework for Ad-Hoc Type Inference

A Framework for Ad-Hoc Type Inference

Hosein Askari
Ole I. Hougaard
Michael I. Schwartzbach

In 6th NWPT, pages 36-50


Languages based on variations of the lambda calculus are designed to permit the slick, unification-based technique for type inference, which is by now a well-established discipline.

Other widely used languages have been created less by design and more by coincidence and compromise. It seems therefore that the question of type inference for such languages could be infeasible or should at least permit only ad-hoc solutions.

In this paper we argue the existence of a uniform framework for developing type inference algorithms, even for seemingly ad-hoc languages. This framework provides useful generalizations of well-known concepts related to type inference. It is, however, by no means a universal algorithm. In fact, the essential algorithmic problem must generally be solved from scratch.

We demonstrate the viability of our approach by developing a type inference algorithm for a full version of the Turbo Pascal language.

BRICS, Department of Computer Science, University of Aarhus, 8000 Aarhus C, Denmark.

Available as PostScript, DVI.

[BRICS symbol] BRICS WWW home page