An optimizing compiler for lexically scoped LISP

ABSTRACT

We are developing an optimizing compiler for a dialect of the LISP language. The current target architecture is the S-I, a multiprocessing supercomputer designed at Lawrence Livermore National Laboratory. While LISP is usually thought of as a language primarily for symbolic processing and list manipulation, this compiler is also intended to compete with the S-1 PASCAL and FORTRAN compilers for quality of compiled numerical code. The S-1 is designed for extremely high-speed signal processing as well as for symbolic computation; it provides primitive operations on vectors of floating-point and complex numbers. The LISP compiler is designed to exploit the architecture heavily. The compiler is structurally and conceptually similar to the BLISS-11 compiler and the compilers produced by PQCC. In particular, the TNBIND technique has been borrowed and extended.

REFERENCES

• 1: J. D. Ichbiah, Preliminary Ada reference manual, ACM SIGPLAN Notices, v.14 n.6a, p.1-145, June 1979 [doi>10.1145/956650.956651]
• 2: Reference Manual for the ADA Programming Language Proposed Standard Document. United States Department of Defense (1980).
• 3: Allen, Frances E., and Cocke, Jolm. "A Catalogue of Optimizing Transformations.'" In Design and Optimization of Compilers, Rustin, Randall (Ed.), Prentice-Hall (Englewood Cliffs, N.J., 1972), 1-30.
• 4: Jacques J. Arsac, Syntactic source to source transforms and program manipulation, Communications of the ACM, v.22 n.1, p.43-54, Jan. 1979 [doi>10.1145/359046.359057]
• 5: Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
• 6: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 7: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 8: J. Lawrence Carter, A case study of a new code generation technique for compilers, Communications of the ACM, v.20 n.12, p.914-920, Dec. 1977 [doi>10.1145/359897.359902]
• 9: Alonzo Church, The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies), Princeton University Press, Princeton, NJ, 1985
• 10: Coonen, Jerome T. "An Implementation Guide to a Proposed Standard for Floating-Point Arithmetic." Computer 13, 1 (Jan. 1980)', 68-79. Errata for this paper appeared as {11}.
• 11: Coonen, Jerome T. "Errata for 'An Implementation Guide to a Proposed Standard for Floating-Point Arithmetic'." Computer 14, 3 (March 1981), 62. These are errata for {10}.
• 12: Correll, Steven. "S-1 Uniprocessor Architecture (SMA-4)." In The S-I Project 1979 Annual Report, Lawrence Livermore Laboratory (Livermore, California, 1979), Chapter 4.
• 13: PDP-II Handbook. Digital Equipment Corporation (Maynard, Massachusetts, 1969).
• 14: DecSystem 10 Assembly language Handbook (third edition.). Digital Equipment Corporation (Maynard, Massachusetts, 1973).
• 15: VAX Architecture Itandbook. Digital Equipment Corporation (Maynard, Massachusetts, 1981).
• 16: A. D. Falkoff , D. L. Orth, Development of an APL standard, Proceedings of the international conference on APL: part 2, p.409-453, May 30-June 01, 1979, New York, New York, United States
• 17: R. J. Fateman, Reply to an editorial, ACM SIGSAM Bulletin [doi>10.1145/1086803.1086804]
• 18: Gary Ford , Brian Hansche, Optional, repeatable, and varying type parameters, ACM SIGPLAN Notices, v.17 n.2, p.41-48, February 1982 [doi>10.1145/947902.947906]
• 19: Galley, S.W. and Pfistcr, Greg. The MDL Language Programming Technology Division Document SYS.11.01, MIT Project MAC (Cambridge, Massachusetts, Nov. 1975).
• 20: Charles Matthew Geschke, Global program optimizations., 1973
• 21: Goldberg, Adele, and Kay, Alan. Smalltalk-72 Instruction Manual. Learning Research Group, Xerox Palo Alto Research Center (Palo Alto, California, March 1976).
• 22: William Harrison, A new strategy for code generation: the general purpose optimizing compiler, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-37, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512954]
• 23: Hewitt, Carl. "Viewing Control Structures as Patterns of Passing Messages." Artificial Intelligence8, 3 (June 1977), 323-364. A comment on this paper appeared as {24}.
• 24: Hewitt, Carl. "Comments on 'Viewing Control Structures as Patterns of Passing Messages'." Artificial Intelligence 10, 3 (Nov. 1978), 317-318. This is a comment on {23}.
• 25: APL\360 User's Manual International Business Machines Corporation (1968).
• 26: IEEE Computer Society Standard Committee, Microprocessor Standards Subcommittee. Floating-Point Working Group. "A Proposed Standard for Binary Floating-Point Arithmetic." Computer 14, 3 (March 1981), 51-62.
• 27: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 28: Richard Karl Johnsson, An approach to global register allocation., 1976
• 29: Leverett, Bruce W.; Cattell, Roderic G.G.; Hobbs, Steven O.; Newcomer, Joseph M.; Reiner, Andrew H.; Schatz, Bruce R.; and Wulf, William A. An Overview of the Production Quality Compiler-Compiler Project. Tech. Rept. CMU-CSD-79-105, Carnegie-Mellon University Computer Science Department (Pittsburgh, Feb. 1979).
• 30: Levine, Ronald D. "Supercomputers." Scientific American 246, 1 (Jan, 1982), 118-135.
• 31: The Mathlab Group. MACSYMA Reference Manual (Version Nine). MIT Lab. for Computer Science (Cambridge, Massachusetts, 1977).
• 32: Moon, David. MacLISP Reference Manual, Revision O. M.I.T. Project MAC (Cambridge, Massachusetts, April 1974).
• 33: Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, June 1970).
• 34: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 35: Elliott I. Organick, The Multics System: An Examination of Its Structure, The MIT Press, 1972
• 36: Rees, Jonathan. Private communication.
• 37: Jean E. Sammet, Programming languages: history and future, Communications of the ACM, v.15 n.7, p.601-610, July 1972 [doi>10.1145/361454.361485]
• 38: Schatz, Bruce R. Algorithms for Optimizing Transformations in a General Purpose Compiler: Propagation and Renaming. Tech. RepL RC 6232 (#26773), IBM Thomas J. Watson Research Center (Yorktown Heights, New York, Oct. 1976).
• 39: Michael D. Schroeder , Jerome H. Saltzer, A hardware architecture for implementing protection rings, Communications of the ACM, v.15 n.3, p.157-170, March 1972 [doi>10.1145/361268.361275]
• 40: Standish, T.A.; Harriman, D.C.; Kibler, D.F.; and Neighbors, J.M. The lrvine Program Transformation Catalogue. University of California (Irvine, California, Jan. 1976).
• 41: Thomas A. Standish , Dennis F. Kibler , James M. Neighbors, Improving and refining programs by program manipulation, Proceedings of the annual conference, p.509-516, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805652]
• 42: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 43: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 44: Steele, Guy Lewis Jr. "Fast Arithmetic in MacLISP." Proceedings of the 1977 MACSYMA Users" Conference. NASA Scientific and Technical Information Office (Washington, D.C., July 1977), 215-224. Also published as {48}.
• 45: Steele, Guy Lewis Jr. Compiler Optimization Based on Viewing LAMBDA as Rename plus Goto. Master Th., MIT (May 1977). Published as {49}.
• 46: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 47: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 48: Steele, Guy Lewis Jr. Fast Arithmetic in MacLISP. AI Memo 421, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, Sept. 1977). Also appeared as {44}.
• 49: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 50: Steele, Guy Lewis Jr., and Sussman, Gerald Jay. The Revised Report on SCHEME: A Dialect of LISP. AI Memo 452, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, Jan. 1978).
• 51: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 52: Teitelman, Warren, et al. InterLISP Reference Manual. Xerox Palo Alto Research Center (Palo Alto, California, 1975). Second revision.
• 53: Teitelman, Warren, et al. InterLISP Reference Manual Xerox Palo Alto Research Center (Palo Alto, California, 1978). Third revision.
• 54: van Wijngaarden, A.; MaiUoux, B.J.; Peck, J.E.L.; Koster, C.H.A.; Sintzoff, M.; Lindsey. C.H.; Merrtens, L.G.L.T.; and Fisker, R.G. (eds.). "Revised Report on the Algorithmic Language ALGOL 68." SIGPLAN Notices 12, 5 (May 1977), 1-70,
• 55: Wegbreit, Ben; Holloway, Glenn; Spitzen, Jay; and Townley, Judy. ECL Programmer's Manual. Tech. Rept. 23-74, Harvard University Center for Research in Computing Technology (Cambridge, Massachusetts, Dec. 1974).
• 56: Daniel Weinreb, Lisp machine manual, Massachusetts Institute of Technology, 1981
• 57: White, Jon L. "LISP: Program is Data: A Historical erspective on Macl.ISP." Proceedings of the 1977 MACSYMA Users' Conference. NASA Scientific and Technical Information Office (Washington, D.C., July 1977), 181-189.
• 58: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages