A practical approach to type inference for EuLisp
Tóm tắt
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 inLisp 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 forEuLisp. The approach is partly related to Milner-style polymorphic type inference, but differs by describing functions withgeneric 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-calledstrategic 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.
Tài liệu tham khảo
Baker, H. G. The Nimble type inferencer for Common Lisp-84. (April 1990). Pre-publication version.
Beer, R. D. Preliminary report on a practical type inference system for Common Lisp.Lisp Pointers, 1, 4 (1987) 5–11.
Bretthauer, H., Christaller, Th., Friedrich, H., Goerigk, W., Heicking, W., Hoffmann, U., Hovekamp, D., Knutzen, H., Kopp, J., Kriegel, E. U., Mohr, I., Rosenmüller, R., and Simon, F. Das Verbundvorhaben APPLY: Ein modernes und bedarfsgerechtes Lisp.KI, 2 (June 1992) 50–54.
Harper, R.Introduction to Standard ML. Report ECS-LFCS-86-14, University of Edinburgh (November 1986). Laboratory for Foundations of Computer Science.
Henglein, F. Global tagging optimization by type inference. InSymposium on Lisp and Functional Programming, ACM (1992) 205–215.
Jones, N. D. and Muchnick, S. Binding time optimization in programming languages. InThird Symposium on Principles of Programming Language (1976) 77–94.
Kaplan, M. A. and Ullman, J. D. A scheme for the automatic inference of variable types.Journal of the ACM, 27, 1 (January 1980) 128–145.
Ma, K.-L. and Kessler, R. R. TICL—A type inference system for Common Lisp.Software—Practice and Experience, 20, 6 (June 1990) 593–623.
Milner, R. A theory of type polymorphism in programming.Journal of Computer and System Sciences,, 17 (1978) 348–375.
Milner, R. A proposal for standard ML. InACM Symposium on Lisp and Functional Programming (1984) 184–197.
Padget, J., Nuyens, G., and Bretthauer, H. (eds.). An overview of EuLisp. (1993). In this issue.
Robinson, J. A. A machine-oriented logic based on the resolution principle.Journal of the ACM, 12, 1 (1965) 23–41.
Steenkiste, P. and Hennessy, J. Tags and type checking in Lisp: Hardware and software approaches. InSecond International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (October 1987).