Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , a subroutine or subprogram (also called procedure
Procedure
A procedure is a specified series of actions, acts or operations which have to be executed in the same manner in order to always obtain the same result under the same circumstances .... , function, method
Method (computer science)
In object-oriented programming, a method is a subroutine that is exclusively associated either with a class or with an object . Like a procedure in procedural programming languages, a method usually consists of a sequence of statement to perform an action, a set of input parameter to customize those actions, and possibly an output value... , or routine) is a portion of code within a larger program
Computer program
Computer programs are Instruction for a computer. A computer requires programs to function. Moreover, a computer program does not run unless its instructions are executed by a Central processing unit; however, a program may communicate an Algorithm#Formalization of algorithms to people without running.... , which performs a specific task
Task (computers)
A task is "an execution path through address space". In other words, a set of Computer program instruction s that are loaded in computer storage.... and is relatively independent of the remaining code. (The name "method
Method (computer science)
In object-oriented programming, a method is a subroutine that is exclusively associated either with a class or with an object . Like a procedure in procedural programming languages, a method usually consists of a sequence of statement to perform an action, a set of input parameter to customize those actions, and possibly an output value... " is mostly used in object-oriented programming
Object-oriented programming
Object-oriented programming is a programming paradigm that uses "Object_" and their interactions to design applications and computer programs.... , specifically for subroutines that are part of object
Object (computer science)
In its simplest embodiment, an object is an allocated region of storage. Since programming languages use variable#Computer_programmings to access objects, the terms object and variable are often used interchangeably.... s or object class
Type class
In computer science, a type class is a type system construct that supports Type polymorphism#Ad-hoc polymorphism. This is achieved by adding constraints to type variables in Parametric polymorphism#Parametric polymorphism types.... es.)
As the name suggests, a subprogram or subroutine behaves in much the same way as a complete computer program that is used as a step in a larger program.
Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , a subroutine or subprogram (also called procedure
Procedure
A procedure is a specified series of actions, acts or operations which have to be executed in the same manner in order to always obtain the same result under the same circumstances .... , function, method
Method (computer science)
In object-oriented programming, a method is a subroutine that is exclusively associated either with a class or with an object . Like a procedure in procedural programming languages, a method usually consists of a sequence of statement to perform an action, a set of input parameter to customize those actions, and possibly an output value... , or routine) is a portion of code within a larger program
Computer program
Computer programs are Instruction for a computer. A computer requires programs to function. Moreover, a computer program does not run unless its instructions are executed by a Central processing unit; however, a program may communicate an Algorithm#Formalization of algorithms to people without running.... , which performs a specific task
Task (computers)
A task is "an execution path through address space". In other words, a set of Computer program instruction s that are loaded in computer storage.... and is relatively independent of the remaining code. (The name "method
Method (computer science)
In object-oriented programming, a method is a subroutine that is exclusively associated either with a class or with an object . Like a procedure in procedural programming languages, a method usually consists of a sequence of statement to perform an action, a set of input parameter to customize those actions, and possibly an output value... " is mostly used in object-oriented programming
Object-oriented programming
Object-oriented programming is a programming paradigm that uses "Object_" and their interactions to design applications and computer programs.... , specifically for subroutines that are part of object
Object (computer science)
In its simplest embodiment, an object is an allocated region of storage. Since programming languages use variable#Computer_programmings to access objects, the terms object and variable are often used interchangeably.... s or object class
Type class
In computer science, a type class is a type system construct that supports Type polymorphism#Ad-hoc polymorphism. This is achieved by adding constraints to type variables in Parametric polymorphism#Parametric polymorphism types.... es.)
As the name suggests, a subprogram or subroutine behaves in much the same way as a complete computer program that is used as a step in a larger program. A subroutine is often coded so that it can be executed (called) several times and/or from several places during a single execution of the program, including from other subroutines, and branch back (return) to the point after the call once its task is done.
Subroutines are a powerful programming tool , and the syntax
Syntax
In linguistics, syntax is the study of the principles and rules for constructing Sentence s in natural languages. In addition to referring to the discipline, the term syntax is also used to refer directly to the rules and principles that govern the sentence structure of any individual language, as in "the Irish syntax".... of many programming language
Programming language
A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer.... s includes support for writing and using them. Judicious use of subroutines (for example, though the structured programming
Structured programming
Structured programming can be seen as a subset or subdiscipline of procedural programming, one of the major programming paradigms. It is most famous for removing or reducing reliance on the GOTO Statement .... 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
Library (computer science)
In computer science, a library is a collection of subroutines or Class used to develop software. Libraries contain code and data that provide services to independent programs.... , are an important mechanism for sharing and trading software.
Professor Stanley Gill was a United Kingdom computer scientist credited, along with Maurice Wilkes and David Wheeler , with the invention of the first computer subroutine.... are credited with the invention of this concept, which they referred to as closed subroutine .
Main concepts
The main component of a subroutine is its body, the piece of program that is executed when the subprogram is called, and defines its effect.
A subroutine may be coded so as to obtain a specific set of data values from the calling program (its parameters
Parameter (computer science)
In computer programming, a parameter is a special kind of variable#In_computer_programming that refers to data that a subroutine receives to operate on.... ), and eventually provide a specific set of values to it (its return values). Indeed, a common use of subroutines is to implement mathematical function
Function (mathematics)
The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output.... s, such as the logarithm
Logarithm
In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number.... of a number or the determinant
Determinant
In algebra, a determinant is a function depending on n that associates a scalar , det, to an n?n square matrix A. The fundamental geometric meaning of a determinant is a scale factor for measure when A is regarded as a linear transformation.... of a matrix
Matrix
Matrix usually refers to:* Matrix , a mathematical object generally represented as an array of numbers;* The Matrix , a series of films, video games and comic books;... , for which the return values are entirely determined by the parameters. However, a subroutine call may also have other side effect
Side effect
Side effect can mean:* Adverse reaction, an unintended consequence specifically arising from drug therapy* Therapeutic effect, an unintended but desirable consequence of any kind of medical treatment... s, such as reading from or writing to a peripheral device, examining or modifying data structure
Data structure
A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data.... s in the computer's memory
Memory
In psychology, memory is an organism's mental ability to store, retain and recall information. Traditional studies of memory began in the fields of philosophy, including techniques of mnemonic.... , halting the program
Computer program
Computer programs are Instruction for a computer. A computer requires programs to function. Moreover, a computer program does not run unless its instructions are executed by a Central processing unit; however, a program may communicate an Algorithm#Formalization of algorithms to people without running.... or the machine
Machine
A machine is any device that uses energy to perform some activity. In common usage, the meaning is that of a device having parts that perform or assist in performing any type of work.... , or even delaying the program's execution for a specified time.
A subroutine can be coded so that it may call itself recursively
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... , at one or more places, in order to perform its task. This technique allows direct implementation of functions defined by mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then... and recursive divide and conquer algorithms.
In computing, a high-level programming language is a programming language with strong Abstraction from the details of the computer. In comparison to low-level programming languages, it may use natural language elements, be easier to use, or more Porting across platforms.... s usually include specific constructs for
delimiting the part of the program (body) that comprises the subroutine,
In computer science, Identifiers are Lexical Token s that name entity. The concept is analogy to that of a "name". Identifiers are used extensively in virtually all information processing systems.... to the subroutine,
specifying the names and/or types of its parameters and/or return values,
In computer programming, a temporary variable is a variable whose purpose is short-lived, usually to hold temporarily data that will soon be discarded, or before it can be placed at a more permanent Memory location.... s,
identifying variables outside the subroutine which are accessible within it,
calling the subroutine,
providing values to its parameters,
specifying the return values from within its body,
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after where the subroutine was called ? known as its return address.... to the calling program,
Exception may refer to:* An Action that is not part of ordinary operations or standards* exception handling, in programming languages* Exception , the second single from Ana Johnsson's second album Little Angel... encountered during the call,
A library is a collection of information, sources, resources, books, and services, and the structure in which it is housed: it is organized for use and maintained by a public body, an institution, or a private individual.... , object
Object
Object may refer to,* Object , a thing, being or concept** Entity, something that is tangible and within the grasp of the senses* Object , a sentence element, such as a direct object or an indirect object... , class
Pascal is an influential imperative programming and Procedural programming programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structure.... , Fortran
Fortran
Fortran is a general-purpose programming language, procedural programming language, imperative programming language programming language that is especially suited to numerical analysis and scientific computing.... , and Ada
Ada (programming language)
Ada is a structured programming, statically typed, Imperative programming, and Object-oriented programming high-level language computer programming programming language, extended from Pascal and other languages.... , distinguish between functions or function subprograms, which provide an explicit return value to the calling program, and subroutines or procedures, which do not. Other languages, such as C
C (programming language)
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... and Lisp, do not make this distinction, and treat those terms as synonymous.
Advantages
The advantages of breaking a program into subroutines include:
Duplicate code is a computer programming term for 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.... of code within a program,
In writing and typography Readability is defined as reading ease, especially as it results from a writing style. Extensive research has shown that easy-reading text improves comprehension, retention, reading speed, and reading persistence.... , maintainability, and extensibility,
Decomposition in computer science, also known as factoring, refers to the process by which a complex problem or system is broken down into parts that are easier to conceive, understand, program, and maintain.... a complex programming task into simpler steps
dividing a large programming task among various programmer
Programmer
A programmer is someone who writes computer software. The term computer programmer can refer to a specialist in one area of computer programming or to a generalist who writes code for many kinds of software.... s, or various stages of a project,
Information hiding in computer science is the principle of hiding of design decisions in a computer program that are most likely to change, thus protecting other parts of the program from change if the design decision is changed.... implementation details from users of the subroutine, and,
limiting the consequences of program errors or hardware failures.
History
Self-modifying code
The first use of subprograms was on early computers that were programmed in machine code
Machine code
Machine code or machine language is a system of instructions and data executed directly by a computer's central processing unit. Machine code may be regarded as a primitive programming language or as the lowest-level representation of a compiled and/or assembly language computer program.... or assembly language
Assembly language
An assembly language is a low-level language for programming computers. It implements a symbolic representation of the numeric machine codes and other constants needed to program a particular CPU architecture.... , and did not have a specific call instruction . On these computers, subroutines had to be called by a sequence of lower level machine instructions, possibly implemented as a macro. These instructions typically modified the program itself
Self-modifying code
In computer science, self-modifying code is Code that alters its own Instruction while it is Execution - usually to reduce the instruction path length and improve performance.... , replacing the operand
Operand
An operand is one of the inputs of an operator in mathematics. The following arithmetic expression shows an example of operators and operands:... of a branch instruction at the end of the procedure's body so that it would return to the proper location in the calling program (the return address
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 with a means to determine how to respond to the sender of the message if needed.... , usually just after the instruction that jumped into the subroutine).
Subroutine libraries
Even with this cumbersome approach, subroutines proved very useful. For one thing they allowed the same code to be used in many different programs. Morever, memory was a very scarce resource on early computers, and subroutines allowed significant savings in program size.
In many early computers, the program instructions were entered into memory from a punched paper tape
Punched tape
Punched tape or paper tape is a largely obsolete form of data storage, consisting of a long strip of paper in which holes are punched to store data.... . Each subroutine could then be provided by a separate piece of tape, loaded or spliced before or after the main program; and the same subroutine tape could then be used by many different programs. A similar approach was used in computers whose main input was through punched cards. The name "subroutine library" originally meant a library, in the literal sense, which kept indexed collections of such 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 jump" instruction, whose operand, instead of being the return address, was the location of a variable that contained said address.
In those computers, instead of modifying the subroutine's return jump, the calling program would store the return address in some predefined location. When done, the subroutine had only to execute an indirect jump through that location.
The IBM System/360 is a mainframe computer system family announced by IBM on April 7, 1964. It was the first family of computers making a clear distinction between computer architecture and implementation, allowing IBM to release a suite of compatible designs at different price points.... , for example, the return address was typically saved in a processor register
Processor register
In computer architecture, a processor register is a small amount of Computer storage available on the CPU whose contents can be accessed more quickly than storage available elsewhere.... (usually as part of the branch instructions (BAL or BALR). If necessary, the subroutine would save the contents of that register to a private memory location such as a register stack
Stack (data structure)
In computer science, a stack is an abstract data type and data structure based on the principle of LIFO . Stacks are used extensively at every level of a modern computer system.... (or, for simple subroutines, not alter that designated register whilst executing that code). Subroutines would therefore often be coded without the need for a stack, using just a single machine instruction (BAL) to call the subroutine and another single machine instruction (BR) to return, thereby minimizing overhead
Computational overhead
In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal.... significantly. Additionally, where a 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
Branch table
In computer programming, a branch table is a term used to describe an efficient method of transferring program control to another part of a program using a table of branch Instruction s.... index - with the branch table often located immediately after the call instruction to avoid extra conditional tests, further improving efficiency
Algorithmic efficiency
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. The two most frequently encountered are... .
Example: BAL 14,SUBRTN01 go to sub-routine , using reg 14 as save register (sets reg 15 to 0,4,8 as return value)
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 }
Jump to subroutine
Another advance was the "jump to subroutine" instruction, which combined the saving of the return address with the calling jump. In the HP 2100
HP 2100
The HP 2100 was a series of minicomputers produced by Hewlett-Packard from the mid 1960s to early 1990s. The 2100 was also a specific model in this series.... assembly language, for example, one would write
...
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 them 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 technique was used by Lotus 1-2-3
Lotus 1-2-3
Lotus 1-2-3 is a spreadsheet program from Lotus Software . It was the IBM PC's first "killer application"; its huge popularity in the mid-1980s contributed significantly to the success of the IBM PC in the corporate environment.... , 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
Circular reference
A circular reference, sometimes referred to as a run-around, is a series of references where the last object references the first, thus causing the whole series of references to be unusable.... 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
IBM PC
The IBM Personal Computer, commonly known as the IBM PC, is the original version and progenitor of the IBM PC compatible hardware platform .... .
In computer science, a call stack is a dynamic Stack data structure that stores information about the active subroutines of a computer program.... , a special case of the stack data structure
Stack (data structure)
In computer science, a stack is an abstract data type and data structure based on the principle of LIFO . Stacks are used extensively at every level of a modern computer system.... , 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 RISC and 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 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 implementations, used two separate call stacks, one mainly for control information (like return addresses and loop counters) and the other for data.
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 which 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 automatic memory management
Garbage collection
Garbage collection may refer to:* Waste collection, one part of the municipal waste management cycle.* Garbage collection , the detection and pruning of unused or inaccessible data structures.... .
However, another advantage of the call stack method is that it allows recursive
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... 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
Stack overflow
In software, a stack overflow occurs when too much computer memory is used on the call stack. In many programming languages the call stack contains a limited amount of memory, usually determined at the start of the program.... ), and accessing the local variables and parameters by frame-relative addresses, instead of absolute addresses. The cost may be realized in increased excution time, or increased processor complexity, or both.
This overhead is most obvious and objectionable in leaf procedures 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 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) which will be needed after Q returns.
The parts of the program which are responsible for the entry into and exit out of the subroutine (and hence, the setting up and removal of each stack frame) are called the function prologue
Function prologue
In assembly language Computer programming, the function prologue is a few lines of code which appear at the beginning of a function, which prepare the Call stack and Processor register for use within the function.... and epilogue.
If the procedure or function itself uses stack handling commands, outside of the prologue and epilogue, e.g. to store intermediate calculation values, the programmer needs to keep track of the number of 'push' and 'pop' instructions so as not to corrupt the original return address.
In computer science, imperative programming is a programming paradigm that describes computation in terms of statement s that change a program state .... languages, subprograms may have so-called side-effects; that is, they may cause changes that remain after the subprogram has returned. It can be technically very difficult to predict whether a subprogram has a side-effect or not. In imperative programming, compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language . The most common reason for wanting to transform source code is to create an executable program.... s usually assume every subprogram has a side-effect to avoid complex analysis of execution paths. Because of its side-effects, a subprogram may return different results each time it is called, even if it is called with the same argument
Parameter (computer science)
In computer programming, a parameter is a special kind of variable#In_computer_programming that refers to data that a subroutine receives to operate on.... s. A simple example is a subprogram that implements a pseudorandom number generator
Pseudorandom number generator
A pseudorandom number generator is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state. Although sequences that are closer to truly random can be gen... ; that is, a subprogram that returns a random number each time it is called.
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data.... languages such as Haskell
Haskell (programming language)
Haskell is a standardized, purely functional programming language with non-strict programming language, named after logician Haskell Curry. The goals of the language are described as:... , subprograms can have no side effects, and 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 functional programming writing to a file is a side effect.
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... and C++
C++
C++ is a general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level programming language and low-level programming language language features.... programming languages, subprograms are referred to as "functions" (or "methods" when associated with a class
Class (computer science)
In object-oriented programming, a class is a programming language construct that is used as a blueprint to create Object s. This blueprint includes Attribute s and Method s that the created objects all share.... ). Note that these languages use the special keyword void to indicate that a function takes no parameters (especially in C) and/or does not return any value. Note that C/C++ functions can have side-effects, including modifying any variables whose addresses are passed as parameters (i.e. "passed by reference"). Examples:
void function1(void)
The function does not return a value and has to be called as a stand-alone function, e.g., function1;
int function2(void)
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 to 6 into the initial letter of the corresponding day of the week, namely 0 \u2192 'S', 1 \u2192 'M', ..., 6 \u2192 '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);".
Local variables, recursion and re-entrancy
A subprogram may find it useful to make use of a certain amount of "scratch" space; that is, memory used during the execution of that subprogram to hold intermediate results. Variables stored in this scratch space are referred to as local variables, and the scratch space itself is referred to as an activation record. An activation record typically has a return address
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 with a means to determine how to respond to the sender of the message if needed.... 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
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... is a useful technique for simplifying some complex algorithms, and breaking 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.
Fortran is a general-purpose programming language, procedural programming language, imperative programming language programming language that is especially suited to numerical analysis and scientific computing.... 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
PDP-8
The PDP-8 was the first successful commercial minicomputer, produced by Digital Equipment Corporation in the 1960s. DEC introduced it on 22 March 1965, and sold more than 50,000 systems, the most of any computer up to that date.... did not have support for hardware stack registers.
Modern languages after ALGOL such as Pl/1 and C almost invariably use a stack, usually supported 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
Call stack
In computer science, a call stack is a dynamic Stack data structure that stores information about the active subroutines of a computer program.... 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 referred to as stack frames.
In computer programming, a nested function is a subroutine which is lexically encapsulated within another function. It can only be called by the enclosing function or by functions directly or indirectly nested within the same enclosing function.... , which are subroutines callable only within the scope
Scope (programming)
In computer programming, scope is an enclosing context where values and expressions are associated. Various programming languages have various types of scopes.... of an outer (parent) subroutine. Inner subroutines have access to the local variables of the outer subroutine which called them. This is accomplished by storing extra context information within the activation record, also known as a display.
If a subprogram can function properly even when called while another execution is already in progress, that subprogram is said to be re-entrant. A recursive subprogram must be re-entrant. Re-entrant subprograms are also useful in multi-threaded
Thread (computer science)
In computer science, a thread of execution is a Fork of a computer program into two or more Concurrency running task s. The implementation of threads and process es differs from one operating system to another, but in most cases, a thread is contained inside a process.... situations, since multiple threads can call the same subprogram without fear of interfering with each other.
In computer science, a thread of execution is a Fork of a computer program into two or more Concurrency running task s. The implementation of threads and process es differs from one operating system to another, but in most cases, a thread is contained inside a process.... environment, there is generally more than one stack. An environment which fully supports coroutine
Coroutine
In computer science, coroutines are program components that generalize subroutines to allow multiple entry points for suspending and resuming of execution at certain locations.... s or lazy evaluation
Lazy evaluation
In computer programming, lazy evaluation is the technique of delaying a computation until such time as the result of the computation is known to be needed.... may use data structures other than stacks to store their activation records.
Overloading
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.
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
Method overloading
Method overloading is a feature found in various programming languages such as Ada , C Sharp , C++, D and Java that allows the creation of several subprograms with the same name which differ from each other in terms of the type of the input and the type of the output of the function.... .
As another example, a subroutine might construct an object 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).
Conventions
A number of conventions for the coding of subprograms have been developed. It has been commonly preferable that the name of a subprogram should be a verb when it does a certain task, an adjective when it makes some inquiry, and a noun when it is used to substitute variables and such.
Experienced programmers recommend that a subprogram perform only one task. If a subprogram performs more than one task, it should be split up into more subprograms. They argue that subprograms are key components in maintaining code and their roles in the program must be distinct.
Some advocate that each subprogram should have minimal dependency on other pieces of code. For example, they see the use of global variable
Global variable
In computer programming, a global variable is a variable that is accessible in every scope . Interaction mechanisms with global variables are called global environment mechanisms.... s as unwise because it adds tight-coupling between subprograms and global variables. If such coupling is not necessary at all, they advise to refactor subprograms to take parameters instead. This practice is controversial because it tends to increase the number of passed parameters to subprograms.
In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal.... associated with:-
passing parameters (which now frequently also involves copying existing data values if pointers are not used)
calling the subprogram
returning to the caller
and frequently
testing a return code passed by the subroutine (although the test can be eliminated in Assembler - see earlier example)
The actual overhead for each invocation depends on the local context at the point of call and the requirements specified in the architecture's application binary interface
Application binary interface
In computer software, an application binary interface describes the low-level interface between an application program and the operating system or an other application.... .
One technique used to eliminate this overhead is inline expansion
Inline expansion
In computing, inline expansion, or inlining, is a compiler optimization that replaces a function call site with the body of the callee. This optimization may improve time and space usage at runtime, at the possible cost of increasing the size of the final program.... of the subprogram call site
Call site
In programming, a call site of a function is a line in the code which calls a function. A call site passes zero or more argument to the function, and receives zero or more return values.... (literally, not using a subroutine). However, "inlining" often increases code size (if the subroutine is used more than once) and can introduce cache misses into a previously optimised block of code.
In computer science, dynamic dispatch is the process of mapping a Message passing to a specific sequence of code at runtime. This is done to support the cases where the appropriate method cannot be determined at compile-time .... can introduce further overheads - although the performance difference between indirect and direct calls on commodity CPUs has narrowed since the 1980s, because of research and work done by CPU designers (driven by the increasing popularity of object-oriented programming, which uses dynamic dispatch extensively). Also, software techniques have been developed to make dynamic dispatch more efficient.
Related terms and clarification
Different programming languages and methodologies possess notions and mechanisms related to subprograms:
Subroutine is practically synonymous with "subprogram." The former term may derive from the terminology of assembly language
Assembly language
An assembly language is a low-level language for programming computers. It implements a symbolic representation of the numeric machine codes and other constants needed to program a particular CPU architecture.... s and Fortran.
Function and Procedure are also synonymous with "subprogram" - with the distinction (in some programming languages) that "functions" generate return values and appear in expressions
Expression (programming)
An expression in a programming language is a combination of value s, variables, operator s, and function s that are interpreted according to the particular Order of operations and of association for a particular programming language, which computes and then produces another value.... , where "procedures" generate no return values and appear in statements
Statement (programming)
In computer programming a statement can be thought of as the smallest standalone element of an imperative programming language. A program is formed by a sequence of one or more statements.... . Hence, a subprogram that calculates the square root of a number would be a "function" (eg: y = sqrt(x)) where a subprogram to print out a number might be a "procedure" (eg: print(x)). This is not a distinction found in all programming languages and notably the C family of programming languages use the two terms interchangeably. See also: Command-Query Separation
Command-query separation
Command-query separation is a principle of Imperative_programming computer programming. It was devised by Bertrand Meyer as part of his pioneering work on the Eiffel .... .
A boolean-valued function, in some usages 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.... (a function that returns a boolean). In logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy 's [1958] Advice taker proposal, logic is used as a purely Declarative programming language representation language, and a automated theorem proving o... languages, often all subroutines are called "predicates", since they primarily determine success or failure.
In object-oriented programming, a method is a subroutine that is exclusively associated either with a class or with an object . Like a procedure in procedural programming languages, a method usually consists of a sequence of statement to perform an action, a set of input parameter to customize those actions, and possibly an output value... or Member function is a special kind of subprogram used in object-oriented programming
Object-oriented programming
Object-oriented programming is a programming paradigm that uses "Object_" and their interactions to design applications and computer programs.... that describes some behaviour of an object
Object (computer science)
In its simplest embodiment, an object is an allocated region of storage. Since programming languages use variable#Computer_programmings to access objects, the terms object and variable are often used interchangeably.... .
In computer science, a closure is a function that is evaluated in an environment containing one or more bound variables. When called, the function can access these variables.... is a subprogram together with the values of some of its variables captured from the environment in which it was created.
In computer science, coroutines are program components that generalize subroutines to allow multiple entry points for suspending and resuming of execution at certain locations.... is a subprogram that returns to its caller before completing.
In computer programming, an event handler is an asynchronous callback subroutine that handles inputs received in a program. Each event is a piece of application-level information from the underlying framework, typically the GUI toolkit.... , or simply "handler," is a subprogram that is called in response to an "event", such as a computer user moving the mouse or typing on the keyboard. The AppleScript
AppleScript
AppleScript is a scripting language devised by Apple Inc., and built into Mac OS. More generally, "AppleScript" is the word used to designate the Mac OS scripting interface, which is meant to operate in parallel with the graphical user interface.... scripting language simply uses the term "handler" as a synonym for subprogram. Event handlers are often used to respond to an Interrupt
Interrupt
In computing, an interrupt is an asynchronous communication signal from hardware indicating the need for attention or a synchronous event in software indicating the need for a change in execution.... - in which case they may be termed an Interrupt handler.
People who write compilers, and people who write in assembly language, deal with the low-level details involved in implementing subroutines:
In computer science, a calling convention is a scheme for how function s receive parameters from their caller and how they return a result; calling conventions can differ in:...
Nearly all implementations of subroutines involve a call stack
Call stack
In computer science, a call stack is a dynamic Stack data structure that stores information about the active subroutines of a computer program.... .
A link register, in many CPU architectures such as the IBM POWER, ARM architecture, and the PA-RISC family, is a special purpose processor register which holds the address to return to when a function call completes....
In assembly language Computer programming, the function prologue is a few lines of code which appear at the beginning of a function, which prepare the Call stack and Processor register for use within the function.... and function epilogue
In computer science, the term threaded code refers to a compiler implementation technique where the generated code has a form that essentially consists entirely of calls to subroutines.... makes code even more compact. It uses a small interpreter
Interpreter (computing)
In computer science, an interpreter normally means a computer program that execution , i.e. performs, instructions written in a programming language.... to execute subroutines that consist of lists of subroutine addresses. The lowest levels of subroutine are the only machine language.
Most subprograms typically implement the idea of an algorithm
Algorithm
In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing.... -- they are given a finite amount of information when they start, they are given no more information while they run, and they give out no information until they end.
However, each process
Process (computing)
In computing, a process is an Object of a computer program that is being sequentially executed by a computer system that has the ability to run several computer programs Concurrency .... , job
Job (software)
In computing a job is a term used to refer to a single instance of a Computer program. The term is mostly used on Computer multitasking systems.... , task
Task (computers)
A task is "an execution path through address space". In other words, a set of Computer program instruction s that are loaded in computer storage.... , or thread
Thread (computer science)
In computer science, a thread of execution is a Fork of a computer program into two or more Concurrency running task s. The implementation of threads and process es differs from one operating system to another, but in most cases, a thread is contained inside a process.... is a program or subprogram that typically sends and receives information many times before it ends.
The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output....
In object-oriented programming, a method is a subroutine that is exclusively associated either with a class or with an object . Like a procedure in procedural programming languages, a method usually consists of a sequence of statement to perform an action, a set of input parameter to customize those actions, and possibly an output value...
In computer programming, operator overloading is a specific case of polymorphism in which some or all of operator s like +, =, or have different implementations depending on the types of their arguments....
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data....
