preface

This article is 2433 words and takes about 10 minutes to read.

Summary: this paper introduces the concept of tail-call, tail-recursion, combined with examples to explain what is tail-call optimization, and describes the current situation of tail-call optimization.

  • Reference article: A follow-up to tail recursion
  • Public account: “front-end advanced learning”, reply to “666”, get a package of front-end technology books

Things close to respect, the United States more than three.

The body of the

Tail calls are an important concept in functional programming, and this article will learn about tail calls.

The tail call

In the previous article on Javascript higher-order functions, we said that if you print a function within a function, that function can be called higher-order. A tail call is similar to the protagonist of this article. If a function returns the result of another function call, it is called a tail call. Example:

function add(x, y) {
  return x + y;
}
function sum() {
  return add(1.2);
}
Copy the code

The sum function returns the result of the call to Add. But the following example is not a tail call:

function add(x, y) {
  return x + y;
}
/ / 1
function sum() {
  return add(1.2) + 1;
}
/ / 2
function sum2() {
  let a = add(1.2);
  return a;
}
Copy the code

In the example above, neither case 1 nor case 2 are tail calls. Case 1 has a +1 operation after the call to add, and case 2 has an assignment to A after the call to add, so neither case is tail calls.

Tail recursion

Recursion, as we all know, is when a function calls itself. So, a function that returns its own call is called tail recursion. That is, a tail-recursion is necessarily a tail-call, but a tail-call is not necessarily a tail-recursion. Let’s start with an example of regular recursion:

function sum(n) {
	if (n <= 1) return 1;
  return sum(n - 1) + n;
}
sum(10000); / / 50005000
Copy the code

Sum is a recursive function, but it does not fit our definition of tail-calling, so it is not a tail-calling function, nor is it a tail-recursive function. Rewrite as a tail recursive function:

function sum(n, result = 1) {
	if (n <= 1) return result;
  return sum(n - 1, result + n);
}
sum(10000); // Maximum call stack size exceeded
Copy the code

We still call sum(10000), but we get an error, the more common stack overflow. What you don’t know about execution stacks (also known as call stacks) can be found in a previous post on Understanding execution context and execution stacks in Javascript.

Tail-call optimization

Now suppose function A is A function that returns the result of A call to function B. Function B is a function that returns the result of function C. Something like this:

function C() {}
function B() { return C(); }
function A() { return B(); }
A();
Copy the code

When function A is called, A function execution context of A is pushed onto the execution stack, and when function B is called, A function execution context of B is pushed onto the execution stack, and the corresponding execution context is not pushed off the execution stack until function A and function B have finished executing. If function B also returns a call to function C, the process is repeated, and so on. If the number of execution contexts in the stack exceeds the maximum, a stack overflow error is reported, which is why the previous example failed. See the following figure for the execution stack of the function above:

If function B has A reference to A variable in function A, then the execution context of function A cannot be extruded from the execution stack even if the execution ends. This is also known as A closure. But if there is no reference to function A in function B, it would be nice to deduce the execution context of function A directly after execution.

If the above idea is true, the execution stack only needs to keep the execution context of the last function (the innermost function), which is tail-call optimization.

Tail-call optimization: For tail-call functions that meet the requirements, only one implementation of the innermost function’s execution context is kept in the execution stack.

If our optimization works, the ideal stack would look like this:

Remember that an execution context holds a lot of information, and tail-call optimization, if effective, will only have one execution context in the execution stack, which can save a lot of memory. This is what tail-call optimization is all about.

Tail-call optimization, however, is not a feature that ordinary developers can write functions that can be optimized. This feature is usually supported by the compiler or runtime environment. Javascript originally did not support tail-call optimization **, and ES6 only began to specify that program engines should use tail-call optimization ** in strict mode. Moreover, ECMAScript 6 restricts tail calls that do not contain closures to be optimized. This coincides with what we said earlier.

However, in my tests, Chrome(79.0.3945.130) and Safari(13.0.3) are not supported yet, which means that the stack overflow error will still be reported. Tail-recursive call optimization is only supported in earlier versions of Node. Node (6.0.0) can enable tail-recursive call optimization. The same example as before, but in strict mode:

