JavaScript tail recursion emulation

If someone else doesn’t know what tail recursion is, here’s a simple example of a method that adds natural numbers from 1 to n (n≥0) in the forehead:

function add(n,acc) { if(n===0) return acc; return add(n-1,acc+n); } 

Initially, the function is called with the parameter acc = 0. If n is not zero, the method calls itself with other parameters and returns the result. The compiler (or interpreter, or virtual machine) can understand that the current function call in the stack is no longer needed, erase it and replace it with the next one. Thus, recursion does not cause stack growth. Strictly speaking, a tail call is not required to refer to the current function: any other call can also be a tail call. The main condition: calling a function and returning its result must be the last actions in the current function. For example, in such an implementation of the tail-recursion method there is no, because after the call, addition is still happening:

 function add(n) { if(n===0) return 0; return n+add(n-1); } 

For a number of reasons, tail recursion is not supported in JavaScript (discussion on this topic is on StackOverflow ). Therefore, a call like add (100000.0) ends with an exception. At Habré attempts were made to solve this problem through setTimeout, but it does not look very fair and not very beautiful. A more elegant solution for the Python language was proposed using the " springboard ". A similar approach for javascript is reviewed here . But I wanted it to work quickly and so that the function could be written just like in the example above. See what you can do.

In this article we will consider a limited, but rather popular case, when a function calls the tail method only to itself (it can call any other functions, but their calls will not be optimized). Thus, instead of calling again, you just need to replace the values ​​of the arguments with new ones and go to the beginning of the current function. There is no goto operator in JavaScript, but you can always wrap a function in such a block:

 $tail$label:while(true) { < >; return; } 

Then go to the beginning of the function using continue $tail$label . How to replace a function call with such a transition? The easy way that came to mind is to replace the function of another, which throws an exception. Then you can catch it and rewrite the parameters. It will look something like this:

 function add(n,acc) { function add() {throw arguments;} while(true) { try { if(n===0) return acc; return add(n-1,acc+n); } catch($tail$ex) { n = $tail$ex[0]; acc = $tail$ex[1]; } } } 

As you can see, instead of ourselves, we now call a nested function that throws an exception. We gracefully catch it, rewrite the arguments and move on to the next iteration of the loop (even the label was not useful).

But I don’t want to write this every time, the task was simply to write. How to remake a simple function in this? We decompile the source code of the function (using toString), correct it and compile it back using eval like this:

 Function.prototype.tail = function() { var funcStr = Object.toString.apply(this); var paramsPos = funcStr.indexOf('('); var paramsEndPos = funcStr.indexOf(')'); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, ""); var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(","); var body = funcStr.substring(bodyPos+1, bodyEndPos); var paramPassString = ""; for(var i=0; i<args.length; i++) paramPassString += args[i]+"=$tail$ex["+i+"];"; var newBody = "function "+name+"() {throw arguments;} while(true) {try{"+body+ "return;}catch($tail$ex) {"+paramPassString+"}}"; return eval("var $tail$function = function "+name+"("+args.join(",")+") {\n"+ newBody+"};$tail$function"); } 

First, in the source text of the function, its name, arguments and body are searched. Then additional lines are generated before and after the body, after which everything is going back to the function. This approach has the following limitations:

• The function must have a name;
• The function should call itself exclusively in the tail mode;
• The call itself should not be in the try-catch block (in principle, this follows from the previous one).

Thus, while add (100000.0) drops, add.tail () (100000.0) counts everything perfectly.
')
But what is the price of such a decision? For ease of profiling, add a time function to the Function prototype:

The function takes as the argument the number of starts and averages the time. Let's add such tests:

 var addTail = add.tail(); (function() {return add(10000,0)}).time(500); (function() {return add(100000,0)}).time(500); (function() {return addTail(10000,0)}).time(500); (function() {return addTail(100000,0)}).time(500); 

Now run all this stuff in Google Chrome 25 and see a disappointing result:

 Code: return add(10000,0); result: 50005000; time=0.102 Code: return add(100000,0); error: RangeError: Maximum call stack size exceeded; time=0.162 Code: return addTail(10000,0); result: 50005000; time=2.392 Code: return addTail(100000,0); result: 5000050000; time=24.826 

Although we are no longer limited to the number of iterations, but the performance decrease of 24 times cannot please. What else can be done?

To do without obviously slow things (exceptions and arguments appeals), you have to get into the very body of the function that we are changing. Here, of course, ideally, you should write a JavaScript parser (you can use jslint.js ). But to illustrate the idea, regular expressions will also go, although they will require code in a certain format.

 Function.prototype.tail2 = function() { var funcStr = Object.toString.apply(this); var paramsPos = funcStr.indexOf('('); var paramsEndPos = funcStr.indexOf(')'); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, ""); var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(","); var body = funcStr.substring(bodyPos+1, bodyEndPos); body = body.replace(new RegExp("return\\s+"+name+"\\s*\\((.+?)\\);", "g"), function(match,argsStr) { var passArgs = argsStr.split(","); var result = ""; for(var i=0; i<args.length; i++) result+="var $tail$arg"+i+"="+passArgs[i]+";" for(var i=0; i<args.length; i++) result+=args[i]+"="+"$tail$arg"+i+";" return "{"+result+"continue $tail$label;}"; }); var newBody = "$tail$label:while(true) {"+body+"return;}"; return eval("var $tail$function = function "+name+"("+args.join(",")+") {"+newBody+"};$tail$function"); } 

Here we make every occurrence of a string like return < >(val1, val2, ..., valN) into a block, where we assign new values ​​to the arguments through intermediate variables, and then call continue. At once I will make a reservation that the code is very naive and will easily break if you have additional brackets or, for example, the?: Operator in the return expression.

Test:

 var addTail2 = add.tail2(); (function() {return addTail2(10000,0)}).time(500); (function() {return addTail2(100000,0)}).time(500); 

The results are impressive:

 Code: return addTail2(10000,0); result: 50005000; time=0.022 Code: return addTail2(100000,0); result: 5000050000; time=0.222 

It has become even faster than the original! Of course, now we save on function calls.

What else to test? Take the original function to find the Fibonacci numbers from the above article :

 function cpsFib(n, prev, cur, _return) { if (n < 2) { return _return(cur); } return cpsFib(--n, cur, cur + prev, _return); } function identity(x) {return x} var cpsFibTail = cpsFib.tail(); var cpsFibTail2 = cpsFib.tail2(); (function() {return cpsFib(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail2(1300, 0, 1, identity)}).time(5000); 

Results:

 Code: return cpsFib(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0222 Code: return cpsFibTail(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.3436 Code: return cpsFibTail2(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0036 

If we take the implementation from the article, it will turn out like this:

 Code: return cpsFib.tco(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.187 

Faster than our version with exceptions, but still 8 times slower than the usual recursive form and 52 times slower than our optimized form.

I do not know whether such things can be useful in real projects, but for fun, why not. In any case, you should pay attention to the possibility of regeneration of JavaScript source code. This is usually used by viruses and obfuscators, but it is likely that this tool can also be used for other purposes.