Content deleted Content added
mNo edit summary |
m Reverted edit by 192.145.175.229 (talk) to last version by Chatul |
||
| (14 intermediate revisions by 11 users not shown) | |||
Line 14:
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
==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."<ref name=mauchly0>{{cite book |first=J.W. |last=Mauchly |chapter=Preparation of Problems for EDVAC-Type Machines |author-link=John Mauchly |editor-first=Brian |editor-last=Randell |title=The Origins of Digital Computers |doi=10.1007/978-3-642-61812-3_31 |publisher=Springer|date=1982|pages=393–397 |isbn=978-3-642-61814-7 |chapter-url=https://archive.org/details/originsofdigital0000rand/page/365}}</ref> [[Maurice Wilkes]], [[David Wheeler (British computer scientist)|David Wheeler]], and [[Stanley Gill]] are generally credited with the formal invention of this concept, which they termed a ''closed sub-routine'',<ref>{{Cite conference |last1 = Wheeler |first1 = D. J. |author-link1 = David Wheeler (computer scientist) |chapter = The use of sub-routines in programmes |doi = 10.1145/609784.609816 |title = Proceedings of the 1952 ACM national meeting (Pittsburgh) on - ACM '52 |pages = 235 |year = 1952 |chapter-url = http://www.laputan.org/pub/papers/wheeler.pdf|doi-access = free }}</ref><ref>{{cite book |last1= Wilkes |first1= M. V. |last2= Wheeler |first2= D. J. |last3= Gill |first3=S. |title= Preparation of Programs for an Electronic Digital Computer |publisher= Addison-Wesley |year= 1951}}</ref> contrasted with an ''open subroutine'' or [[Macro (computer science)|macro]].<ref>{{cite encyclopedia |last=Dainith |first=John |title="open subroutine." A Dictionary of Computing | date=2004 |url=http://www.encyclopedia.com/doc/1O11-opensubroutine.html |encyclopedia=Encyclopedia.com |access-date=January 14, 2013}}</ref> However, [[Alan Turing]] had discussed subroutines in a paper of 1945 on design proposals for the NPL [[Automatic Computing Engine|ACE]], going so far as to invent the concept of a [[Call stack|return address stack]].<ref>{{Citation | last = Turing | first =Alan M. | author-link = Alan Turing | title = Report by Dr. A.M. Turing on proposals for the development of an Automatic Computing Engine (ACE): Submitted to the Executive Committee of the NPL in February 1946 | year = 1945 }} reprinted in {{Cite book | editor-last = Copeland | editor-first = B. J. | editor-link = Jack Copeland | title = Alan Turing's Automatic Computing Engine | ___location = Oxford | publisher = Oxford University Press | publication-date = 2005 | isbn = 0-19-856593-3 | year = 2005 | url-access = registration | url = https://archive.org/details/alanturingsautom0000unse |page=383}}</ref>
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 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 195 ⟶ 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 219 ⟶ 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 231 ⟶ 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 affecting any of the suspended calls variables.
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 253 ⟶ 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 331 ⟶ 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 584 ⟶ 594:
* [[Functional programming]]
* [[Fused operation]]
* [[Generator (computer programming)]]
* [[Intrinsic function]]
* [[Lambda function (computer programming)]], a function that is not bound to an identifier
| |||