c 1993 Kluwer Academic Publishers { Manufactured in The Netherlands A Practical Approach to Type Inference for EuLisp

Abstract. Lisp applications need to show a reasonable cost-benet relationship be-tween the oered expressiveness and their demand for storage and run-time. Drawbacks in eciency, apparent in Lisp as a dynamically typed programming language, can be avoided by optimizations. Statically inferred type information can be decisive for the success of these optimizations. This paper describes a practical approach to type inference realized in a module and application compiler for EuLisp. The approach is partly related to Milner-style poly-morphic type inference, but diers by describing functions with generic type schemes. Dependencies between argument and result types can be expressed more precisely by us-ing generic type schemes of several lines than by using the common one-line type schemes. Generic type schemes contain types of a rened complementary lattice and bounded type variables. Besides standard and dened types so-called strategic types (e.g. singleton, zero, number-list) are combined into the type lattice. Local, global and control ow in-ference using generic type schemes with rened types generate precise typings of dened functions. Due to module compilation, inferred type schemes of exported functions can be stored in export interfaces, so they may be reused when imported elsewhere. 1