JavaScript stack overflows even when no recursive function is present

user_1031791 0
Viewed 779

Suppose we wanted to build big structures by using lambdas as "holes" representing the location where we want to add new data. For example, here we build [0,[1,[2,null]]] using that idea:

builder_0 = hole => hole;                // hole => hole;
builder_1 = hole => builder_0([0,hole]); // hole => [0, hole];
builder_2 = hole => builder_1([1,hole]); // hole => [0, [1, hole]];
builder_3 = hole => builder_2([2,hole]); // hole => [0, [1, [2, hole]]];

// prints [0,[1,[2,null]]], but will stack overflows if too many lines
console.log(JSON.stringify(builder_3(null)));

This works fine. We can also do it in a loop:

let builder = hole => hole;
for (let i = 0; i < 1000; ++i) {
  let last_builder = builder;
  builder = hole => last_builder([i, hole]);
};
console.log(builder(null));

This works too, but this algorithm will stack overflow if the limit is larger than 10000. The problem is that, since last_builder([i,hole]) isn't evaluated inside the hole => ... closure, it will build up chunks of unevaluated lambdas that will rapidly consume the whole stack. Note that [0,[1,[2,null]]] is just a useless example, JavaScript will fail to build any large structure using the hole-based technique above (think of trees, JSONs, immutable containers and so on).

Tail-call optimization and trampolining won't help here, as we don't even have a recursive function to begin with. Is there any clever trick that allows this kind of functional idiom to work without stack overflows?

stack-overflow functional-programming javascript
4 Answers

As you're transpiling functional code you can allow yourself not being 'functional' in the JS part. So you can create the data structure that you need without recursion:

const builder = (count,hole) => {
   let arr = [hole];
   let i = 0;
   while (count--) arr = [count,arr]
   return arr;
}

console.log(builder(22333,null))

(please try it out on the browser's console, as the code snippet tool is not able to reproduce it)

user_27296050

I realized the right way to do it is by trampolining. We just use a direct lambda to wrap the result:

builder_0 = hole => () => hole;                // hole => hole;
builder_1 = hole => () => builder_0([0,hole]); // hole => [0, hole];
builder_2 = hole => () => builder_1([1,hole]); // hole => [0, [1, hole]];
builder_3 = hole => () => builder_2([2,hole]); // hole => [0, [1, [2, hole]]];

Then we use a while loop to peel the layers without blowing the stack:

var result = builder(null);
while (typeof result === "function") {
  result = result();
}

Here is a complete example that builds a linked list with 100000 numbers:

let builder = x => x;
for (let i = 0; i < 100000; ++i) {
  let last_builder = builder;
  builder = x => (() => last_builder([i,x]));
};

var result = builder(null);
while (typeof result === "function") {
  result = result();
}

console.log(result);

It doesn't stack overflow.

user_10317910

You could take a recusion with three functions.

const
    identity = value => value,
    structure = (number, value) => [number, value],
    construct = (number, value) => number--
        ? construct(number, structure(number, value))
        : value;
    
console.log(JSON.stringify(construct(1000, null)));

user_14476750

I am not sure if this is suitable for your needs, but you could run your "lambda composition" calling a reducer on an array with the values you want to insert in your structure.

Reduce calls the provided function for each entry in the array, "accumulating" the return in a variable

const build = (last_o,new_v) => [new_v,last_o]
const values = [4,3,2,1,0]
const str = values.reduce(build,null)
console.log('Structure: ',str)
user_53519880
Related