Skip to content
TobiasWrigstad edited this page Dec 24, 2014 · 8 revisions

A page for discussing the semantics, implementation and syntax of futures in Encore.

A Design Draft for Future Chaining

Overview

When actor A blocks on a future, there might be a need to work out the identity of the actor B that is responsible for eventually unblocking A. If A and B turns out to be the same, then we might want to do some more synchronous work.

Working out the identity requires back-tracking chains of futures and looking at who is computing them.

Full Story

First, we want to make three extensions to futures:

  • The producer identity, i.e., the identity of the agent computing its value.
  • A handle to the previous future in a chain.
  • A handle to the fulfilling message, i.e., the message that will result in computing the future value.

There is some overlap between these three, especially the last two. Room for improvement.

When get is called on a future F whose value is not ready, we compare the consumer identity (the actor doing the get) with the producer identity. If these are different (probably the common case), the semantics of get is:

  1. Save the necessary state to suspend the current execution
  2. Register a desire to be "woken up" in F, by its producer, once the future value is ready
  3. Suspend, and "go to sleep"

However, if the producer and consumer identities are the same:

  1. Traverse the chain of previous unfulfilled futures.
  2. If we find an unfulfilled future UF whose producer identity is different than the current consumer identity, then goto (A) below.
  3. If in the process of searching for UF, we find a fulfilled future FF (regardless of producer identity), compute all the closures traversed and install the resulting values in the correct futures with FF's value as the starting point. (Turned out the future could be fulfilled.)
  4. If we hit the end of the chain without finding either UF or FF, then goto (B) below.

Case (A)

Let A be the current consumer identity. We have found a future F with a producer identity B.

  1. Save the necessary state to suspend the current execution
  2. In addition to 1. save the necessary information to traverse the entire chain in forward direction to compute the future values, with G as the starting point. On a resume, this step will be executed before resuming the suspended execution in 1.
  3. Register a desire to be "woken up" in F, by B, once F's value is ready
  4. Suspend, and "go to sleep"

Case (B)

We have found a circular dependency.

This future will always be one fulfilled by a method call, not a chain. (Since a chain always requires a pre-existing future.) To make progress, make the current actor process the fulfilling message M synchronously and remove M from its queue. With the resulting value, we can traverse the chain in the forward direction fulfilling all futures. In this case, no suspension is needed.

Some Observations

The closures chained on a future may block on futures themselves. (Notably, they may capture the very future they are chained on.)

Just because we have identified the "root value" in a chain of closures, it does not mean that we should compute them all. A more scalable solution might perhaps compute each closure separately.

A lot of these problems seem to go away if we make futures actors allowing them to perform the chained computations, or simply have the actor fulfilling the future perform all its chained work. However, this breaks the single thread of control.

Extra stuff to be put in futures not without cost.

Thoughts on Self-Fulfilled Future

Self-fulfilled future: a future resulting from an asynchronous self-send. Problem: how does one detect self-sending? What is the semantics of leaking a self-fulfilled future to another actor, etc.

Blocking on a self-fulfilled future may cause deadlocks.

Hence, blocking on a self-fulfilled future must be treated differently.

Scenario 1:

Actor A calls method M on itself asynchronously which returns a self-fulfilled future F. Getting on F could be implemented by running M in the current thread producing the future F value.

Scenario 2:

Actor A calls method M on actor B which returns a future F. A subsequently chains closure C on F which returns a self-fulfilled (*) future G. Getting on G cannot be implemented by the same strategy as Scenario 1 as the future F value on which the future G value depends may not yet have been produced.

(*) G is self-fulfilled because C will eventually be executed by A because C can capture mutable state in A.