Type Inference for an Interpretive Language

Folks,


I am writing a compiler for a language which is currently interpretive.
The goal is to create objects which are much faster (order of magnitude,
at least) than the interpretive versions. The language does not require
(indeed, has no mechanism for), variable declarations; the type and size
of storage for every variable and formal parameter is determined at each
use. Therefore, an assignment like


      A = B + C


can change the type and the storage for A depending on B and C; the
operation "+" may have different (though predefined) effects depending on
the types and sizes of B and C). The languge is otherwise a
straightforward imperative, procedural language not so different from
Basic, say.


Therefore, I am interested in algorithms to infer the types of variables
and to fix the types of polymorphic operators. I am familiar with some of
the work of Meertens on B, Mitchell on inference and coercion, several
works on Smalltalk inference and on ML inference, of Fagan and Cartwright
on soft typing, and of Chambers and Ungar on SELF. There is a brief note
in Aho, Sethi, and Ullman (Red Dragon) that the general problem of type
inference for variables in languages with function polymorphism is
undecidable; they suggest that this is a result coming from the work with
HOPE. I have not been able to track that result down.


I would appreciate any comments or pointers the readers of this group
might be able to give to


      further theoretical work on type inference


      type inference in the presence of traditional flow


      interprocedural type inference


      type inference in practical languages


      translations systems which use type inference


Please mail your comments to me; if there is enough to warrant, I will
summarize and post to the net.


Thank you in advance for your help


Charles Wetherell
csw@btr.com
--

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