LISP and Symbolic Computation, 6(1/2)159-176
A Practical Approach to Type Inference for EuLispAndreas Kind, Fraunhofer Institute for Software Engineering and Systems Engineering (ISST), Kurstrasse 33, 10117 Berlin, Germany
Horst Friedrich, Fraunhofer Institute for Software Engineering and Systems Engineering (ISST), Kurstrasse 33, 10117 Berlin, Germany
|
Abstract: 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 combined into the type lattice. Local, global and control flow inference using generic type schemes with refined types generate precise typings of defined 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. Keywords: type inference, Lisp, compilation, unification |
[local copy]
![[picture of journal cover]](../LISP.JPG)