SUPPORT THE WORK

GetWiki

Subroutine

ARTICLE SUBJECTS
aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
ARTICLE TYPES
essay  →
feed  →
help  →
system  →
wiki  →
ARTICLE ORIGINS
critical  →
discussion  →
forked  →
imported  →
original  →
Subroutine
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{Refimprove|date=February 2013}}In computer programming, a subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed.{{anchor|SUBROUTINE_DEFINITION}}Subprograms may be defined within programs, or separately in libraries that can be used by many programs. In different programming languages, a subroutine may be called a procedure, a function, a routine, a method, or a subprogram. The generic term callable unit is sometimes used.WEB
, U.S. Election Assistance Commission
, Definitions of Words with Special Meanings
, Voluntary Voting System Guidelines
, 2007
,weblink
, 2013-01-14
, Election Assistance Commission
, yes
,weblink" title="web.archive.org/web/20121208084203weblink">weblink
, 2012-12-08
,
, The name subprogram suggests a subroutine behaves in much the same way as a computer program that is used as one step in a larger program or another subprogram. A subroutine is often coded so that it can be started several times and from several places during one execution of the program, including from other subroutines, and then branch back (return) to the next instruction after the call, once the subroutine's task is done. The idea of a subroutine was initially conceived by John Mauchly during his work on ENIAC,BOOK, Subrata Dasgupta, It Began with Babbage: The Genesis of Computer Science,weblink 7 January 2014, Oxford University Press, 978-0-19-930943-6, 155–, and recorded in a Harvard symposium in January of 1947 entitled 'Preparation of Problems for EDVAC-type Machines'.J.W. Mauchly, "Preparation of Problems for EDVAC-type Machines" (1947), in Brian Randell (Ed.), The Origins of Digital Computers, Springer, 1982.. Maurice Wilkes, David Wheeler, and Stanley Gill are generally credited with the formal invention of this concept, which they termed a closed subroutine,CONFERENCE, Wheeler, D. J., David Wheeler (computer scientist), The use of sub-routines in programmes, 10.1145/609784.609816, Proceedings of the 1952 ACM national meeting (Pittsburgh) on - ACM '52, 235, 1952,weblink BOOK, Wilkes, M. V., Wheeler, D. J., Gill, S., Preparation of Programs for an Electronic Digital Computer, Addison-Wesley, 1951, contrasted with an open subroutine or macro.WEB, Dainith, John, "open subroutine." A Dictionary of Computing. 2004.,weblink Encyclopedia.com, January 14, 2013, Subroutines are a powerful programming tool,BOOK, The Art of Computer Programming, Volume I: Fundamental Algorithms, Donald E. Knuth, Donald Knuth, Addison-Wesley, 0-201-89683-4, and the syntax of many programming languages includes support for writing and using them. Judicious use of subroutines (for example, through the structured programming approach) will often substantially reduce the cost of developing and maintaining a large program, while increasing its quality and reliability.BOOK, O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare, Structured Programming, Academic Press, 1972, 0-12-200550-3, Subroutines, often collected into libraries, are an important mechanism for sharing and trading software. The discipline of object-oriented programming is based on objects and methods (which are subroutines attached to these objects or object classes).In the compiling method called threaded code, the executable program is basically a sequence of subroutine calls.

Main concepts

