Tags and type checking in LISP: hardware and software approaches

Abstract

One of the major factors that distinguishes LISP from many other languages (Pascal, C, Fortran, etc.) is the need for run-time type checking. Run-time type checking is implemented by adding to each data object a tag that encodes type information. Tags must be compared for type compatibility, removed when using the data, and inserted when new data items are created. This tag manipulation, together with other work related to dynamic type checking and generic operations, constitutes a significant component of the execution time of LISP programs. This has led both to the development of LISP machines that support tag checking in hardware and to the avoidance of type checking by users running on stock hardware. To understand the role and necessity of special-purpose hardware for tag handling, we first measure the cost of type checking operations for a group of LISP programs. We then examine hardware and software implementations of tag operations and estimate the cost of tag handling with the different tag implementation schemes. The data shows that minimal levels of support provide most of the benefits, and that tag operations can be relatively inexpensive, even when no special hardware support is present.

References

1. Bawden, A., Greenblatt, R., Holloway, J., Knight, T., Moon, D., and Weinreb, D. LISP Machine Progress Report. Memo No 444, MIT Artificial Intelligence Laboratory, August, 1977.
2. Bosshart, P., Hewes, C., Chang, M., and Chau, K. A 553K-Transistor LISP Processor Chip. Digest 1987 International Solid-State Circuits Conference, IEEE, New York, February, 1987, pp. 202--203.
3. Brooks, R., Posner, D., McDonald, J., White, J., Benson, E., and Gabriel, R. Design of An Optimizing, Dynamically Retargetable Compiler for Common Lisp. Proceedings of the 1986 Conference on LISP and Functional Programming, ACM, Boston, August, 1986, pp. 67--85.
4. Charniak, E., Riesbeck, C. K., and McDermott, D. V. Artificial Intelligence Programming. Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1980.
5. Chow, P., and Horowitz, M. Architectural Tradeoffs in the Design of MIPS-X. Proceedings of the 14th Annual International Symposium on Computer Architecture, ACM, June, 1987, pp.
6. Corley, C. J. and Statz, J. A. "LISP workstation brings AI power to a user's desk". Computer Design 24, 1 (January 1985).
7. Gabriel, R. P. Computer Systems Series. Volume: Performance and evaluation of LISP systems. The MIT Press, 1985.
8. Griss, M. L. and Hearn, A. C. "A Portable LISP Compiler". Software - Practice and Experience 11, 6 (June 1981), 541--605.
9. Griss, M. L., Benson, E., and Maguire, G. Q. PSL:A Portable LISP System. Proceedings of the 1982 Symposium on LISP and Functional Programming, Pittsburgh, August, 1982, pp. 88--97.
10. Horowitz, M., Hennessy, J., Chow, P., Gulak, P., Acken, J., Agarwal, A., Chu, C. Y., McFarling, S., Przybylski, S., Richardson, S., Salz, A., Simoni, R., Stark, D., Steenkiste, P., Tjiang, S., and Wing, M. A 32b Microprocessor with On-Chip 2K Byte Instruction Cache. Digest 1987 International Solid-State Circuits Conference, IEEE, New York, February, 1987, pp. 30--31.
11. Kranz, D., Kelsey, R., Rees, R., Hudak, P., Philbin, J. and Adams, N. ORBIT: An Optimizing Compiler for Scheme. Proceedings of the SIGPLAN'86 Symposium on Compiler Construction, ACM, Palo Alto, June, 1986, pp. 219--233.
12. Milner, R. "A Theory of Type Polymorphism in Programming". Journal of Computer and System Science 17, 3 (December 1978), 348--375.
13. Moon, D. A. Maclisp Reference Manual. MIT, Laboratory of Computer Science, 1983.
14. Moon, D. A. Architecture of the Symbolics 3600. Proceedings of the 12th Annual International Symposium on Computer Architecture, ACM, Boston, June, 1985, pp. 76--83. Also in SIGARCH Newsletter 13(3).
15. Rees, J. and Adams, N. T: A Dialect of Lisp or, or LAMBDA: The Ultimate Software Tool. Proceedings of the 1982 Symposium on LISP and Functional Programming, Pittsburgh, August, 1982, pp. 114--122.
16. Steele, G. L. Jr. Fast Arithmetic in MacLISP. Proceedings of the 1977 MACSYMA Users' Conference, July, 1977.
17. Steele, G. L. Jr. Common Lisp - The Language. Digital Press, 1984.
18. Steenkiste, P., and Hennessy, J. LISP on a Reduced-Instruction-Set-Processor. Proceedings of the 1986 Conference on LISP and Functional Programming, ACM, Boston, August, 1986, pp. 192--201.
19. Steenkiste, P. LISP on a Reduced-Instruction-Set Processor: Characterization and Optimization. Ph.D. Th., Stanford University, March 1987.
20. Stritter, E., and Gunter, T. "A Microprocessor Architecture for a Changing World: The Motorola 68000". IEEE Computer 12, 2 (February 1979), 43--52.
21. Taylor, G. S., Hillfinger, P. N. Larus, J., et al. Evaluation of the SPUR Lisp Architecture. Proceedings of the 13th Annual International Symposium on Computer Architecture, ACM, Tokyo, June, 1986, pp. 444--452.
22. Ungar, D. The Design and Evaluation of A High Performance Smalltalk System. Ph.D. Th., UC Berkeley, March 1986. Technical Report UCB/CSD 86/287.
23. White, J. "LISP/370: A Short Technical Description of the Implementation". SIGSAM 12, 4 (November 1978), 23--27.
24. White, J. Reconfigurable, Retargetable Bignums. Proceedings of the 1986 Conference on LISP and Functional Programming, ACM, Boston, August, 1986, pp. 174--191.
25. Winston, P. and Horn, B. Lisp. Addison-Wesley Publishing Company, 1981.

Index Terms

• Computer systems organization

  • Architectures

    • Serial architectures

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

      • Language types