This content originally appeared on DEV Community and was authored by Muhammad Ahmad
JavaScript has been called the “assembly language of the web”. The analogy (it isn’t perfect, but which analogy is?) draws from the fact that JavaScipt is often a target for compilation, namely from Clojure and CoffeeScript, but also from many other sources such as pyjamas (python to JS) and Google Web Kit (Java to JS).
But the analogy also references the foolish idea that JavaScript is as expressive and lowlevel as x86 assembly. Perhaps this notion stems from the fact that JavaScript has been bashed for its design flaws and oversights ever since it was first shipped with Netscape back in 1995. It was developed and released in a hurry, before it could be fully developed.
And because of that, some questionable design choices made its way into JavaScript, the language that soon became the de-facto scripting language of the web. Semicolons were a big mistake. So were its ambiguous methods for defining functions. Is it var foo = function(); or function foo();?
Functional programming is an excellent way to side-step some of these mistakes.
By focusing on the fact that JavaScript is truly a functional language, it becomes clear that, in the preceding example about the different ways to declare a function, it’s best to declare functions as variables. And that semicolons are mostly just syntactic sugar to make JavaScript appear more C-like.
But always remember the language you are working with. JavaScript, like any other language, has its pitfalls. And, when programming in a style that often skirts the bleeding edge of what’s possible, those minor stumbles can become non recoverable gotchas. Some of these gotchas include:
- Recursion
- Variable scope and closures
- Function declarations vs. function expressions
However, these issues can be overcome with a little attention.
Recursion, revisited!
Recursion is very important to functional programming in any language. Many functional languages go so far as to require recursion for iteration by not providing for and while loop statements; this is only possible when tail-call elimination is guaranteed by the language, which is not the case for JavaScript. A quick primer on recursion was given in [0x03 (https://dev.to/0xf10yd/fp-in-js-0x03-37bm). But in this section, we’ll dig deeper into exactly how recursion works in JavaScript.
Tail recursion
JavaScript’s routine for handling recursion is known as tail recursion, a stack-based implementation of recursion. This means that, for every recursive call, there is a new frame in the stack.
To illustrate the problems that can arise from this method, let’s use the classic recursive algorithm for factorials.
var factorial = function(n) {
if (n == 0) {
// base case
return 1;
} else {
// recursive case
return n * factorial(n - 1);
}
}
The algorithm will call itself n times to get the answer. It’s literally computing (1 x 1 x 2 x 3 x … x N). That means the time complexity is O(n).
Note
O(n), pronounced “big oh to the n”, means that the complexity of the algorithm will grow at a rate of n as the size of the input grows, which is leaner growth. O(n2) is exponential growth, O(log(n)) is logarithmic growth, and so on. This notation can be used for time complexity as well as space complexity.
But, because a new frame in the memory stack is allocated for each iteration, the space complexity is also O(n). This is a problem. This means that memory will be consumed at such a rate the memory limit will be exceeded far too easily. On my setup, factorial(23456) returns Uncaught Error: RangeError: Maximum call stack size exceeded.
While calculating the factorial of 23,456 is a frivolous endeavor, you can be assured that many problems that are solved with recursion will grow to that size without too much trouble. Consider the case of data trees. The tree could be anything: search applications, file systems, routing tables, and so on. Below is a very simple implementation of the tree traversal function:
var traverse = function(node) {
node.doSomething(); // whatever work needs to be done
node.childern.forEach(traverse); // many recursive calls
}
With just two children per node, both time complexity and space complexity, (in the worst case, where the entire tree must be traversed to find the answer), would be O(n2) because there would be two recursive calls each. With many children per node, the complexity would be O(nm) where m is the number of children. And recursion is the preferred algorithm for tree traversal; a while loop would be much more complex and would require the maintenance of a stack.
Exponential growth like this would mean that it would not take a very large tree to throw a RangeError exception. There must be a better way.
The Tail-call elimination
We need a way to eliminate the allocation of new stack frames for every recursive call. This is known as tail-call elimination.
With tail-call elimination, when a function returns the result of calling itself, the language doesn’t actually perform another function call. It turns the whole thing into a loop for you.
OK, so how do we do this? With lazy evaluation. If we could rewrite it to fold over a lazy sequence, such that the function returns a value or it returns the result of calling another function without doing anything with that result, then new stack frames don’t need to be allocated.
To put it in “tail recursion form”, the factorial function would have to be rewritten such that the inner procedure fact calls itself last in the control flow, as shown in the following code snippet:
var factorial = function(n) {
var _fact = function(x, n) {
if (n == 0) {
// base case
return x;
} else {
// recursive case
return _fact(n * x, n - 1);
}
}
return fact(1, n);
}
Note
Instead of having the result produced by the first function in the recursion tail (like in n * factorial(n-1)), the result is computed going down the recursion tail (with the call to _fact(r*n, n-1)) and is produced by the last function in this tail (with return r;).
The computation goes only one way down, not on its way up. It’s relatively easy to process it as an iteration for the interpreter.
However, tail-call elimination does not work in JavaScript. Put the above code into your favorite JavaScript engine and factorial(24567) still returns Uncaught Error: RangeError: Maximum call stack size exceeded exception. Tail-call elimination islisted as a new feature included in ECMAScript 6.
This content originally appeared on DEV Community and was authored by Muhammad Ahmad
Muhammad Ahmad | Sciencx (2021-11-07T19:27:56+00:00) Functional Programming in JS: 0x07 – Advanced Topics and Pitfalls. Retrieved from https://www.scien.cx/2021/11/07/functional-programming-in-js-0x07-advanced-topics-and-pitfalls/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.