# 27. Tail call optimization ECMAScript 6 offers *tail call optimization*, where you can make some function calls without growing the call stack. This chapter explains how that works and what benefits it brings. ## 27.1 What is tail call optimization? Roughly, whenever the last thing a function does is to call another function then the latter does not need to return to its caller. As a consequence, no information needs to be stored on the call stack and the function call is more of a goto (a jump). This kind of call is named *tail call*; not growing the stack is named *tail call optimization* (TCO). Let’s look at an example to better understand TCO. I’ll first explain how it is executed without TCO and then with TCO. ```function` `id``(``x``)` `{` `return` `x``;` `// (A)` `}` `function` `f``(``a``)` `{` `const` `b` `=` `a` `+` `1``;` `return` `id``(``b``);` `// (B)` `}` `console``.``log``(``f``(``2``));` `// (C)` ### 27.1.1 Normal execution Let’s assume there is a JavaScript engine that manages function calls by storing local variables and return addresses on a stack. How would such an engine execute the code? **Step 1.** Initially, there are only the global variables `id` and `f` on the stack. The block of stack entries encodes the state (local variables, including parameters) of the current scope and is called a *stack frame*. **Step 2.** In line C, `f()` is called: First, the location to return to is saved on the stack. Then `f`’s parameters are allocated and execution jumps to its body. The stack now looks as follows. There are now two frames on the stack: One for the global scope (bottom) and one for `f()` (top). `f`’s stack frame includes the return address, line C. **Step 3.**`id()` is called in line B. Again, a stack frame is created that contains the return address and `id`’s parameter. **Step 4.** In line A, the result `x` is returned. `id`’s stack frame is removed and execution jumps to the return address, line B. (There are several ways in which returning a value could be handled. Two common solutions are to leave the result on a stack or to hand it over in a register. I ignore this part of execution here.) The stack now looks as follows: **Step 5.** In line B, the value that was returned by `id` is returned to `f`’s caller. Again, the topmost stack frame is removed and execution jumps to the return address, line C. **Step 6.** Line C receives the value `3` and logs it. ### 27.1.2 Tail call optimization ```function` `id``(``x``)` `{` `return` `x``;` `// (A)` `}` `function` `f``(``a``)` `{` `const` `b` `=` `a` `+` `1``;` `return` `id``(``b``);` `// (B)` `}` `console``.``log``(``f``(``2``));` `// (C)` If you look at the previous section then there is one step that is unnecessary – step 5. All that happens in line B is that the value returned by `id()` is passed on to line C. Ideally, `id()` could do that itself and the intermediate step could be skipped. We can make this happen by implementing the function call in line B differently. Before the call happens, the stack looks as follows. If we examine the call we see that it is the very last action in `f()`. Once `id()` is done, the only remaining action performed by `f()` is to pass `id`’s result to `f`’s caller. Therefore, `f`’s variables are not needed, anymore and its stack frame can be removed before making the call. The return address given to `id()` is `f`’s return address, line C. During the execution of `id()`, the stack looks like this: Then `id()` returns the value `3`. You could say that it returns that value for `f()`, because it transports it to `f`’s caller, line C. Let’s review: The function call in line B is a tail call. Such a call can be done with zero stack growth. To find out whether a function call is a tail call, we must check whether it is in a *tail position* (i.e., the last action in a function). How that is done is explained in the next section. ## 27.2 Checking whether a function call is in a tail position We have just learned that tail calls are function calls that can be executed more efficiently. But what counts as a tail call? First, the way in which you call a function does not matter. The following calls can all be optimized if they appear in a tail position: - Function call: `func(···)` - Dispatched method call: `obj.method(···)` - Direct method call via `call()`: `func.call(···)` - Direct method call via `apply()`: `func.apply(···)` ### 27.2.1 Tail calls in expressions Arrow functions can have expressions as bodies. For tail call optimization, we therefore have to figure out where function calls are in tail positions in expressions. Only the following expressions can contain tail calls: - The conditional operator (`? :`) - The logical Or operator (`||`) - The logical And operator (`&&`) - The comma operator (`,`) Let’s look at an example for each one of them. #### 27.2.1.1 The conditional operator (`? :`) ```const` `a` `=` `x` `=>` `x` `?` `f``()` `:` `g``();` Both `f()` and `g()` are in tail position. #### 27.2.1.2 The logical Or operator (`||`) ```const` `a` `=` `()` `=>` `f``()` `||` `g``();` `f()` is not in a tail position, but `g()` is in a tail position. To see why, take a look at the following code, which is equivalent to the previous code: ```const` `a` `=` `()` `=>` `{` `const` `fResult` `=` `f``();` `// not a tail call` `if` `(``fResult``)` `{` `return` `fResult``;` `}` `else` `{` `return` `g``();` `// tail call` `}` `};` The result of the logical Or operator depends on the result of `f()`, which is why that function call is not in a tail position (the caller does something with it other than returning it). However, `g()` is in a tail position. #### 27.2.1.3 The logical And operator ```const` `a` `=` `()` `=>` `f``()` `&&` `g``();` `f()` is not in a tail position, but `g()` is in a tail position. To see why, take a look at the following code, which is equivalent to the previous code: ```const` `a` `=` `()` `=>` `{` `const` `fResult` `=` `f``();` `// not a tail call` `if` `(``!``fResult``)` `{` `return` `fResult``;` `}` `else` `{` `return` `g``();` `// tail call` `}` `};` The result of the logical And operator depends on the result of `f()`, which is why that function call is not in a tail position (the caller does something with it other than returning it). However, `g()` is in a tail position. #### 27.2.1.4 The comma operator (`,`) ```const` `a` `=` `()` `=>` `(``f``()` `,` `g``());` `f()` is not in a tail position, but `g()` is in a tail position. To see why, take a look at the following code, which is equivalent to the previous code: ```const` `a` `=` `()` `=>` `{` `f``();` `return` `g``();` `}` ### 27.2.2 Tail calls in statements For statements, the following rules apply. Only these compound statements can contain tail calls: - Blocks (as delimited by `{}`, with or without a label) - `if`: in either the “then” clause or the “else” clause. - `do-while`, `while`, `for`: in their bodies. - `switch`: in its body. - `try-catch`: only in the `catch` clause. The `try` clause has the `catch` clause as a context that can’t be optimized away. - `try-finally`, `try-catch-finally`: only in the `finally` clause, which is a context of the other clauses that can’t be optimized away. Of all the atomic (non-compound) statements, only `return` can contain a tail call. All other statements have context that can’t be optimized away. The following statement contains a tail call if `expr` contains a tail call. ```return` `«``expr``»``;` ### 27.2.3 Tail call optimization can only be made in strict mode In non-strict mode, most engines have the following two properties that allow you to examine the call stack: - `func.arguments`: contains the arguments of the most recent invocation of `func`. - `func.caller`: refers to the function that most recently called `func`. With tail call optimization, these properties don’t work, because the information that they rely on may have been removed. Therefore, strict mode forbids these properties ([as described in the language specification](http://www.ecma-international.org/ecma-262/6.0/#sec-addrestrictedfunctionproperties)) and tail call optimization only works in strict mode. ### 27.2.4 Pitfall: solo function calls are never in tail position The function call `bar()` in the following code is not in tail position: ```function` `foo``()` `{` `bar``();` `// this is not a tail call in JS` `}` The reason is that the last action of `foo()` is not the function call `bar()`, it is (implicitly) returning `undefined`. In other words, `foo()` behaves like this: ```function` `foo``()` `{` `bar``();` `return` `undefined``;` `}` Callers can rely on `foo()` always returning `undefined`. If `bar()` were to return a result for `foo()`, due to tail call optimization, then that would change `foo`’s behavior. Therefore, if we want `bar()` to be a tail call, we have to change `foo()` as follows. ```function` `foo``()` `{` `return` `bar``();` `// tail call` `}` ## 27.3 Tail-recursive functions A function is *tail-recursive* if the main recursive calls it makes are in tail positions. For example, the following function is not tail recursive, because the main recursive call in line A is not in a tail position: ```function` `factorial``(``x``)` `{` `if` `(``x` `<=` `0``)` `{` `return` `1``;` `}` `else` `{` `return` `x` `*` `factorial``(``x``-``1``);` `// (A)` `}` `}` `factorial()` can be implemented via a tail-recursive helper function `facRec()`. The main recursive call in line A is in a tail position. ```function` `factorial``(``n``)` `{` `return` `facRec``(``n``,` `1``);` `}` `function` `facRec``(``x``,` `acc``)` `{` `if` `(``x` `<=` `1``)` `{` `return` `acc``;` `}` `else` `{` `return` `facRec``(``x``-``1``,` `x``*``acc``);` `// (A)` `}` `}` That is, some non-tail-recursive functions can be transformed into tail-recursive functions. ### 27.3.1 Tail-recursive loops Tail call optimization makes it possible to implement loops via recursion without growing the stack. The following are two examples. #### 27.3.1.1 `forEach()` ```function` `forEach``(``arr``,` `callback``,` `start` `=` `0``)` `{` `if` `(``0` `<=` `start` `&&` `start` `<` `arr``.``length``)` `{` `callback``(``arr``[``start``],` `start``,` `arr``);` `return` `forEach``(``arr``,` `callback``,` `start``+``1``);` `// tail call` `}` `}` `forEach``([``'a'``,` `'b'``],` `(``elem``,` `i``)` `=>` `console``.``log``(`````${``i``}``. ``${``elem``}`````));` `// Output:` `// 0. a` `// 1. b` #### 27.3.1.2 `findIndex()` ```function` `findIndex``(``arr``,` `predicate``,` `start` `=` `0``)` `{` `if` `(``0` `<=` `start` `&&` `start` `<` `arr``.``length``)` `{` `if` `(``predicate``(``arr``[``start``]))` `{` `return` `start``;` `}` `return` `findIndex``(``arr``,` `predicate``,` `start``+``1``);` `// tail call` `}` `}` `findIndex``([``'a'``,` `'b'``],` `x` `=>` `x` `===` `'b'``);` `// 1` Next: [28. Metaprogramming with proxies](ch_proxies.html)