Continuation

In the computer programming languages

Explicit use

In some computer programming languages, the continuations can be handled explicitly as objects of the language with whole share: one can store the current continuation in a Variable that one can thus handle as such; then further, one can restore the continuation, which causes to divert the execution of the current program towards the future that one had recorded.

In C, the instruction setjmp makes it possible to capture a continuation (in fact, to store the value of the Instruction counter in a variable), and the instruction longjmp makes it possible to divert the program towards a recorded continuation.

In functional Programming, a continuation takes the form of a function which can take various arguments (which influence the value of return of the instruction which had " saisi" the current continuation) and which does not have a value of return (in fact does not finish from the point of view of the appealing one, because the program is diverted).

Example in Design: (define fonction1 (lambda (K) (begin (display " Toto") (K " Titi") (display " Tata") ))) (display (cal-with-current-continuation fonction1))

has as an exit with the screen:

Louse Titi

Let us note that the instruction “(display " Tata")” was ignored.

Explanation:

we start by defining a function “fonction1”, then we ask to post the result (“display”) of “(cal-with-current-continuation fonction1)”.
the instruction “cal-with-current-continuation” causes to capture the current continuation (which is to post the value of return thanks to the order “display”, then to finish the program) and to send it in argument to the function “fonction1”
but this function is a sequence of three instructions, of which second is to call the continuation “K” passed in argument, therefore to leave the function since the continuation will have been captured outside.
after that, the continuation is carried out normally: “display” is carried out with the value of return of “(cal-with-current-continuation fonction1)”, which had been provided in argument of “K”, i.e. " Titi" ; then the program finishes.

Implicit use: exceptions

However the most current use of the concept of continuation is done in an implicit way, when one handles the exceptions.

Indeed, the block of exception is only a syntactic structure to say that before carrying out, one recorded the current continuation (without the block) preceded by the execution of the routine of treatment of exception, and that when an exception is met during execution of the block, then the corresponding continuation will be called.

Example in OCaml: try 50/0 with Division_by_zero - > 42; ;

turn over

-: int = 42

Explanation: before carrying out this stupid division, OCaml records the continuation consisting in turning over 42 then to finish the execution in the exception “Division_by_zero”. Then OCaml tries to precisely launch the division which results in the call from this exception, to which one had just associated a continuation.

Programming by continuation

In functional Programming, the programming by continuation indicates a technique of programming consisting in using only simple calls of function which take for argument their own continuation, instead of calling functions sequentially, or to carry out a function on the result of the preceding one. These functions are found to some extent main of their destiny, and are not satisfied any more to undergo the context.

One of the stakes of the programming by continuation is to obtain a program recursive terminal, which after compilation and optimization does not require any more to pile up the overlapping successive calls. This results in a less consumption of memory.

Example: calculation of the factorial, in OCaml

“Traditional” version:

let rec fact = function | 0 - > 1 | N - > n* (fact (N - 1)); ;

Version by continuation (which is strictly speaking recursive final, but could be simplified well to consume less memory, by storing the accumulation of the result rather than a continuation, which it is increasingly large, with the result that one gained nothing on the practical level):

let rec fact K = function | 0 - > (K 1) | N - > fact (fun X - > K (N * X)) (N - 1); ;

(If one wants just to calculate the factorial of 5 and to post it, the syntax of call would be then:)

fact print_int 5; ;

In dénotationnelle semantics

There exists a dénotationnelle Sémantique known as by passage of continuation . In this semantic, the mathematical direction of a program is a function which takes a continuation (that which follows its execution) and returns a continuation (that which precedes its execution).

Thus, if P is a program, then its semantics P is of type Continuation - > Continuation , where the type Continuation is the type State - > Observation .

And if E is expression (program which has a value in the language), E is of type E_Continuation - > Continuation , where the type E_Continuation (or continuation of expression) is the type Valeur - > Continuation .

The continuations make it possible to give computational contents to the traditional Logique within the framework of the correspondence of Curry-Howard.

Random links: