17

An interesting discussion about the distinction between callbacks and continuations over on SO has prompted this question. By definition, a continuation is an abstract representation of the logic needed to complete a computation. In most languages this manifests as a one argument procedure to which you pass whatever value needs continued processing.

In a purely functional language (where all functions are pure and first class citizens), I would think a continuation could be entirely modeled as a function. This is, after all, how I've previously understood continuations up to this point. However, the world is full of state (sigh..) and so the general definition does not require that a continuation capture program state -- it need only encompass intent.

To help my understanding, can an example be provided in a functional language where the continuation is expressed in a more abstract way than a function? I know Scheme allows you to grab the current continuation in a first-class manner (call/cc), but even so, it seems that the one argument procedure passed to call/cc is simply given the current continuation in the form of another one argument procedure to which the call/cc'd function can apply its result.

3
  • Perhaps the intersection of continations and defunctionalization as: continuations can be converted to data structures via defunctionalization; might be an interesting area to look at.
    – Dan D.
    Sep 20, 2013 at 8:38
  • @DanD. do you have any suggestions for interesting literature I can read? That topic sounds useful. Sep 20, 2013 at 8:43
  • For instance: Recycling Continuations (Sobel, Friedman)
    – Dan D.
    Sep 20, 2013 at 22:03

4 Answers 4

12

tl;dr; The type is the overarching abstraction over a continuation


A continuation is the type of its inputs and outputs

The closest thing you will find to a non-procedure based continuation is likely the continuation monad in Haskell as it is expressed as a type, for which many functions may be used to interact with the type to interrupt, resume, backtrack, et al.

You can encapsulate that closure in a type such as the Cont type in Haskell where you get the monad abstraction as a "higher level abstraction", and there are other forms of abstraction over continuations you get when you look at the continuation as a type instead of simply a procedure, for instance

  • You can take two continuations and do an alternative between them if the type follows the laws to be a monoid
  • You can abstract over the type to change the input or output types of the continuation if you encapsulate the closure in a type that abides the laws of a functor
  • You can arbitrarily and partially apply or decorate your continuation with functionality such as input validation or input conversion if you encapsulate the closure in a type that follows the laws of an applicative functor

Closure vs. Procedure

At the end of the day you're basically right; a continuation is a "procedure", though I would rather refer to it as a closure. Often times continuations are best expressed as first class closures that have enclosed a bound environment. In a pure functional language you might say this is not particularly reasonable because you lack references; this is true but you can enclose values and single assignment makes enclosing the value vs. the reference the exact same thing. This gives rise to in Haskell:

(\x -> \y -> insideYIcanAccess x (and y))

A language that lacks the ability to enclose a binding environment may technically lack first class closures, but even then there is some environment (generally the global) which is available to the closure.

So I would say it's more accurate to describe a continuation as: A closure being used in a particular way.


Conclusion

To the question of "Is a continuation implementable in any way other than a procedure?" No. If you don't have first class functions you really can't have continuations as such (yes function pointers count as first class functions, so alternatively arbitrary memory access can suffice).

Now to the question of "Are there any ways to express a continuation in a more abstract way than a procedure?" Expressing it as a type gives you a much greater abstraction, allowing you to treat the continuation in very general ways such that you can interact with the continuation in many more ways than just executing it.

2
  • 1
    This generalizes to "A continuation can simply be anything that let's you get the result of the rest of the program". Since this normally mandates having some code (the rest of the program) most languages use functions. Theoretically you can construct a continuation out of anything. During continuation conversion in my compilers, I've used partially filled trees. Sep 21, 2013 at 1:51
  • 1
    @jozefg partially filled trees are a proper representation of a computation as an expression, but at the end of the day the actual code being written is an expression of sorts that cannot be identifiably different from a procedure, such as I understand it. That aside, partially filled trees are the compiler representation; the developers representation is expectantly a computation expression normative with the syntax and semantics of the language, which would appear to 99% of developers as a "procedure", "function" or otherwise. You're thinking from the compiler developer's perspective heh Sep 23, 2013 at 15:16
2

One example you might like are coroutines. For example, the Coroutines from Lua or the iterators/generators from Python or C# are similar in power to one-shot continuations (continuations that you are only allowed to call once) but the continuation is not explicitly made into a function. Instead, you have have ways to advance the coroutine to until the next "yield" statement.

For example, consider the following Python program:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

Its kind of similar to the following Javascript program with explicit callbacks:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

The Javascript example is kind of noisy because each step needs to return the next continuation in addition to returning the yielded value (in the Python keeps track of the continuation inside the ite

0

In Swift, most bits of code can be turned into a closure, which can be used where in other languages you would use something called a continuation. You can also just call closures as you like. And every function is automatically a special case of a closure.

(A common use in Swift is initialising static variables with something more complex than an expression: Defining a closure expression and calling it immediately is an expression, so this can be used to initialise a variable. Another common use is the same moderately complex bit of code being used multiple times. In order not to repeat yourself, put the code into a closure then call the closure as needed).

0

Imagine you are in the middle of a computation and you get to a point where you say "I need to stop, and go do something else for a while (like wait for a aysnc event to complete), but at that later point, I want to come back to this state and complete my computation"

What you want do is capture the call stack and the binding stack at the current point, put that into an Object [let's call that object a "continuation"]. Then you can call some other procedure (for example: the browser main event loop), saying: "please do other computations, at some point, get back to me (by re-establishing the binding and control stack)"

In Scheme, you do this with call-with-current-continuation [call/cc], the "continuation" is the information needed to restart the computation.

Sadly, most language/computational processors do not allow you to "freeze" the computational state of your Thread.

But imagine how much easier async Javascript would be IF you were not required to "return" from a function!

That is: instead of returning a Promise of a later value, you could just freeze the computation, let the language processor handle other activities/events, and then later, when the async value is available, regain control (on the original Thread) and return that value directly from your function to the original caller, in the original context.

I would want a function of the form: ReleaseToEventProcessor(Promise) which tells the main loop to capture the current continuation, do other things (including presumably, things that will resolve the given Promise) and re-start my continuation when the promise is resolved.

That is the utility of a language with call/cc

Note that in Java/JVM, 'continuations' are somewhat moot because Java has explicit Thread objects and a documented Thread scheduler. Thread.sleep() or BlockingQueue.read() or Future.wait() all do as above: the Thread state is suspended, other things happen, and later control returns to the 'continuation'; your code never had to do a 'return' or specify a 'callback'.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.