Rodney A. Brooks
Richard P. Gabriel
Guy L. Steele
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.
- 1.United States Department of Defense. "Preliminary ADA Reference Manual." SIGPLAN Notices 14, 6A (June 1979). Google Scholar
Digital Library
- 2.Reference Manual for the ADA Programming Language Proposed Standard Document. United States Department of Defense (1980).Google Scholar
- 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.Google Scholar
- 4.Arsac, Jacques J. "Syntactic Source to Source Transforms and Program Manipulation." Comm. ACM 22, 1 (Jan. 1979), 43-54. Google ScholarDigital Library
- 5.Baker, Henry B., Jr. "Shallow Binding in LISP 1.5." Comm. ACM 21, 7 (July 1978), 565-569. Google ScholarDigital Library
- 6.Bobrow, Daniel G. and Wegbreit, Ben. "A Model and Stack Implementation of Multiple Environments." Comm. ACM 16, 10 (Oct. 1973), 591-603. Google ScholarDigital Library
- 7.Burstall, R.M., and Darlington, John. "A Transformation System for Developing Recursive Programs." J. ACM 24, 1 (Jan. 1977), 44-67. Google ScholarDigital Library
- 8.Carter, J. Lawrence. "A Case Study of a New Code Generation Technique for Compilers." Comm. ACM 20, 12 (Dec. 1977), 914-920. Google ScholarDigital Library
- 9.Church, Alonzo. Annals of Mathematics Studies Volume 6: The Calculi of Lambda Conversion. Princeton University Press (Princeton, 1941). Reprinted by Klaus Reprint Corp. (New York, 1965). Google ScholarDigital Library
- 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}.Google ScholarDigital Library
- 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}.Google ScholarDigital Library
- 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.Google Scholar
- 13.PDP-II Handbook. Digital Equipment Corporation (Maynard, Massachusetts, 1969).Google Scholar
- 14.DecSystem 10 Assembly language Handbook (third edition.). Digital Equipment Corporation (Maynard, Massachusetts, 1973).Google Scholar
- 15.VAX Architecture Itandbook. Digital Equipment Corporation (Maynard, Massachusetts, 1981).Google Scholar
- 16.Falkoff, A.D., and Orth, D.L. "'Development of an APL Standard." APL 79 Conference Proceedings. ACM SIGPLAN/STAPL (Rochester, New York, June 1979), 409-453. Proceedings published as APL Quote Quad 9, 4 (June 1979). Google ScholarDigital Library
- 17.Fateman, Richard J. "Reply to an Editorial." ACM SIGSAM Bulletin (March 1973), 9-11. 273 Google ScholarDigital Library
- 18.Ford, Gary, and Hansche, Brian. "Optional, Repeatable, and Varying Type Parameters." SIGPLAN Notices 17, 2 (Feb. 1982), 41-48. Google ScholarDigital Library
- 19.Galley, S.W. and Pfistcr, Greg. The MDL Language Programming Technology Division Document SYS.11.01, MIT Project MAC (Cambridge, Massachusetts, Nov. 1975).Google Scholar
- 20.Geschke, Charles M. Global Program Optimizations. Ph.D. Th., Carnegie-Mellon University (Pittsburgh, Oct. 1972). Google ScholarDigital Library
- 21.Goldberg, Adele, and Kay, Alan. Smalltalk-72 Instruction Manual. Learning Research Group, Xerox Palo Alto Research Center (Palo Alto, California, March 1976).Google Scholar
- 22.Harrison, William. "A New Strategy for Code Generation: The General Purpose Optimizing Compiler." Proceedings of the Fourth Symposium on Principles of Programming Languages. Association for Computing Machinery (Los Angeles, Jan. 1977), 29-37. Google ScholarDigital Library
- 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}.Google ScholarDigital Library
- 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}.Google ScholarDigital Library
- 25.APL\360 User's Manual International Business Machines Corporation (1968).Google Scholar
- 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.Google ScholarDigital Library
- 27.Jensen, Kathleen, and Wirth, Niklaus. Pascal User Manual and Report. Springer-Veflag (New York, 1974). Google ScholarDigital Library
- 28.Johnsson, Richard Karl. An Approach to Global Register Allocation. Ph.D. Th., Carnegie-Mellon University (Pittsburgh, Dec. 1975). Google ScholarDigital Library
- 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).Google Scholar
- 30.Levine, Ronald D. "Supercomputers." Scientific American 246, 1 (Jan, 1982), 118-135.Google ScholarCross Ref
- 31.The Mathlab Group. MACSYMA Reference Manual (Version Nine). MIT Lab. for Computer Science (Cambridge, Massachusetts, 1977).Google Scholar
- 32.Moon, David. MacLISP Reference Manual, Revision O. M.I.T. Project MAC (Cambridge, Massachusetts, April 1974).Google Scholar
- 33.Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, June 1970).Google Scholar
- 34.Naur, Peter (ed.), et at. "Revised Report on the Algorithmic Language ALGOl, 60." Comm. ACM 6, 1 (Jan. 1963), 1-20. Google ScholarDigital Library
- 35.Organick, Elliot I. The Multics System: An Examination of Its Structure. MIT Press (Cambridge, Massachusetts, 1972). Google ScholarDigital Library
- 36.Rees, Jonathan. Private communication.Google Scholar
- 37.Sammet, Jean E. Programming Languages: History and Fundamentals Prentice-Hall (Englewood Cliffs, New Jersey, 1969). Google ScholarDigital Library
- 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).Google Scholar
- 39.Schroeder, Michael D., and Saltzer, Jerome H. "A Hardware Architecture for Implementing Protection Rings." Comm. ACM 15, 3 (March 1972), 157-170. Google ScholarDigital Library
- 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).Google Scholar
- 41.Standish, Thomas A.; Kibler, Dennis F.: and Neighbors, James M. "Improving and Refining Programs by Program Manipulation." Proceedings of the ACM National Conference. Association for Computing Machinery (Houston, Texas, Oct. 1976), 509-516. Google ScholarDigital Library
- 42.Steele, Guy Lewis Jr. LAMBDA: The Ultimate Declarative. AI Memo 379, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, Nov. 1970. Google ScholarDigital Library
- 43.Steele, Guy Lewis Jr., and Sussman, Gerald Jay: LAMBDA: The Ultimate Imperative. AI Memo 353, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, March 1976). Google ScholarDigital Library
- 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}.Google Scholar
- 45.Steele, Guy Lewis Jr. Compiler Optimization Based on Viewing LAMBDA as Rename plus Goto. Master Th., MIT (May 1977). Published as {49}.Google Scholar
- 46.Steele, Guy Lewis Jr. "Debunking the 'Expensive Procedure Call' Myth; or, Procedure Call Implementations Considered Harmful; or, LAMBDA: "File Ultimate GOTO. Proceedings of the ACM National Conference. Association for Computing Machinery (Seattle, Oct. 1977), 153-162. Revised version published as {47}. Google ScholarDigital Library
- 47.Steele, Guy Lewis Jr. Debunking the "Expensive Procedure Call' Myth; or, Procedure Call Implementations Considered Itermful; or, LAMBDA: The Ultimate GOTO. AI Memo 443, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, Oct. 1977). This is a revised version of {46}. Google ScholarDigital Library
- 48.Steele, Guy Lewis Jr. Fast Arithmetic in MacLISP. AI Memo 421, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, Sept. 1977). Also appeared as {44}.Google Scholar
- 49.Steele, Guy Lewis Jr. RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization). Tech. Rept. 474, M1T Artificial Intelligence Lab. (May 1978). This is a revised version of the author's master's thesis 1451. Google ScholarDigital Library
- 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).Google Scholar
- 51.Sussman, Gerald Jay, and Steele, Guy Lewis Jr. SCHEME: An Interpreter for Extended Lambda Calculus. Tech. Repl 349, MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, Dec. 1975). Google ScholarDigital Library
- 52.Teitelman, Warren, et al. InterLISP Reference Manual. Xerox Palo Alto Research Center (Palo Alto, California, 1975). Second revision.Google Scholar
- 53.Teitelman, Warren, et al. InterLISP Reference Manual Xerox Palo Alto Research Center (Palo Alto, California, 1978). Third revision.Google Scholar
- 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,Google Scholar
- 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).Google Scholar
- 56.Weinreb, Daniel, and Moon, David. LISP Machine Manual Fourth Edition. MIT Artificial Intelligence Lab. (Cambridge, Massachusetts, July 1981). Google ScholarDigital Library
- 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.Google Scholar
- 58.Wulf William; Johnsson, Richard K.: Weinstock, Charles B.; Hobbs, Stcven O.; and Geschke, Charles M. Programming Language Seriex Volume 2: The Design of an Optimizing Compiler. American Elsevier (New York, 1975). Google ScholarDigital Library
Index Terms
- An optimizing compiler for lexically scoped LISP
Recommendations
An optimizing compiler for lexically scoped LISP
Proceedings of the 1982 SIGPLAN symposium on Compiler constructionWe 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 ...
EPIC - a retargetable, highly optimizing Lisp compiler
The Experimental Portable Standard Lisp Compiler (EPIC) is a compiler testbed for experimentation with, and development of, Lisp compilation strategies. EPIC uses an architectural description of the target machine to increase portability, and performs ...
RICE: An Optimizing Curry Compiler
Practical Aspects of Declarative LanguagesAbstractThis paper introduces the RICE compiler, an optimizing compiler for the functional logic language Curry, written entirely in Curry. We show the advantages of using Curry as an implementation language by creating a robust optimizer that is easy to ...
Comments