HOME

TheInfoList




In
computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, generating algorithms, Profilin ...
, a subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed. Subroutines may be defined within programs, or separately in
libraries A library is a collection of materials, books or media that are easily accessible for use and not just for display purposes. It is responsible for housing updated information in order to meet the user's needs on a daily basis. A library provi ...
that can be used by many programs. In different programming languages, a subroutine may be called a routine, subprogram, function, method, or procedure. Technically, these terms all have different definitions, and the nomenclature varies from language to language. The generic,
umbrella term In linguistics Linguistics is the scientific study of language, meaning that it is a comprehensive, systematic, objective, and precise study of language. Linguistics encompasses the analysis of every aspect of language, as well as the m ...
callable unit is sometimes used. The name ''subprogram'' suggests a subroutine behaves in much the same way as a computer program that is used as one step in a larger program or another subprogram. A subroutine is often coded so that it can be started several times and from several places during one execution of the program, including from other subroutines, and then branch back (''return'') to the next instruction after the ''call'', once the subroutine's task is done. The idea of a subroutine was initially conceived by
John Mauchly John William Mauchly (August 30, 1907 – January 8, 1980) was an American physicist A physicist is a scientist A scientist is a person who conducts Scientific method, scientific research to advance knowledge in an Branches of science, ...
during his work on
ENIAC ENIAC (; Electronic Numerical Integrator and Computer) was the first programmable, electronic Electronic may refer to: *Electronics Electronics comprises the physics, engineering, technology and applications that deal with the emission ...

ENIAC
, and recorded in a January 1947 Harvard symposium on "Preparation of Problems for EDVAC-type Machines".J.W. Mauchly, "Preparation of Problems for EDVAC-type Machines" (1947), in Brian Randell (Ed.), The Origins of Digital Computers, Springer, 1982.
Maurice Wilkes Sir Maurice Vincent Wilkes (26 June 1913 – 29 November 2010) was a British computer scientist who designed and helped build the Electronic Delay Storage Automatic Calculator (EDSAC), one of the earliest stored program computers, and who i ...
, David Wheeler, and
Stanley GillProfessor Stanley J. Gill (26 March 1926 – 1975) was a British computer scientist credited, along with Maurice Wilkes and David Wheeler, with the invention of the first computer subroutine. Early life, education and career Stanley Gill was bo ...
are generally credited with the formal invention of this concept, which they termed a ''closed subroutine'', contrasted with an ''open subroutine'' or
macro Macro (or MACRO) may refer to: Science and technology * Macroscopic The macroscopic scale is the length scale on which objects or phenomena are large enough to be visible with the naked eye, without magnifying optical instruments. It is the o ...
. However,
Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalysis, cryptanalyst, philosopher, and mathematical and theoretical biology, theoretical biologist. Turing was high ...

