Before there is any confusion, I’m not talking about JavaScript promises that are used for asynchronous computations. In this case, a promise is just a delayed computation. For example, a simple form of a promise is a function that takes in no arguments and returns a result. In this blog post, we will be focusing on promises that remember their results and promises that may evaluate to other promises. Promises are useful for control flow and implementing lazy semantics in a strict language.

In this blog post, we will learn what promises are and how to implement them efficiently. Promises are useful and interesting, but honestly, I mainly wrote this just to talk about the algorithm for forcing composable promises because I think it’s very cool!

1  What is a Promise?

A promise is a delayed computation. The computation executes at most once and remembers its result. Here are some examples of using promises:

Notice that the "in the delay" is only printed after the promise is forced, not when the promise is created with delay. And the print does not run when we force the promise again. This tells us that the promise remembers its result and does not re-evaluate its body upon subsequent forces. In general, the body of a promise runs at most once. These simple promises can be implemented by storing the return value of a zero-argument function.

If the promise has already been forced, we return the stored result. Otherwise, we call the thunk, store the result, and return it.

One practical use of promises is for lazy streams.

2  Composable Promises

What if you have a promise in a promise?

If you are using promises in a complicated way, you may end up producing promises inside of other promises like this. For example, let’s say you’re implementing an interpreter for a language with lazy semantics. If you use promises, you will likely end up producing deeply nested promises. lazy allows us to work with these nested promises:

With lazy, forcing the outer promise forces all the intermediate promises and they all remember the inner result.

3  How Does it Work?

Let’s use the following chain of promises as a running example:

Here is a diagram of the situation:

Here is a diagram of what we want after forcing p1:

In these diagrams, -?> represents an unforced promise and -> represents a forced promise.

How can we implement this? Naively, you’d write a function that just forces promises until you get a result. Something like this:

Here is what the chain would look like after we used force-deep on p1:

If we apply this function to p1, we will get back "hello". However, if we force p1 again, we will get p2, not "hello". If we use force-deep again, we will get "hello" and it will be faster than the first time since the result is remembered and the sleep would not run again. However, each promise stores its child, not the inner result. This means that when we use force-deep on p1 again, even though all the promises were already forced, we would still have to traverse the whole "chain" again just to access the inner result stored in the innermost promise. We want each promise to remember the inner result, not its child promise.

Here is another attempt, ignoring regular promises for the moment:

As before, if the promise has already been forced, we return the stored result. Otherwise, we start by calling the thunk to get an initial result. If that is yet another composable promise, we force that one too. Then we store and return that promise’s result. If the thunk returned a regular value, we store and return it. The recursive case will go all the way down the chain, forcing every inner promise and storing the inner value, not the inner promise itself.

This is better. If we have a chain of promises and we force it, each promise will remember its result. Here is the diagram after forcing:

That’s exactly what we want! Forcing p1 once more will immediately return the stored result and wouldn’t have to traverse the chain again. But there is still one problem: that (force initial-result) does not occur in tail position. This means that the forcing algorithm will use stack space that grows linearly with respect to the chain length.

How can we implement this with tail recursion?

Consider this diagram:

Let’s say we shallowly force a.

We realize that a results in another promise, so we shallowly force that too.

Next, we swap a and b.

Then, we repeat from a.

shallowly force it.

It was already forced, so nothing changed. Next, we realize that the result is another promise, namely c. So we shallowly force that too.

Next, swap a and c.

Then, we repeat from a and continue until a points to a non-promise or its child points to a non-promise. In either of those two cases, we store the non-promise.

Here is what we’d get if we ran this algorithm on p1:

In general, the pattern will be

Intermediate promises will store the outer-most promise, the outer-most promise will store the final value, and the inner-most promise will store the final value. Each promise is at most 2 levels of indirection away from the final value. If we forced p2 from this example after forcing p1, it would end up pointing directly to the final value.

This is not quite what we wanted. We wanted all promises to store the final value directly. Realistically, however, a single layer of indirection for inner promises doesn’t matter. Especially when it would end up being collapsed if an intermediate promise was forced afterwards. Asymptotically, we still get linear time with respect to chain length on the first force and constant time on any subsequent force on a promise in the chain. That’s the same as our naive algorithm. However, our naive algorithm used linear space, whereas this algorithm uses constant space. This is a tradeoff.

Either way, I think this algorithm is pretty cool! In a single, linear-time, constant-space pass, we collapse the indirection. Here is the code:

We can examine the stored results of the promises directly to see that it does, in fact, produce the graph we predicted.

This implementation is missing a lot of things. There are no regular promises, there is no error handling, there is no support for values, and many more subtle things the real promise library handles. Regardless, this provides insights into the inner workings of the library and an interesting algorithm for collapsing indirection.