Recent posts

Asynchronous programming with promises in JavaScript


Posted by Diego Assencio on 2017.10.22 under Programming (JavaScript)

Asynchronous programming in JavaScript is unfortunately not trivial. One way of dealing with asynchronous work is by simply using plain callbacks when certain events are triggered (e.g. a file is loaded from a server), but this is error-prone since it is difficult to make sure that all errors and exceptions are properly handled, especially through multiple callback functions.

A Promise in JavaScript is a great tool for writing asynchronous code, but understanding how to use it is requires some effort. Sadly, a great deal of the literature written on the topic makes it seem much more complicated than it actually is, which is why I decided to write this post.

Let's first start with a statement of the problem we are trying to solve: we wish to do some work, but this work can take long (e.g. fetch a file from a server) and we cannot simply wait until it is done before continuing the execution of the program, otherwise the user experience may suffer considerably (e.g. the webpage the user is visiting would stop responding to events such as key pressing until the file is completely loaded). On top of that, when this work is done, we may wish to do additional work (e.g. fetch another file) based on the results obtained.

So how can promises help us solve this problem? The high-level answer is simple: a promise is an object which wraps a unit of work to be executed and acts as a handle to the outcome of this work. As soon as the outcome becomes available (e.g. our file has been loaded), it is handled by an appropriate user-defined callback function which is attached to the promise. We say that a promise is "resolved" (or "fulfilled") when the work it wraps finishes successfully and we say it is "rejected" when something goes wrong; to handle these situations separately, we can attach two callback functions to a promise: one to handle success and one to handle failure.

Before jumping into a code example using promises, consider the following naive attempt to execute an asynchronous file request:

/* WARNING: this will NOT work as expected! */

function getFile(fileUrl)
{
    /* prepare an asynchronous request for fileUrl */
    var request = new XMLHttpRequest();
    request.open("GET", fileUrl, true);

    /* specify what to do when the loading operation finishes */
    request.addEventListener("load", function() {
        if (request.status < 400)
        {
            /* successful execution: return the file contents */
            return request.responseText;
        }
        else
        {
            /* failed execution: throw an exception */
            throw new Error(request.statusText);
        }
    });

    /* send the request */
    request.send();
}

/* request a file; handle success and failure separately */
try
{
    var contents = getFile("files/John.json");
    console.log("file contents:\n" + contents);
}
catch (error)
{
    console.log("could not get file: " + error);
}

Our intention in the program above is to asynchronously download a JSON file and handle success (file downloaded) by printing its contents and failure (file not downloaded) by throwing an exception. If you do not understand all technical aspects of the program, read it this way: XMLHttpRequest is an API which we use to prepare an asynchronous file request. The request variable acts as a handle to the result of this file request. By registering a callback function to handle the request's "load" event, we can define what needs to be done when the loading operation finishes: if the HTTP status code returned is smaller than 400, the file was successfully downloaded and its contents are then returned by the callback function, otherwise an exception is thrown to indicate that the file request failed. Unfortunately, even when the file request succeeds, the output of this program shows that we made a serious mistake in our thinking:

file contents:
undefined

What happened here? The answer is simple: getFile does not return anything. The return statement appearing on its body belongs to the callback function which handles the load event from request; the returned value will never be seen by getFile itself. As a matter of fact, from the way the code is written, any value returned by the callback function will actually be lost — no one will receive it. In the program above, the try block invokes getFile, and since getFile does not return anything, its return value is assumed to be undefined, and that is exactly what the program prints as the "file contents".

Asynchronous programming is not that easy in JavaScript, but making the program above work correctly requires only a few changes if we use a Promise object. Our first corrected version will be kept similar to the original (incorrect) program, but we will improve it afterwards:

var fileUrl = "files/John.json";

function getFile(succeed, fail)
{
    /* prepare an asynchronous request for fileUrl */
    var request = new XMLHttpRequest();
    request.open("GET", fileUrl, true);

    /* specify what to do when the loading operation finishes */
    request.addEventListener("load", function() {
        if (request.status < 400)
        {
            /* success: resolve promise with file contents */
            succeed(request.responseText);
        }
        else
        {
            /* failure: reject promise with an error */
            fail(new Error(request.statusText));
        }
    });

    /* send the request */
    request.send();
}

function processSuccess(contents)
{
    console.log("file contents:\n" + contents);
}

function processFailure(error)
{
    console.log("could not get file: " + error);
}

/* request file asynchronously */
var requestHandle = new Promise(getFile);

/* define how to handle success and failure */
requestHandle.then(processSuccess, processFailure);

