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 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 polymorphic type inference, but differs by describing functions with generic type schemes. Dependencies between argument and result types can be expressed more precisely by using generic type schemes of several lines than by using the common one-line type schemes. Generic type schemes contain types of a refined complementary lattice and bounded type variables. Besides standard and defined types so-called strategic types (e.g. singleton, zero, number-list) are combine..