Turing
had discussed subroutines in a paper of 1945 on design proposals for the NPL
ACE An ace is a playing card A playing card is a piece of specially prepared , heavy paper, thin cardboard, , cotton-paper blend, or thin plastic that is marked with distinguishing motifs. Often the front (face) and back of each card has a to ...
, going so far as to invent the concept of a return address stack. Subroutines are a powerful
programming
programming
tool, and the
syntax In linguistics Linguistics is the scientific study of language, meaning that it is a comprehensive, systematic, objective, and precise study of language. Linguistics encompasses the analysis of every aspect of language, as well as the ...
of many
programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
s includes support for writing and using them. Judicious use of subroutines (for example, through the
structured programming Structured programming is a programming paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mainly with impli ...
approach) will often substantially reduce the cost of developing and maintaining a large program, while increasing its quality and reliability. Subroutines, often collected into
libraries A library is a collection of materials, books or media that are easily accessible for use and not just for display purposes. It is responsible for housing updated information in order to meet the user's needs on a daily basis. A library provi ...
, are an important mechanism for sharing and trading software. The discipline of
object-oriented programming Object-oriented programming (OOP) is a programming paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mai ...
is based on objects and methods (which are subroutines attached to these objects or object
classes Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently f ...
). In the
compiling In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithm of an algorithm (Euclid's algorithm) for calculating the greatest com ...

compiling
method called
threaded code In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , ...
, the executable program is basically a sequence of subroutine calls.


Main concepts

The content of a subroutine is its body, which is the piece of program code that is executed when the subroutine is called or invoked. A subroutine may be written so that it expects to obtain one or more data values from the calling program (to replace its
parameters A parameter (), generally, is any characteristic that can help in defining or classifying a particular system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified wh ...
or formal parameters). The calling program provides actual values for these parameters, called
arguments In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, ...
. Different programming languages may use different conventions for passing arguments: A subroutine call may also have
side effects In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequences ...
such as modifying
data structure In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of ...

data structure
s in a
computer memory In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and soft ...
, reading from or writing to a
peripheral device A peripheral or peripheral device is an auxiliary device used to put information into and get information out of the computer. The term peripheral device refers to all hardware components that are attached to a computer and are controlled by the co ...
, creating a
file File or filing may refer to: Mechanical tools and processes * File (tool) A file is a tool used to remove fine amounts of material from a workpiece. It is common in woodworking, metalworking, and other similar trade and hobby tasks. Most are ...
, halting the program or the machine, or even delaying the program's execution for a specified time. A subprogram with side effects may return different results each time it is called, even if it is called with the same arguments. An example is a random number subroutine, available in many languages, that returns a different pseudo-random number each time it is called. The widespread use of subroutines with side effects is a characteristic of
imperative programming In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algori ...
languages. A subroutine can be coded so that it may call itself recursively, at one or more places, to perform its task. This method allows direct implementation of functions defined by
mathematical induction Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a mathematical proof A mathematical proof is an Inference, inferential Argument-deduction-proof distinct ...
and recursive
divide and conquer algorithm In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorit ...
s. A subroutine whose purpose is to compute one
boolean-valued function A Boolean-valued function (sometimes called a predicate or a proposition In linguistics and logic, a proposition is the meaning of a declarative sentence. In philosophy, "Meaning (philosophy), meaning" is understood to be a non-linguistic enti ...
(that is, to answer a yes/no question) is sometimes called a predicate. In
logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic prog ...
languages, often all subroutines are called predicates, since they primarily determine success or failure. A subroutine that returns no value or returns a null value is sometimes called a procedure. Procedures usually modify their arguments and are a core part of
procedural programming Procedural programming is a programming paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mainly with im ...
.


Functions

A ''Function'' is a subroutine that returns a value. The primary purpose of functions is to break up complicated computations into meaningful chunks and name them. The subroutine may return a computed value to its caller (its
return value In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a specific task. Programming involves tasks such as: analysis, generat ...
), or provide various result values or output parameters. Indeed, a common use of subroutines is to implement
mathematical functions Mathematics (from Greek: ) includes the study of such topics as quantity Quantity is a property that can exist as a multitude or magnitude, which illustrate discontinuity and continuity. Quantities can be compared in terms of "more", " ...
, in which the purpose of the subroutine is purely to compute one or more results whose values are entirely determined by the arguments passed to the subroutine. (Examples might include computing the
logarithm In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...

logarithm
of a number or the
determinant In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

determinant
of a
matrix Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryoti ...
.) In some languages the syntax for a procedure that returns a value is essentially the same as the syntax for a procedure that does not return a value, except for the absence of, e.g., RETURNS clause. In some languages a procedure may dynamically choose to return with or without a value, depending on its arguments.


Language support

High-level programming language In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , ...
s usually include specific constructs to: * Delimit the part of the program (body) that makes up the subroutine * Assign an
identifier An identifier is a name that identifies (that is, labels the identity of) either a unique object or a unique ''class'' of objects, where the "object" or class may be an idea, physical countable In mathematics Mathematics (from Greek: ) i ...
(name) to the subroutine * Specify the names and
data type In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Alg ...
s of its parameters and return values * Provide a private naming scope for its
temporary variable In computer programming, a temporary variable is a variable (programming), variable with short object lifetime, lifetime, usually to hold data (computing), data that will soon be discarded, or before it can be placed at a more permanent memory loca ...
s * Identify variables outside the subroutine that are accessible within it * Call the subroutine * Provide values to its parameters * The main program contains the address of the subprogram * The subprogram contains the address of the next instruction of the function call in the main program * Specify the return values from within its body * Return to the calling program * Dispose of the values returned by a call * Handle any exceptional conditions encountered during the call * Package subroutines into a
module Module, modular and modularity may refer to the concept of modularity. They may also refer to: Computing and engineering * Modular design, the engineering discipline of designing complex devices using separately designed sub-components * Modula ...
,
library A library is a collection of materials, books or media that are easily accessible for use and not just for display purposes. It is responsible for housing updated information in order to meet the user's needs on a daily basis. A library provi ...
,
object Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Entity, something that is tangible and within the grasp of the senses ** Object (abstract), an object which does not exist at any particular time or pl ...
, or
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently f ...
Some
programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
s, such as
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, French ...
,
Fortran Fortran (; formerly FORTRAN) is a general-purpose, compiled language, compiled imperative programming, imperative programming language that is especially suited to numerical analysis, numeric computation and computational science, scientific com ...

Fortran
,
Ada Ada may refer to: Places Africa * Ada Foah Ada Foah is a town on the southeast coast of Ghana, where the Volta River meets the Atlantic Ocean. The town is located along the Volta River, off of the Accra-Aflao motorway. Known for Palm tree, pal ...
and many
dialects The term dialect (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of th ...
of
BASIC BASIC (Beginners' All-purpose Symbolic Instruction Code) is a family of general-purpose, high-level programming language In computer science Computer science deals with the theoretical foundations of information, algorithms and the ar ...

BASIC
, distinguish between functions or function subprograms, which provide an explicit return value to the calling program, and subroutines or procedures, which do not. In those languages, function calls are normally embedded in
expressions Expression may refer to: Linguistics * Expression (linguistics), a word, phrase, or sentence * Fixed expression, a form of words with a specific meaning * Idiom, a type of fixed expression * Metaphor#Common types, Metaphorical expression, a parti ...
(e.g., a sqrt function may be called as y = z + sqrt(x)). Procedure calls either behave syntactically as
statements Statement or statements may refer to: Common uses *Statement (computer science)In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to ...
(e.g., a print procedure may be called as if x > 0 then print(x) or are explicitly invoked by a statement such as CALL or GOSUB (e.g., call print(x)). Other languages, such as C and
Lisp Lisp (historically LISP) is a family of programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbo ...
, do not distinguish between functions and subroutines. In strictly
functional programming In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
languages such as Haskell, subprograms can have no
side effects In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequences ...
, which means that various internal states of the program will not change. Functions will always return the same result if repeatedly called with the same arguments. Such languages typically only support functions, since subroutines that do not return a value have no use unless they can cause a side effect. In
programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
s such as C,
C++ C++ () is a general-purpose programming language In computer software, a general-purpose programming language is a programming language dedicated to a general-purpose, designed to be used for writing software in a wide variety of application ...

C++
, and C#, subroutines may also simply be called functions (not to be confused with
mathematical functions Mathematics (from Greek: ) includes the study of such topics as quantity Quantity is a property that can exist as a multitude or magnitude, which illustrate discontinuity and continuity. Quantities can be compared in terms of "more", " ...
or
functional programming In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
, which are different concepts). A language's
compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...

compiler
will usually translate procedure calls and returns into machine instructions according to a well-defined
calling convention In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algori ...
, so that subroutines can be compiled separately from the programs that call them. The instruction sequences corresponding to call and return statements are called the procedure's prologue and epilogue.


Advantages

The advantages of breaking a program into subroutines include: *
Decomposing Decomposition is the process by which dead organic substances are broken down into simpler organic or inorganic matter such as carbon dioxide, water, simple sugars and mineral salts. The process is a part of the nutrient cycle and is essential f ...
a complex programming task into simpler steps: this is one of the two main tools of
structured programming Structured programming is a programming paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mainly with impli ...
, along with
data structure In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of ...

data structure
s * Reducing
duplicate codeDuplicate code is a computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as an ...

duplicate code
within a program * Enabling reuse of code across multiple programs * Dividing a large programming task among various programmers or various stages of a project * Hiding implementation details from users of the subroutine * Improving readability of code by replacing a block of code with a function call where
descriptive
function name serves to describe the block of code. This makes the calling code concise and readable even if the function is not meant to be reused. * Improving
traceabilityTraceability is the capability to trace something. In some cases, it is interpreted as the ability to verify the history, location, or application of an item by means of documented recorded identification. Other common definitions include the capabi ...

traceability
(i.e. most languages offer ways to obtain the call trace which includes the names of the involved subroutines and perhaps even more information such as file names and line numbers); by not decomposing the code into subroutines, debugging would be severely impaired


Disadvantages

Compared to using in-line code, invoking a subroutine imposes some
computational overhead In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algo ...
in the call mechanism. A subroutine typically requires standard
housekeeping Housekeeping refers to the management of duties and chores involved in the running of a household, such as cleaning, cooking, home maintenance, shopping, and bill payment. These tasks may be performed by members of the household, or by other pers ...
code – both at the entry to, and exit from, the function ( function prologue and epilogue – usually saving
general purpose register A processor register is a quickly accessible location available to a computer's processor. Registers usually consist of a small amount of fast storage, although some registers have specific hardware functions, and may be read-only or write-only. ...
s and return address as a minimum).


History

The idea of a subroutine was worked out after computing machines had already existed for some time. The arithmetic and conditional jump instructions were planned ahead of time and have changed relatively little, but the special instructions used for procedure calls have changed greatly over the years. The earliest computers and microprocessors, such as the
Manchester Baby The Manchester Baby, also called the Small-Scale Experimental Machine (SSEM), was the first electronic stored-program computer A stored-program computer is a computer A computer is a machine that can be programmed to carry out sequences ...
and the
RCA 1802 The COSMAC is an 8-bit In computer architecture In computer engineering, computer architecture is a set of rules and methods that describe the functionality, organization, and implementation of computer systems. Some definitions of archi ...
, did not have a single subroutine call instruction. Subroutines could be implemented, but they required programmers to use the call sequence—a series of instructions—at each
call site In programming, a call site of a function or subroutine is the location (line of code) where the function is called (or may be called, through dynamic dispatch In computer science Computer science deals with the theoretical foundations of ...
. Subroutines were implemented in
Konrad Zuse Konrad Zuse (; 22 June 1910 – 18 December 1995) was a German civil engineer, pioneering computer scientist, inventor and businessman. His greatest achievement was the world's first programmable computer; the functional program-controlled ...

Konrad Zuse
's Z4 in 1945. In 1945,
Alan M. Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such to ...
used the terms "bury" and "unbury" as a means of calling and returning from subroutines. (NB. Presented on 1946-03-19 before the Executive Committee of the National Physical Laboratory (Great Britain).) (11 pages) In January 1947 John Mauchly presented general notes at 'A Symposium of Large Scale Digital Calculating Machinery' under the joint sponsorship of Harvard University and the Bureau of Ordnance, United States Navy. Here he discusses serial and parallel operation suggesting Kay McNulty had worked closely with John Mauchly on the
ENIAC ENIAC (; Electronic Numerical Integrator and Computer) was the first programmable, electronic Electronic may refer to: *Electronics Electronics comprises the physics, engineering, technology and applications that deal with the emission ...

ENIAC
team and developed an idea for subroutines for the
ENIAC ENIAC (; Electronic Numerical Integrator and Computer) was the first programmable, electronic Electronic may refer to: *Electronics Electronics comprises the physics, engineering, technology and applications that deal with the emission ...

ENIAC
computer she was programming during World War II. She and the other ENIAC programmers used the subroutines to help calculate missile trajectories. and
von Neumann Von Neumann may refer to: * John von Neumann (1903–1957), a Hungarian American mathematician * Von Neumann family * Von Neumann (surname), a German surname * Von Neumann (crater), a lunar impact crater See also

* Von Neumann algebra * Von Ne ...

von Neumann
wrote a paper dated 16 August 1948 discussing the use of subroutines. Some very early computers and microprocessors, such as the
IBM 1620 The IBM 1620 was announced by IBM International Business Machines Corporation (IBM) is an American multinational technology company headquartered in Armonk, New York, with operations in over 170 countries. The company began in 1911, found ...

IBM 1620
, the
Intel 4004 The Intel 4004 is a 4-bit In , 4-bit s, or other units are those that are 4 s wide. Also, 4-bit and architectures are those that are based on s, or es of that size. es (and thus es) for 4-bit CPUs are generally much larger than 4-bi ...

Intel 4004
and
Intel 8008 The Intel 8008 ("''eight-thousand-eight''" or "''eighty-oh-eight''") is an early byte-oriented microprocessor A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, ...

Intel 8008
, and the
PIC microcontroller PIC (usually pronounced as ''"pick"'') is a family of microcontroller A microcontroller (MCU for ''microcontroller unit'') is a small computer A computer is a machine that can be programmed to carry out sequences of arithmetic or l ...
s, have a single-instruction subroutine call that uses a dedicated hardware stack to store return addresses—such hardware supports only a few levels of subroutine nesting, but can support recursive subroutines. Machines before the mid-1960s—such as the
UNIVAC I The UNIVAC I (UNIVersal Automatic Computer I) was the first general-purpose electronic digital computer design for business application produced in the . It was designed principally by and , the inventors of the . Design work was started by th ...
, the
PDP-1 The PDP-1 (''Programmed Data Processor-1'') is the first computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operatio ...

PDP-1
, and the
IBM 1130 The IBM 1130 Computing System, introduced in 1965, was IBM International Business Machines Corporation (IBM) is an American multinational technology company headquartered in Armonk, New York, with operations in over 170 countries. The co ...
—typically use a
calling convention In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algori ...
which saved the instruction counter in the first memory location of the called subroutine. This allows arbitrarily deep levels of subroutine nesting but does not support recursive subroutines. The
PDP-11 The PDP-11 is a series of 16-bit 16-bit microcomputers are computers in which 16-bit microprocessors were the norm. A 16-bit register can store 216 different values. The range (computer programming), range of integer values that can be stored i ...
(1970) is one of the first computers with a stack-pushing subroutine call instruction; this feature supports both arbitrarily deep subroutine nesting and also supports recursive subroutines. Guy Lewis Steele Jr.
AI Memo The AI Memos are a series of influential memorandum A memorandum (abbrev.: memo; from Latin ''memorandum est'', "It must be remembered") is a Writing, written message that may be used in a business office. The plural form of the Latin noun ''mem ...
443
'Debunking the "Expensive Procedure Call" Myth; or, Procedure call implementations considered harmful"
Section "C. Why Procedure Calls Have a Bad Reputation".


Language support

In the very early assemblers, subroutine support was limited. Subroutines were not explicitly separated from each other or from the main program, and indeed the source code of a subroutine could be interspersed with that of other subprograms. Some assemblers would offer predefined macro (computer science), macros to generate the call and return sequences. By the 1960s, assemblers usually had much more sophisticated support for both inline and separately assembled subroutines that could be linked together. One of the first programming languages to support user-written subroutines and functions was Fortran#FORTRAN_II, FORTRAN II. The IBM FORTRAN II compiler was released in 1958. ALGOL 58 and other early programming languages also supported procedural programming.


Subroutine libraries

Even with this cumbersome approach, subroutines proved very useful. For one thing, they allowed the use of the same code in many different programs. Moreover, memory was a very scarce resource on early computers, and subroutines allowed significant savings in the size of programs. Many early computers loaded the program instructions into memory from a punched tape, punched paper tape. Each subroutine could then be provided by a separate piece of tape, loaded or spliced before or after the main program (or "mainline"); and the same subroutine tape could then be used by many different programs. A similar approach applied in computers that used punched cards for their main input. The name ''subroutine library'' originally meant a library, in the literal sense, which kept indexed collections of tapes or card-decks for collective use.


Return by indirect jump

To remove the need for self-modifying code, computer designers eventually provided an ''indirect branch, indirect jump'' instruction, whose operand, instead of being the return statement, return address itself, was the location of a variable or processor register containing the return address. On those computers, instead of modifying the subroutine's return jump, the calling program would store the return address in a variable so that when the subroutine completed, it would execute an indirect jump that would direct execution to the location given by the predefined variable.


Jump to subroutine

Another advance was the ''jump to subroutine'' instruction, which combined the saving of the return address with the calling jump, thereby minimizing computational overhead, overhead significantly. In the IBM System/360, for example, the branch instructions BAL or BALR, designed for procedure calling, would save the return address in a processor register specified in the instruction, by convention register 14. To return, the subroutine had only to execute an indirect branch instruction (BR) through that register. If the subroutine needed that register for some other purpose (such as calling another subroutine), it would save the register's contents to a private memory location or a register stack (data structure), stack. In systems such as the HP 2100, the JSB instruction would perform a similar task, except that the return address was stored in the memory location that was the target of the branch. Execution of the procedure would actually begin at the next memory location. In the HP 2100 assembly language, one would write, for example ... JSB MYSUB (Calls subroutine MYSUB.) BB ... (Will return here after MYSUB is done.) to call a subroutine called MYSUB from the main program. The subroutine would be coded as MYSUB NOP (Storage for MYSUB's return address.) AA ... (Start of MYSUB's body.) ... JMP MYSUB,I (Returns to the calling program.) The JSB instruction placed the address of the NEXT instruction (namely, BB) into the location specified as its operand (namely, MYSUB), and then branched to the NEXT location after that (namely, AA = MYSUB + 1). The subroutine could then return to the main program by executing the indirect jump JMP MYSUB, I which branched to the location stored at location MYSUB. Compilers for Fortran and other languages could easily make use of these instructions when available. This approach supported multiple levels of calls; however, since the return address, parameters, and return values of a subroutine were assigned fixed memory locations, it did not allow for recursive calls. Incidentally, a similar method was used by Lotus 1-2-3, in the early 1980s, to discover the recalculation dependencies in a spreadsheet. Namely, a location was reserved in each cell to store the ''return'' address. Since circular references are not allowed for natural recalculation order, this allows a tree walk without reserving space for a stack in memory, which was very limited on small computers such as the IBM PC.


Call stack

Most modern implementations of a subroutine call use a call stack, a special case of the stack (data structure), stack data structure, to implement subroutine calls and returns. Each procedure call creates a new entry, called a ''stack frame'', at the top of the stack; when the procedure returns, its stack frame is deleted from the stack, and its space may be used for other procedure calls. Each stack frame contains the ''private data'' of the corresponding call, which typically includes the procedure's parameters and internal variables, and the return address. The call sequence can be implemented by a sequence of ordinary instructions (an approach still used in reduced instruction set computing (RISC) and very long instruction word (VLIW) architectures), but many traditional machines designed since the late 1960s have included special instructions for that purpose. The call stack is usually implemented as a contiguous area of memory. It is an arbitrary design choice whether the bottom of the stack is the lowest or highest address within this area, so that the stack may grow forwards or backwards in memory; however, many architectures chose the latter. Some designs, notably some Forth (programming language), Forth implementations, used two separate stacks, one mainly for control information (like return addresses and loop counters) and the other for data. The former was, or worked like, a call stack and was only indirectly accessible to the programmer through other language constructs while the latter was more directly accessible. When stack-based procedure calls were first introduced, an important motivation was to save precious memory. With this scheme, the compiler does not have to reserve separate space in memory for the private data (parameters, return address, and local variables) of each procedure. At any moment, the stack contains only the private data of the calls that are currently ''active'' (namely, which have been called but haven't returned yet). Because of the ways in which programs were usually assembled from libraries, it was (and still is) not uncommon to find programs that include thousands of subroutines, of which only a handful are active at any given moment. For such programs, the call stack mechanism could save significant amounts of memory. Indeed, the call stack mechanism can be viewed as the earliest and simplest method for garbage collection (computer science), automatic memory management. However, another advantage of the call stack method is that it allows recursion (computer science), recursive subroutine calls, since each nested call to the same procedure gets a separate instance of its private data.


Delayed stacking

One disadvantage of the call stack mechanism is the increased cost of a procedure call and its matching return. The extra cost includes incrementing and decrementing the stack pointer (and, in some architectures, checking for stack overflow), and accessing the local variables and parameters by frame-relative addresses, instead of absolute addresses. The cost may be realized in increased execution time, or increased processor complexity, or both. This overhead is most obvious and objectionable in ''leaf procedures'' or ''leaf functions'', which return without making any procedure calls themselves. To reduce that overhead, many modern compilers try to delay the use of a call stack until it is really needed. For example, the call of a procedure ''P'' may store the return address and parameters of the called procedure in certain processor registers, and transfer control to the procedure's body by a simple jump. If the procedure ''P'' returns without making any other call, the call stack is not used at all. If ''P'' needs to call another procedure ''Q'', it will then use the call stack to save the contents of any registers (such as the return address) that will be needed after ''Q'' returns.


C and C++ examples

In the C and
C++ C++ () is a general-purpose programming language In computer software, a general-purpose programming language is a programming language dedicated to a general-purpose, designed to be used for writing software in a wide variety of application ...

C++
programming languages, subprograms are termed ''functions'' (further classified as ''member functions'' when associated with a
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently f ...
, or ''free functions'' when not). These languages use the special keyword void to indicate that a function does not return any value. Note that C/C++ functions can have side-effects, including modifying any variables whose addresses are passed as parameters. Examples: void Function1() The function does not return a value and has to be called as a stand-alone function, e.g., Function1(); int Function2() This function returns a result (the number 5), and the call can be part of an expression, e.g., x + Function2() char Function3(int number) This function converts a number between 0 and 6 into the initial letter of the corresponding day of the week, namely 0 to 'S', 1 to 'M', ..., 6 to 'S'. The result of calling it might be assigned to a variable, e.g., num_day = Function3(number);. void Function4(int* pointer_to_var) This function does not return a value but modifies the variable whose address is passed as the parameter; it would be called with Function4(&variable_to_increment);.


Small Basic example

Example() ' Calls the subroutine Sub Example ' Begins the subroutine TextWindow.WriteLine("This is an example of a subroutine in Microsoft Small Basic.") ' What the subroutine does EndSub ' Ends the subroutine In the example above, Example() calls the subroutine. To define the actual subroutine, the Sub keyword must be used, with the subroutine name following Sub. After content has followed, EndSub must be typed.


Visual Basic 6 examples

In the Visual Basic 6 language, subprograms are termed ''functions'' or ''subs'' (or ''methods'' when associated with a class). Visual Basic 6 uses various terms called ''types'' to define what is being passed as a parameter. By default, an unspecified variable is registered as a variant type and can be passed as ''ByRef'' (default) or ''ByVal''. Also, when a function or sub is declared, it is given a public, private, or friend designation, which determines whether it can be accessed outside the module or project that it was declared in. * By value [ByVal] – a way of passing the value of an argument to a procedure by passing a copy of the value, instead of passing the address. As a result, the variable's actual value can't be changed by the procedure to which it is passed. * By reference [ByRef] – a way of passing the value of an argument to a procedure by passing an address of the variable, instead of passing a copy of its value. This allows the procedure to access the actual variable. As a result, the variable's actual value can be changed by the procedure to which it is passed. Unless otherwise specified, arguments are passed by reference. * Public (optional) – indicates that the function procedure is accessible to all other procedures in all modules. If used in a module that contains an Option Private, the procedure is not available outside the project. * Private (optional) – indicates that the function procedure is accessible only to other procedures in the module where it is declared. * Friend (optional) – used only in a class module. Indicates that the Function procedure is visible throughout the project, but not visible to a controller of an instance of an object. Private Function Function1() ' Some Code Here End Function The function does not return a value and has to be called as a stand-alone function, e.g., Function1 Private Function Function2() as Integer Function2 = 5 End Function This function returns a result (the number 5), and the call can be part of an expression, e.g., x + Function2() Private Function Function3(ByVal intValue as Integer) as String Dim strArray(6) as String strArray = Array("M", "T", "W", "T", "F", "S", "S") Function3 = strArray(intValue) End Function This function converts a number between 0 and 6 into the initial letter of the corresponding day of the week, namely 0 to 'M', 1 to 'T', ..., 6 to 'S'. The result of calling it might be assigned to a variable, e.g., num_day = Function3(number). Private Function Function4(ByRef intValue as Integer) intValue = intValue + 1 End Function This function does not return a value but modifies the variable whose address is passed as the parameter; it would be called with "Function4(variable_to_increment)".


PL/I example

In PL/I a called procedure may be passed a ''Data descriptor, descriptor'' providing information about the argument, such as string lengths and array bounds. This allows the procedure to be more general and eliminates the need for the programmer to pass such information. By default PL/I passes arguments by reference. A (trivial) subroutine to change the sign of each element of a two-dimensional array might look like:
  change_sign: procedure(array);
    declare array(*,*) float;
    array = -array;
    end change_sign;
This could be called with various arrays as follows:
  /* first array bounds from -5 to +10 and 3 to 9 */
  declare array1 (-5:10, 3:9)float;
  /* second array bounds from 1 to 16 and 1 to 16 */
  declare array2 (16,16) float;
  call change_sign(array1);
  call change_sign(array2);


Python example

In Python (programming language), Python, the keyword def is used to define a function. The statements that form the body of the function must either continue on the same line or start on the next line and be indented. The following example program "Hello, World!" program, prints "Hello world!" followed by "Wikipedia" on the next line. def simple_function(): print('Hello world!') print('Wikipedia') simple_function()


Local variables, recursion and reentrancy

A subprogram may find it useful to make use of a certain amount of ''scratch'' space; that is, virtual memory, memory used during the execution of that subprogram to hold intermediate results. Variables stored in this scratch space are termed ''local variables'', and the scratch space is termed an ''activation record''. An activation record typically has a return address (computing), return address that tells it where to pass control back to when the subprogram finishes. A subprogram may have any number and nature of call sites. If recursion is supported, a subprogram may even call itself, causing its execution to suspend while another ''nested'' execution of the same subprogram occurs. Recursion is a useful means to simplify some complex algorithms and break down complex problems. Recursive languages generally provide a new copy of local variables on each call. If the programmer desires the value of local variables to stay the same between calls, they can be declared ''static'' in some languages, or global values or common areas can be used. Here is an example of recursive subroutine in C/C++ to find Fibonacci numbers: int Fib(int n) Early languages like
Fortran Fortran (; formerly FORTRAN) is a general-purpose, compiled language, compiled imperative programming, imperative programming language that is especially suited to numerical analysis, numeric computation and computational science, scientific com ...

Fortran
did not initially support recursion because variables were statically allocated, as well as the location for the return address. Most computers before the late 1960s such as the PDP-8 did not have support for hardware stack registers. Modern languages after ALGOL such as PL/I and C almost invariably use a stack, usually supported by most modern computer instruction sets to provide a fresh activation record for every execution of a subprogram. That way, the nested execution is free to modify its local variables without concern for the effect on other suspended executions in progress. As nested calls accumulate, a call stack structure is formed, consisting of one activation record for each suspended subprogram. In fact, this stack structure is virtually ubiquitous, and so activation records are commonly termed ''stack frames''. Some languages such as
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, French ...
, PL/I, and
Ada Ada may refer to: Places Africa * Ada Foah Ada Foah is a town on the southeast coast of Ghana, where the Volta River meets the Atlantic Ocean. The town is located along the Volta River, off of the Accra-Aflao motorway. Known for Palm tree, pal ...
also support nested function, nested subroutines, which are subroutines callable only within the scope (programming), scope of an outer (parent) subroutine. Inner subroutines have access to the local variables of the outer subroutine that called them. This is accomplished by storing extra context information within the activation record, also termed a ''display''. If a subprogram can be executed properly even when another execution of the same subprogram is already in progress, that subprogram is said to be ''reentrant (subroutine), reentrant''. A recursive subprogram must be reentrant. Reentrant subprograms are also useful in thread (computer science), multi-threaded situations since multiple threads can call the same subprogram without fear of interfering with each other. In the IBM CICS transaction processing system, ''quasi-reentrant'' was a slightly less restrictive, but similar, requirement for application programs that were shared by many threads. In a thread (computer science), multi-threaded environment, there is generally more than one stack. An environment that fully supports coroutines or lazy evaluation may use data structures other than stacks to store their activation records.


Overloading

In strong typing, strongly typed languages, it is sometimes desirable to have a number of functions with the same name, but operating on different types of data, or with different parameter profiles. For example, a square root function might be defined to operate on reals, complex values or matrices. The algorithm to be used in each case is different, and the return result may be different. By writing three separate functions with the same name, the programmer has the convenience of not having to remember different names for each type of data. Further, if a subtype can be defined for the reals, to separate positive and negative reals, two functions can be written for the reals, one to return a real when the parameter is positive, and another to return a complex value when the parameter is negative. In
object-oriented programming Object-oriented programming (OOP) is a programming paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mai ...
, when a series of functions with the same name can accept different parameter profiles or parameters of different types, each of the functions is said to be method overloading, overloaded. Here is an example of subroutine overloading in
C++ C++ () is a general-purpose programming language In computer software, a general-purpose programming language is a programming language dedicated to a general-purpose, designed to be used for writing software in a wide variety of application ...

C++
: #include double Area(double h, double w) double Area(double r) int main() In this code, there are two functions of the same name but they have different parameters. As another example, a subroutine might construct an
object Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Entity, something that is tangible and within the grasp of the senses ** Object (abstract), an object which does not exist at any particular time or pl ...
that will accept directions, and trace its path to these points on screen. There are a plethora of parameters that could be passed in to the constructor (colour of the trace, starting x and y co-ordinates, trace speed). If the programmer wanted the constructor to be able to accept only the color parameter, then he could call another constructor that accepts only color, which in turn calls the constructor with all the parameters passing in a set of ''default values'' for all the other parameters (X and Y would generally be centered on screen or placed at the origin, and the speed would be set to another value of the coder's choosing). PL/I has the GENERIC attribute to define a generic name for a set of entry references called with different types of arguments. Example:
  DECLARE gen_name GENERIC(
                      name  WHEN(FIXED BINARY),
                      flame  WHEN(FLOAT),
                      pathname OTHERWISE 
                           );
Multiple argument definitions may be specified for each entry. A call to "gen_name" will result in a call to "name" when the argument is FIXED BINARY, "flame" when FLOAT", etc. If the argument matches none of the choices "pathname" will be called.


Closures

A ''closure (computer science), closure'' is a subprogram together with the values of some of its variables captured from the environment in which it was created. Closures were a notable feature of the Lisp programming language, introduced by John McCarthy (computer scientist), John McCarthy. Depending on the implementation, closures can serve as a mechanism for side-effects.


Conventions

A wide number of conventions for the coding of subroutines have been developed. Pertaining to their naming, many developers have adopted the approach that the name of a subroutine should be a verb when it does a certain task, and adjective when it makes some inquiry, and a noun when it is used to substitute variables. Some programmers suggest that a subroutine should perform only one task, and if a subroutine does perform more than one task, it should be split up into more subroutines. They argue that subroutines are key components in software maintenance, code maintenance, and their roles in the program must remain distinct. Proponents of modular programming (modularizing code) advocate that each subroutine should have minimal dependency on other pieces of code. For example, the use of global variables is generally deemed unwise by advocates for this perspective, because it adds tight coupling between the subroutine and these global variables. If such coupling is not necessary, their advice is to code refactoring, refactor subroutines to accept passed parameter (computer programming), parameters instead. However, increasing the number of parameters passed to subroutines can affect code readability.


Return codes

Besides its ''main'' or ''normal'' effect, a subroutine may need to inform the calling program about ''exceptional'' conditions that may have occurred during its execution. In some languages and programming standards, this is often done through a ''return code'', an integer value placed by the subroutine in some standard location, which encodes the normal and exceptional conditions. In the IBM System/360, where return code was expected from the subroutine, the return value was often designed to be a multiple of 4—so that it could be used as a direct branch table index into a branch table often located immediately after the call instruction to avoid extra conditional tests, further improving efficiency. In the System/360 assembly language, one would write, for example: BAL 14, SUBRTN01 go to a subroutine, storing return address in R14 B TABLE(15) use returned value in reg 15 to index the branch table, * branching to the appropriate branch instr. TABLE B OK return code =00 GOOD } B BAD return code =04 Invalid input } Branch table B ERROR return code =08 Unexpected condition }


Optimization of subroutine calls

There is a significant runtime computational overhead, overhead in calling a subroutine, including passing the arguments, branching to the subprogram, and branching back to the caller. The overhead often includes saving and restoring certain processor registers, allocating and reclaiming call frame storage, etc.. In some languages, each subroutine call also implies automatic testing of the subroutine's return code or the handling of exception (programming), exceptions that it may raise. A significant source of overhead in object-oriented languages is the intensively used dynamic dispatch for method calls. There are some seemingly obvious optimizations of procedure calls that cannot be applied if the procedures may have side effects. For example, in the expression (f(x)-1)/(f(x)+1), the function f must be called twice, because the two calls may return different results. Moreover, the value of x must be fetched again before the second call, since the first call may have changed it. Determining whether a subprogram may have a side effect is very difficult (indeed, undecidable problem, undecidable by virtue of Rice's theorem). So, while those optimizations are safe in purely functional programming languages, compilers of typical imperative programming usually have to assume the worst.


Inlining

A method used to eliminate this overhead is ''inline expansion'' or ''inlining'' of the subprogram's body at each
call site In programming, a call site of a function or subroutine is the location (line of code) where the function is called (or may be called, through dynamic dispatch In computer science Computer science deals with the theoretical foundations of ...
(versus branching to the subroutine and back). Not only does this avoid the call overhead, but it also allows the
compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...

compiler
to code optimization, optimize the procedure's ''body'' more effectively by taking into account the context and arguments at that call. The inserted body can be optimized by the compiler. Inlining, however, will usually increase the code size, unless the program contains only one call to the subroutine.


Trope in popular media

The term "subroutine" has been used countless times in television and movies since the 1990s. Sometimes set in present day, sometimes in the far future, any plot element involving
computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, generating algorithms, Profilin ...
or Security hacker, hacking may evoke the concept; often it is often misapplied.


See also

* Function (mathematics) * Method (computer programming) * Builtin function * Evaluation strategy * Modular programming * Transclusion * Operator overloading * Protected procedure * Functional programming * Command–query separation (CQS) * Coroutines, subprograms that call each other as if both were the main programs * Event handler, a subprogram that is called in response to an input event or interrupt * Asynchronous procedure call, a subprogram that is called after its parameters are set by other activities


References

{{Authority control Source code Articles with example C code University of Cambridge Computer Laboratory Holism Programming constructs Subroutines,