The main difference now is on how getFile is called and how it signals success or failure (see the highlighted lines): a promise (requestHandle) is created to wrap the file request; its constructor takes a function (getFile) which defines the work to be done (let's call it the "task function" from now on). The constructor of a promise immediately invokes its given task function with two arguments which are themselves functions which the task function must use to indicate success or failure respectively. These functions are not provided by the user, but by the promise constructor itself. On the definition of getFile, the parameters succeed and fail represent these functions: the former is used to return a value while the latter is used to return an error. If the file download succeeds, getFile calls succeed with the file contents as argument, otherwise fail is called with an error as argument indicating what went wrong. In both cases, the result is stored on requestHandle, i.e., requestHandle acts as a handle to the outcome of getFile.

Notice that the signaling of success or failure is asynchronous: it does not happen while getFile is executing, but only when the file request is finished — an event which can occur much later in time.

After getFile calls either succeed or fail, what happens to the result it sends? The answer is on the last line of the program: requestHandle calls its then method to register callback functions which handle success and failure respectively. As soon as requestHandle receives a result from getFile, it will call the appropriate callback function with that result as argument. In the program above, these callback functions are processSuccess (the "success handler") and processFailure (the "failure handler") respectively. If you attempt to run this program on your browser console, you should get the following output:

file contents:
{
    "name": "John",
    "age": 35,
    "mother": "Mary"
}

One unfortunate aspect of the way this program is written is the fact that we cannot invoke getFile with fileUrl as its single argument; instead, we converted fileUrl into a global variable so it can be used by getFile. This is ugly but can be easily fixed by changing getFile to make it create and return the promise which wraps the file request. Additionally, let's use the opportunity to improve the names of the success and failure handlers:

function getFile(fileUrl)
{
    /* auxiliary function to be invoked by the promise constructor */
    function getFileTask(succeed, fail)
    {
        /* prepare an asynchronous request for fileUrl */
        var request = new XMLHttpRequest();
        request.open("GET", fileUrl, true);

        /* specify what to do when the loading operation finishes */
        request.addEventListener("load", function() {
            if (request.status < 400)
            {
                /* success: resolve promise with file contents */
                succeed(request.responseText);
            }
            else
            {
                /* failure: reject promise with an error */
                fail(new Error(request.statusText));
            }
        });

        /* send the request */
        request.send();
    }

    return new Promise(getFileTask);
}

function displayFile(contents)
{
    console.log("file contents:\n" + contents);
}

function printError(error)
{
    console.log("could not get file: " + error);
}

/* request a file; handle success and failure separately */
getFile("files/John.json").then(displayFile, printError);

The last line of this program deserves appreciation: it clearly communicates that we wish to fetch the file files/John.json and then display its contents if the file request succeeds or print an error message if it fails.

Despite the fact that all this sounds very interesting, the programs above can be written without using promises in ways which some will find easier to understand. However, if you need to chain actions together, using promises will make your life a lot easier. Indeed, when the then method is called for a promise (let's call it the "original promise" from now on), it produces a new Promise object which can register its own success and failure handlers (let's call it the "then-promise" from now on). The then-promise will succeed or fail depending on the outcome of the result-handler callback which is invoked by the original promise, regardless of whether this is a success or failure handler. Specifically, the following will happen:

1.If the result-handler callback invoked by the original promise returns a non-promise value, the then-promise will be resolved with that value, i.e., its success handler will be called with that value as argument.
2.If the result-handler callback invoked by the original promise throws an exception, the then-promise will be rejected with that exception, i.e., its failure handler will be invoked with that exception as argument.
3.If the result-handler handler callback invoked by the original promise returns a promise, the success and failure handlers of the then-promise will be used as success and failure handlers for the returned promise respectively.

All of this may sound complicated, but I hope that seeing each of these cases in action will make things clearer for the reader.

Example #1: original promise handler returns a non-promise value

function getFile(fileUrl)
{
    /* same as before... */
}

function getAge(jsonData)
{
    return JSON.parse(jsonData).age;
}

function addTen(number)
{
    return number + 10;
}

function printResult(result)
{
    console.log("John's age plus 10 is: " + result);
}

function printError(error)
{
    console.log("something went wrong: " + error);
}

getFile("files/John.json").then(getAge)
                          .then(addTen)
                          .then(printResult, printError);

In this example, we omitted the callbacks for handling failures on the first two promises (notice the absence of a second parameter on the first two calls to then). This is allowed and equivalent to setting these failure handlers to null, in which case a rejection of the promise simply passes on the error to the then-promise to be handled by its own failure handler. In this program, any error will be passed on until it is received by printError, which will then print it. From the structure of the program, we can see that provided the file request succeeds, the result of the success handler of each promise is passed on to the success handler of its associated then-promise, forming a chain which results in the following output:

John's age plus 10 is: 45

Example #2: original promise handler throws an exception

The example below is the same as example #1, with a single difference: we modify getAge to have it simply throw an exception instead of return an age value:

function getFile(fileUrl)
{
    /* same as before... */
}

function getAge(jsonData)
{
    throw new Error("getAge does not want to share this data!");
}

function addTen(number)
{
    return number + 10;
}

function printResult(result)
{
    console.log("John's age plus 10 is: " + result);
}

function printError(error)
{
    console.log("something went wrong: " + error);
}

getFile("files/John.json").then(getAge)
                          .then(addTen)
                          .then(printResult, printError);

When getAge is called, it throws an exception, causing the first then-promise in the chain to be rejected with that exception as result. Since it only registered a success handler (addTen), it simply passes on the exception to the second then-promise, which then invokes its own failure handler (printError) with the exception as argument. The output of this program is then:

something went wrong: Error: getAge does not want to share this data!

Example #3: original promise handler returns a promise

The third and final example will illustrate the case in which a success handler returns a promise. If that happens, the then-promise will become a proxy to it, meaning the then-promise will be resolved or rejected with the same value or error as the promise returned by the original success handler.

In this example, we will attempt to fetch a file, and if that operation succeeds, we will request another file and return a promise which is a handle to the outcome of this second file request:

function getFile(fileUrl)
{
    /* same as before... */
}

function getMotherFile(jsonData)
{
    var motherName = JSON.parse(jsonData).mother;

    /* return a promise */
    return getFile("files/" + motherName + ".json");
}

function printAge(jsonData)
{
    console.log("age of John's mother: " + JSON.parse(jsonData).age);
}

function printError(error)
{
    console.log("something went wrong: " + error);
}

getFile("files/John.json").then(getMotherFile)
                          .then(printAge, printError);

The output of this program shows that the success handler for the first then-promise (printAge) is used as the success handler for the promise returned by getMotherFile itself:

age of John's mother: 62

Summary

This post explained how a Promise object wraps a unit of (possibly asynchronous) work and acts as a handle to its outcome, processing success or failure using dedicated callback functions which are registered through the promise's then method. The real advantage of using promises instead of manually handling asynchronous tasks comes from the fact that the then method also returns a promise, making work chains easier to create and understand.

Comments (0) Direct link

Run-time limits of comparison-based sorting algorithms


Posted by Diego Assencio on 2017.10.01 under Computer Science (Algorithms)

Let $T(n)$ be the run-time of some comparison-based sorting algorithm for a sequence of length $n$. By "comparison-based", we mean a sorting algorithm which accesses input array elements only via comparisons as is the case for general-purpose sorting algorithms such as merge sort, quicksort, and heapsort. Such an algorithm does not know in advance which values the input array can store (as is for instance the case with bucket sort), but simply orders them using a predefined "less than" comparison function. In this post, we will show that regardless of how well designed an algorithm of this type is, its worst-case running time cannot be faster than $c n\log_2(n)$ as $n$ becomes large (for some constant $c \gt 0$). In more technical words, there exist constants $n_0 \geq 0$ and $c \gt 0$ such that $T(n) \geq cn\log_2(n)$ for $n \geq n_0$, and therefore $T(n) = \Omega(n\log_2(n))$.

This post will only deal with deterministic algorithms, but the results extend to randomized algorithms as well. The main idea of the proof is to consider only input arrays which are permutations of $S_n = \{1, 2, \ldots, n\}$. The total number of distinct arrays which represent permutations of $S_n$ is $n!$.

For a given deterministic, comparison-based sorting algorithm, let $k$ be the largest number of comparisons within which it can sort any of the $n!$ arrays mentioned above. Because the execution of the algorithm is based on the results of the value comparisons it performs, there are at most $2^k$ possible distinct execution paths for it. To clarify, the algorithm sorts an input array by repeatedly comparing pairs of values and deciding on how to proceed depending on which value is greater according to the comparison function. Each comparison generates two possible branches of execution, and since we know the total number of comparisons performed cannot exceed $k$, there can be at most $2^k$ distinct execution paths for the arrays we are considering.

Suppose now that $2^k \lt n!$. If that is the case, then the number of possible execution paths of the algorithm is smaller than the total number of input arrays we are considering. Therefore, there must be at least two distinct input arrays for which the algorithm executes following the exact same path (this is referred to as the pigeonhole principle in Mathematics). This implies that when the algorithm is applied to these arrays, the same transformations (e.g. elements swaps) are applied to each of them, with the final result being the same: the values of $S_n$ ordered according to the predefined comparison function. This is not possible since the algorithm is deterministic: by inverting its steps from the final (sorted) result, we cannot arrive at two distinct initial inputs. Therefore $2^k \geq n!$.

The final step in the proof needs a simple fact about $n!$: $$ \displaystyle n! = n(n-1)(n-2)\ldots\frac{n}{2}\left(\frac{n}{2} - 1\right) \ldots1 \geq \left(\frac{n}{2}\right)^{\frac{n}{2}} $$ Hence, since $2^k \geq n!$: $$ \log_2(2^k) \geq \log_2(n!) \Longrightarrow k \geq \frac{n}{2}\log\left(\frac{n}{2}\right) \Longrightarrow k = \Omega(n\log_2(n)) $$ Therefore, the best lower bound for the worst-case running time of the sorting algorithm is $T(n) = \Omega(n\log_2(n))$.

Comments (0) Direct link

The DFT of an image: phase vs. magnitude


Posted by Diego Assencio on 2017.09.01 under Computer Science (Digital Signal Processing)

Let $X$ be an $M \times N$ matrix (a two-dimensional array) of complex numbers $x_{mn}$ for $m = 0, 1, \ldots, M - 1$ and $n = 0, 1, \ldots, N - 1$. The discrete Fourier transform of $X$ is another $M \times N$ matrix $\tilde{X}$ of complex numbers $\tilde{x}_{pq}$ such that: $$ \tilde{x}_{pq} = \sum_{m = 0}^{M - 1} \sum_{n = 0}^{N - 1} x_{mn} e^{-i2\pi pm/M} e^{-i2\pi qn/N} \label{post_81059bc883bd6156c2e83f83e2e38c2b_dft_2d} $$ for $p = 0, 1, \ldots, M - 1$ and $q = 0, 1, \ldots, N - 1$. The original matrix $X$ can be recovered from $\tilde{X}$ through its inverse discrete Fourier transform: $$ x_{mn} = \displaystyle\frac{1}{MN} \sum_{p = 0}^{M - 1} \sum_{q = 0}^{N - 1} \tilde{x}_{pq} e^{i2\pi pm/M} e^{i2\pi qn/N} $$ Since a grayscale image can be represented as a matrix whose elements are 8-bit integers representing pixel values ranging from $0$ (black) to $255$ (white), we can compute its DFT using equation \eqref{post_81059bc883bd6156c2e83f83e2e38c2b_dft_2d}. Interestingly, the magnitude of the DFT of such an image does not contain much information, but its phase does. To clarify what this means, let us define two $M \times N$ matrices $\tilde{X}_{\textrm{mag}}$ and $\tilde{X}_{\textrm{phase}}$ whose elements are given by: $$ \begin{eqnarray} (\tilde{X}_{\textrm{mag}})_{pq} &=& \left|\tilde{x}_{pq}\right| \label{post_81059bc883bd6156c2e83f83e2e38c2b_M}\\[5pt] (\tilde{X}_{\textrm{phase}})_{pq} &=& \tilde{x}_{pq} / \left|\tilde{x}_{pq}\right| \label{post_81059bc883bd6156c2e83f83e2e38c2b_P} \end{eqnarray} $$ Being a complex number, $\tilde{x}_{pq} = \rho_{pq} e^{i\phi_{pq}}$, where $\rho_{pq}$ is its magnitude and $\phi_{pq}$ is its phase. From equations \eqref{post_81059bc883bd6156c2e83f83e2e38c2b_M} and \eqref{post_81059bc883bd6156c2e83f83e2e38c2b_P}, we have that $(\tilde{X}_{\textrm{mag}})_{pq} = \rho_{pq}$ and $(\tilde{X}_{\textrm{phase}})_{pq} = e^{i\phi_{pq}}$, so the matrices $\tilde{X}_{\textrm{mag}}$ and $\tilde{X}_{\textrm{phase}}$ contain only magnitude and phase information of the elements of $\tilde{X}$ respectively.

If we compute the inverse DFTs of $\tilde{X}_{\textrm{mag}}$ and $\tilde{X}_{\textrm{phase}}$, what type of "images" will we recover? Our original image had only real values, but these inverse DFTs will in general not, so we will consider only their real components. Additionally, the pixel values of the resulting images will not necessarily fall within the closed interval $[0, 255]$, but we can clip the negative values (set them to zero) and rescale the nonnegative values to have them fall within this interval. An example of what the resulting images look like is shown on figure 1 (all figures in this post were generated using the script available here).

Fig. 1: An original image (left) and the images produced by computing the inverse DFTs of the magnitude (center) and phase (right) components of the original image's DFT.

From figure 1, we can see that the inverse DFT of the magnitude matrix $\tilde{X}_{\textrm{mag}}$ produces a nearly black image, but the inverse DFT of the phase matrix $\tilde{X}_{\textrm{phase}}$ shows well-defined contours from the original image (if you cannot see them, try increasing the brightness of your screen or click on the figure to see a larger version of it). This indicates that the phase component of the image's DFT carries more information than the magnitude component. To better see this, we can apply histogram equalization to the images produced from the inverse DFTs. The results, shown in figure 2, serve as further confirmation of our hypothesis.

Fig. 2: An original image (left) and the images produced (after histogram equalization) by computing the inverse DFTs of the magnitude (center) and phase (right) components of the original image's DFT.

Comments (1) Direct link