Content deleted Content added
Thomas Meng (talk | contribs) |
m Reverted edit by 192.145.175.229 (talk) to last version by Chatul |
||
| (42 intermediate revisions by 27 users not shown) | |||
Line 2:
{{Other uses|Function (disambiguation){{!}}Function}}
{{Use dmy dates|date=April 2022}}
{{anchor|SUBROUTINE_DEFINITION}}
In [[computer programming]], a '''function'''
|title=Terminology Glossary
|url=https://pages.nist.gov/ElectionGlossary/
Line 11 ⟶ 10:
|publisher=NIST
|quote=Callable unit: (Of a software program or logical design) Function, method, operation, subroutine, procedure, or analogous structural unit that appears within a module.
|access-date=9 February 2024}}</ref> of [[software logic]] that has a well-defined [[Interface (computing)|interface]] and [[behavior]] and can be invoked
Callable units provide a powerful programming tool.<ref name="knuth1">{{cite book |title= The Art of Computer Programming, Volume I: Fundamental Algorithms |author= Donald E. Knuth |year= 1997 |author-link= Donald Knuth |publisher= Addison-Wesley |isbn=0-201-89683-4}}</ref> The primary purpose is to allow for the decomposition of a large and/or complicated problem into chunks that have relatively low [[cognitive load]] and to assign the chunks meaningful names (unless they are anonymous). Judicious application can reduce the cost of developing and maintaining software, while increasing its quality and reliability.<ref name="structprog">{{cite book |author= O.-J. Dahl |author2=E. W. Dijkstra |author3=C. A. R. Hoare |title= Structured Programming |publisher= Academic Press |year= 1972 |isbn= 0-12-200550-3}}</ref>
Callable units are present at multiple levels of [[abstraction]] in the programming environment. For example, a [[programmer]] may write a function in [[source code]] that is compiled to [[machine code]] that implements similar [[semantics]]. There is a callable unit in the source code and an associated one in the machine code, but they are different kinds of callable units {{endash}} with different implications and features.
==Terminology==
Some [[programming language]]s, such as [[COBOL]] and [[BASIC]], make a distinction between functions that return a value (typically called "functions") and those that do not (typically called "subprogram", "subroutine", or "procedure"); some, such as [[C (programming language)|C]], [[C++]], and [[Rust (programming language)|Rust]], only use the term "function" irrespective of whether they return a value or not; others, such as [[ALGOL 60]] and [[PL/I]], only use the word ''procedure''. Some [[Object-oriented programming|object-oriented]] languages, such as [[Java (programming language)|Java]] and [[C Sharp (programming language)|C#]], refer to functions inside [[Class (computer programming)|classes]] as "[[Method (computer programming)|method]]s".
==History==
The idea of a callable unit was initially conceived by [[John Mauchly]] and [[Kathleen Antonelli]] during their work on [[ENIAC]] and recorded in a January 1947 Harvard symposium on "Preparation of Problems for [[EDVAC]]-type Machines
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
Subroutines were implemented in [[Konrad Zuse]]'s [[Z4 (computer)|Z4]] in 1945.
In 1945, [[Alan
In January 1947 John Mauchly presented general notes at 'A Symposium of Large Scale Digital Calculating Machinery'
Line 137 ⟶ 140:
====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.{{ clarify | date = November 2015 | reason = increased relative to what?}} 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
<!---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.-->
<!--Major cleanup needed from this point on-->
== Features ==
{{uncited section|date=August 2025}}
In general, a callable unit is a list of instructions that, starting at the first instruction, executes sequentially except as directed via its internal logic. It can be invoked (called) many times during the [[Execution (computing)|execution]] of a program. Execution continues at the next instruction after the call instruction when it [[Return statement|returns]] control.
Line 162 ⟶ 167:
* Specify a return value in the function body
* Call a function
* Provide [[actual parameters]] that correspond to a called function's
* [[return statement|Return]] control to the caller at the point of call
* Consume the return value in the caller
Line 168 ⟶ 173:
* Provide a private [[scope (computer science)|naming scope]] for variables
* Identify variables outside the function that are accessible within it
* Propagate
* Package functions into a container such as [[modular programming|module]], [[library (computing)|library]], [[object (computer science)|object]], or [[class (computer programming)|class]]
Line 192 ⟶ 197:
! Convention !! Description !! Used in
|-
| [[Call by value|by value]] || A copy of the
|-
| [[Call by reference|by reference]] || A reference to the argument is passed; typically its address || 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 including C++, Fortran, PL/I
Line 216 ⟶ 221:
In many contexts, a callable may have [[side-effect (computer science)|side effect]] behavior such as modifying passed or global data, reading from or writing to a [[peripheral device]], accessing a [[computer file|file]], halting the program or the machine, or temporarily pausing program execution.
Side effects are considered
In strictly [[functional programming]] languages such as [[Haskell (programming language)|Haskell]], a function can have no [[Side effect (computer science)|side effects]], which means it cannot change the state of the program. Functions always return the same result for the same input. Such languages typically only support functions that return a value, since there is no value in a function that has neither return value nor side effect.
Line 228 ⟶ 233:
=== Nested call {{endash}} recursion ===
If supported by the language, a callable may call itself, causing its execution to suspend while another ''nested'' execution of the same callable executes. [[Recursion (computer science)|Recursion]] is a useful means to simplify some complex algorithms and break down complex problems. Recursive languages provide a new copy of local variables on each call. If the programmer desires the recursive callable to use the same variables instead of using locals, they typically declare them in a shared context such static or global.
Languages going back to [[ALGOL]], [[PL/I]] and [[C (programming language)|C]] and modern languages, almost invariably use a call stack, usually supported by the instruction sets to provide an activation record for each call. That way, a nested call can modify its local variables without
Recursion allows direct implementation of functionality defined by [[mathematical induction]] and recursive [[divide and conquer algorithm]]s. Here is an example of a recursive function in C/C++ to find [[Fibonacci
<syntaxhighlight lang="c">
Line 250 ⟶ 255:
Some languages, e.g., [[Ada (programming language)|Ada]], [[Pascal (programming language)|Pascal]], [[PL/I]], [[Python (programming language)|Python]], support declaring and defining a function inside, e.g., a function body, such that the name of the inner is only visible within the body of the outer.
A simple example in Pascal:<syntaxhighlight lang="pascal">function E(x: real): real;
function F(y: real): real;
begin
F := x + y
end;
begin
E := F(3) + F(4)
end;</syntaxhighlight>The function <code>F</code> is nested within <code>E</code>. Note that <code>E</code>'s parameter <code>x</code> is also visible in <code>F</code> (as <code>F</code> is a part of <code>E</code>) while both <code>x</code> and <code>y</code> are invisible outside <code>E</code> and <code>F</code> respectively.
=== Reentrancy ===
Line 328 ⟶ 341:
==== Compiler optimization ====
Some optimizations for minimizing call overhead may seem straight forward, but cannot be used if the callable has side effects. For example, in the expression <code>(f(x)-1)/(f(x)+1)</code>, the function <code>f</code> cannot be called only once with its value used two times since the two calls may return different results. Moreover, in the few languages which define the order of evaluation of the division operator's operands, the value of <code>x</code> must be fetched again before the second call, since the first call may have changed it. Determining whether a callable has a side effect is difficult {{endash}} indeed, [[undecidable problem|undecidable]] by virtue of [[Rice's theorem]]. So, while this optimization is safe in a purely functional programming language, a compiler for
==== Inlining ====
Line 581 ⟶ 594:
* [[Functional programming]]
* [[Fused operation]]
* [[Intrinsic function]]
* [[Lambda function (computer programming)]], a function that is not bound to an identifier
* [[Logic programming]]
▲* [[Method (computer programming)]]
* [[Modular programming]]
* [[Operator overloading]]
| |||