CODEWITHSUNDEEP
javascriptfunctional-programmingstack-overflow
MaiaVictor
MaiaVictor

Reputation: 52987

JavaScript stack overflows even when no recursive function is present

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?

Upvotes: 2

Views: 806

Answers (4)

MaiaVictor
MaiaVictor

Reputation: 52987

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.

Upvotes: 2

malarres
malarres

Reputation: 2946

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)

Upvotes: 2

Pietro Pepe
Pietro Pepe

Reputation: 389

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)

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386654

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)));

Upvotes: 1

Related Questions