Promise Resolution

This is related to this previous post, but it adds some value (for me at least), so I'll go ahead with this short post. Basically, in JavaScript a Promise will never resolve to another Promise, it will wait for the resolution of that second Promise and will resolve to its value. We come across this mainly when we have a Promise.then(handler) where that handler returns another Promise, e.g.:

let pr1 = new Promise(res => {
    setTimeout(() => {
        console.log(Date.now() + " resolving Promise");
        res("hello");
    }, 1000);
});

let pr2 = pr1.then(result => new Promise(res => {
    setTimeout(() => {
        console.log(Date.now() + " resolving Promise");
        res(result + " world");
    }, 3000);
}));

(async () => {
    let res = await pr2;
    //pr2 resolves when the promise returned by pr1.then handler resolves
    console.log(res);
})();

// 1590336489677 resolving Promise
// 1590336492702 resolving Promise
// hello world

The above is the behaviour explained in MDN:

the resolution/rejection of the promise returned by then will be subsequent to the resolution/rejection of the promise returned by the handler. Also, the resolved value of the promise returned by then will be the same as the resolved value of the promise returned by the handler.

But we have the same if we create a Promise with the Promise constructor and then the "action function" provided to the constructor returns also a Promise rather than returning a value:

let pr1 = new Promise(res => {
    console.log(Date.now() + " Promise 1 started");
    setTimeout(() => {
        let pr2 = new Promise(res2 => {
            console.log(Date.now() + " Promise 2 started");
            setTimeout(() => {
                console.log(Date.now() + " resolving Promise 2");
                res2("result");
            }, 3000);
        });
        console.log(Date.now() + " resolving Promise 1");
        res(pr2);
    }, 1000);
});

(async () => {
    let result = await pr1;
    console.log("result: " + result);
})();

// 1590337331838 Promise 1 started
// 1590337332874 Promise 2 started
// 1590337332875 resolving Promise 1
// 1590337335878 resolving Promise 2
// result: result

Additionally, while revisiting the MDN documentation for Promise.resolve() I've found 2 interesting points:

• If the parameter that we pass to Promise.resolve is already a Promise, that promise is returned, rather than creating an second promise that will be resolved once the first one is resolved.

  let pr1 = Promise.resolve(5);
  let pr2 = Promise.resolve(pr1);
  pr1 === pr2;
  //true
  

• The main use for Promise.resolve(value) is when we don't know if value is a normal value or a Promise:

  if (val instanceof Promise)
   val.then(result => console.log(result));
  else
   console.log(val);
   
  //rather than the above we can just do:
  Promise.resolve(val).then(result => console.log(result));
  
  

Notice than using await Promise.resolve() becomes unnecessary, as if we await for a non-promise the runtime will take care of wrapping the value in a Promise.

Prevent Overfilling the Stack, Part 2

In my previous post I showed a technique to prevent overfilling the stack in deep recursion cases. In my example there I was using this technique for a recursive function that has no additional action to perform after the recursive call returns (that is, the case that would be optimized by Tail Calls if JavaScript implemented them). In this post we'll see how to apply this technique for recursive functions that perform additional actions after the child recursive call.

Let's say we have this recursive function:

function transformString (source){
    if (source.length === 1)
        return source.toUpperCase() + source;
    
    let curItem = source[0];
    let transformed = transformString(source.substring(1));
    return curItem.toUpperCase() + transformed + curItem;
}

let st = "helloworld";

console.log(transformString(st));

//Output:
//HELLOWORLDdlrowolleh

As you can see, after invoking the recursive function we still run an action with the returned value and a value obtained before invoking the recursion (curItem). When applying the technique of the previous post we no longer have the current stack frame for running this action (as we are no longer stacking stack frames), so we have to provide this "post action" to the recursive function. So basically, the adapted recursive function receives an array with all the post actions. Notice that these "post action" functions trap as closure variables the values that normally would be in their stack frames.

