Asynchronicity in F#

Deadvlei clay pan, Namibia

Asynchronous and event-based programming is an increasingly popular style of programming that have the potential of considerably improving the responsiveness for many applications. This is especially the case if the application is mostly using its time waiting for other tasks to finish, such as when reading and writing files, or accessing other web services.

“If you do nothing, you can scale infinitely.” — Hanselman’s rule of scale

Web servers such as Nginx, Express/Node.js have made asynchronous event-driven architectures very popular. The more recent arrival of ASP.NET Core and Kestrel continues this trend.

Several programming languages now supports asynchronous programming through the async and await syntactic pattern. This includes languages such as C#, F#, Python, JavaScript, Dart and Kotlin.

The title should probably have been “Asynchronous Programming with Examples in F#”, but for some reason I liked the shorter title. Thus, the goal of this article is not to describe how Async is actually implemented in F#, but to take a step back and discuss synchronous vs asynchronous programming, from simple callbacks, though continuations (CPS), promises, and and all the way to the modern programming construct of async and the let! await.

Synchronous Programming

But before we start discussing asynchronous programming it’s probably a good idea to take a short review of synchronous programming. This might seem obvious but synchronous programming is programming with synchronous values and synchronous functions.

A synchronous value is a normal value binding. The value is always there and it’s always the same value. At least in F# it’s always the same value. Here is a synchronous value:

A synchronous function is a function produces its result as the return value of the function. We say the function blocks while waiting for the result:

This all sound nice. So what is the problem with synchronous programming? Calling synchronous functions is usually very fast, but they can also be very slow. Functions may block for a long time just waiting for stuff to happen:

Sometimes they may even block forever:

Functions that blocks for a long time is a problem. They consume system resources, and may significantly reduce the overall responsiveness of an application or a service.

In order to achieve concurrency when programming with synchronous functions, we often resort to multi-threaded programming.

Multi-threading — Here be dragons

Multi-threading, it all sounded like a good idea. In order to do more than one thing at the same time when using synchronous programming, we have to use multiple threads. Programming with multiple threads is called multi-threaded programming.

The problem is that multi-threaded programs can be very hard to write correctly, and programs that are hard to write correctly are extremely hard to debug.

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it? — — Brian W. Kernighan

Threads also consume system resources, so a multi-threaded server may have a hard time serving hundreds of thousands of concurrent requests and connections, even if the server spends most of its time just waiting for other resources such as disk I/O or an authentication service.

Last but not least, multi-threaded programs are almost impossible to unit-test since timing between threads becomes nondeterministic and may yield different results for different runs of the test.

To solve the problems that arise with blocking functions, synchronous programming and multi-threaded programming we some times need to resort to non-blocking functions and asynchronous programming.

Asynchronous Programming

In the same way as synchronous programming is programming with synchronous values and functions, asynchronous programming is programming with asynchronous values and functions.

An asynchronous value is an abstraction that represents a future value. The value is not necessarily there, but may be there in the future. You can think of an asynchronous value as a box, that might have a value.

You can also think about the difference between synchronous and asynchronous values as being pull-values and push-values.

  • Pull value: A value you control by pulling on the value.
  • Push value: Is out of your control and the value may be “thrown” at you from the environment around you.

An asynchronous function returns before the result is ready. We say that the function is non-blocking.

The return value of this function is Async<int>. To run this code we need to use Async.Start or use Async.RunSynchronously if we want to use the result value in a non-async function.

The F# async block syntax may be unfamiliar if you come from another programming language, so we will use the rest of this article to try and explain what is going on. But first let us first take a few steps back discuss the difference between asynchronous, concurrent and parallel programming.

Asynchronous programming vs concurrent programming vs parallel programming

  • Parallel programming is about doing multiple things at the same time. In order to do multiple things at the same time, a computer needs to be able to process multiple streams on instructions simultaneously. Most computers these days have multi-core processors that enables parallel processing of instructions.
  • Concurrent programming is about using abstractions within a program that may enable things to happen in parallel. If things actually happen in parallel depends on the run-time operating system and underlying hardware. You can think of concurrent programming as virtual parallel programming.
  • Asynchronous programming is simply doing something else while you are waiting for some another task to finish.

We briefly looked at the strange async computation syntax of F#. What is really going on there, and what would it look like if we tried to implement it ourselves?

Callbacks and Higher Order Functions

One way to get the result back from a function, is to provide a callback handler that the function will call with the result when it’s ready. A callback handler is simply a function or a method that we pass to another function, and we expect that the function calls the callback handler at some later time.

A function that takes another function as an argument, or returns a function as a result, is called a higher-order function.

Continuation Passing Style (CPS)

Related to programming with callbacks is programming with a style called Continuation Passing Style (CPS). This is a functional programming style where you instead of returning the result from your functions, pass a continuation function that will be applied to the result. You can think of the continuation as being a callback handler, but it’s really a call-next handler for invoking the rest of the computation.

Consider this synchronous function pythagoras:

Let us rewrite this into CPS style:

So you had a problem and wanted to solve it with continuations, but soon you realize that you have another problem.

Now you have two problems!

The code you write is almost unreadable. You might be able to write code that looks like this, but most of us will have problems reading it two weeks later. How can we do better?

Part of the solution is to rewrite the original synchronous pythagoras function by binding a name to each intermediate result:

This actually don’t look that different from the CPS version if we un-indent it. Can you see how the name binding with let, becomes the same as the parameter name of the continuation function?

This starts to look like something, but the code is badly indented and in a syntax that is very unfamiliar. It looks like we might have pushed the programming language to its limits, or can we perhaps do even better?

The basic problem with CPS is that we give the continuation as an extra argument instead of returning the result.