The content of a subroutine is its body, which is the piece of program code that is executed when the subroutine is called or invoked.A subroutine may be written so that it expects to obtain one or more data values from the calling program (to replace its parameters or formal parameters). The calling program provides actual values for these parameters, called arguments. Different programming languages may use different conventions for passing arguments:{| class="wikitable"! Convention !! Description !! Common use
| Default in most Algol-like languages after Algol 60, such as Pascal, Delphi, Simula, CPL, PL/M, Modula, Oberon, Ada, and many others. C, C++, Java (References to objects and arrays are also passed by value)
| Selectable in most Algol-like languages after Algol 60, such as Algol 68, Pascal, Delphi, Simula, CPL, PL/M, Modula, Oberon, Ada, and many others. C++, Fortran, PL/I
| Ada OUT parameters
| Algol
Scala (programming language)>Scala
| PL/I NONASSIGNABLE parameters, Ada IN parameters
The subroutine may return a computed value to its caller (its return value), or provide various result values or output parameters. Indeed, a common use of subroutines is to implement mathematical functions, in which the purpose of the subroutine is purely to compute one or more results whose values are entirely determined by the arguments passed to the subroutine. (Examples might include computing the logarithm of a number or the determinant of a matrix.)A subroutine call may also have side effects such as modifying data structures in a computer memory, reading from or writing to a peripheral device, creating a file, 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 subroutines with side effects is a characteristic of imperative programming languages.A subroutine can be coded so that it may call itself recursively, at one or more places, to perform its task. This method allows direct implementation of functions defined by mathematical induction and recursive divide and conquer algorithms.A subroutine whose purpose is to compute one boolean-valued function (that is, to answer a yes/no question) is sometimes called a predicate. In logic programming languages, often{{Vague|date=November 2009}} all subroutines are called predicates, since they primarily{{Vague|date=November 2009}} determine success or failure.{{Citation needed|date=November 2009}}

Language support

High-level programming languages usually include specific constructs to:
  • delimit the part of the program (body) that makes up the subroutine
  • assign an identifier (name) to the subroutine
  • specify the names and data types of its parameters and return values
  • provide a private naming scope for its temporary variables
  • identify variables outside the subroutine that are accessible within it
  • call the subroutine
  • provide values to its parameters
  • the main program contains the address of the subprogram
  • the sub program contains the address of next instruction of the function call in main program
  • specify the return values from within its body
  • return to the calling program
  • dispose of the values returned by a call
  • handle any exceptional conditions encountered during the call
  • package subroutines into a module, library, object, class, etc.
Some programming languages, such as Pascal, Fortran, Ada and many dialects of BASIC, distinguish between functions or function subprograms, which provide an explicit return value to the calling program, and subroutines or procedures, which do not. In those languages, function calls are normally embedded in expressions (e.g., a sqrt function may be called as y = z + sqrt(x)). Procedure calls either behave syntactically as statements (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, do not distinguish between functions and subroutines.In strictly functional programming languages such as Haskell, subprograms can have no side effects, which means that various internal states of the program will not change. Functions will always return the same result if repeatedly called with the same arguments. Such languages typically only support functions, since subroutines that do not return a value have no use unless they can cause a side effect.In programming languages such as C, C++, and C#, subroutines may also simply be called functions, not to be confused with mathematical functions or functional programming, which are different concepts.A language's compiler will usually translate procedure calls and returns into machine instructions according to a well-defined calling convention, so that subroutines can be compiled separately from the programs that call them. The instruction sequences corresponding to call and return statements are called the procedure's prologue and epilogue.

Advantages

The advantages of breaking a program into subroutines include:
  • Decomposing a complex programming task into simpler steps: this is one of the two main tools of structured programming, along with data structures
  • Reducing duplicate code within a program
  • Enabling reuse of code across multiple programs
  • Dividing a large programming task among various programmers, or various stages of a project
  • Hiding implementation details from users of the subroutine
  • Improving readability of code by replacing a block of code with a function call where a descriptive function name serves to describe the block of code. This makes the calling code concise and readable even if the function is not meant to be reused.
  • Improving traceability (i.e. most languages offer ways to obtain the call trace which includes the names of the involved subroutines and perhaps even more information such as file names and line numbers); by not decomposing the code into subroutines, debugging would be severely impaired

Disadvantages

Invoking a subroutine (versus using in-line code) imposes some computational overhead in the call mechanism.A subroutine typically requires standard housekeeping code – both at entry to, and exit from, the function (function prologue and epilogue – usually saving general purpose registers 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 and the RCA 1802, 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 January of 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 {{block quote|...the structure of the machine need not be complicated one bit. It is possible, since all the logical characteristics essential to this procedure are available, to evolve a coding instruction for placing the subroutines in the memory at places known to the machine, and in such a way that they may easily be called into use.{{pb}}In other words, one can designate subroutine A as division and subroutine B as complex multiplication and subroutine C as the evaluation of a standard error of a sequence of number, and so on through the list of subroutines needed for a particular problem. ... All these subroutines will then be stored in the machine, and all one needs to do is make a brief reference to them by number, as they are indicated in the coding.}}Kay McNulty had worked closely with John Mauchly on the ENIAC team and developed an idea for subroutines for the ENIAC computer she was programming in the late 1940s.WEB,weblink Walter Isaacson on the Women of ENIAC, Isaacson, Walter, 18 September 2014, Fortune, en,weblink" title="web.archive.org/web/20181212003245weblink">weblink 12 December 2018, 2018-12-14, She and the other ENIAC programmers used the subroutines to help calculate missile trajectories. Goldstine and von Neumann wrote a paper dated 16 August 1948 discussing the usefulness of subroutines.Planning and Coding of Problems for an Electronic Computing Instrument, Pt 2, Vol. 3weblink (see pg 163 of the pdf for the relevant page)Some very early computers and microprocessors, such as the IBM 1620, the Intel 8008, and the PIC microcontrollers, have a single-instruction subroutine call that uses 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 PDP-1, and the IBM 1130—typically use a calling convention which saved the instruction counter in the first memory location of the called subroutine. This allows arbitrarily deep levels of subroutine nesting, but does not support recursive subroutines. The PDP-11 (1970) is one of the first computers with a stack-pushing subroutine call instruction; this feature supports both arbitrarily deep subroutine nesting and also supports recursive subroutines.Guy Lewis Steele Jr.AI Memo 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.

Subroutine libraries

Even with this cumbersome approach, subroutines proved very useful. For one thing they allowed use of the same code in many different programs. Moreover, memory was a very scarce resource on early computers, and subroutines allowed significant savings in the size of programs.Many early computers loaded the program instructions into memory from a punched paper tape. Each subroutine could then be provided by a separate piece of tape, loaded or spliced before or after the main program (or "mainline"BOOK, Frank, Thomas S., Introduction to the PDP-11 and Its Assembly Language,weblink Prentice-Hall software series, Prentice-Hall, 1983, 195, 9780134917047, 2016-07-06, We could supply our assembling clerk with copies of the source code for all of our useful subroutines and then when presenting him with a mainline program for assembly, tell him which subroutines will be called in the mainline [...], ); and the same subroutine tape could then be used by many different programs. A similar approach applied in computers which used punched cards for their main input. The name subroutine library originally meant a library, in the literal sense, which kept indexed collections of tapes or card-decks for collective use.

Return by indirect jump

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

Jump to subroutine

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

Call stack

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

Delayed stacking {{anchor|Leaf procedure}}{{anchor|Leaf function}}

One disadvantage of the call stack mechanism is the increased cost of a procedure call and its matching return. The extra cost includes incrementing and decrementing the stack pointer (and, in some architectures, checking for stack overflow), and accessing the local variables and parameters by frame-relative addresses, instead of absolute addresses. The cost may be realized in increased execution time, or increased processor complexity, or both.This overhead is most obvious and objectionable in leaf procedures or leaf functions, which return without making any procedure calls themselves.WEB,weblink ARM Information Center, Infocenter.arm.com, 2013-09-29, WEB,weblink Overview of x64 Calling Conventions, Msdn.microsoft.com, 2013-09-29, WEB,weblink Function Types, Msdn.microsoft.com, 2013-09-29, To reduce that overhead, many modern compilers try to delay the use of a call stack until it is really needed.{{Citation needed|date=June 2011}} 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) that will be needed after Q returns.

C and C++ examples

In the C and C++ programming languages, subprograms are termed functions (further classified as member functions when associated with a class, or free functionsWEB, "what is meant by a free function",weblink when not). These languages use the special keyword void to indicate that a function takes no parameters (especially in C) 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) { /* some code */ }
The function does not return a value and has to be called as a stand-alone function, e.g., function1();
int function2(void)
{
return 5;
}
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)
{
char selection[] = {'S','M','T','W','T','F','S'};
return selection[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)
{
(*pointer_to_var)++;
}
This function does not return a value but modifies the variable whose address is passed as the parameter; it would be called with "function4(&variable_to_increment);".

Small Basic example

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

Visual Basic 6 examples

In the Visual Basic 6 language, subprograms are termed functions or subs (or methods when associated with a class). Visual Basic 6 uses various terms called types to define what is being passed as a parameter. By default, an unspecified variable is registered as a variant type and can be passed as ByRef (default) or ByVal. Also, when a function or sub is declared, it is given a public, private, or friend designation, which determines whether it can be accessed outside the module or project that it was declared in.
  • By value [ByVal] – a way of passing the value of an argument to a procedure by passing a copy of the value, instead of passing the address. As a result, the variable's actual value can't be changed by the procedure to which it is passed.
  • By reference [ByRef] – a way of passing the value of an argument to a procedure by passing an address of the variable, instead of passing a copy of its value. This allows the procedure to access the actual variable. As a result, the variable's actual value can be changed by the procedure to which it is passed. Unless otherwise specified, arguments are passed by reference.
  • Public (optional) – indicates that the function procedure is accessible to all other procedures in all modules. If used in a module that contains an Option Private, the procedure is not available outside the project.
  • Private (optional) – indicates that the function procedure is accessible only to other procedures in the module where it is declared.
  • Friend (optional) – used only in a class module. Indicates that the Function procedure is visible throughout the project, but not visible to a controller of an instance of an object.
Private Function Function1()
' Some Code Here
End FunctionThe function does not return a value and has to be called as a stand-alone function, e.g., Function1Private Function Function2() as Integer
Function2 = 5
End FunctionThis 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 FunctionThis 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 FunctionThis function does not return a value but modifies the variable whose address is passed as the parameter; it would be called with "Function4(variable_to_increment)".

PL/I example

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

{{Anchor|LVRR}}Local variables, recursion and reentrancy

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 termed local variables, and the scratch space is termed an activation record. An activation record typically has a return address that tells it where to pass control back to when the subprogram finishes.A subprogram may have any number and nature of call sites. If recursion is supported, a subprogram may even call itself, causing its execution to suspend while another nested execution of the same subprogram occurs. Recursion is a useful means to simplify some complex algorithms and break down complex problems. Recursive languages generally provide a new copy of local variables on each call. If the programmer desires the value of local variables to stay the same between calls, they can be declared static in some languages, or global values or common areas can be used. Here is an example of recursive subroutine in C/C++ to find Fibonacci numbers:int fib(int n){ if(n

- content above as imported from Wikipedia
- "Subroutine" does not exist on GetWiki (yet)
- time: 6:16pm EDT - Mon, Mar 18 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
CONNECT