//postActions: array of functions where we stack the code to run after recursion ends
//resFn: Promise resolve function
function transformStringWithTimeout (source, counter = 0, postActions, resFn){
    let curItem;
    let postAction = transformed =>  curItem.toUpperCase() + transformed + curItem;
    
    //initial call 
 if (resFn === undefined){
        var pr = new Promise((res, rej) => resFn = res);
        postActions = [];
 }

    //end recursion
    if (source.length === 1){
        let initValue = source.toUpperCase() + source;
        //using reduceRight to run the stack of actions
        let result = postActions.reduceRight((accum, fn) => fn(accum), initValue);
        resFn(result);
    }
 else{
        curItem = source[0];
        postActions.push(postAction);
  //use this so low "recursion break" value for the sake of testing
  if (counter < 5){
   transformStringWithTimeout(source.substring(1), ++counter, postActions, resFn);
  }
  else{
            //let's release the stack
            setTimeout(() => {
                console.log("timeout handling");
                transformStringWithTimeout(source.substring(1), 0, postActions, resFn);
            }, 0);
            
  }
 }
 return pr;
}

(async () => {
    console.log("-- with timeout");
    let result = await transformStringWithTimeout("helloworld");
    console.log(result);
})();

//Output:
//HELLOWORLDdlrowolleh
//-- with timeout
//timeout handling
//HELLOWORLDdlrowolleh

As you see, I've moved into a function postAction the piece of code that in the original function we were running after the recursive call. I push those postActions in an array postActions that I keep passing over in ensuing calls. When we reach the end of the recursion we run these post actions in reverse order. Notice than rather than using a for-of and pop for executing these actions I'm using reduceRight, just for the pleasure of it :-)
You can get the full code here

Prevent Overfilling the Stack

Recursion can be terribly useful, but there is a problem with it. A deep recursion involves having many function calls "alive" (waiting for the last one to complete and do the return path). Each of these calls is a new frame pushed on the stack, and programs limit the size a thread stack can reach, meaning that occasionally we can reach that limit before completing, crashing our program. When our recursive function has nothing pending to do once the child call returns (the recursive call is the last thing done in our function) an optimization can be done, reusing the same stack for all calls, I'm talking about Tail Call Optimizations. Indeed, as you can read here there are 2 related options: Tail Call Optimizations (TCO) and Proper Tail Calls (PTC). Current JavaScript engines do not implement any of them, so if we run into a deep recursion we are fucked, our code will throw a Maximum call stack size exceeded exception (at least in node.js).

To avoid this we need a way to release our current stack frame before doing the recursive call, so that its stack frame replaces the current frame rather than being pushed on top. We have an obvious way to invoke a function after the current function ends, delay its invokation with setTimeout. So let's see an example of how to transform a recursive function to use setTimeout and avoid overfilling the stack.

We can calculate the factorial of a number in 2 ways, the most common one being:

function factorial(n) {
 return (n !== 0) ? n * factorial(n - 1) : 1;
}

In the above, we leave an operation to be done after the recursive call is done. We can transform it so that nothing is left for doing after ther recursive call.

function tailFactorial(n, total = 1) {
    //console.trace();
    if (n === 0) {
        return total;
    }    // proper tail call
    return tailFactorial(n - 1, n * total);
}

If the JavaScript runtime implemented PTC, using the second factorial function the stack would not crash regardless of the number of calls, but we can see that this is not the case and when using a big enough number of recursions (largeValue) we crash the stack in both cases:

const smallValue = 100;
const largeValue = 50000;

function runFactorial(factorialFn){
 let res = factorialFn(smallValue);
 console.log("factorial: " + res);

 //stack overflow:
 try {
  res = factorialFn(largeValue);
  console.log("factorial: " + res);
 }
 catch (ex){
  console.log("Exception: " + ex.message);
  //Maximum call stack size exceeded
 }
}

[factorial, tailFactorial].forEach(fn => runFactorial(fn));

/* Output:
factorial: 9.33262154439441e+157
Exception: Maximum call stack size exceeded
factorial: 9.332621544394418e+157
Exception: Maximum call stack size exceeded
*/

As I mentioned before, we can fix this by delaying the function call with setTimeout (so that the current stack frame gets freed). I'm returning a Promise that will get resolved once the last recursion is done:

function factorialWithTimeoutAndPromise(n, total = 1, resFn){
 //initial call 
 if (resFn === undefined){
  var pr = new Promise((res, rej) => resFn = res);
 }
 if (n === 0){
  resFn(total);
 }
 else{
  setTimeout(() => factorialWithTimeoutAndPromise(n-1, n * total, resFn), 0);
 }
 return pr;
}

The above works fine, but even using a timeout of 0, the operation takes quite time (almost 1 minute on my laptop). From what I've read this setTimeout(0) can cause up to 4ms delay:
someone told me that setTimeout(0) creates, on average, a 4 ms delay. They claimed that’s the time it takes to pop the callback off the stack, onto the callback queue and back on the stack again.