We’re not really used to sending in a function that gets the result. We want to return the result. A trick we can do, is that instead of returning nothing, we can return a function that takes the continuation as a parameter. Note that we actually get this for free with currying in F# but for now lets return the function explicitly ourselves like this:

This almost looks like normal imperative programming again, except that the thenDo is not really our result. It’s a function that takes a function that takes the result. Working with functions that returns a function that takes a function that takes a result can be confusing, so to make life easier we should try to move the abstraction a bit higher. Let’s turn our thenDo into an object representation instead.

The Promise

A Promise or a Future is an abstraction and an object that represent a future value. The idea with the promise is that we return an object representation of the future value. You may already be familiar similar constructs such as Task<T> in C#, Future in Python, Promise in JavaScript, and Async<’a> in F#.

“You can make a Promise and it’s up to you to keep it. When someone else makes you a promise you must wait to see if they honour it in the Future”

This is a great idea since we’re not really that used to programming with callbacks and CPS, and it brings us closer to “normal” programming where you return the result from functions instead of passing a callback. Here is one possible implementation for a Promise class:

We can now create promises using Promise, resolve them using Resolve, and handle the result by calling the Then method with our result handler. Note that in F# we must handle return values, so if we are not interested in the return value we must explicitly ignore it.

We can also signal errors using Reject, and handle errors by calling Catch with our error handler. This is handy if e.g a web request should fail since throwing exceptions upwards does not make any sense when the callbacks goes down.

Lets make a sleep function that returns a promise that will resolve after the given number of milliseconds msecs.

We can now use this sleep function to simulate an asynchronous web request that we call fetch.

Let’s simulate a fetch from http://test.

This all looks nice, but a problem arises when we want to do a series of requests where a request depends on the result of the previous request. We then have to resort to a technique called “inside chaining” which doesn’t sound that bad in itself, but unfortunately it’s also infamously known as the pyramid of doom.

The pyramid of doom

It looks like we’re back in a similary situation as with CPS. What if we could chain our Then calls on the outside instead of the inside, then we could avoid the nesting problem. To make this work we need to return a new Promise from the Then call instead of unit, so we can continue chaining on this new Promise instead of the original one:

As you can see we return a new Promise called newPromise. This promise will be resolved with the value of the Promise tmpPromise that is returned from the fn callback.

With our new Then method overload in place, we can now write our series of fetch calls using “outside chaining” instead of “inside chaining”:

This looks much better, and it’s also better than with CPS since the indenting now looks OK. It’s still not 100% optimal since the Then chaining looks like some sort of a custom new programming language we have invented inside of the F# programming language.

But unlike many other programming languages F# still has another trick up its sleeve, and it’s called computational expressions.

Enter Computational Expressions

Computational expressions offer a uniform syntax and abstraction model for encoding context-sensitive computations. This article will not go into any depth trying to explain this construct other than to show how we can use it to create a new Promise based domain specific language (DSL) that we will call promise.

With the query builder in place we can now rewrite our series of fetch operations in out our new promise based language:

Isn’t this amazing!? The promise computational expression lets us in fact write asynchronous statements the same way as synchronous statements. The only difference is that use need to use let! (let bang) to unwrap the promise value. By looking at the query builder implementation we know the let! statement is really just a hidden Then call returning a new Promise, and the name of the binding is really just the name of the parameter passed to the callback.

If you have followed us this far then you have finally discovered what the mysterious async block in the start of the article was all about. Basically, async in F# is exactly the same thing as the promise we just created. Other programming languages implements similar logic behind their async and await statements, although the actual implementation might differ.

This article could have ended here, but there’s still more to the story. There is a hidden problem in our implementation of the Promise. The problem is that the calling of the Then callback might be a bit too aggressive. This is because we’re calling the callback handler immediately, even if we are not finished doing what we were currently doing.

The Zen of Python actually sums it up nicely:

Now is better than never. Although never is often better than right now.

If we make a factorial implementation using Promises we can bring the problem out in the light.

If we try to run this example we will see the problem:

Process is terminating due to StackOverflowException.

This is not good. A way to solve this is to use a scheduler to delay the computation of the inner Then’s.

Event-loops and Schedulers

Event-based programming is programming where the control of the program is not driven by the program itself, but by events triggered by the environment. The environment is everything external to the program itself.

Fundamental to event-based programming is the concept of an event-loop. An event-loop uses cooperative scheduling to process one event at a time. This is very similar to a scheduler. We can create a scheduler that uses continuations to schedule work that needs to be done later.

With the scheduler in place we can go back and modify our Promise implementation.

A Scheduled Promise

Lets modify our Promise implementation to schedule the callback handlers using a scheduler. This way we can make sure we finish any Then-block before we start processing the next one.

Using the new implementation we can re-run the factorial example and this time it produces the correct result even for very high input numbers.

It’s also worth metioning that using a scheduler makes things very flexible since we can now decide if the continuation should be done immediately, later on the same thread, on a new thread, in a new process, or a different server etc.

Summary

Asynchronous programming is really just the programming equivalent of:

I’ll call you back!

This means that the the calling program is free to do other stuff while waiting to be called back. Async and await is basically the combination of everything we have talked about in this article:

  • Callbacks
  • Continuations and CPS
  • Promises.
  • Event-loops and Schedulers.

We have seen that we need to use functional programming techniques to compose callbacks and continuations, and there’s a lot we can learn from functional programming to improve upon imperative programming. Async and await is really just syntactic sugar for continuations and CPS.

Async and await is really just syntactic sugar

Using async and await makes the code cleaner and easier to debug. How do you set a breakpoint in a Promise Then-chain anyways?

References and Further Reading