Editing Continuation (section)

==First-class continuations==
<!-- linked from redirect [[First-class continuations]] -->

First-class continuations are a language's ability to completely control the execution order of instructions. They can be used to jump to a function that produced the call to the current function, or to a function that has previously exited. One can think of a first-class continuation as saving the ''execution'' state of the program. True first-class continuations do not save program data – unlike a [[process image]] – only the execution context. This is illustrated by the "continuation sandwich" description:

<blockquote>
''Say you're in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there's a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :-)''<ref name="cont-sandwich">{{cite web|url=https://groups.google.com/group/perl.perl6.language/msg/b0cfa757f0ce1cfd|title=undo()? ("continuation sandwich" example)|last=Palmer|first=Luke|date=June 29, 2004|work=perl.perl6.language (newsgroup)|access-date=2009-10-04}}</ref>
</blockquote>

In this description, the sandwich is part of the program ''data'' (e.g., an object on the heap), and rather than calling a "make sandwich" routine and then returning, the person called a "make sandwich with current continuation" routine, which creates the sandwich and then continues where execution left off.

[[Scheme (programming language)|Scheme]] was the first full production system providing first "catch"<ref name="history_of_continuations"/> and then [[call-with-current-continuation|call/cc]]. Bruce Duba introduced call/cc into [[Standard ML|SML]].

Continuations are also used in models of computation including [[denotational semantics]], the [[actor model]], [[process calculi]], and [[lambda calculus]]. These models rely on programmers or semantics engineers to write mathematical functions in the so-called [[continuation-passing style]]. This means that each function consumes a function that represents the rest of the computation relative to this function call. To return a value, the function calls this "continuation function" with a return value; to abort the computation it returns a value.

Functional programmers who write their programs in [[continuation-passing style]] gain the expressive power to manipulate the flow of control in arbitrary ways. The cost is that they must maintain the invariants of control and continuations by hand, which can be a highly complex undertaking (but see 'continuation-passing style' below).

===Uses===
Continuations simplify and clarify the implementation of several common [[software design pattern|design pattern]]s,  including [[coroutine]]s/[[green thread]]s and [[exception handling]], by providing the basic, low-level primitive which unifies these seemingly unconnected patterns.  Continuations can provide elegant solutions to some difficult high-level problems, like programming a web server that supports multiple pages, accessed by the use of the forward and back buttons and by following links.  The [[Smalltalk]] [[Seaside (software)|Seaside]] web framework uses continuations to great effect, allowing one to program the web server in procedural style, by switching continuations when switching pages.

More complex constructs for which ''"continuations provide an elegant description"''<ref name="history_of_continuations"/> also exist. For example, in [[C (programming language)|C]], [[longjmp]] can be used to jump from the middle of one [[Function (computer science)|function]] to another, provided the second function lies deeper in the stack (if it is waiting for the first function to return, possibly among others). Other more complex examples include [[coroutine]]s in [[Simula|Simula 67]], [[Lua (programming language)|Lua]], and [[Perl]]; tasklets in [[Stackless Python]]; [[Generator (computer science)|generators]] in [[Icon (programming language)#Generators|Icon]] and [[Python (programming language)|Python]]; continuations in [[Scala (programming language)|Scala]] (starting in 2.8); [[Fiber (computer science)|fibers]] in [[Ruby (programming language)|Ruby]] (starting in 1.9.1); the [[backtracking]] mechanism in [[Prolog]]; [[Monad (functional programming)|monads]] in [[functional programming]]; and [[Thread (computer science)|threads]].

===Examples===

The [[Scheme (programming language)|Scheme]] programming language includes the control operator [[call-with-current-continuation]] (abbreviated as: call/cc) with which a Scheme program can manipulate the flow of control:

<syntaxhighlight lang="scheme">
 (define the-continuation #f)

 (define (test)
   (let ((i 0))
     ; call/cc calls its first function argument, passing
     ; a continuation variable representing this point in
     ; the program as the argument to that function.
     ;
     ; In this case, the function argument assigns that
     ; continuation to the variable the-continuation.
     ;
     (call/cc (lambda (k) (set! the-continuation k)))
     ;
     ; The next time the-continuation is called, we start here.
     (set! i (+ i 1))
     i))
</syntaxhighlight>

Using the above, the following code block defines a function <code>test</code> that sets <code>the-continuation</code> to the future execution state of itself:

<syntaxhighlight lang="scheme">
 > (test)
 1
 > (the-continuation)
 2
 > (the-continuation)
 3
 > ; stores the current continuation (which will print 4 next) away
 > (define another-continuation the-continuation)
 > (test) ; resets the-continuation
 1
 > (the-continuation)
 2
 > (another-continuation) ; uses the previously stored continuation
 4
</syntaxhighlight>

For a gentler introduction to this mechanism, see [[call-with-current-continuation]].

====Coroutines====

This example shows a possible usage of continuations to implement [[coroutines]] as separate threads.<ref>Haynes, C. T., Friedman, D. P., and Wand, M. 1984. Continuations and coroutines. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Texas, United States, August 06–08, 1984). LFP '84. ACM, New York, NY, 293-298.</ref>

<syntaxhighlight lang="scheme">
 ;;; A naive queue for thread scheduling.
 ;;; It holds a list of continuations "waiting to run".

   (define *queue* '())

   (define (empty-queue?)
     (null? *queue*))

   (define (enqueue x)
     (set! *queue* (append *queue* (list x))))

   (define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))

   ;;; This starts a new thread running (proc).

   (define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))

   ;;; This yields the processor to another thread, if there is one.

   (define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))

   ;;; This terminates the current thread, or the entire program
   ;;; if there are no other threads left.

   (define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))
</syntaxhighlight>

The functions defined above allow for defining and executing threads through [[Computer multitasking#Cooperative multitasking|cooperative multitasking]], i.e. threads that yield control to the next one in a queue:

<syntaxhighlight lang="scheme">
   ;;; The body of some typical Scheme thread that does stuff:

   (define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (format #t "~A ~A\n" str n)
         (yield)
         (loop (+ n 1)))))

   ;;; Create two threads, and start them running.
   (fork (do-stuff-n-print "This is AAA"))
   (fork (do-stuff-n-print "Hello from BBB"))
   (thread-exit)
</syntaxhighlight>

The previous code will produce this output:
  This is AAA 0
  Hello from BBB 0
  This is AAA 1
  Hello from BBB 1
  This is AAA 2
  Hello from BBB 2
  ...

===Implementation===

A program must allocate space in memory for the variables its functions use. Most programming languages use a [[call stack]] for storing the variables needed because it allows for fast and simple allocating and automatic deallocation of memory. Other programming languages use a [[Dynamic memory allocation|heap]] for this, which allows for flexibility at a higher cost for allocating and deallocating memory. Both of these implementations have benefits and drawbacks in the context of continuations.<ref>{{cite web | url = http://community.schemewiki.org/?call-with-current-continuation-for-C-programmers | title = Call with current continuation for C programmers | work = Community-Scheme-Wiki | date = 12 October 2008}}</ref>

===Programming language support===
Many programming languages exhibit first-class continuations under various names; specifically:
*[[Common Lisp]]: [http://common-lisp.net/project/cl-cont/ cl-cont]. One can also use custom macros
*[[C Sharp (programming language)|C#]] / [[VB.NET]]: <code>async</code> and <code>await</code>: "sign up the rest of method as the continuation, and then return to your caller immediately; the task will invoke the continuation when it completes". [http://msdn.microsoft.com/en-us/vstudio/gg316360 Asynchronous Programming for C#]
*[[Factor (programming language)|Factor]]: <code>callcc0</code> and <code>callcc1</code>
*[[Haskell (programming language)|Haskell]]: The Continuation [[Monad (functional programming)|monad]] in <code>[http://hackage.haskell.org/packages/archive/mtl/2.0.1.0/doc/html/Control-Monad-Cont.html Control.Monad.Cont]</code>
*[[Haxe]]: [https://github.com/Atry/haxe-continuation haxe-continuation]
*[[Icon (programming language)|Icon]], [[Unicon (programming language)|Unicon]] : <code>create, suspend, @</code> operator: coexpressions
*[[Java (programming language)|Java]]: [http://lightwolf.sourceforge.net/index.html Lightwolf] [http://commons.apache.org/sandbox/commons-javaflow/ javaflow] (requires bytecode manipulation at runtime or compile time)
*[[Kotlin (programming language)|Kotlin]] : <code>Continuation</code>
*[[Rhino (JavaScript engine)|JavaScript Rhino]] : <code>Continuation</code>
*[[Parrot virtual machine|Parrot]]: <code>Continuation</code> PMC; uses [[continuation-passing style]] for all control flow
*[[Perl]]: [https://metacpan.org/module/Coro Coro] and [https://metacpan.org/module/Continuity Continuity]
*[[Pico (programming language)|Pico]]: <code>call(exp())</code> and <code>continue(aContinuation, anyValue)</code>
*[[Python (programming language)|Python]]: [[PyPy]]'s <code>[https://web.archive.org/web/20231217182002/https://doc.pypy.org/en/latest/stackless.html#continulets _continuation.continulets]</code>
*[[Racket (programming language)|Racket]]: <code>[[call-with-current-continuation]]</code> (commonly shortened to <code>call/cc</code>)
*[[Ruby (programming language)|Ruby]]: <code>callcc</code>
*[[Scala (programming language)|Scala]]: <code>scala.util.continuations</code> provides <code>shift</code>/<code>reset</code>
*[[Scheme (programming language)|Scheme]]: <code>[[call-with-current-continuation]]</code> (commonly shortened to <code>call/cc</code>)
*[[Smalltalk]]: <code>Continuation currentDo:</code>; in most modern Smalltalk environments continuations can be implemented without additional VM support.
*[[Standard ML of New Jersey]]: <code>SMLofNJ.Cont.callcc</code>
*[[Unlambda]]: <code>c</code>, the flow control operation for call with current continuation
<!--
Please do not re-add the following entries:
*Python: generators are not first-class continuations
*Stackless Python: provides tasklets/coroutines only;  first-class continuations were a target for the first implementation, but dropped
-->

In any language which supports [[closure (computer science)|closures]] and [[tail recursion|proper tail calls]], it is possible to write programs in [[continuation-passing style]] and manually implement call/cc.  (In continuation-passing style, call/cc becomes a simple function that can be written with [[lambda calculus|lambda]].)  This is a particularly common strategy in [[Haskell (programming language)|Haskell]], where it is easy to construct a "continuation-passing [[Monad (functional programming)|monad]]" (for example, the <code>Cont</code> monad and <code>ContT</code> monad transformer in the <code>mtl</code> library). The support for [[tail recursion|proper tail calls]] is needed because in continuation-passing style no function ever returns; ''all'' calls are tail calls.