Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO

ABSTRACT

Folklore states that GOTO statements are “cheap”, while procedure calls are “expensive”. This myth is largely a result of poorly designed language implementations. The historical growth of this myth is considered. Both theoretical ideas and an existing implementation are discussed which debunk this myth. It is shown that the unrestricted use of procedure calls permits great stylistic freedom. In particular, any flowchart can be written as a “structured” program without introducing extra variables. The difficulty with the GOTO statement and the procedure call is characterized as a conflict between abstract programming concepts and concrete language constructs.

REFERENCES

• 1: Allen, Frances E., and Cocke, John. "A Catalogue of Optimizing Transformations." In Rustin, Randall (ed.), Design and Optimization of Compilers. Proc. Courant Comp. Sci. Symp. 5. Prentice-Hall (Englewood Cliffs, N.J., 1972).
• 2: American National Standards Institute. Draft proposed ANS FORTRAN (BSR X3.9). Reprinted as SIGPLAN Notices 11, 3 (March 1976).
• 3: Auslander, M.A., and Strong, H.R. Systematic Recursion Removal. Report RC 5841 (#25283) IBM T.J. Watson Research Center (Yorktown Heights, New York, February 1976).
• 4: 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]
• 5: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 6: Church, Alonzo. The Calculi of Lambda Conversion. Annals of Mathematics Studies Number 6. Princeton University Press (Princeton, 1941). Reprinted by Klaus Reprint Corp. (New York, 1965).
• 7: Darlington, J., and Burstall, R. M. "A System which Automatically Improves Programs." Acta Informatica 6 (1976), 41-60.
• 8: Digital Equipment Corporation. PDP-10 COBOL Language Programmer's Reference Manual. DEC-10-KCIA-D (Maynard, Mass., 1969).
• 9: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 10: R. J. Fateman, Reply to an editorial, ACM SIGSAM Bulletin [doi>10.1145/1086803.1086804]
• 11: Hopper, Captain Grace Murray. In "An Interview with Captain Grace Murray Hopper, USNR". Computing (October 10, 1973). Reprinted in SIGPLAN Notices 9, 1 (January 1974), 3-6.
• 12: International Business Machines. IBM System/360 Operating System COBOL Language. Form C28-6516-8. Ninth Edition (November 1968).
• 13: International Business Machines. IBM System/360 Operating System American National Standard COBOL. Form GC28-6396-2. Third edition (June 1970).
• 14: International Business Machines. IBM System/360 Operating System PL/I (F) Language Reference Manual. Form GC28-8201-3. Revised (November 1970).
• 15: Jenks, Richard D., and Griesmer, James H. "Editor's Comment." SIGSAM Bulletin No. 24 (October 1972), 2-3.
• 16: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 17: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 18: Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT AI Lab (Cambridge, June 1970).
• 19: Neighbors, Michael A. "Assuring Software Reliability." Computer Decisions 8, 12 (December 1976), 44-46.
• 20: Leon Presser, Structured languages, ACM SIGPLAN Notices, v.10 n.7, July 1975 [doi>10.1145/987305.987311]
• 21: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 22: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 23: Steele, Guy Lewis Jr. Compiler Optimization Based on Viewing LAMBDA as RENAME plus GOTO. S.M. Thesis. MIT AI Lab (Cambridge, May 1977).
• 24: Steele, Guy Lewis Jr. "Fast Arithmetic in MacLISP." Proc. 1977 MACSYMA Users' Conference. NASA Sci. and Tech. Info. Office (Washington, D.C., July 1977), 215-224.
• 25: Strong, H.R., Jr. "Translating Recursion Equations into Flow Charts." Journal of Computer and System Sciences 5, 3 (June 1971), 254-285.
• 26: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 27: Sykes, Roy A., Jr. "Whizbang of the Month: Branching and Iteration." Scientific Time Sharing Corporation News 2, 10 (Bethesda, Maryland, January-February 1977), 5-6.
• 28: Wegbrert, Ben. "The ECL Programming System." Proc. AFIPS 1971 FJCC, Vol. 39. AFIPS Press, Montvale, N.J. pp. 253-262.
• 29: Wegbrert, Ben. et al. ECL Programmer's Manual. Technical Report 23-74. Center for Research in Computing Technology, Harvard U. (Cambridge, December 1974).
• 30: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]
• 31: W. Wulf , Mary Shaw, Global variable considered harmful, ACM SIGPLAN Notices, v.8 n.2, p.28-34, February 1973 [doi>10.1145/953353.953355]
• 32: 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
• 33: Edward Yourdon, Techniques of Program Structure and Design, Prentice Hall PTR, Upper Saddle River, NJ, 1986

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Structured programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages