Vero - Wikipedia - User contributions [en]

Inline expansion

2025-10-19T16:12:44Z

2605:8D80:6C24:88A9:E0B2:AD7C:76A8:4BDF: Brackets and update code aligning it

{{Short description|Optimization replacing a function call with that function's source code}}
{{Use American English|date=March 2019}}
{{More citations needed|date=December 2013}}

In [[computing]], '''inline expansion''', or '''inlining''', is a manual or [[compiler optimization]] that replaces a function [[call site]] with the body of the called function. Inline expansion is similar to [[macro expansion]], but occurs during compiling, without changing the [[source code]] (the text), while macro expansion occurs before compiling, and results in different text that is then processed by the [[compiler]].

Inlining is an important optimization, but has complex effects on performance.{{sfn|Chen|Chang|Conte|Hwu|1993}} As a [[rule of thumb]], some inlining will improve speed at very minor cost of space, but excess inlining will hurt speed, due to inlined code consuming too much of the [[instruction cache]], and also cost significant space. A survey of the modest academic literature on inlining from the 1980s and 1990s is given in Peyton Jones & Marlow 1999.{{sfn|Peyton Jones|Marlow|1999|loc=8. Related work, p. 17}}

==Overview==
Inline expansion is similar to macro expansion as the compiler places a new copy of the function in each place it is called. Inlined functions run a little faster than the normal functions as function-calling-overheads are saved, however, there is a memory penalty. If a function is inlined 10 times, there will be 10 copies of the function inserted into the code. Hence inlining is best for small functions that are called often. In C++ the member functions of a class, if defined within the class definition, are inlined by default (no need to use the ''inline'' [[reserved word]] (keyword)); otherwise, the keyword is needed. The compiler may ignore the programmer’s attempt to inline a function, mainly if it is particularly large.

Inline expansion is used to eliminate the time overhead (excess time) when a function is called. It is typically used for functions that execute frequently. It also has a space benefit for very small functions, and is an enabling transformation for other [[Optimization (computer science)|optimizations]].

Without inline functions, the [[compiler]] decides which functions to inline. The programmer has little or no control over which functions are inlined and which are not. Giving this degree of control to the programmer allows for the use of application-specific knowledge in choosing which functions to inline.

Ordinarily, when a function is invoked, [[control flow|control]] is transferred to its definition by a [[branch (computer science)|branch]] or call instruction. With inlining, control drops through directly to the code for the function, without a branch or call instruction.

[[Compiler]]s usually implement [[Statement (computer science)|statements]] with inlining. Loop conditions and loop bodies need [[lazy evaluation]]. This property is fulfilled when the code to compute loop conditions and loop bodies is inlined. Performance considerations are another reason to inline statements.

In the context of [[functional programming]] languages, inline expansion is usually followed by the [[Lambda calculus#.CE.B2-reduction|beta-reduction]] transformation.

A programmer might inline a function manually through [[copy-and-paste programming]], as a one-time operation on the [[source code]]. However, other methods of controlling inlining (see below) are preferable, because they do not precipitate bugs arising when the programmer overlooks a (possibly modified) duplicated version of the original function body, while fixing a bug in the inlined function.

==Effect on performance==
The direct effect of this optimization is to improve time performance (by eliminating call overhead), at the cost of worsening space usage{{efn|Space usage is "number of instructions", and is both runtime space usage and the [[binary file]] size.}} (due to [[code duplication|duplicating]] the function body). The code expansion due to duplicating the function body dominates, except for simple cases,{{efn|Code size actually shrinks for very short functions, where the call overhead is larger than the body of the function, or single-use functions, where no duplication occurs.}} and thus the direct effect of inline expansion is to improve time at the cost of space.

However, the main benefit of inline expansion is to allow further optimizations and improved scheduling, due to increasing the size of the function body, as better optimization is possible on larger functions.{{sfn|Chen|Chang|Conte|Hwu|1993|loc=3.4 Function inline expansion, p. 14}} The ultimate impact of inline expansion on speed is complex, due to multiple effects on performance of the memory system (mainly [[instruction cache]]), which dominates performance on modern processors: depending on the specific program and cache, inlining particular functions can increase or decrease performance.{{sfn|Chen|Chang|Conte|Hwu|1993}}

The impact of inlining varies by [[programming language]] and program, due to different degrees of abstraction. In lower-level imperative languages such as [[C (programming language)|C]] and [[Fortran]] it is typically a 10–20% speed boost, with minor impact on code size, while in more abstract languages it can be significantly more important, due to the number of layers inlining removes, with an extreme example being [[Self (programming language)|Self]], where one compiler saw improvement factors of 4 to 55 by inlining.{{sfn|Peyton Jones|Marlow|1999|loc=8. Related work, p. 17}}

The direct benefits of eliminating a function call are:
* It eliminates instructions needed for a [[function call]], both in the calling function and in the callee: placing arguments on a [[Stack-based memory allocation|stack]] or in [[Processor register|registers]], the function call itself, the [[function prologue]], then at return the [[function epilogue]], the [[return statement]], and then getting the return value back, and removing arguments from stacks and restoring registers (if needed).
* Due to not needing registers to pass arguments, it reduces [[register spilling]].
* It eliminates having to pass references and then dereference them, when using [[call by reference]] (or [[call by address]], or [[call by sharing]]).

The main benefit of inlining, however, is the further optimizations it allows. Optimizations that cross function boundaries can be done without requiring [[interprocedural optimization]] (IPO): once inlining has been performed, added ''intra''procedural optimizations ("global optimizations") become possible on the enlarged function body. For example:
* A [[Constant (computer programming)|constant]] passed as an argument can often be propagated to all instances of the matching parameter, or part of the function may be "hoisted out" of a loop (via [[loop-invariant code motion]]).
* [[Register allocation]] can be done across the larger function body.
* High-level optimizations, such as [[escape analysis]] and [[tail duplication]], can be performed on a larger scope and be more effective, more so if the compiler implementing those optimizations relies on mainly intra-procedural analysis.<ref name="prokopec2019" /> These can be done without inlining, but require a significantly more complex compiler and linker (in case caller and callee are in separate compiling units).

Conversely, in some cases a language specification may allow a program to make added assumptions about arguments to procedures that it can no longer make after the procedure is inlined, preventing some optimizations. Smarter compilers (such as [[Glasgow Haskell Compiler]] (GHC)) will track this, but naive inlining loses this information.

A further benefit of inlining for the memory system is:
* Eliminating branches and keeping code that is executed close together in memory improves instruction cache performance by improving [[locality of reference]] (spatial locality and sequentiality of instructions). This is smaller than optimizations that specifically target sequentiality, but is significant.{{sfn|Chen|Chang|Conte|Hwu|1993|loc=3.4 Function inline expansion, p. 19–20}}

The direct cost of inlining is increased code size, due to duplicating the function body at each call site. However, it does not always do so, namely in case of very short functions, where the function body is smaller than the size of a function call (at the caller, including argument and return value handling), such as trivial [[accessor method]]s or [[mutator method]]s (getters and setters); or for a function that is only used in one place, in which case it is not duplicated. Thus inlining may be minimized or eliminated if optimizing for code size, as is often the case in [[embedded system]]s.

Inlining also imposes a cost on performance, due to the code expansion (due to duplication) hurting instruction cache performance.<ref name="webkit">{{cite web |url=https://www.webkit.org/blog/2826/unusual-speed-boost-size-matters/ |title=Unusual speed boost: size matters |author=Benjamin Poulain |date=August 8, 2013}}</ref> This is most significant if, before expansion, the [[working set]] of the program (or a hot section of code) fit in one level of the memory hierarchy (e.g., [[L1 cache]]), but after expansion it no longer fits, resulting in frequent cache misses at that level. Due to the significant difference in performance at different levels of the hierarchy, this hurts performance considerably. At the highest level this can result in increased [[page fault]]s, catastrophic performance degradation due to [[thrashing (computer science)|thrashing]], or the program failing to run at all. This last is rare in common desktop and server applications, where code size is small relative to available memory, but can be an issue for resource-constrained environments such as embedded systems. One way to mitigate this problem is to split functions into a smaller hot inline path ([[fast path]]), and a larger cold non-inline path (slow path).<ref name="webkit"/>

Inlining hurting performance is a problem for mainly large functions that are used in many places, but the break-even point beyond which inlining reduces performance is difficult to determine and depends in general on precise load, so it can be subject to manual optimization or [[profile-guided optimization]].<ref>See for example the [http://jikesrvm.org/Adaptive+Optimization+System Adaptive Optimization System] {{Webarchive|url=https://web.archive.org/web/20110809144146/http://jikesrvm.org/Adaptive+Optimization+System |date=2011-08-09}} in the [[Jikes RVM]] for Java.</ref> This is a similar issue to other code expanding optimizations such as [[loop unrolling]], which also reduces number of instructions processed, but can decrease performance due to poorer cache performance.

The precise effect of inlining on cache performance is complex. For small cache sizes (much smaller than the working set before expansion), the increased sequentiality dominates, and inlining improves cache performance. For cache sizes close to the working set, where inlining expands the working set so it no longer fits in cache, this dominates and cache performance decreases. For cache sizes larger than the working set, inlining has negligible impact on cache performance. Further, changes in cache design, such as [[load forwarding]], can offset the increase in cache misses.{{sfn|Chen|Chang|Conte|Hwu|1993|loc=3.4 Function inline expansion, p. 24–26}}

==Compiler support==
Compilers use a variety of mechanisms to decide which function calls should be inlined; these can include manual hints from programmers for specific functions, together with overall control via [[command-line option]]s. Inlining is done automatically by many compilers in many languages, based on judgment of whether inlining is beneficial, while in other cases it can be manually specified via compiler [[Directive (programming)|directives]], typically using a keyword or [[compiler directive]] called <code>inline</code>. Typically this only hints that inlining is desired, rather than requiring inlining, with the force of the hint varying by language and compiler.

Typically, compiler developers keep the above performance issues in mind, and incorporate [[heuristics]] into their compilers that choose which functions to inline so as to improve performance, rather than worsening it, in most cases.

== Implementation ==
Once the [[compiler]] has decided to inline a particular function, performing the inlining operation itself is usually simple. Depending on whether a compiler inlines functions across code in different languages, the compiler can inline on either a high-level [[intermediate representation]] (like [[abstract syntax tree]]s) or a low-level intermediate representation. In either case, the compiler simply computes the [[Parameter|arguments]], stores them in variables corresponding to the function's arguments, and then inserts the body of the function at the call site.

[[Linker (computing)|Linkers]] can also do function inlining. When a linker inlines functions, it may inline functions whose source is not available, such as library functions (see [[link-time optimization]]). A [[runtime system]] can inline a function also. [[Runtime (program lifecycle phase)|Runtime]] inlining can use dynamic profiling information to make better decisions about which functions to inline, as in the [[HotSpot (virtual machine)|Java HotSpot compiler]].<ref>[https://www.researchgate.net/publication/331408280_An_Optimization-Driven_Incremental_Inline_Substitution_Algorithm_for_Just-in-Time_Compilers] Description of the inliner used in the Graal JIT compiler for Java</ref>

Here is a simple example of inline expansion performed "by hand" at the source level in the [[C (programming language)|C language]]:
<syntaxhighlight lang="c">
int pred(int x) {
if (x == 0) {
return 0;
} else {
return x - 1;
}
}
</syntaxhighlight>

''Before inlining:''
<syntaxhighlight lang="c">
int func(int y) {
return pred(y) + pred(0) + pred(y + 1);
}
</syntaxhighlight>

''After inlining:''
<syntaxhighlight lang="c">
int func(int y) {
int tmp;

// (1)
if (y == 0) {
tmp = 0;
} else {
tmp = y - 1;
}

// (2)
if (0 == 0) {
tmp += 0;
} else {
tmp += 0 - 1;
}

// (3)
if (y + 1 == 0) {
tmp += 0;
} else {
tmp += (y + 1) - 1;
}

return tmp;
}
</syntaxhighlight>

Note that this is only an example. In an actual C application, it would be preferable to use an inlining language feature such as [[parameterized macro]]s or [[inline function]]s to tell the compiler to transform the code in this way. The next section lists ways to optimize this code.

=== Inlining by assembly macro expansion ===
[[Macro assembler#Macros|Assembler macros]] provide an alternative approach to inlining whereby a sequence of instructions can normally be generated inline by macro expansion from a single macro source statement (with zero or more parameters). One of the parameters might be an option to alternatively generate a one-time separate [[subroutine]] containing the sequence and processed instead by an inlined call to the function.
Example:
MOVE FROM=array1,TO=array2,INLINE=NO

=== Heuristics ===
A range of different heuristics have been explored for inlining. Usually, an inlining algorithm has a certain code budget (an allowed increase in program size) and aims to inline the most valuable callsites without exceeding that budget. In this sense, many inlining algorithms are usually modeled after the [[Knapsack problem]].<ref>[https://dl.acm.org/citation.cfm?id=359830] Scheifler, An Analysis of Inline Substitution for a Structured Programming Language</ref> To decide which callsites are more valuable, an inlining algorithm must estimate their benefit—i.e. the expected decrease in the execution time. Commonly, inliners use profiling information about the frequency of the execution of different code paths to estimate the benefits.<ref>[https://dl.acm.org/citation.cfm?id=351416] Matthew Arnold, Stephen Fink, Vivek Sarkar, and Peter F. Sweeney, A Comparative Study of Static and Profile-based Heuristics for Inlining</ref>

In addition to profiling information, newer [[just-in-time compiler]]s apply several more advanced heuristics, such as:<ref name="prokopec2019">[https://www.researchgate.net/publication/331408280_An_Optimization-Driven_Incremental_Inline_Substitution_Algorithm_for_Just-in-Time_Compilers] Prokopec et al., An Optimization Driven Incremental Inline Substitution Algorithm for Just-In-Time Compilers, CGO'19 publication about the inliner used in the Graal compiler for the JVM</ref>
* Speculating which code paths will result in the best reduction in execution time (by enabling additional compiler optimizations as a result of inlining) and increasing the perceived benefit of such paths.
* Adaptively adjusting the benefit-per-cost threshold for inlining based on the size of the compiling unit and the amount of code already inlined.
* Grouping subroutines into clusters, and inlining entire clusters instead of singular subroutines. Here, the heuristic guesses the clusters by grouping those methods for which inlining just a proper subset of the cluster leads to a worse performance than inlining nothing at all.

== Benefits ==
Inline expansion itself is an optimization, since it eliminates overhead from calls, but it is much more important as an [[enabling transformation]]. That is, once the compiler expands a function body in the context of its call site—often with arguments that may be fixed [[Constant (mathematics)|constants]]—it may be able to do a variety of transformations that were not possible before. For example, a [[conditional branch]] may turn out to be always true or always false at this particular call site. This in turn may enable [[dead code elimination]], [[loop-invariant code motion]], or [[induction variable elimination]].


In the C example in the prior section, optimizing opportunities abound. The compiler may follow this sequence of steps:
* The <code>tmp += 0</code> statements in the lines marked (2) and (3) do nothing. The compiler can remove them.
* The condition <code>0 == 0</code> is always true, so the compiler can replace the line marked (2) with the consequent, <code>tmp += 0</code> (which does nothing).
* The compiler can rewrite the condition <code>y+1 == 0</code> to <code>y == -1</code>.
* The compiler can reduce the expression <code>(y + 1) - 1</code> to <code>y</code>.
* The expressions <code>y</code> and <code>y+1</code> cannot both equal zero. This lets the compiler eliminate one test.
* In statements such as <code>if (y == 0) return y</code> the value of <code>y</code> is known in the body, and can be inlined.
The new function looks like:

<syntaxhighlight lang="c">
int func(int y) {
if (y == 0) {
return 0;
}
if (y == -1) {
return -2;
}
return 2 * y - 1;
}
</syntaxhighlight>

== Limits ==
Complete inline expansion is not always possible, due to [[Recursion (computer science)|recursion]]: recursively inline expanding the calls will not terminate. There are various solutions, such as expanding a bounded amount, or analyzing the [[call graph]] and breaking loops at certain nodes (i.e., not expanding some edge in a recursive loop).{{sfn|Peyton Jones|Marlow|1999|loc=4. Ensuring Termination, pp. 6–9}} An identical problem occurs in macro expansion, as recursive expansion does not terminate, and is typically resolved by forbidding recursive macros (as in C and C++).

== Comparison with macros ==
Traditionally, in languages such as [[C (programming language)|C]], inline expansion was accomplished at the source level using [[parameterized macro]]s. Use of true inline functions, as are available in [[C99]], provides several benefits over this approach:
* In C, macro invocations do not perform [[type checking]], or even check that arguments are well-formed, whereas function calls usually do.
* In C, a macro cannot use the return keyword with the same meaning as a function would do (it would make the function that asked the expansion terminate, rather than the macro). In other words, a macro cannot return anything which is not the result of the last expression invoked inside it.
* Since C macros use mere textual substitution, this may result in unintended side-effects and inefficiency due to re-evaluation of arguments and [[order of operations]].
* Compiler errors within macros are often difficult to understand, because they refer to the expanded code, rather than the code the programmer typed. Thus, debugging information for inlined code is usually more helpful than that of macro-expanded code.
* Many constructs are awkward or impossible to express using macros, or use a significantly different syntax. Inline functions use the same syntax as regular functions, and can be inlined and un-inlined at will with ease.
Many compilers can also inline expand some [[Recursion (computer science)|recursive functions]];<ref>[https://web.archive.org/web/20041013180231/http://home.pipeline.com/~hbaker1/Inlines.html Inlining Semantics for Subroutines which are Recursive]" by Henry G. Baker</ref> recursive macros are typically illegal.

[[Bjarne Stroustrup]], the designer of C++, likes to emphasize that macros should be avoided wherever possible, and advocates extensive use of inline functions.

== Selection methods ==
Many compilers aggressively inline functions wherever it is beneficial to do so. Although it can lead to larger [[executable]]s, aggressive inlining has nevertheless become more and more desirable as memory capacity has increased faster than CPU speed. Inlining is a critical optimization in languages for [[Functional programming|functional]] and [[object-oriented programming]], which rely on it to provide enough context for their typically small functions to make classical optimizations effective.

== Language support ==
Many languages, including [[Java (programming language)|Java]] and functional languages, do not provide language constructs for inline functions, but their compilers or [[Interpreter (computing)|interpreters]] often perform aggressive inline expansion.<ref name="prokopec2019"/> Other languages provide constructs for explicit hints, generally as compiler [[Directive (programming)|directives]] (pragmas).

The language [[Ada (programming language)|Ada]] has a pragma for inline functions.

Functions in [[Common Lisp]] may be defined as inline by the <code>inline</code> declaration as such:<ref>[http://www.lispworks.com/documentation/HyperSpec/Body/d_inline.htm#inline ''Declaration'' '''INLINE''', '''NOTINLINE'''] at the [[Common Lisp HyperSpec]]</ref>

<syntaxhighlight lang="lisp">
(declaim (inline dispatch))
(defun dispatch (x)
(funcall
(get (car x) 'dispatch) x))
</syntaxhighlight>

The [[Haskell]] compiler [[Glasgow Haskell Compiler|GHC]] tries to inline functions or values that are small enough but inlining may be noted explicitly using a language pragma:<ref>[http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/pragmas.html 7.13.5.1. INLINE pragma] Chapter 7. GHC Language Features</ref>

<syntaxhighlight lang="haskell">
key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}
</syntaxhighlight>

=== C and C++ ===
{{Further|Inline function}}
[[C (programming language)|C]] and [[C++]] have an <code>inline</code> keyword which serves as a hint that inlining may be beneficial; however, in newer versions, its main purpose is instead to alter the visibility and linking behavior of the function.<ref>https://en.cppreference.com/w/cpp/language/inline {{Bare URL inline|date=August 2025}}</ref>

=== Rust ===
In [[Rust (programming language)|Rust]], inlining is automatically done by the compiler.<ref name="rust-ref-inline">{{Cite web |title=Code generation - The Rust Reference |url=https://doc.rust-lang.org/nightly/reference/attributes/codegen.html?highlight=inline#r-attributes.codegen.inline |access-date=2025-05-01 |website=doc.rust-lang.org}}</ref> Rust provides an <code>#[inline]</code> attribute that suggests to the compiler that a function should be inlined, but does not guarantee it; the compiler may ignore even <code>#[inline(always)]</code>. In debug mode, the compiler will never inline.<ref name="rust-stddev-inlining">{{Cite web |title=When to #[inline] - Standard library developers Guide |url=https://std-dev-guide.rust-lang.org/policy/inline.html |access-date=2025-05-01 |website=std-dev-guide.rust-lang.org}}</ref>

== See also ==
* [[Macro (computer science)]]
* [[Partial evaluation]]
* [[Tail-call elimination]]
* [[Code outlining]]

== Notes ==
{{Notelist}}

== References ==
{{Reflist}}
* {{Cite journal |last1=Chen |first1=W. Y. |last2=Chang |first2=P. P. |last3=Conte |first3=T. M. |last4=Hwu |first4=W. W. |date=September 1993 |title=The effect of code expanding optimizations on instruction cache design |url=http://impact.crhc.illinois.edu/shared/report/crhc-91-17.icache.pdf |journal=IEEE Transactions on Computers |volume=42 |issue=9 |pages=1045–1057 |doi=10.1109/12.241594 |bibcode=1993ITCmp..42.1045C |hdl=2142/74513 |hdl-access=free}}
* {{cite tech report |last1=Peyton Jones |first1=Simon |author1-link=Simon Peyton Jones |last2=Marlow |first2=Simon |author2-link=Simon Marlow |date=September 1999 |url=http://research.microsoft.com/~simonpj/Papers/inlining/ |title=Secrets of the Glasgow Haskell Compiler Inliner}}

== External links ==
{{Wiktionary|in-line expansion|inlining}}
*"[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.1036 Eliminating Virtual Function Calls in C++ Programs]"; Gerald Aigner, [[Urs Hölzle]]
*"[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.187.7208 Reducing Indirect Function Call Overhead In C++ Programs]"; Brad Calder, Dirk Grumwald
*[https://web.archive.org/web/20060907183845/http://www.cs.arizona.edu/alto/Doc/alto.html ALTO - A Link-Time Optimizer for the DEC Alpha]
*"[https://web.archive.org/web/20160303171839/http://www.iecc.com/linker/linker11.html Advanced techniques]"; [[John R. Levine]]
*"[https://web.archive.org/web/20041010124209/http://www.codeproject.com/tips/gloption.asp Whole Program Optimization with Visual C++ .NET]"; Brandon Bray

{{Compiler optimizations}}

[[Category:Compiler optimizations]]
[[Category:Subroutines]]
[[Category:Programming language comparisons]]

[[Category:Articles with example C code]]
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Lisp (programming language) code]]

Tail call

2025-10-19T16:07:33Z

2605:8D80:6C24:88A9:E0B2:AD7C:76A8:4BDF: /* C example */

{{Short description|Subroutine call performed as final action of a procedure}}
In [[computer science]], a '''tail call''' is a [[subroutine]] call performed as the final action of a procedure.<ref name="MuchnickAssociates1997">
{{Cite book
| author1 = Steven Muchnick
| author2 = Muchnick and Associates
| date = 15 August 1997
| isbn = 978-1-55860-320-2
| publisher = Morgan Kaufmann
| title = Advanced Compiler Design Implementation
| url = https://archive.org/details/advancedcompiler00much
| url-access = registration
}}
</ref>
If the target of a tail is the same subroutine, the subroutine is said to be '''tail recursive''', which is a special case of direct [[recursion (computer science)|recursion]]. '''Tail recursion''' (or '''tail-end recursion''') is particularly useful, and is often easy to optimize in implementations.

Tail calls can be implemented without adding a new [[stack frame]] to the [[call stack]]. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to [[Exec (system call)|overlay]] for processes, but for function calls). The program can then [[jump (computer science)|jump]] to the called subroutine. Producing such code instead of a standard call sequence is called '''tail-call elimination''' or '''tail-call optimization'''. Tail-call elimination allows procedure calls in tail position to be implemented as efficiently as [[goto]] statements, thus allowing efficient [[structured programming]]. In the words of [[Guy L. Steele]], "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions."<ref name="aim-443"/>

Not all programming languages require tail-call elimination. However, in [[functional programming language]]s, tail-call elimination is often guaranteed by the [[Programming language specification|language standard]], allowing tail recursion to use a similar amount of memory as an equivalent [[loop (computing)|loop]]. The special case of tail-recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize '''sibling calls''', or tail calls to functions which take and return the same types as the caller.<ref name="llvm.org">
{{Cite web
| url = http://llvm.org/docs/CodeGenerator.html#sibling-call-optimization
| title = The LLVM Target-Independent Code Generator — LLVM 7 documentation
| website = llvm.org
}}
</ref>

== Description ==

When a function is called, the computer must "remember" the place it was called from, the ''[[Return address (computing)|return address]]'', so that it can return to that location with the result once the call is complete. Typically, this information is saved on the [[call stack]], a list of return locations in the order that the call locations were reached. In addition, compilers allocate memory for local variables of the called function and push register content (if any and/or relevant) onto the stack. Typically, it is done by allocating a stack frame including saved registers, space allocated for non-register local variables, return address and call parameters (unless they are passed in registers). For tail calls, there is no need to remember the caller or preserve content of registers – instead, tail-call elimination avoids allocation of new stack frames and makes only the minimum necessary changes to the existing stack frame before passing it on, and the tail-called function will return directly to the ''original'' caller.<ref>
{{Cite web
| access-date = 2013-03-21
| date = 2011-07-29
| publisher = Cstheory.stackexchange.com
| title = recursion - Stack memory usage for tail calls - Theoretical Computer Science
| url = https://cstheory.stackexchange.com/q/7540
}}
</ref>
This, however, leads to complete loss of the caller's stack frame, which is sometimes considered as a hindrance in debugging. The tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function is bypassed when the optimization is performed.

For non-recursive function calls, this is usually an [[Program optimization|optimization]] that saves only a little time and space, since there are not that many different functions available to call. When dealing with recursive or [[mutually recursive]] functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be very significant, since a function can call itself, directly or indirectly, creating a new call stack frame each time. Tail-call elimination often reduces asymptotic stack space requirements from linear, or [[Big-O notation|O]](n), to constant, or [[Big-O notation|O]](1). Tail-call elimination is thus required by the standard definitions of some programming languages, such as [[Scheme (programming language)|Scheme]], and languages in the [[ML (programming language)|ML]] family among others.<ref name='SchemeProperTailRec'>
{{Cite web
| access-date = 2013-03-21
| publisher = R6rs.org
| title = Revised [6] Report on the Algorithmic Language Scheme
| url = http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11
}}
</ref><ref>
{{Cite web
| access-date = 2013-03-21
| publisher = R6rs.org
| title = Revised [6] Report on the Algorithmic Language Scheme - Rationale
| url = http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3
}}
</ref>
The Scheme language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context.<ref>
{{Cite web
| access-date = 2013-03-21
| publisher = R6rs.org
| title = Revised [6] Report on the Algorithmic Language Scheme
| url = http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.20
}}
</ref>
Implementations allowing an unlimited number of tail calls to be active at the same moment, thanks to tail-call elimination, can also be called 'properly tail recursive'.<ref name='SchemeProperTailRec'/>

Besides space and execution efficiency, tail-call elimination is important in the [[functional programming]] idiom known as [[continuation-passing style]] (CPS), which would otherwise quickly run out of stack space.

== Syntactic form ==

A tail call can be located just before the syntactical end of a function:

<syntaxhighlight lang="javascript">
function foo(data) {
a(data);
return b(data);
}
</syntaxhighlight>

Here, both <code>a(data)</code> and <code>b(data)</code> are calls, but <code>b</code> is the last thing the procedure executes before returning and is thus in tail position. However, not all tail calls are necessarily located at the syntactical end of a subroutine:

<syntaxhighlight lang="javascript">
function bar(data) {
if (a(data)) {
return b(data);
}
return c(data);
}
</syntaxhighlight>

Here, both calls to <code>b</code> and <code>c</code> are in tail position. This is because each of them lies in the end of if-branch respectively, even though the first one is not syntactically at the end of <code>bar</code>'s body.

In this code:

<syntaxhighlight lang="javascript">
function foo1(data) {
return a(data) + 1;
}
</syntaxhighlight>
<syntaxhighlight lang="javascript">
function foo2(data) {
var ret = a(data);
return ret;
}
</syntaxhighlight>
<syntaxhighlight lang="javascript">
function foo3(data) {
var ret = a(data);
return (ret == 0) ? 1 : ret;
}
</syntaxhighlight>

the call to <code>a(data)</code> is in tail position in <code>foo2</code>, but it is '''not''' in tail position either in <code>foo1</code> or in <code>foo3</code>, because control must return to the caller to allow it to inspect or modify the return value before returning it.

==Example programs==
The following program is an example in [[Scheme (programming language)|Scheme]]:<ref name="sicp">{{cite book|last1=Sussman|first1=G. J.|last2=Abelson|first2=Hal|title=Structure and Interpretation of Computer Programs|date=1984|publisher=MIT Press|location=Cambridge, MA|isbn=0-262-01077-1|url=https://archive.org/details/structureinterpr00abel}}</ref>

<syntaxhighlight lang="scheme">
;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
</syntaxhighlight>

This is not written in a tail-recursive style, because the multiplication function ("*") is in the tail position. This can be compared to:

<syntaxhighlight lang="scheme">
;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
(fact-iter 1 n))
(define (fact-iter product n)
(if (= n 0)
product
(fact-iter (* product n)
(- n 1))))
</syntaxhighlight>

This program assumes [[Evaluation strategy#Applicative order|applicative-order]] evaluation. The inner procedure <code>fact-iter</code> calls itself ''last'' in the control flow. This allows an [[interpreter (computer software)|interpreter]] or [[compiler]] to reorganize the execution which would ordinarily look like this:<ref name="sicp" />

call factorial (4)
call fact-iter (1 4)
call fact-iter (4 3)
call fact-iter (12 2)
call fact-iter (24 1)
return 24
return 24
return 24
return 24
return 24

into the more [[Algorithmic efficiency|efficient]] variant, in terms of both space and time:

call factorial (4)
call fact-iter (1 4)
replace arguments with (4 3)
replace arguments with (12 2)
replace arguments with (24 1)
return 24
return 24

This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap, and the call stack frame for <code>fact-iter</code> is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. In typical implementations, the tail-recursive variant will be substantially faster than the other variant, but only by a constant factor.

Some programmers working in functional languages will rewrite recursive code to be tail recursive so they can take advantage of this feature. This often requires addition of an "accumulator" argument (<code>product</code> in the above example) to the function.

==Tail recursion modulo cons==
'''Tail recursion modulo cons''' is a generalization of tail-recursion optimization introduced by [[David H. D. Warren]]<ref>D. H. D. Warren, ''DAI Research Report 141'', University of Edinburgh, 1980.</ref> in the context of [[compiler|compilation]] of [[Prolog]], seen as an ''explicitly'' [[Single assignment#Single assignment|''set once'']] language. It was described (though not named) by [[Daniel P. Friedman]] and [[David S. Wise]] in 1974<ref>Daniel P. Friedman and David S. Wise, [http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR19 ''Technical Report TR19: Unwinding Structured Recursions into Iterations''], Indiana University, Dec. 1974. PDF available [https://legacy.cs.indiana.edu/ftp/techreports/TR19.pdf ''here''] (webarchived copy [https://web.archive.org/web/20221023082940/https://legacy.cs.indiana.edu/ftp/techreports/TR19.pdf ''here'']).</ref> as a [[LISP]] compilation technique. As the name suggests, it applies when the only operation left to perform after a recursive call is to prepend a known value in front of the list returned from it (or to perform a constant number of simple data-constructing operations, in general). This call would thus be a ''tail call'' save for ("[[modulo (jargon)|modulo]]") the said ''[[cons]]'' operation. But prefixing a value at the start of a list ''on exit'' from a recursive call is the same as appending this value at the end of the growing list ''on entry'' into the recursive call, thus building the list as a [[side effect (computer science)|side effect]], as if in an implicit accumulator parameter. The following Prolog fragment illustrates the concept:

===Example code===
{|
|-
|<syntaxhighlight lang="prolog">
% Prolog, tail recursive modulo cons:
partition([], _, [], []).
partition([X|Xs], Pivot, [X|Rest], Bigs) :-
X @< Pivot, !,
partition(Xs, Pivot, Rest, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Rest]) :-
partition(Xs, Pivot, Smalls, Rest).
</syntaxhighlight>
|<syntaxhighlight lang="haskell">
-- In Haskell, guarded recursion:
partition [] _ = ([],[])
partition (x:xs) p
| x < p = (x:a,b)
| otherwise = (a,x:b)
where
(a,b) = partition xs p

</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
% Prolog, with explicit unifications:
% non-tail recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
( X @< Pivot
-> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest]
; partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest]
).
</syntaxhighlight>
|<syntaxhighlight lang="prolog">
% Prolog, with explicit unifications:
% tail-recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
( X @< Pivot
-> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs)
; Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest)
).

</syntaxhighlight>
|}

Thus in tail-recursive translation such a call is transformed into first creating a new [[Node (computer science)|list node]] and setting its <code>first</code> field, and ''then'' making the tail call with the pointer to the node's <code>rest</code> field as argument, to be filled recursively. The same effect is achieved when the recursion is ''guarded'' under a lazily evaluated data constructor, which is automatically achieved in lazy programming languages like Haskell.

===C example===
The following fragment defines a recursive function in [[C (programming language)|C]] that duplicates a linked list (with some equivalent Scheme and Prolog code as comments, for comparison):
{|
|-valign="top"
|rowspan="2"|
<syntaxhighlight lang="c">
typedef struct LinkedList {
void* value;
struct LinkedList* next;
} LinkedList;

LinkedList* duplicate(const LinkedList** ls) {
LinkedList* head = NULL;

if (ls) {
LinkedList* p = duplicate(ls->next);
head = (LinkedList*)malloc(sizeof(*head));
head->value = ls->value;
head->next = p;
}
return head;
}
</syntaxhighlight>
|<syntaxhighlight lang="scheme">
;; in Scheme,
(define (duplicate ls)
(if (not (null? ls))
(cons (car ls)
(duplicate (cdr ls)))
'()))
</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
%% in Prolog,
duplicate([X|Xs],R):-
duplicate(Xs,Ys),
R=[X|Ys].
duplicate([],[]).
</syntaxhighlight>
|}

In this form the function is not tail recursive, because control returns to the caller after the recursive call duplicates the rest of the input list. Even if it were to allocate the ''head'' node before duplicating the rest, it would still need to plug in the result of the recursive call into the <code>next</code> field ''after'' the call.{{efn|Like this:
<syntaxhighlight lang="c">
if (ls) {
head = (LinkedList*)malloc(sizeof(*head));
head->value = ls->value;
head->next = duplicate(ls->next);
}</syntaxhighlight>
}}
So the function is ''almost'' tail recursive. Warren's method pushes the responsibility of filling the <code>next</code> field into the recursive call itself, which thus becomes tail call.{{efn|Like this:
<syntaxhighlight lang="c">
if (ls) {
head = (LinkedList*)malloc(sizeof(*head));
head->value = ls->value;
duplicate(ls->next, &(head->next));
}</syntaxhighlight>
}} Using sentinel head node to simplify the code,

{|
|-valign="top"
|rowspan="2"|
<syntaxhighlight lang="c">
void duplicate_aux(const LinkedList* ls, LinkedList* end) {
if (ls) {
end->next = (LinkdList*)malloc(sizeof(*end));
end->next->value = ls->value;
duplicate_aux(ls->next, end->next);
} else {
end->next = NULL;
}
}

LinkedList* duplicate(const LinkedList* ls) {
LinkedList head;

duplicate_aux(ls, &head);
return head.next;
}
</syntaxhighlight>
|<syntaxhighlight lang="scheme">
;; in Scheme,
(define (duplicate ls)
(let ((head (list 1)))
(let dup ((ls ls)
(end head))
(cond
((not (null? ls))
(set-cdr! end (list (car ls)))
(dup (cdr ls) (cdr end)))))
(cdr head)))
</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
%% in Prolog,
duplicate([X|Xs],R):-
R=[X|Ys],
duplicate(Xs,Ys).
duplicate([],[]).
</syntaxhighlight>
|}

The callee now appends to the end of the growing list, rather than have the caller prepend to the beginning of the returned list. The work is now done on the way ''forward'' from the list's start, ''before'' the recursive call which then proceeds further, instead of ''backward'' from the list's end, ''after'' the recursive call has returned its result. It is thus similar to the accumulating parameter technique, turning a recursive computation into an iterative one.

Characteristically for this technique, a parent [[call frame|frame]] is created on the execution call stack, which the tail-recursive callee can reuse as its own call frame if the tail-call optimization is present.

The tail-recursive implementation can now be converted into an explicitly iterative implementation, as an accumulating [[Loop (computing)#Loops|loop]]:
{|
|-valign="top"
|rowspan="2"|
<syntaxhighlight lang="c">
LinkedList* duplicate(const LinkedList* ls) {
LinkedList head;
LinkedList* end;
end = &head;
while (ls) {
end->next = (LinkedList*)malloc(sizeof(*end));
end->next->value = ls->value;
ls = ls->next;
end = end->next;
}
end->next = NULL;
return head.next;
}
</syntaxhighlight>
|<syntaxhighlight lang="scheme">
;; in Scheme,
(define (duplicate ls)
(let ((head (list 1)))
(do ((end head (cdr end))
(ls ls (cdr ls )))
((null? ls) (cdr head))
(set-cdr! end (list (car ls))))))
</syntaxhighlight>
|-
|<syntaxhighlight lang="prolog">
%% in Prolog,
%% N/A
</syntaxhighlight>
|}

==History==
In a paper delivered to the [[Association for Computing Machinery|ACM]] conference in Seattle in 1977, [[Guy L. Steele]] summarized the debate over the [[GOTO]] and [[structured programming]], and observed that procedure calls in the tail position of a procedure can be best treated as a direct transfer of control to the called procedure, typically eliminating unnecessary stack manipulation operations.<ref name="aim-443">{{Cite book|doi=10.1145/800179.810196|isbn=978-1-4503-2308-6|hdl=1721.1/5753|chapter=Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO|title=Proceedings of the 1977 annual conference on - ACM '77|year=1977|last1=Steele|first1=Guy Lewis|pages=153–162 |s2cid=9807843}}</ref> Since such "tail calls" are very common in [[Lisp (programming language)|Lisp]], a language where procedure calls are ubiquitous, this form of optimization considerably reduces the cost of a procedure call compared to other implementations. Steele argued that poorly-implemented procedure calls had led to an artificial perception that the GOTO was cheap compared to the procedure call. Steele further argued that "in general procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions", with the machine code stack manipulation instructions "considered an optimization (rather than vice versa!)".<ref name="aim-443"/> Steele cited evidence that well-optimized numerical algorithms in Lisp could execute faster than code produced by then-available commercial Fortran compilers because the cost of a procedure call in Lisp was much lower. In [[Scheme (programming language)|Scheme]], a Lisp dialect developed by Steele with [[Gerald Jay Sussman]], tail-call elimination is guaranteed to be implemented in any interpreter.<ref name="r5rs">R5RS Sec. 3.5, {{Cite journal
|author1=Richard Kelsey |author2=William Clinger |author3=Jonathan Rees |date=August 1998
| title = Revised<sup>5</sup> Report on the Algorithmic Language Scheme
| url = http://www.schemers.org/Documents/Standards/R5RS/
| journal = Higher-Order and Symbolic Computation
| volume = 11
| issue = 1
| pages = 7–105
| doi = 10.1023/A:1010051815785
|s2cid=14069423 |display-authors=etal| url-access = subscription
}}</ref>

==Implementation methods==
Tail recursion is important to some [[high-level programming language|high-level languages]], especially [[functional programming|functional]] and [[logic programming|logic]] languages and members of the [[Lisp programming language|Lisp]] family. In these languages, tail recursion is the most commonly used way (and sometimes the only way available) of implementing iteration. The language specification of Scheme requires that tail calls are to be optimized so as not to grow the stack. Tail calls can be made explicitly in [[Perl]], with a variant of the "goto" statement that takes a function name: <code>goto &NAME;</code><ref>{{cite web|author=Contact details |url=http://perldoc.perl.org/functions/goto.html |title=goto |publisher=perldoc.perl.org |access-date=2013-03-21}}</ref>

However, for language implementations which store function arguments and local variables on a [[call stack]] (which is the default implementation for many languages, at least on systems with a [[hardware stack]], such as the [[x86]]), implementing generalized tail-call optimization (including mutual tail recursion) presents an issue: if the size of the callee's activation record is different from that of the caller, then additional cleanup or resizing of the stack frame may be required. For these cases, optimizing tail recursion remains trivial, but general tail-call optimization may be harder to implement efficiently.

For example, in the [[Java virtual machine]] (JVM), tail-recursive calls can be eliminated (as this reuses the existing call stack), but general tail calls cannot be (as this changes the call stack).<ref>"[https://stackoverflow.com/questions/12045299/what-is-difference-between-tail-calls-and-tail-recursion What is difference between tail calls and tail recursion?]", ''Stack Overflow''</ref><ref>"[http://programmers.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization What limitations does the JVM impose on tail-call optimization]", ''Programmers Stack Exchange''</ref> As a result, functional languages such as [[Scala (programming language)|Scala]] that target the JVM can efficiently implement direct tail recursion, but not mutual tail recursion.

The [[GNU Compiler Collection|GCC]], [[Clang|LLVM/Clang]], and [[Intel C Compiler|Intel]] compiler suites perform tail-call optimization for [[C (programming language)|C]] and other languages at higher optimization levels or when the <code>-foptimize-sibling-calls</code> option is passed.<ref name="llvm-documentation-tco">{{cite web |last1=Lattner |first1=Chris |title=LLVM Language Reference Manual, section: The LLVM Target-Independent Code Generator, sub: Tail Call Optimization |url=http://llvm.org/docs/CodeGenerator.html#tail-call-optimization |website=The LLVM Compiler Infrastructure |publisher=The LLVM Project |access-date=24 June 2018 |ref=llvm.org}}</ref><ref>{{cite web|url=https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html|title=Using the GNU Compiler Collection (GCC): Optimize Options|website=gcc.gnu.org}}</ref><ref>{{cite web |url=https://software.intel.com/en-us/node/522809 |title=foptimize-sibling-calls|website=software.intel.com}}</ref> Though the given language syntax may not explicitly support it, the compiler can make this optimization whenever it can determine that the return types for the caller and callee are equivalent, and that the argument types passed to both function are either the same, or require the same amount of total storage space on the call stack.<ref>{{cite web|url=http://www.drdobbs.com/tackling-c-tail-calls/184401756|title=Tackling C++ Tail Calls}}</ref>

Various implementation methods are available.

===In assembly===
{{unreferenced section|date=June 2014}}
Tail calls are often optimized by [[interpreter (computing)|interpreters]] and [[compiler]]s of [[functional programming]] and [[logic programming]] languages to more efficient forms of [[iteration]]. For example, [[Scheme (programming language)|Scheme]] programmers commonly express [[while loop]]s as calls to procedures in tail position and rely on the Scheme compiler or interpreter to substitute the tail calls with more efficient [[jump (computer science)|jump]] instructions.<ref>{{cite web | url=https://gcc.gnu.org/ml/gcc/2000-07/msg00595.html | title=proper tail recursion for gcc | publisher=GCC Project | date=20 July 2000 | access-date=10 March 2015 | author=Probst, Mark}}</ref>

For compilers generating assembly directly, tail-call elimination is easy: it suffices to replace a call opcode with a jump one, after fixing parameters on the stack. From a compiler's perspective, the first example above is initially translated into pseudo-[[assembly language]] (in fact, this is valid [[x86 assembly language|x86 assembly]]):

<syntaxhighlight lang="asm">
foo:
call B
call A
ret
</syntaxhighlight>

Tail-call elimination replaces the last two lines with a single jump instruction:

<syntaxhighlight lang="asm">

foo:
call B
jmp A
</syntaxhighlight>

After subroutine <code>A</code> completes, it will then return directly to the return address of <code>foo</code>, omitting the unnecessary <code>ret</code> statement.

Typically, the subroutines being called need to be supplied with [[parameter (computer science)|parameter]]s. The generated code thus needs to make sure that the [[call frame]] for A is properly set up before jumping to the tail-called subroutine. For instance, on [[computing platform|platform]]s where the [[call stack]] does not just contain the [[return statement|return address]], but also the parameters for the subroutine, the compiler may need to emit instructions to adjust the call stack. On such a platform, for the code:

'''function''' foo(data1, data2)
B(data1)
'''return''' A(data2)

(where <code>data1</code> and <code>data2</code> are parameters) a compiler might translate that as:{{efn| The <code>call</code> instruction first pushes the current code location onto the stack and then performs an unconditional jump to the code location indicated by the label. The <code>ret</code> instruction first pops a code location off the stack, then performs an unconditional jump to the retrieved code location. }}

<syntaxhighlight lang="nasm" line>
foo:
mov reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
push reg ; put data1 on stack where B expects it
call B ; B uses data1
pop ; remove data1 from stack
mov reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
push reg ; put data2 on stack where A expects it
call A ; A uses data2
pop ; remove data2 from stack.
ret
</syntaxhighlight>

A tail-call optimizer could then change the code to:

<syntaxhighlight lang="nasm" line>
foo:
mov reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
push reg ; put data1 on stack where B expects it
call B ; B uses data1
pop ; remove data1 from stack
mov reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
mov [sp+data1],reg ; put data2 where A expects it
jmp A ; A uses data2 and returns immediately to caller.
</syntaxhighlight>

This code is more efficient both in terms of execution speed and use of stack space.

===Through trampolining===
Since many [[Scheme (programming language)|Scheme]] compilers use [[C (programming language)|C]] as an intermediate target code, the tail recursion must be encoded in C without growing the stack, even if the C compiler does not optimize tail calls. Many implementations achieve this by using a device known as a [[Trampoline (computers)|trampoline]], a piece of code that repeatedly calls functions. All functions are entered via the trampoline. When a function has to tail-call another, instead of calling it directly and then returning the result, it returns the address of the function to be called and the call parameters back to the trampoline (from which it was called itself), and the trampoline takes care of calling this function next with the specified parameters. This ensures that the C stack does not grow and iteration can continue indefinitely.

It is possible to implement trampolines using [[higher-order function]]s in languages that support them, such as [[Groovy (programming language)|Groovy]], [[Visual Basic .NET]] and [[C Sharp (programming language)|C#]].<ref name="onyourtail">Samuel Jack, [http://blog.functionalfun.net/2008/04/bouncing-on-your-tail.html Bouncing on your tail]. ''Functional Fun''. April 9, 2008.</ref>

Using a trampoline for all function calls is rather more expensive than the normal C function call, so at least one Scheme compiler, [[Chicken (Scheme implementation)|Chicken]], uses a technique first described by [[Henry Baker (computer scientist)|Henry Baker]] from an unpublished suggestion by [[Andrew Appel]],<ref name="Chicken">Henry Baker, [http://home.pipeline.com/~hbaker1/CheneyMTA.html "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A."] {{Webarchive|url=https://web.archive.org/web/20060303155622/http://home.pipeline.com/~hbaker1/CheneyMTA.html |date=2006-03-03 }}</ref> in which normal C calls are used but the stack size is checked before every call. When the stack reaches its maximum permitted size, objects on the stack are [[garbage collection (computer science)|garbage-collected]] using the [[Cheney algorithm]] by moving all live data into a separate heap. Following this, the stack is unwound ("popped") and the program resumes from the state saved just before the garbage collection. Baker says "Appel's method avoids making a large number of small trampoline bounces by occasionally jumping off the Empire State Building."<ref name="Chicken" /> The garbage collection ensures that mutual tail recursion can continue indefinitely. However, this approach requires that no C function call ever returns, since there is no guarantee that its caller's stack frame still exists; therefore, it involves a much more dramatic internal rewriting of the program code: [[continuation-passing style]].

==Relation to the ''while'' statement==
Tail recursion can be related to the [[while loop|''while'' statement]], an explicit iteration, for instance by transforming

'''procedure''' foo(''x'')
'''if''' ''p''(''x'')
'''return''' bar(''x'')
'''else'''
'''return''' foo(baz(''x''))

into

'''procedure''' foo(''x'')
'''while''' '''true'''
'''if''' ''p''(''x'')
'''return''' bar(''x'')
'''else'''
''x'' ← baz(''x'')

where ''x'' may be a tuple involving more than one variable: if so, care must be taken in implementing the [[Assignment (computer science)|assignment statement]] ''x'' ← baz(''x'') so that dependencies are respected. One may need to introduce auxiliary variables or use a ''[[Swap (computer science)|swap]]'' construct.

More generally,

'''procedure''' foo(''x'')
'''if''' ''p''(''x'')
'''return''' bar(''x'')
'''else if''' ''q''(''x'')
'''return''' baz(''x'')
...
'''else if''' ''r''(''x'')
'''return''' foo(qux(''x''))
...
'''else'''
'''return''' foo(quux(''x''))

can be transformed into

'''procedure''' foo(''x'')
'''while''' '''true'''
'''if''' ''p''(''x'')
'''return''' bar(''x'')
'''else if''' ''q''(''x'')
'''return''' baz(''x'')
...
'''else if''' ''r''(''x'')
''x'' ← qux(''x'')
...
'''else'''
''x'' ← quux(''x'')

For instance, this [[Julia (programming language)|Julia]] program gives a non-tail recursive definition <code>fact</code> of the factorial:

<syntaxhighlight lang="julia" line="1">
function factorial(n)
if n == 0
return 1
else
return n * factorial(n - 1)
end
end
</syntaxhighlight>

Indeed, <code>n * factorial(n - 1)</code> wraps the call to <code>factorial</code>. But it can be transformed into a tail-recursive definition by adding an argument <code>a</code> called an ''accumulator''.<ref name="sicp" />

This Julia program gives a tail-recursive definition <code>fact_iter</code> of the factorial:

<syntaxhighlight lang="julia" line="1">
function factorial(n::Integer, a::Integer)
if n == 0:
return a
else
return factorial(n - 1, n * a)
end
end

function factorial(n::Integer)
return factorial(n, 1)
end
</syntaxhighlight>

This Julia program gives an iterative definition <code>fact_iter</code> of the factorial:

<syntaxhighlight lang="julia">
function fact_iter(n::Integer, a::Integer)
while n > 0
a = n * a
n = n - 1
end
return a
end

function factorial(n::Integer)
return fact_iter(n, one(n))
end
</syntaxhighlight>

==Language support==
* [[C++ (programming language)|C++]] {{En dash}} C and C++ both do tail-call optimization.<ref>{{cite web|url=https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization|title=Which, if any, C++ compilers do tail-recursion optimization?|website=stackoverflow}}</ref>
* [[Clojure (programming language)|Clojure]] {{En dash}} Clojure has <code>recur</code> special form.<ref>{{cite web|url=https://clojure.org/reference/special_forms#recur|title=(recur expr*)|website=clojure.org}}</ref>
* [[Common Lisp]] {{En dash}} Some implementations perform tail-call optimization during compilation if optimizing for speed
* [[Elixir (programming language)|Elixir]] {{En dash}} Elixir implements tail-call optimization,<ref>{{cite web|url=http://elixir-lang.org/getting-started/recursion.html|title=Recursion|website=elixir-lang.github.com}}</ref>as do all languages currently targeting the BEAM VM.
* [[Elm (programming language)|Elm]] {{En dash}} Yes<ref>{{ cite web|url=https://functional-programming-in-elm.netlify.app/recursion/tail-call-elimination.html|title=Functional Programming in Elm: Tail-Call Elimination|first=Evan|last=Czaplicki}}</ref>
* [[Erlang (programming language)|Erlang]] {{En dash}} Yes
* [[F Sharp (programming language)|F#]] {{En dash}} F# implements TCO by default where possible <ref>{{cite web|url=https://blogs.msdn.microsoft.com/fsharpteam/2011/07/08/tail-calls-in-f/|title=Tail Calls in F#|website=msdn|date=8 July 2011 |publisher=Microsoft}}</ref>
* [[Go (programming language)|Go]] {{En dash}} No support<ref>{{cite web|url=https://github.com/golang/go/issues/22624|title=proposal: Go 2: add become statement to support tail calls|website=github.com}}</ref>
* [[Haskell (programming language)|Haskell]] {{En dash}} Yes<ref>{{Cite web|url=https://wiki.haskell.org/Tail_recursion|title=Tail recursion - HaskellWiki|website=wiki.haskell.org|access-date=2019-06-08}}</ref>
* [[JavaScript]] {{En dash}} [[ECMAScript]] 6.0 compliant engines should have tail calls<ref>{{cite web|url=http://bdadam.com/blog/video-douglas-crockford-about-the-new-good-parts.html|title=Worth watching: Douglas Crockford speaking about the good new parts of JavaScript in 2014|first=Adam|last=Beres-Deak|website=bdadam.com}}</ref> which is now implemented on [[Safari (browser)|Safari]]/[[WebKit]]<ref>{{cite web|url=https://www.webkit.org/blog/4054/es6-in-webkit/|title=ECMAScript 6 in WebKit| date=13 October 2015}}</ref> but rejected by V8 and SpiderMonkey
* [[Kotlin (programming language)|Kotlin]] {{En dash}} Has <code>tailrec</code> modifier for functions<ref>{{cite web| url=https://kotlinlang.org/docs/reference/functions.html#tail-recursive-functions|title=Functions: infix, vararg, tailrec - Kotlin Programming Language|website=Kotlin}}</ref>
* [[Lua (programming language)|Lua]] {{En dash}} Tail recursion is required by the language definition<ref>{{cite web| url=https://www.lua.org/manual/5.3/manual.html#3.4.10|title=Lua 5.3 Reference Manual|website=www.lua.org}}</ref>
* [[Objective-C]] {{En dash}} Compiler optimizes tail calls when -O1 (or higher) option specified, but it is easily disturbed by calls added by [[Automatic Reference Counting]] (ARC).
* [[OCaml]] {{En dash}} Yes
* [[Perl (programming language)|Perl]] {{En dash}} Explicit with a variant of the "goto" statement that takes a function name: <code>goto &NAME;</code><ref>{{cite web|url=http://perldoc.perl.org/functions/goto.html|title=goto - perldoc.perl.org| website=perldoc.perl.org}}</ref>
* [[Prolog|Prolog]] {{En dash}} [[SWI-Prolog]] implements tail-recursion optimization.<ref>{{cite web|url=https://www.lix.polytechnique.fr/~catuscia/teaching/prolog/Manual/sec-2.10.html | title=SWI-Prolog Reference Manual | website=www.lix.polytechnique.fr}}</ref>
* [[PureScript]] {{En dash}} Yes
* [[Python (programming language)|Python]] {{En dash}} Stock Python implementations do not perform tail-call optimization, though a third-party module is available to do this.<ref>{{cite web|url=https://github.com/baruchel/tco|title=baruchel/tco|website=GitHub|date=29 March 2022}}</ref> Language inventor [[Guido van Rossum]] contended that [[stack traces]] are altered by tail-call elimination making debugging harder, and preferred that programmers use explicit [[iteration]] instead.<ref>{{cite web|url=http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html|title=Neopythonic: Tail Recursion Elimination|first=Guido Van|last=Rossum|date=22 April 2009}}</ref> In Python 3.14, a new interpreter was introduced that uses tail-call based dispatch of Python opcodes.<ref name="Python Tail-Call Interpreter Dev Discussion">{{cite web |date=2024-01-08 |title=Tail-calling interpreter |url=https://github.com/faster-cpython/ideas/issues/642 |access-date=2025-03-08 |website=GitHub}}</ref> This resulted in overall improved performance when compared to Python 3.13.<ref>{{Cite web |title=What's new in Python 3.14 |url=https://docs.python.org/3.14/whatsnew/3.14.html#a-new-type-of-interpreter |access-date=2025-02-19 |website=Python documentation |language=en}}</ref><ref name="Python Tail-Calling Interpreter Proposal">{{cite web |date=2025-01-06 |title=A new tail-calling interpreter for significantly better interpreter performance |url=https://github.com/python/cpython/issues/128563 |access-date=2025-03-08 |website=GitHub}}</ref>
* [[R (programming language)|R]] {{En dash}} Yes, {{Code|tailcall()}} function introduced in R.4.4.0<ref>{{Cite web |date=2024-04-25 |title=What's new in R 4.4.0? |url=https://www.jumpingrivers.com/blog/whats-new-r44/ |access-date=2024-04-28 |website=www.jumpingrivers.com |language=en-gb}}</ref>
* [[Racket (programming language)|Racket]] {{En dash}} Yes<ref>{{cite web|url=https://docs.racket-lang.org/reference/eval-model.html#(part._.Tail_.Position)|title=The Racket Reference|website=docs.racket-lang.org}}</ref>
* [[Ruby (programming language)|Ruby]] {{En dash}} Yes, but disabled by default <ref>{{cite web|url=https://docs.ruby-lang.org/en/master/RubyVM/InstructionSequence.html#method-c-compile_option-3D|title=Ruby Tail Call Optimisation}}</ref>
* [[Rust (programming language)|Rust]] {{En dash}} tail-call optimization may be done in limited circumstances, but is not guaranteed<ref>{{cite web|url=https://prev.rust-lang.org/en-US/faq.html#does-rust-do-tail-call-optimization|title=Rust FAQ|website=prev.rust-lang.org}}</ref>
* [[Scala (programming language)|Scala]] {{En dash}} Tail-recursive functions are automatically optimized by the compiler. Such functions can also optionally be marked with a <code>@tailrec</code> annotation, which makes it a compilation error if the function is not tail recursive<ref>{{Cite web|url=https://www.scala-lang.org/api/2.13.0/scala/annotation/tailrec.html|title=Scala Standard Library 2.13.0 - scala.annotation.tailrec|website=www.scala-lang.org|access-date=2019-06-20}}</ref>
* [[Scheme (programming language)|Scheme]] {{En dash}} Required by the language definition<ref>{{cite web|url=http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%25_sec_3.5|title=Revised^5 Report on the Algorithmic Language Scheme| website=www.schemers.org}}</ref><ref>{{cite web|url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11| title=Revised [6] Report on the Algorithmic Language Scheme|website=www.r6rs.org}}</ref>
* [[Swift_(programming_language)|Swift]] {{En dash}} In some cases (as of 2014).<ref>{{cite web |title=Does Swift implement tail call optimization? |url=https://stackoverflow.com/questions/24023580/does-swift-implement-tail-call-optimization-and-in-mutual-recursion-case |access-date=13 March 2024 |date=2014}}</ref>
* [[Tcl]] {{En dash}} Since Tcl 8.6, Tcl has a {{Code|tailcall}} command<ref>{{cite web|url=http://www.tcl.tk/man/tcl/TclCmd/tailcall.htm| title=tailcall manual page - Tcl Built-In Commands|website=www.tcl.tk}}</ref>
* [[Zig (programming language)|Zig]] {{En dash}} Yes<ref>{{cite web | url=https://ziglang.org/documentation/master/#call | title=Documentation - the Zig Programming Language }}</ref>

==See also==
{{Portal|Computer programming}}
{{Wiktionary|tail recursion}}
* [[Course-of-values recursion]]
* [[Recursion (computer science)]]
* [[Primitive recursive function]]
* [[Inline expansion]]
* [[Leaf subroutine]]
* [[Corecursion]]

==Notes==
{{Notelist}}

==References==
{{Reflist}}

{{DEFAULTSORT:Tail Call}}
[[Category:Programming language implementation]]
[[Category:Implementation of functional programming languages]]
[[Category:Subroutines]]
[[Category:Control flow]]
[[Category:Recursion]]
[[Category:Scheme (programming language)]]
[[Category:Articles with example C code]]
[[Category:Articles with example Scheme (programming language) code]]
[[pt:Recursividade (ciência da computação)#Funções recursivas em cauda]]
[[es:Recursión (ciencias de computación)#Funciones de recursión de cola]]

Stack trace

2025-10-19T15:53:24Z

2605:8D80:6C24:88A9:E0B2:AD7C:76A8:4BDF: /* Java */

{{Short description|Report of stack frames during program execution}}
{{Redirect|Backtrace|the 2018 film|Backtrace (film)}}

In [[computing]], a '''stack trace''' (also called '''stack backtrace'''<ref>{{cite web | url=https://www.gnu.org/software/libc/manual/html_node/Backtraces.html | title=libc manual: backtraces | publisher=gnu.org | accessdate=8 July 2014}}</ref> or '''stack traceback'''<ref>{{cite web | url=https://docs.python.org/3/library/traceback.html | title=traceback — Print or retrieve a stack traceback | publisher=python.org | accessdate=8 July 2014}}</ref>) is a report of the active [[stack frame]]s at a certain point in time during the execution of a [[computer program|program]]. When a program is run, memory is often dynamically allocated in two places: the [[Stack (abstract data type)#Hardware stack|stack]] and the [[Memory_management#HEAP|heap]]. Memory is continuously allocated on a stack but not on a heap. Stack also refers to a programming construct, thus to differentiate it, this stack is referred to as the program's '''[[Call stack|function call stack]]'''. Technically, once a block of memory has been allocated on the stack, it cannot be easily removed as there can be other blocks of memory that were allocated after it. Each time a function is called in a program, a block of memory called an '''activation record''' is allocated on top of the call stack. Generally, the activation record stores the function's arguments and local variables. What exactly it contains and how it's laid out is determined by the [[calling convention]].

Programmers commonly use stack tracing during interactive and post-mortem [[debugging]]. End-users may see a stack trace displayed as part of an [[error message]], which the user can then report to a programmer.

A stack trace allows tracking the sequence of [[nested function]]s called - up to the point where the stack trace is generated. In a post-mortem scenario this extends up to the function where the failure occurred (but was not necessarily caused). [[Tail call|Sibling calls]] do not appear in a stack trace.

== Language support ==
Many programming languages, including [[Java (programming language)|Java]]<ref>{{cite web | title=Thread (Java SE 16 & JDK 16) | website=Java Platform Standard Edition & Java Development Kit Version 16 API Specification | date=2021-03-04 | url=https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/lang/Thread.html#getStackTrace() | access-date=2021-07-04}}</ref> and [[C Sharp (programming language)|C#]],<ref>{{cite web | title=Environment.StackTrace Property (System) | website=Microsoft Docs | date=2021-05-07 | url=https://docs.microsoft.com/en-us/dotnet/api/system.environment.stacktrace | access-date=2021-07-04}}</ref> have built-in support for retrieving the current stack trace via system calls. Before <code>std::stacktrace</code> was added in standard library as a container for <code>std::stacktrace_entry</code>, pre-[[C++23]] has no built-in support for doing this, but C++ users can retrieve stack traces with (for example) the [https://stacktrace.sourceforge.net/ stacktrace] [[library (computing)|library]]. In [[JavaScript]], [[Exception handling|exceptions]] hold a <code>stack</code> property that contain the stack from the place where it was thrown.

=== Python ===
As an example, the following [[Python (programming language)|Python]] program contains an error.
<syntaxhighlight lang="python" line="1" highlight="3,9,13,16">
def a() -> int:
i: int = 0
j: int = b(i)
return j

def b(z: int) -> int:
k: int = 5
if z == 0:
c()
return k + z

def c() -> None:
error()

if __name__ == "__main__":
a()
</syntaxhighlight>
Running the program under the standard Python interpreter produces the following error message.
<syntaxhighlight lang="pytb">
Traceback (most recent call last):
File "file.py", line 16, in <module>
a()
File "file.py", line 3, in a
j = b(i)
File "file.py", line 9, in b
c()
File "file.py", line 13, in c
error()
NameError: name 'error' is not defined
</syntaxhighlight>
The stack trace shows where the error occurs, namely in the <code>c</code> function. It also shows that the <code>c</code> function was called by <code>b</code>, which was called by <code>a</code>, which was in turn called by the code on line 15 (the last line) of the program. The activation records for each of these three functions would be arranged in a stack such that the <code>a</code> function would occupy the bottom of the stack and the <code>c</code> function would occupy the top of the stack.

=== Java ===
In [[Java (programming language)|Java]], stack traces can be dumped manually with <code>Thread.dumpStack()</code><ref>{{Cite web|title=Thread (Java Platform SE 8 )|url=https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#dumpStack--|access-date=2021-06-15|website=docs.oracle.com}}</ref> Take the following input:
<syntaxhighlight lang="java" line="1" highlight="3,7,11,19">
public class Main {
static void demo() {
demo1();
}

static void demo1() {
demo2();
}

static void demo2() {
demo3();
}

static void demo3() {
Thread.dumpStack();
}

public static void main(String args[]) {
demo();
}
}
</syntaxhighlight>

The exception lists functions in descending order, so the most-inner call is first.

<syntaxhighlight lang="java">
java.lang.Exception: Stack trace
at java.lang.Thread.dumpStack(Thread.java:1336)
at Main.demo3(Main.java:15)
at Main.demo2(Main.java:11)
at Main.demo1(Main.java:7)
at Main.demo(Main.java:3)
at Main.main(Main.java:19)
</syntaxhighlight>

=== C and C++ ===
Both [[C (programming language)|C]] and [[C++]] (pre-[[C++23]]) do not have native support for obtaining stack traces, but libraries such as [[GNU C Library|glibc]] and [[Boost (C++ libraries)|boost]] provide this functionality.<ref name="glibc Backtraces">{{Cite web|title=Backtraces (The GNU C Library)|url=https://www.gnu.org/software/libc/manual/html_node/Backtraces.html|access-date=2021-06-15|website=www.gnu.org}}</ref><ref>{{Cite web|title=Getting Started - 1.76.0|url=https://www.boost.org/doc/libs/1_76_0/doc/html/stacktrace/getting_started.html|access-date=2021-06-15|website=www.boost.org}}</ref> In these languages, some compiler optimizations may interfere with the call stack information that can be recovered at runtime. For instance, [[Inline expansion|inlining]] can cause missing stack frames, [[tail call]] optimizations can replace one stack frame with another, and frame pointer elimination can prevent call stack analysis tools from correctly interpreting the contents of the call stack.<ref name="glibc Backtraces" />

For example, glibc's <code>backtrace()</code> function returns an output with the program function and memory address.
<syntaxhighlight lang="c">
./a.out() [0x40067f]
./a.out() [0x4006fe]
./a.out() [0x40070a]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf5) [0x7f7e60738f45]
./a.out() [0x400599]
</syntaxhighlight>

As of [[C++23]], stack traces can be dumped manually by printing the value returned by static member function <code>std::stacktrace::current()</code>:<ref>{{Cite web|date=2021-10-23|title=Working Draft, Standard for Programming Language C++|url=http://open-std.org/JTC1/SC22/WG21/docs/papers/2020/n4901.pdf|website=open-std.org|publisher=ISO/IEC|page=766}}</ref>
<syntaxhighlight lang="c++">
import std;

using std::stacktrace;

void bar() {
std::println("Stacktrace from bar():\n{}", stacktrace::current());
}

void foo() {
bar();
}

int main() {
foo();
}
</syntaxhighlight>

=== Rust ===
[[Rust (programming language)|Rust]] has two types of errors. Functions that use the panic [[Macro (computer science)|macro]] are "unrecoverable" and the current thread will become poisoned experiencing stack unwinding. Functions that return a <code>std::result::Result</code> are "recoverable" and can be handled gracefully.<ref>{{Cite web|title=rustonomicon unwinding - Rust|url=https://doc.rust-lang.org/nomicon/unwinding.html#:~:text=Rust%20has%20a%20tiered%20error,be%20handled%2C%20the%20thread%20panics.|website=doc.rust-lang.org}}</ref> However, recoverable errors cannot generate a stack trace as they are manually added and not a result of a runtime error.

As of June 2021, [[Rust (programming language)|Rust]] has experimental support for stack traces on unrecoverable errors. Rust supports printing to [[stderr]] when a thread panics, but it must be enabled by setting the <code>RUST_BACKTRACE</code> [[environment variable]].<ref>{{Cite web|title=std::backtrace - Rust|url=https://doc.rust-lang.org/std/backtrace/index.html|access-date=2021-06-15|website=doc.rust-lang.org}}</ref>

When enabled, such backtraces look similar to below, with the most recent call first.
<syntaxhighlight lang="rust">
thread 'main' panicked at 'execute_to_panic', main.rs:3
stack backtrace:
0: std::sys::imp::backtrace::tracing::imp::unwind_backtrace
1: std::panicking::default_hook::{{closure}}
2: std::panicking::default_hook
3: std::panicking::rust_panic_with_hook
4: std::panicking::begin_panic
5: futures::task_impl::with
6: futures::task_impl::park
...
</syntaxhighlight>

==See also==
* [[Tail call]]
* [[Context (computing)]]
* [[Stack overflow]]
* [[Exception handling]]
* [[Call stack]]

==References==
{{reflist}}

{{DEFAULTSORT:Stack Trace}}
[[Category:Debugging]]
[[Category:Articles with example Python (programming language) code]]