So we better find a balance between normal recursion (to keep things fast), and setTimeout (to avoid overfilling the stack). In this version below I do normal recursive calls up to 50, then schedule the next call and clean the stack, and so on.

function factorialWithTimeoutAndPromiseImproved(n, total = 1, counter = 0, resFn){
 //initial call 
 if (resFn === undefined){
  var pr = new Promise((res, rej) => resFn = res);
 }
 if (n === 0){
  resFn(total);
 }
 else{
  if (counter < 50){
   factorialWithTimeoutAndPromiseImproved(n-1, n * total, ++counter, resFn);
  }
  else{
   setTimeout(() => factorialWithTimeoutAndPromiseImproved(n-1, n * total, 0, resFn), 0);
  }
 }
 return pr;
}

(async() => {
 console.log("-- using Timeout");

 let options = [
  { 
   name: "Not optimized",
   value: smallValue,
   fn: factorialWithTimeoutAndPromise
  },
  { 
   name: "Not optimized",
   value: largeValue,
   fn: factorialWithTimeoutAndPromise
  },
  { 
   name: "Optimized",
   value: smallValue,
   fn: factorialWithTimeoutAndPromiseImproved
  },
  { 
   name: "Optimized",
   value: largeValue,
   fn: factorialWithTimeoutAndPromiseImproved
  }
 ];
 
 for (let option of options) {
  console.log(option.name + " factorial for: " + option.value);
  let start = Date.now();
  let result = await option.fn(option.value);
  console.log("result: " + result);
  console.log("it took " + (Date.now() - start) + "\n");
 }

})();

/* Output:
Not optimized factorial for: 100
result: 9.332621544394418e+157
it took 132

Not optimized factorial for: 50000
result: Infinity
it took 57441

Optimized factorial for: 100
result: 9.332621544394418e+157
it took 2

Optimized factorial for: 50000
result: Infinity
it took 1187

*/

I've uploaded all the code into a gist

Question Mark in Programming

If you code in C# or TypeScript you should be aware that different kinds of "?" are showing up more and more often in code bases. As most of these developments are pretty recent I'll try to catch up with them here:

Ternary Operator. For sure this is nothing new, but what I think is becoming more common is to see it used in its nested form. I had always considered these nested cases very confusing, but if you write them in the right way, as explained here they can be pretty expressive and easy to follow.

 (conditionA)
    ? valueA
    : (conditionB)
    ? valueB
    : valueC

Null Coalescing operator "??" This has existed in C# since its first version, but has just been added to TypeScript (and should be featured by JavaScript in the future).

 string city = birthPlace ?? "Paris";

In C#: The null-coalescing operator ?? returns the value of its left-hand operand if it isn't null; otherwise, it evaluates the right-hand operand and returns its result.
In TypeScript it's just the same, only that it applies both to null and undefined (the "nullish" values). Notice that in TypeScript it comes as a replacement for the idiomatic use of "||" to provide default values (with the difference that || applies also to the falsy values: 0, "" and NaN, read more)

Null-coalescing assignment is much related to the above. It has been added to C# 8, but is missing from TypeScript so far.

 city ??= "Paris";
 //is equivalent to this:
 city = city ?? "Paris";

Safe Navigation operator I first saw this operator in Groovy (called Safe Dereferencing there) many years ago and I loved it so much that I wrote about how to try to emulate it at that time in C# and in JavaScript.
C# 6 added this little marvel to our toolbox, and TypeScript has recently added (it should make it into JavaScript in a near future).

 //both in C# and TypeScript 
 var street = person?.Address?.Street;

 //safe array access in C#
 var cityName = cities?[0]?.Name;

 //safe array access in TypeScript
 var cityName = cities?.[0]?.Name;

 //safe Dictionary access in C#
 var cityName = countriesDictionary?["France"];

 //safe property access via indexer in TypeScript
 var cityName = city?.["name"];

 
 //safe delegate invokation in C#
 myFn?.Invoke("a");

 //safe function invokation in TypeScript
 myFn?.("a");

As you can see there are some syntax differences when using it with arrays and with delegates/functions. For C# delegates we have to use ?.Invoke() rather than just ?(). For TypeScript we have to use that odd fn?.(), that likewise we also have to use for array indexes or accessing object properties via indexes (ar?.[0] or obj?.["key"])