Article

Free access

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

Author:

Guy Lewis Steele, Jr.Authors Info & Claims

ACM '77: Proceedings of the 1977 annual conference

Pages 153 - 162

https://doi.org/10.1145/800179.810196

Published: 01 January 1977 Publication History

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).]]

Digital Library

[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]

Bobrow, Daniel G. and Wegbreit, Ben. "A Model and Stack Implementation of Multiple Environments." Comm. ACM 16, 10 (October 1973) pp. 591-603.]]

Digital Library

[5]

Boehm, Corrado, and Jacopini, Guiseppe. "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules." Comm. ACM 9, 5 (May 1966), 366-371.]]

Digital Library

[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).]]

Digital Library

[7]

Darlington, J., and Burstall, R. M. "A System which Automatically Improves Programs." Acta Informatica 6 (1976), 41-60.]]

Digital Library

[8]

Digital Equipment Corporation. PDP-10 COBOL Language Programmer's Reference Manual. DEC-10-KCIA-D (Maynard, Mass., 1969).]]

[9]

Dijkstra, Edsger W. A Discipline of Programming. Prentice-Hall (Englewood Cliffs, N.J., 1976).]]

Digital Library

[10]

Fateman, Richard J. "Reply to an Editorial." SIGSAN Bulletin 25 (March 1973), 9-11.]]

Digital Library

[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]

McCarthy, John. "Recursive functions of symbolic expressions and their computation by machine - I." Comm. ACM 3, 4 (April 1960), 184-195.]]

Digital Library

[17]

McKeeman, W.M. "Peephole optimization." Comm. ACM 8, 7 (July 1965). 443-444.]]

Digital Library

[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]

Presser, Leon. "Structured Languages." Proc. National Computer Conference 1975. Reprinted in SIGPLAN Notices 10, 7 (July 1975), 22-24.]]

Digital Library

[21]

Steele, Guy Lewis Jr., and Sussman, Gerald Jay. LAMBDA: The Ultimate Imperative. AI Memo 353. MIT AI Lab (Cambridge, March 1976).]]

Digital Library

[22]

Steele, Guy Lewis Jr. LAMBDA: The Ultimate Declarative. AI Memo 379. MIT AI Lab (Cambridge, November 1976).]]

Digital Library

[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.]]

Digital Library

[26]

Sussman, Gerald Jay, and Steele, Guy Lewis Jr. SCHEME: An Interpreter for Extended Lambda Calculus. AI Memo 349. MIT AI Lab (Cambridge, December 1975).]]

Digital Library

[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]

Wulf, W.A., Russell, D.B., and Habermann, A.N. "BLISS: A Language for Systems Programming." Comm. ACM 14, 12 (December 1971), 780-790.]]

Digital Library

[31]

Wulf, William A., and Shaw, Mary. Global Variable Considered Harmful. SIGPLAN Notices 8, 2 (February 1973), 28-34.]]

Digital Library

[32]

Wulf, William A., et al. The Design of an Optimizing Compiler. American Elsevier (New York, 1975).]]

Digital Library

[33]

Yourdon, Edward. Techniques of Program Structure and Design. Prentice-Hall (Englewood Cliffs, N.J., 1975).]]

Digital Library

Cited By

Xu HKjolstad F(2021)Copy-and-patch compilation: a fast compilation algorithm for high-level languages and bytecodeProceedings of the ACM on Programming Languages10.1145/34855135:OOPSLA(1-30)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485513
Solomon CHarvey BKahn KLieberman HMiller MMinsky MPapert ASilverman B(2020)History of LogoProceedings of the ACM on Programming Languages10.1145/33863294:HOPL(1-66)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386329
Duta CGrust TMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Functional-Style SQL UDFs With a Capital 'F'Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389707(1273-1287)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389707
Show More Cited By

Index Terms

Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development techniques
  2. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures

Recommendations

C++ templates considered harmful

C++ is considered by many professional software developers and educators to be the lingua franca of programming languages. Once mastered, its power of expression is nearly limitless for the class of problems for which an imperative and object-oriented ...
Debunking the ``Expensive Procedure Call'''' Myth or, Procedure Call Implementations Considered Harmful or, LAMDBA: The Ultimate GOTO
Send-receive considered harmful: Myths and realities of message passing

During the software crisis of the 1960s, Dijkstra's famous thesis "goto considered harmful" paved the way for structured programming. This short communication suggests that many current difficulties of parallel programming based on message passing are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM '77: Proceedings of the 1977 annual conference

January 1977

505 pages

ISBN:9781450339216

DOI:10.1145/800179

Copyright © 1977 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1977

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ACM '77

Sponsor:

ACM

October 16 - 19, 1977

Washington, Seattle

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
3,660
Total Downloads

Downloads (Last 12 months)702
Downloads (Last 6 weeks)71

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu HKjolstad F(2021)Copy-and-patch compilation: a fast compilation algorithm for high-level languages and bytecodeProceedings of the ACM on Programming Languages10.1145/34855135:OOPSLA(1-30)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485513
Solomon CHarvey BKahn KLieberman HMiller MMinsky MPapert ASilverman B(2020)History of LogoProceedings of the ACM on Programming Languages10.1145/33863294:HOPL(1-66)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386329
Duta CGrust TMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Functional-Style SQL UDFs With a Capital 'F'Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389707(1273-1287)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389707
Durmaz CYildirim KKardas GHung CPapadopoulos G(2019)PureMEMProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299739(1544-1551)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299739
Das AHoffmann J(2017)ML for ML: Learning Cost Semantics by ExperimentTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-662-54577-5_11(190-207)Online publication date: 31-Mar-2017
https://doi.org/10.1007/978-3-662-54577-5_11
Iwasaki STaura KZaks AMendelson BRauchwerger LHwu W(2016)A Static Cut-off for Task Parallel ProgramsProceedings of the 2016 International Conference on Parallel Architectures and Compilation10.1145/2967938.2967968(139-150)Online publication date: 11-Sep-2016
https://dl.acm.org/doi/10.1145/2967938.2967968
Reus BReus B(2016)The WHILE-LanguageLimits of Computation10.1007/978-3-319-27889-6_3(29-45)Online publication date: 26-Mar-2016
https://doi.org/10.1007/978-3-319-27889-6_3
Tauber TBi XShi ZZhang WLi HZhang ZOliveira B(2015)Memory-Efficient Tail Calls in the JVM with Imperative Functional ObjectsProgramming Languages and Systems10.1007/978-3-319-26529-2_2(11-28)Online publication date: 9-Dec-2015
https://doi.org/10.1007/978-3-319-26529-2_2
Findler RFelleisen M(2013)ICFP 2002ACM SIGPLAN Notices10.1145/2502508.250252148:4S(34-45)Online publication date: 9-Jul-2013
https://dl.acm.org/doi/10.1145/2502508.2502521
Steele CBonn J(2012)Fast functional simulation with a dynamic language2012 IEEE Conference on High Performance Extreme Computing10.1109/HPEC.2012.6408664(1-3)Online publication date: Sep-2012
https://doi.org/10.1109/HPEC.2012.6408664
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents