Implementation of Optimization of JS Tail Tune

Tail Call is an important concept of functional programming, this article describes its meaning and usage.

First, what is the tail call?

The concept of tail call is very simple, and a sentence can be clear, that is, the final step of a function is to call another function.

Function f (x) {return g (x);}

In the above code, the function f The last step is to call the function G, which is called tail call.
  The following two cases are not tail.  
// A case function f (x) {let y = g (x); returnix y;} // case two function f (x) {Return G ( x) + 1;}
In the above code, the case one is after the call function G, there is another operation, so it is not a tail mode, even if the semantics are exactly the same. The situation is also the operation after the call, even if it is written within one line.

Tissue does not necessarily appear in the tail of the function, as long as it is the last step.

Function f (x) {if (x> 0) {RETURN M (X)} return n (x);}
   In the above code, both functions m and n are tail modes because they are the last step of the function f. 
Second, Tail Tune Optimization

The reason why tail modes is different from other calls, that is, its special call location.

We know that the function call will form a “call record” in memory, also known “Frame “(CALL FRAME), save the call location and internal variables. If the function B is called in the internal call of the function A, the call record of a B is also formed. Wait until the B operation ends, As a result returned to a, the call record will disappear. If the function c is called in the function B, there is a C’s call record stack to push. All call records, form a “call stack” ( Call stack).
 The tail modulation is not required to retain the call record of the outer layer function, because the information such as the call position, internal variables, etc. It will be used again, as long as the internal layer function is recorded directly, the call record of the outer function can be replaced.   
function f () {let m = 1 } f (); // equivalent to function f () {RETURN G (3);} f (); // equivalent to G (3);

In the above code, if the function G is not tail modulation, the function f needs to save the value of the value of the internal variables M and N, the call position of G, and after the call G, The function f is over, so it is executed to the last step, it can completely delete the f () call record, only retain the call record of G (3).
This is called “Tail Call Optimization” ), That is, only the call record of the inner layer function. If all functions are tail modes, then you can do only one at each execution, this will greatly save memory. This is “Optimization of Tail Tune” Significance.

Third, the tail recurrent

The function call itself, called recursive. If the tail is called itself, it is called the tail recurrent.

js尾调用优化的实现 Removable is very consuming, because it is necessary to save thousands of call records, it is easy to happen “Stack overflow” error (STACK overflow). But for the end of the tail, since there is only one call record, “stack overflow” error will never happen.

Function Factorial (N) {if (n === 1) Return 1; Return N * Factorial (N – 1);} Factorial (5) // 120
  The above code is a step-by-step function, calculating the steps of N, and you need to save N call records, complexity O (n).  
If it is rewritten, only one call record and complexity O (1) are retained.

Function Factorial (n, Total) {IF (n === 1) Return Total; Return Factorial (N – 1, N * Total);} Factorial (5 , 1) // 120

This shows that “optimization of tail modulation” is significant for recursion operation, so some functional programming The language writes it into the language specifications. The same is true for ES6. The first clear statement, all ECMAScript implementations must deploy “Optimization of Tail Tune”. That is to say, in ES6, as long as the tail is returned, there will be no stack overflow, which saves memory.

Record of recursive functions

Implementation of tail (123), often need to rewrite recursive functions, ensuring that the last step is only called itself. What to do this is to rewrite all the internal variables used into a function. For example, the example above, the classification function factorial needs to use an intermediate variable Total, then rewrite this intermediate variable into a function of the function. The disadvantage of this is not intuitive, and it is difficult to see the first eye., Why the factorial of 5, need to pass two parameters 5 and 1?
two ways to solve this problem. One method outside tail recursive function, then a normal function of the form.
   
function tailFactorial (n, total) {if (n === 1) return total; return tailFactorial (n – 1, n * total);} function factorial ( n) {return tailFactorial (n, 1);} factorial (5) // 120

the above code via a normal form of factorial function factorial, tail recursive function calls tailFactorial , looks more normal.
have a functional programming concept called curried (as currying), meaning that the transfer function parameters into a single multi-parameter form. Here you can also use currying.
   
function currying (fn, n) {return function (m) {return fn.call (this, m, n);};} function tailFactorial (n, total ) {if (n === 1) return total; return tailFactorial (n – 1, n * total);} const factorial = currying (tailFactorial, 1); factorial (5) // 120

js尾调用优化的实现

the above curried code via the tail recursive function becomes only accept tailFactorial1 parameter Factorial.

The second method is much simpler, that is, the function of the function of ES6 is default.

Function Factorial (n, Total = 1) {IF (n === 1) Return Total; Return Factorial (N – 1, N * Total);} Factorial (5) // 120

In the above code, the parameter TOTAL has default 1, so this value is not provided when calling.

Summary, the recursive is essentially a cycle operation. Pure functional programming languages ​​have no loop operation commands, all loops are implemented in recursive, which is extremely important to these languages. For other languages ​​that support “Optimization” (such as Lua, ES6), you only need to know that the loop can be replaced with recursive, and once you use recursive, it is best to use a tail.

(
(
   

“ES6 tail) Optimization is only turned on in strict mode, and the normal mode is invalid.

This is because in normal mode, there are two variables inside the function to track the call stack of functions.
arguments: Returns the parameters of the function when calling.
 Func.caller: Returns the function that calls the current function.   When the tail tune is optimized, the call stack of the function will be rewritten, so the above two variables are distorted. Strict mode Disable these two variables, so tail modes are only take effect in strict mode. 
The above is all the content of this article, I hope to help everyone, I hope everyone will support Tumi Clouds.

© Copyright Notice
THE END
Just support it if you like
like0
share
comment Grab the couch

Please log in to comment