A practical approach to type inference for EULISP

LISP applications need to show a reasonable cost-benefit relationship between the offered expressiveness and their demand for storage and run-time. Drawbacks in efficiency, apparent in LISP as a dynamically typed programming language, can be avoided by doing compiling optimizations. Statically inferred type information can be decisive for the success of these optimizations. This paper describes a practical approach to type inference used in a module and application compiler for EuLISP. The approach is related to Milner-style polymorphic type inference, but differs by handling refined types, e.g., cons-nodes, recursive lists, structures, classes, singleton types and fine-grained number types, in the absence of type declarations. Due to module compilation inferred type signatures of exported functions are provided in export interfaces, in order to reuse them for later import. The type inference is integrated with the process of compilation to make use of information previously analysed i n the front-end and to be much better adapted to code generation and storage management.