'use strict';
function sum(n, result = 1) {
	if (n <= 1) return result;
  return sum(n - 1, result + n);
}
sum(10000);
Copy the code

Let’s look at the result of calling the above code using Node (6.0.0) :

RangeError: Maximum call stack size exceeded
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:4:13)
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:6:10)
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:6:10)
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:6:10)
Copy the code

Error: Stack overflow. Tail-call optimization is turned off by default in both Node and the browser. You need to add harmony_tailcalls to node to enable tail-call optimization. Then look at:

$ node --harmony_tailcalls tail-call.js                        
5000050000
Copy the code

Results are returned normally. Let’s look at the actual call stack:

'use strict';
function sum(n, result = 1) {
    console.trace();
    if (n <= 1) return result;
    return sum(n - 1, result + n);
}
const result = sum(3);
console.log(result);
Copy the code

Before tail-call optimization is enabled:

Trace
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:3:13)
		at Object.<anonymous> (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:7:16)
Trace
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:3:13)
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:5:10)
		at Object.<anonymous> (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:7:16)
Trace
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:3:13)
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:5:10)
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:5:10)
		at Object.<anonymous> (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:7:16)
Copy the code

As printed above, I have removed all useless information. Let’s look at the last call optimization:

Trace
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:3:13)
    at Object.<anonymous> (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:7:16)
Trace
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:3:13)
    at Object.<anonymous> (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:7:16)
Trace
    at sum (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:3:13)
    at Object.<anonymous> (/Users/mac/Desktop/demo/html-css-js-demo/tail-call.js:7:16)
Copy the code

You can see that, as expected, there is always only one execution context in the execution stack. The space complexity was reduced from O(n) to O(1). Greatly saving memory space.

Here we are left with two questions. One is how to solve the stack overflow error without enabling tail-recursive call optimization. The other is why tail-recursive call should be disabled by default since the benefits are so great. . Let’s start with the first question:

Resolve stack overflow error

  1. forCycle. The root cause is a stack explosion caused by too many execution contexts, so the problem can be solved by not calling the function:
'use strict';
function sum(n) {
    let res = 0;
    for (var i = 0; i < n; i++) {
        res += i;
    }
    return res;
}
const result = sum(3);
console.log(result);
Copy the code
  1. In some cases it does not workforLoop, you’re still calling a function, and you can use thatBounce bed functionThe so-called bounce bed function is equivalent to a transfer station of the function.
// The bouncy bed function executes the function, and if the return type of the function is still function, continues to execute until the end of execution
function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
Copy the code

Accordingly, our original function needs to be rewritten as follows:

function sum(n, result = 1) {
  if (n <= 1) return result;
    return sum.bind(null, n - 1, result + n);
}
Copy the code

Call:

trampoline(sum(100000));
Copy the code

Stack overflow will not be reported.

Tail-call optimization is turned off by default

It must be interesting to see why tail-call optimization is so efficient that it is turned off by default. The answer is twofold:

  1. Implicit optimization problem. Since the engine eliminates tail recursion implicitly, it is difficult for the programmer to tell whether a function conforms to tail call and eliminates tail recursion.
  2. Call stack loss problem. Tail-call optimization requires that the call stack be removed when the tail-call is executed, which causes stack information to be lost in the execution flow.

The reason why Chrome methods that use tail recursion still overflow the call stack is that:

  • The immediate causeNone of the major browsers (except Safari) deploy tail-call optimizations at all;
  • The root cause: Tail call optimization still has the problems of implicit optimization and call stack loss;

Since tail-call optimization is turned off by default, does that mean tail-call is useless? In fact, tail calls are an important concept of functional programming. Properly using tail calls can greatly improve the readability and maintainability of our code. It is more important to write more elegant and easy to read code than to bring a little performance loss.

The above.

The ability is limited, the level is general, welcome to erratum, greatly appreciated.

To subscribe for more articles, follow the public account “Front-end Advanced Learning” and reply to “666” for a package of front-end technology books