In
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, a function or 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.
Functions may be defined within
program
Program, programme, programmer, or programming may refer to:
Business and management
* Program management, the process of managing several related projects
* Time management
* Program, a part of planning
Arts and entertainment Audio
* Progra ...
s, or separately in
libraries
A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
that can be used by many programs. In different
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s, a function may be called a routine, subprogram, subroutine,
method, or procedure. Technically, these terms all have different definitions, and the nomenclature varies from language to language. The generic
umbrella term
In linguistics, semantics, general semantics, and ontologies, hyponymy () is a semantic relation between a hyponym denoting a subtype and a hypernym or hyperonym (sometimes called umbrella term or blanket term) denoting a supertype. In other wor ...
''callable unit'' is sometimes used.
A function is often coded so that it can be started several times and from several places during one
execution
Capital punishment, also known as the death penalty, is the State (polity), state-sanctioned practice of deliberately killing a person as a punishment for an actual or supposed crime, usually following an authorized, rule-governed process to ...
of the program, including from other functions, and then branch back (''
return
Return may refer to:
In business, economics, and finance
* Return on investment (ROI), the financial gain after an expense.
* Rate of return, the financial term for the profit or loss derived from an investment
* Tax return, a blank document or t ...
'') to the next instruction after the ''call'', once the function'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 who, along with J. Presper Eckert, designed ENIAC, the first general-purpose electronic digital computer, as well as EDVAC, BINAC and UNIVAC I, the first co ...
during his work on
ENIAC
ENIAC (; Electronic Numerical Integrator and Computer) was the first programmable, electronic, general-purpose digital computer, completed in 1945. There were other computers that had these features, but the ENIAC had all of them in one packa ...
,
and recorded in a January 1947 Harvard symposium on "Preparation of Problems for
EDVAC-type Machines".
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 inv ...
,
David Wheeler, and
Stanley Gill
Professor 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 bor ...
are generally credited with the formal invention of this concept, which they termed a ''closed sub-routine'', contrasted with an ''open subroutine'' or
macro. However,
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
had discussed subroutines in a paper of 1945 on design proposals for the NPL
ACE
An ace is a playing card, die or domino with a single pip. In the standard French deck, an ace has a single suit symbol (a heart, diamond, spade, or club) located in the middle of the card, sometimes large and decorated, especially in the c ...
, going so far as to invent the concept of a
return address stack.
Functions are a powerful programming tool,
and the
syntax
In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituency) ...
of many programming languages includes support for writing and using subroutines. Judicious use of functions (for example, through the
structured programming
Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection ( if/then/else) and repetition ( ...
approach) will often substantially reduce the cost of developing and maintaining a large program, while increasing its quality and reliability.
Functions, often collected into libraries, are an important mechanism for sharing and trading software. The discipline of
object-oriented programming
Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pr ...
is based on
objects
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ...
and methods (which are functions attached to these objects or object
classes).
Main concepts
The content of a function is its body, which is the piece of program code that is executed when the function is called or invoked.
A function 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 (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
or formal parameters). The calling program provides actual values for these parameters, called
arguments
An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialectic ...
. Different programming languages may use different conventions for passing arguments:
A function 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, consequence ...
such as modifying
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s in a
computer memory
In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term ''primary storage ...
, 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 a computer. The term ''peripheral device'' refers to all hardware components that are attached to a computer and are controlled by the ...
, creating a
file
File or filing may refer to:
Mechanical tools and processes
* File (tool), a tool used to ''remove'' fine amounts of material from a workpiece
**Filing (metalworking), a material removal process in manufacturing
** Nail file, a tool used to gent ...
, 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 function, available in many languages, that returns a different pseudo-random number each time it is called. The widespread use of functions with side effects is a characteristic of
imperative programming
In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program c ...
languages.
A function 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 is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
and recursive
divide and conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
s.
A function whose purpose is to compute one
boolean-valued function
A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are in ...
(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 functions are called predicates, since they primarily determine success or failure.
A function 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, derived from imperative programming, based on the concept of the ''procedure call''. Procedures (a type of routine or subroutine) simply contain a series of computational steps to be carried ...
.
Terminology
A ''subroutine'' is a function that doesn't return a value.
The primary purpose of functions is to break up complicated computations into meaningful chunks and name them.
The function may return a computed value to its caller (its
return value
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after the instruction which called the subroutine, known as its return address. The return address is sa ...
), or provide various result values or output parameters. Indeed, a common use of functions is to implement
mathematical functions
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
, in which the purpose of the function is purely to compute one or more results whose values are entirely determined by the arguments passed to the function. (Examples might include computing the
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
of a number or the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of a
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
.) 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, a high-level programming language is a programming language with strong Abstraction (computer science), abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ...
s usually include specific constructs to:
* Delimit the part of the program (body) that makes up the function
* 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 object (or class thereof), or physical noncountable ...
(name) to the function
* Specify the names and
data type
In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most progra ...
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 with short lifetime, usually to hold data that will soon be discarded, or before it can be placed at a more permanent memory location. Because it is short-lived, it is usually declared ...
s
* Identify variables outside the function that are accessible within it
* Call the function
* 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
Return may refer to:
In business, economics, and finance
* Return on investment (ROI), the financial gain after an expense.
* Rate of return, the financial term for the profit or loss derived from an investment
* Tax return, a blank document or t ...
to the calling program
* Dispose of the values returned by a call
* Handle any
exceptional conditions encountered during the call
* Package functions 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
* Mo ...
,
library
A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
,
object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ...
, 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 differentl ...
Some
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
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, Fren ...
,
Fortran,
Ada
Ada may refer to:
Places
Africa
* Ada Foah, a town in Ghana
* Ada (Ghana parliament constituency)
* Ada, Osun, a town in Nigeria
Asia
* Ada, Urmia, a village in West Azerbaijan Province, Iran
* Ada, Karaman, a village in Karaman Province, ...
and many
dialects
The term dialect (from Latin , , from the Ancient Greek word , 'discourse', from , 'through' and , 'I speak') can refer to either of two distinctly different types of linguistic phenomena:
One usage refers to a variety of a language that is a ...
of
BASIC
BASIC (Beginners' All-purpose Symbolic Instruction Code) is a family of general-purpose, high-level programming languages designed for ease of use. The original version was created by John G. Kemeny and Thomas E. Kurtz at Dartmouth College ...
, 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 (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), the smallest standalone element of an imperative programming language
*Statement (logic), declarative sentence that is either true or false
*Statement, a declarative ...
(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
A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech.
Types
* A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
, do not distinguish between functions and subroutines.
In strictly
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
languages such as
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, 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, consequence ...
, 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 that return a value, since functions that do not return a value have no use unless they can cause a side effect.
In
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s such as
C,
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
, and
C#, functions that return a value and functions that return no value are both called "functions" (not to be confused with
mathematical functions
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
or
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
, which are different concepts).
A language's
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
will usually translate procedure calls and returns into machine instructions according to a well-defined
calling convention
In computer science, a calling convention is an implementation-level (low-level) scheme for how subroutines or functions receive parameters from their caller and how they return a result. When some code calls a function, design choices have been ...
, so that functions 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 functions include:
*
Decomposing
Decomposition or rot 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 e ...
a complex programming task into simpler steps: this is one of the two main tools of
structured programming
Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection ( if/then/else) and repetition ( ...
, along with
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s
* Reducing
duplicate code In computer programming, duplicate code is a sequence of source code that occurs more than once, either within a program or across different programs owned or maintained by the same entity. Duplicate code is generally considered undesirable for a n ...
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 function
* Improving readability of code by replacing a block of code with a function call where
descriptivefunction 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
traceability Traceability 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 capab ...
(i.e. most languages offer ways to obtain the call trace which includes the names of the involved functions and perhaps even more information such as file names and line numbers); by not decomposing the code into functions, debugging would be severely impaired
Disadvantages
Compared to using in-line code, invoking a function imposes some
computational overhead
In computer science, overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to perform a specific task. It is a special case of engineering overhead. Overhead can be a decidin ...
in the call mechanism.
A function typically requires standard
housekeeping
Housekeeping is the management and routine support activities of running an organised physical institution occupied or used by people, like a house, ship, hospital or factory, such as tidying, cleaning, cooking, routine maintenance, shopping, ...
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. It was built at the University of Manchester by Frederic Calland Williams, Frederic C. Williams, Tom Kilburn, and Ge ...
and the
RCA 1802
The COSMAC (Complementary Symmetry Monolithic Array Computer) is an 8-bit microprocessor family introduced by RCA. It is historically notable as the first CMOS microprocessor. The first production model was the two-chip CDP1801R and CDP1801U, w ...
, 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 spot of a function or subroutine is the location (line of code) where the function is called (or may be called, through dynamic dispatch). A call site is where zero or more arguments are passed to the function, and zero or more r ...
.
Subroutines were implemented in
Konrad Zuse
Konrad Ernst Otto 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-c ...
's
Z4 in 1945.
In 1945,
Alan M. Turing 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, general-purpose digital computer, completed in 1945. There were other computers that had these features, but the ENIAC had all of them in one packa ...
team and developed an idea for subroutines for the
ENIAC
ENIAC (; Electronic Numerical Integrator and Computer) was the first programmable, electronic, general-purpose digital computer, completed in 1945. There were other computers that had these features, but the ENIAC had all of them in one packa ...
computer she was programming during World War II.
She and the other ENIAC programmers used the subroutines to help calculate missile trajectories.
Goldstine 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 ...
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 on October 21, 1959, and marketed as an inexpensive scientific computer. After a total production of about two thousand machines, it was withdrawn on November 19, 1970. Modified versions of the 1620 were used as ...
, the
Intel 4004
The Intel 4004 is a 4-bit central processing unit (CPU) released by Intel Corporation in 1971. Sold for US$60, it was the first commercially produced microprocessor, and the first in a long line of Intel CPUs.
The 4004 was the first signific ...
and
Intel 8008
The Intel 8008 ("''eight-thousand-eight''" or "''eighty-oh-eight''") is an early byte-oriented microprocessor designed by Computer Terminal Corporation (CTC), implemented and manufactured by Intel, and introduced in April 1972. It is an 8-bit CP ...
, and the
PIC microcontroller
PIC (usually pronounced as ''"pick"'') is a family of microcontrollers made by Microchip Technology, derived from the PIC1650"PICmicro Family Tree", PIC16F Seminar Presentation originally developed by General Instrument's Microelectronics ...
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 United States. It was designed principally by J. Presper Eckert and John Mauchly, the invento ...
, the
PDP-1
The PDP-1 (''Programmed Data Processor-1'') is the first computer in Digital Equipment Corporation's PDP series and was first produced in 1959. It is famous for being the computer most important in the creation of hacker culture at Massachusetts ...
, and the
IBM 1130
The IBM 1130 Computing System, introduced in 1965, was IBM's least expensive computer at that time. A binary 16-bit machine, it was marketed to price-sensitive, computing-intensive technical markets, like education and engineering, succeeding th ...
—typically use a
calling convention
In computer science, a calling convention is an implementation-level (low-level) scheme for how subroutines or functions receive parameters from their caller and how they return a result. When some code calls a function, design choices have been ...
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
IBM System/360
The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
had a subroutine call instruction that placed the saved instruction counter value into a general-purpose register; this can be used to support arbitrarily deep subroutine nesting and recursive subroutines. The
PDP-11
The PDP-11 is a series of 16-bit minicomputers sold by Digital Equipment Corporation (DEC) from 1970 into the 1990s, one of a set of products in the Programmed Data Processor (PDP) series. In total, around 600,000 PDP-11s of all models were sold, ...
(1970) is one of the first computers with a stack-pushing subroutine call instruction; this feature also supports both arbitrarily deep subroutine nesting and recursive subroutines.
[
]Guy Lewis Steele Jr.
Guy Lewis Steele Jr. (; born October 2, 1954) is an American computer scientist who has played an important role in designing and documenting several computer programming languages and technical standards.
Biography
Steele was born in Missouri ...
AI Memo
AI is artificial intelligence, intellectual ability in machines and robots.
Ai, AI or A.I. may also refer to:
Animals
* Ai (chimpanzee), an individual experimental subject in Japan
* Ai (sloth) or the pale-throated sloth, northern Amazonian ma ...
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
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 II. The IBM FORTRAN II compiler was released in 1958.
ALGOL 58
ALGOL 58, originally named IAL, is one of the family of ALGOL computer programming languages. It was an early compromise design soon superseded by ALGOL 60. According to John Backus
The Zurich ACM-GAMM Conference had two principal motives in pro ...
and other early programming languages also supported procedural programming.
Libraries
Even with this cumbersome approach, subroutines proved very useful. They allowed the use of the same code in many different programs. 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 paper tape
Five- and eight-hole punched paper tape
Paper tape reader on the Harwell computer with a small piece of five-hole tape connected in a circle – creating a physical program loop
Punched tape or perforated paper tape is a form of data storage ...
. 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 card
A punched card (also punch card or punched-card) is a piece of stiff paper that holds digital data represented by the presence or absence of holes in predefined positions. Punched cards were once common in data processing applications or to di ...
s 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
In computer science, self-modifying code (SMC) is code that alters its own instructions while it is executing – usually to reduce the instruction path length and improve performance or simply to reduce otherwise repetitively similar code, ...
, computer designers eventually provided an ''
indirect jump'' instruction, whose operand, instead of being the
return address
In postal mail, a return address is an explicit inclusion of the address of the person sending the message. It provides the recipient (and sometimes authorized intermediaries) with a means to determine how to respond to the sender of the message i ...
itself, was the location of a variable or
processor 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. ...
containing the return address.
On those computers, instead of modifying the function's return jump, the calling program would store the return address in a variable so that when the function 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
overhead significantly.
In the IBM
System/360
The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
, 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
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
.
In systems such as the
HP 2100
The HP 2100 is a series of 16-bit minicomputers that were produced by Hewlett-Packard (HP) from the mid-1960s to early 1990s. Tens of thousands of machines in the series were sold over its twenty-five year lifetime, making HP the fourth largest mi ...
, 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
Lotus 1-2-3 is a discontinued spreadsheet program from Lotus Software (later part of IBM). It was the first killer application of the IBM PC, was hugely popular in the 1980s, and significantly contributed to the success of IBM PC-compatibles i ...
, 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 reference
A circular reference is a series of references where the last object references the first, resulting in a closed loop.
In language
A circular reference is not to be confused with the logical fallacy of a circular argument. Although a circular ...
s 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
The IBM Personal Computer (model 5150, commonly known as the IBM PC) is the first microcomputer released in the IBM PC model line and the basis for the IBM PC compatible de facto standard. Released on August 12, 1981, it was created by a team ...
.
Call stack
Most modern implementations of a function call use a
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or ma ...
, a special case of the
stack data structure, to implement function 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
In computer engineering, a reduced instruction set computer (RISC) is a computer designed to simplify the individual instructions given to the computer to accomplish tasks. Compared to the instructions given to a complex instruction set comput ...
(RISC) and
very long instruction word
Very long instruction word (VLIW) refers to instruction set architectures designed to exploit instruction level parallelism (ILP). Whereas conventional central processing units (CPU, processor) mostly allow programs to specify instructions to exe ...
(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
Forth or FORTH may refer to:
Arts and entertainment
* ''forth'' magazine, an Internet magazine
* ''Forth'' (album), by The Verve, 2008
* ''Forth'', a 2011 album by Proto-Kaw
* Radio Forth, a group of independent local radio stations in Scotla ...
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 functions, 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
automatic memory management
In computer science, garbage collection (GC) is a form of automatic memory management. The ''garbage collector'' attempts to reclaim memory which was allocated by the program, but is no longer referenced; such memory is called '' garbage''. ...
.
However, another advantage of the call stack method is that it allows
recursive function calls, since each nested call to the same procedure gets a separate instance of its private data.
In a
multi-threaded
In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. The implementation of threads and processes dif ...
environment, there is generally more than one stack.
An environment that fully supports
coroutine
Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative ...
s or
lazy evaluation
In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).
The b ...
may use data structures other than stacks to store their activation records.
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
In software, a stack overflow occurs if the call stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program. The size of the call stack depends on many fac ...
), 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.
Examples
C and C++
In the
C and
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
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 differentl ...
, 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);
.
BASIC
BASIC (Beginners' All-purpose Symbolic Instruction Code) is a family of general-purpose, high-level programming languages designed for ease of use. The original version was created by John G. Kemeny and Thomas E. Kurtz at Dartmouth College ...
dialects
Microsoft Small Basic
Microsoft Small Basic is a programming language, interpreter and associated IDE. Microsoft's simplified variant of BASIC, it is designed to help students who have learnt visual programming languages such as Scratch learn text-based programming ...
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 (classic)
The original Visual Basic (also referred to as Classic Visual Basic) is a third-generation event-driven programming language from Microsoft known for its Component Object Model (COM) programming model first released in 1991 and declared leg ...
In the
Visual Basic (classic) 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
In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. O ...
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
yVal'' – 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
yRef'' – 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
In
PL/I
PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language developed and published by IBM. It is designed for scientific, engineering, business and system programming. I ...
a called procedure may be passed a ''
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) function 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
In
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, 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
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,
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
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
In postal mail, a return address is an explicit inclusion of the address of the person sending the message. It provides the recipient (and sometimes authorized intermediaries) with a means to determine how to respond to the sender of the message i ...
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
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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 a recursive function in C/C++ to find
Fibonacci
Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Western ...
numbers:
int Fib(int n)
Early languages like
Fortran did not initially support recursion because variables were statically allocated, as well as the location for the return address.
Early computer instruction sets made storing return addresses and variables on a stack difficult. Machines with
index registers
An index register in a computer's CPU is a processor register (or an assigned memory location) used for pointing to operand addresses during the run of a program. It is useful for stepping through strings and arrays. It can also be used for hol ...
or
general-purpose registers
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. ...
, e.g.,
CDC 6000 series The CDC 6000 series is a discontinued family of mainframe computers manufactured by Control Data Corporation in the 1960s. It consisted of the CDC 6200, CDC 6300, CDC 6400, CDC 6500, CDC 6600 and CDC 6700 computers, which were all extremely rapid a ...
,
PDP-6
The PDP-6, short for Programmed Data Processor model 6, is a computer developed by Digital Equipment Corporation (DEC) during 1963 and first delivered in the summer of 1964.
It was an expansion of DEC's existing 18-bit systems to use a 36-bit da ...
,
GE 635
The GE-600 series was a family of 36-bit mainframe computers originating in the 1960s, built by General Electric (GE). When GE left the mainframe business the line was sold to Honeywell, which built similar systems into the 1990s as the division ...
,
System/360
The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
,
UNIVAC 1100 series
The UNIVAC 1100/2200 series is a series of compatible 36-bit computer systems, beginning with the UNIVAC 1107 in 1962, initially made by Sperry Rand. The series continues to be supported today by Unisys Corporation as the ClearPath Dorado Series. ...
, could use one of those registers as a
stack pointer
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or mach ...
.
Modern languages after
ALGOL
ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
such as
PL/I
PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language developed and published by IBM. It is designed for scientific, engineering, business and system programming. 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
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or ma ...
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 frame
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or mac ...
s''.
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, Fren ...
, PL/I, and
Ada
Ada may refer to:
Places
Africa
* Ada Foah, a town in Ghana
* Ada (Ghana parliament constituency)
* Ada, Osun, a town in Nigeria
Asia
* Ada, Urmia, a village in West Azerbaijan Province, Iran
* Ada, Karaman, a village in Karaman Province, ...
also support
nested function
In computer programming, a nested function (or nested procedure or subroutine) is a function which is defined within another function, the ''enclosing function''. Due to simple recursive scope rules, a nested function is itself invisible outside o ...
s, which are functions callable only within the
scope
Scope or scopes may refer to:
People with the surname
* Jamie Scope (born 1986), English footballer
* John T. Scopes (1900–1970), central figure in the Scopes Trial regarding the teaching of evolution
Arts, media, and entertainment
* Cinem ...
of an outer (parent) function. Inner functions have access to the local variables of the outer function 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''. A recursive subprogram must be reentrant. Reentrant subprograms are also useful in
multi-threaded
In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. The implementation of threads and processes dif ...
situations since multiple threads can call the same subprogram without fear of interfering with each other. In the
IBM CICS
IBM CICS (Customer Information Control System) is a family of mixed-language application servers that provide online transaction management and connectivity for applications on IBM mainframe systems under z/OS and z/VSE.
CICS family products ...
transaction processing system
Transaction processing is a way of computing that divides work into individual, indivisible operations, called transactions. A transaction processing system (TPS) is a software system, or software/ hardware combination, that supports transaction ...
, ''quasi-reentrant'' was a slightly less restrictive, but similar, requirement for application programs that were shared by many threads.
Overloading
In
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 based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pr ...
, 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
overloaded.
Here is an example of function overloading in
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
, demonstrating the implementation of two functions with the same name (Area) but different parameters:
#include
double Area(double h, double w)
/* The first Area function is for finding the area of a rectangle,
* so it accepts two numbers as parameters, for the height and width. */
double Area(double r)
/* The second Area function is for finding the area of a circle,
* so it only accepts one number as a parameter, for the radius. */
int main()
As another example, a function might construct an
object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ...
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'' 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. Depending on the implementation, closures can serve as a mechanism for side-effects.
Conventions
A wide number of conventions for the coding of functions have been developed. Pertaining to their naming, many developers have adopted the approach that the name of a function should be a
verb
A verb () is a word (part of speech) that in syntax generally conveys an action (''bring'', ''read'', ''walk'', ''run'', ''learn''), an occurrence (''happen'', ''become''), or a state of being (''be'', ''exist'', ''stand''). In the usual descri ...
when it does a certain task, and
adjective
In linguistics, an adjective (list of glossing abbreviations, abbreviated ) is a word that generally grammatical modifier, modifies a noun or noun phrase or describes its referent. Its semantic role is to change information given by the noun.
Tra ...
when it makes some inquiry, and a
noun
A noun () is a word that generally functions as the name of a specific object or set of objects, such as living creatures, places, actions, qualities, states of existence, or ideas.Example nouns for:
* Living creatures (including people, alive, d ...
when it is used to substitute variables.
Some programmers suggest that a function should perform only one task, and if a function does perform more than one task, it should be split up into more functions. They argue that functions are key components in
code maintenance, and their roles in the program must remain distinct.
Proponents of
modular programming
Modular programming is a software design technique that emphasizes separating the functionality of a program into independent, interchangeable modules, such that each contains everything necessary to execute only one aspect of the desired function ...
(modularizing code) advocate that each function should have minimal dependency on other pieces of code. For example, the use of
global variable
In computer programming, a global variable is a variable with global scope, meaning that it is visible (hence accessible) throughout the program, unless shadowed. The set of all global variables is known as the ''global environment'' or ''global s ...
s is generally deemed unwise by advocates for this perspective, because it adds tight coupling between the function and these global variables. If such coupling is not necessary, their advice is to
refactor functions to accept passed
parameters
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
instead. However, increasing the number of parameters passed to functions 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
In computer programming, a return code or an error code is a numeric or alphanumeric code that is used to determine the nature of an error and why it occurred. They are also commonly found in consumer electronics and devices when they attempt to ...
'', an integer value placed by the subprogram in some standard location, which encodes the normal and exceptional conditions.
In the
IBM System/360
The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
, 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
In computer programming, a branch table or jump table is a method of transferring program control ( branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump instruction ...
index into a branch table often located immediately after the call instruction to avoid extra conditional tests, further improving efficiency. In the
System/360
The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
assembly language
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
, 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 function calls
There is a significant runtime
overhead in calling a function, 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 function call also implies automatic testing of the function's return code or the handling of
exceptions that it may raise. A significant source of overhead in object-oriented languages is the intensively used
dynamic dispatch
In computer science, dynamic dispatch is the process of selecting which implementation of a polymorphic operation (method or function) to call at run time. It is commonly employed in, and considered a prime characteristic of, object-oriented ...
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 by virtue of
Rice's theorem
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a synta ...
). 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
In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the called function. Inline expansion is similar to macro expansion, but occurs during compilation, without ch ...
'' or ''inlining'' of the subprogram's body at each
call site
In programming, a spot of a function or subroutine is the location (line of code) where the function is called (or may be called, through dynamic dispatch). A call site is where zero or more arguments are passed to the function, and zero or more r ...
(versus branching to the function 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 translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
to
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 function.
See also
*
Function (mathematics)
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the funct ...
*
Method (computer programming)
A method in object-oriented programming (OOP) is a procedure associated with a message and an object. An object consists of ''state data'' and ''behavior''; these compose an ''interface'', which specifies how the object may be utilized by any of ...
*
Builtin function
In computer software, in compiler theory, an intrinsic function (or built-in function) is a function (subroutine) available for use in a given programming language whose implementation is handled specially by the compiler. Typically, it may subst ...
*
Evaluation strategy
In a programming language, an evaluation strategy is a set of rules for evaluating expressions. The term is often used to refer to the more specific notion of a ''parameter-passing strategy'' that defines the kind of value that is passed to the f ...
*
Modular programming
Modular programming is a software design technique that emphasizes separating the functionality of a program into independent, interchangeable modules, such that each contains everything necessary to execute only one aspect of the desired function ...
*
Transclusion
In computer science, transclusion is the inclusion of part or all of an electronic document into one or more other documents by reference via hypertext. Transclusion is usually performed when the referencing document is displayed, and is normal ...
*
Operator overloading
In computer programming, operator overloading, sometimes termed ''operator ad hoc polymorphism'', is a specific case of polymorphism, where different operators have different implementations depending on their arguments. Operator overloading is ...
*
Protected procedure
In computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical ...
*
Functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
*
Command–query separation
Command-query separation (CQS) is a principle of imperative computer programming. It was devised by Bertrand Meyer as part of his pioneering work on the Eiffel programming language.
It states that every method should either be a ''command'' tha ...
(CQS)
*
Coroutine
Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative ...
s, subprograms that call each other as if both were the main programs
*
Event handler
In programming and software design, an event is an action or occurrence recognized by software, often originating asynchronously from the external environment, that may be handled by the software. Computer events can be generated or triggered ...
, a subprogram that is called in response to an input event or
interrupt
In digital computers, an interrupt (sometimes referred to as a trap) is a request for the processor to ''interrupt'' currently executing code (when permitted), so that the event can be processed in a timely manner. If the request is accepted, ...
*
Asynchronous procedure call
Asynchronous procedure call is a unit of work in a computer. Usually a program works by executing a series of synchronous procedure calls on some thread. But if some data are not ready (for example, a program waits user to reply), then keeping thr ...
, a subprogram that is called after its parameters are set by other activities
References
{{Authority control
Source code
Articles with example C code
Holism
Programming constructs
Subroutines