Returning with an associated supended context makes it outlive its scope

[jnicklas]

Sorry for the utterly confusing title, it's the best I could come up with.

This isn't really a bug in Effection, but rather a consequence of some of the design patterns we've started to adopt. Since I ran into this a few times and it is potentially very confusing, I thought it best to actually document this somewhere so we can try to find a solution to it.

The problem occurrs if we're using the RAII-like pattern of creating some value object which has an implicitly created context associated for it, or an ensure block. For example, we might create an http server (value) with an associated ensure block which closes the server (context), like this:

function *createServer() {
  let server = new Server();
  yield suspend(ensure(() => server.close());
  return server;
}

In some other context we could then use the server like this:

function *main() {
  let server = createServer();
  yield fork(function*() {
    server.doSomething();
  });
}

The structured concurrency guarantees ensure that the server won't be closed before any fork in the main function has completed. So we have effectively bound the server to the scope if was created in, and ensured it will be de-allocated at the end of this scope.

Now let's imagine we want to create a special kind of server, and we want to re-use the createServer primitive:

function *createSpecialServer() {
  let server = yield createServer();
  doSomethingSpecial(server);
  return server;
}

Now we have a problem! The server returned from createServer is bound to the scope it was created in, which is the createSpecialServer scope, and the structured concurrency guarantees ensure that it won't close until that scope is complete.

BUT at the end of the scope we are RETURNING the server, and effectively passing it UP to the parent. But we just noted that the server will close at the end of the scope!

function *createSpecialServer() {
  let server = yield createServer();
  doSomethingSpecial(server);
  return server; // close will run here!!!
}

So what we return from createSpecialServer is a closed server!

Okay, so we realize that we need to hoist the server up one scope, maybe we can do this:

function *createSpecialServer() {
  let server = yield suspend(createServer());
  doSomethingSpecial(server);
  return server;
}

Unfortunately this doesn't work, since suspend will return a Context and not the server, so if we use suspend we can't actually get the value!

So fundamentally we have a problem in that this pattern simply does not compose, and when it doesn't compose it fails in a surprising, and (as should be evident by this lengthy explanation) pretty difficult to understand way.

As I said this isn't a bug in Effection per se, but it is something we need to think about as we're trying to find recommended practices in how to use Effection.

[cowboyd]

This is definitely a head scratcher, but this is a great explanation of the problem, and something we'll need to address we have to consider in future releases of Effection. I think there are two problems. The first is that every single operation runs in its own sandbox, and in retrospect, this feels draconian and the benefits of a simple implementation do not outweigh the costs of being difficult and confusing to work with. In order to work with Effection in an advanced way, you need to keep a mental model of the tree of contexts and the sandboxing of the current operation in your head at all times, both when you're writing code and when you're debugging it.

If, on the other hand, all operations ran inside the same context, then there would be no need for suspend at all.

function* createSpecialServer() {
  // Let's call this context A

  // creates a server bound to A
  let server = yield createServer();

  // doSomethingSpecial runs in A
  yield doSomethingSpecial(server);

  // returns server to a context A
  return server;
}

I think we can accomplish this if we model the evaluation of a context as having a current operation, and "queue" of remaining operations. After each operation, we pick off the next operation and run it in the same context until there are no more operations, at which point the context is completed. The key though, is that control functions for the individual operations running in the context can add, remove or replace the remaining operations to the context's queue.

The only thing that would create a new context would be a spawn operation that would not be called implicitly, but explicity and would generate a new child context connected to the parent so that it propagated failure, but not blocking the completion of the parent. A fork operation would then just be a spawn operation, that would also append a join operation to the end of the context's queue.

This idea comports well with the entire generator concept which, even though it made of javascript statements, is really just a list of operations. for example, let's say we have our classic server loop:

function* createServer(handleRequest: (req: Request) => Operation) {
  let server = http.createServer();
  yield setup(server);

  try {
    while (true) {
      let [request]: [Request] = yield once(server, 'request');
      yield handleRequest(request);
    }
  } finally {
    yield cleanup(server);
    server.close();
  }
}

Our context starts like

[run(createServer)]

when we start to evaluate it:

[setup, ...createServer]

once setup is complete:

[once(server, 'request'), ...createServer]

a request comes in:

[handleRequest(request),....createServer]

Now let's say that the handle request fails and an exception is thrown. We don't immediately kill the context, instead we insert a fail operation after createServer:

[cleanup, ....createServer, Fail]

If there are no operations left in createServer, then we proceed immediately to fail, but if there are things left in the finally block, then the iterable corresponding to createServer will not indicate that it is done.

Anyway, this response has gotten a bit longer than I anticipated, but it is all to say that what you're saying really is a problem, and that my re-thinking how evaluation happens, we can pave the way to solve it, as well as solve some of the other problems we've been having.

[cowboyd]

This brings up another question of composability (to which I don't have the answer) that you hinted at that I don't think goes away just by having a queue of operations running in a context, and that is how to feed inputs to the operations.

In other words, if we want to model a fork as a spawn + join, then how do we get the context created by spawn to the join? Maybe something like:

function fork(operation: Operation) {
  return (continuation: Continuation, context: Context) => {
    let child = context.spawn(operation);
    continuation
      .append(join(child))
      .resume(child);
  }
}

[jnicklas]

The tricky part about not creating a new context for operations is that it weakens the structured concurrency guarantees, I think. Right not we can guarantee that a context never "leaks" out of the function where it was created (suspend is an escape hatch to this behaviour). I think that composition will become way harder if we cannot guarantee this property.

It's interesting that there are so many analogies which are drawable to Rust in this context. The problem with the RAII pattern and suspend, I think, is that we're trying to model Rust's ownership model without real language support. Which is obviously challenging. I'm also sometimes reminded a bit about Rayon, which is maybe the coolest rust library there is, and definitely worth studying for some inspiration.

[cowboyd]

I see what you're saying, and I think that the key difference is that in order to run anything concurrently, you still must always create a child context. So the only way that an operation can "leak" something that continues to run after it is completed is to either spawn or fork, but by doing so those operations are bounded by the original context in which the operation was run.

function *main() {
  yield function* createEchoServer() {
    let server = http.createServer();
    
    yield spawn(function*() {
       while (true) {
         let [request, response]: [Request, Response] = yield once(server, 'request');
         response.write("Echo");
       }
    });

    yield spawn(function*() {
      while (true) {
        console.log('heartbeat');
        yield timeout(10000);
      }
    });

    yield;
  }
}

If I recall, where we ran into trouble with the original effection implementation was that invoking fork from within a sub-operation would cause the parent to block without it being clear as to why. While not a "leak", it was a silent block being added to the context that it .

But this was before we had the concept of spawn. If anything, it feels like fork should perhaps be used very sparingly and most of the cases where we use it now should be replaced by a spawn and an explicit synchronization mechanism. In fact, with the RAII resources we've been writing lately, we've been shying away from fork in favor of spawn and join Like here https://github.com/thefrontside/bigtest/blob/master/packages/todomvc/src/index.ts#L29-L37

My conjecture is that if we model it this way, then we can get away using spawn pretty much everywhere we were using suspend, monitor, and fork.

I'll have a look at Rayon.... I'm sure that we can find some inspiration, even if we can't use the concept of ownership as a first class language feature. It's funny, there's this cloud of overlapping solutions in a bunch of different languages that we need to map out to find the best one for our own situation.

I've been looking also at delimited continuations as a source of inspiration:

• https://dev.to/yelouafi/algebraic-effects-in-javascript-part-3---delimited-continuations-42hj
• https://www.microsoft.com/en-us/research/video/delimited-and-composable-continuations-in-plt-scheme/
• https://www.youtube.com/watch?v=QNM-njddhIw

GitHub

thefrontside/bigtest

Expanding the universe of what's possible to test. Contribute to thefrontside/bigtest development by creating an account on GitHub.

The DEV Community

Algebraic Effects in JavaScript part 3 - Delimited Continuations

Operational introduction to Algebraic Effects series

Microsoft Research

Delimited and Composable Continuations in PLT Scheme - Microsoft Research

Many programmers outside of the hard-core functional-programming world now see the value of “continuations” as a programming-language construct. In particular, first-class continuations can simplify the implementation of services that are accessed through a web browser. As it turns out, “delimited continuations” are an even better fit for such applications. Unfortunately, even languages that directly support …

YouTube

Delimited Continuations for Everyone by Kenichi Asai

Info: https://pwlconf.org/2017/kenichi-asai/ Slides: http://bit.ly/2yyHngu Transcription: http://bit.ly/2yb4vju Kenichi's Site: http://pllab.is.ocha.ac.jp/~a...

[jnicklas]

Context returns and resources have proven to be a solid solution to this problem. Closing.