Continuation (informatique)

En informatique, la continuation d'un système est son futur, c'est-à-dire la suite des instructions qu'il lui reste à exécuter à un moment précis. C'est un point de vue pour décrire l'état de la machine.

Dans les langages de programmation

Utilisation explicite

Dans certains langages de programmation, les continuations peuvent être manipulées explicitement en tant qu'objets du langage à part entière : on peut stocker la continuation courante dans une variable que l'on peut donc manipuler en tant que telle ; puis plus loin, on peut restaurer la continuation, ce qui a pour effet de dérouter l'exécution du programme actuel vers le futur que l'on avait enregistré.

En C, l'instruction setjmp permet de capturer une continuation (en fait, stocker la valeur du compteur ordinal dans une variable), et l'instruction longjmp permet de dérouter le programme vers une continuation enregistrée.

En programmation fonctionnelle, une continuation prend la forme d'une fonction qui peut prendre divers arguments (qui influent sur la valeur de retour de l'instruction qui avait « saisi » la continuation courante) et qui n'a pas de valeur de retour (en fait ne finit pas du point de vue de l'appelant, car le programme est dérouté).

Exemple en Scheme :

(define (f k)
  (display "toto\n")
  (k "titi\n")
  (display "tata\n"))
(display (call-with-current-continuation f))

a pour sortie à l'écran :

toto
titi

L'instruction (display "tata\n") a été ignorée.

Explication :

• nous commençons par définir une fonction f, puis nous demandons d'afficher le résultat (display) de (call-with-current-continuation f) ;
• l'instruction (call-with-current-continuation f) a pour effet de capturer la continuation courante (qui est d'afficher la valeur de retour grâce à la commande display, puis de terminer le programme) et de la passer en argument à la fonction f ;
• la fonction f est une séquence de trois instructions, dont la deuxième appelle la continuation k passée en argument avec la valeur "titi" donc sort de la fonction puisque la continuation a été capturée à l'extérieur ;
• après cela, la continuation s'exécute normalement : display s'exécute avec la valeur de retour "titi" de (call-with-current-continuation f) et le programme termine.

Utilisation implicite : les exceptions

Cependant l'utilisation la plus courante de la notion de continuation se fait de manière implicite, lorsque l'on manipule les exceptions.

En effet, le bloc d'exception n'est qu'une structure syntaxique pour dire qu'avant d'exécuter, on a enregistré la continuation courante (sans le bloc) précédée de l'exécution de la routine de traitement d'exception, et que lorsqu'une exception sera rencontrée pendant exécution du bloc, alors on appellera la continuation correspondante.

Exemple en OCaml :

try 
  50/0 
with 
  Division_by_zero -> 42;;

retourne

- : int = 42

Explication : avant d'exécuter la division, OCaml enregistre la continuation consistant à retourner 42 puis à finir l'exécution dans l'exception « Division_by_zero ». Puis OCaml essaye de lancer la division qui résulte en l'appel de cette exception, à laquelle justement on venait d'associer une continuation.

Programmation par continuation

En programmation fonctionnelle, la programmation par continuation désigne une technique de programmation consistant à n'utiliser que de simples appels de fonction qui prennent pour argument leur propre continuation, au lieu d'appeler séquentiellement des fonctions, ou d'exécuter une fonction sur le résultat de la précédente. Ces fonctions se retrouvent en quelque sorte maîtresses de leur destin, et ne se contentent plus de subir le contexte.

Un des enjeux de la programmation par continuation est d'obtenir un programme récursif terminal, qui après compilation et optimisation ne requiert plus d'empiler les appels successifs imbriqués. Ceci se traduit par une moindre consommation de mémoire.

Exemple : calcul de la factorielle, en OCaml

Version « classique » :

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

Version par continuation :

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

Si on veut simplement calculer la factorielle de 5 et l'afficher, la syntaxe d'appel serait alors

print_int (fact 5);;

dans le premier cas et

fact print_int 5;;

dans le second.

En sémantique dénotationnelle

Il existe une sémantique dénotationnelle dite par passage de continuation. Dans cette sémantique, le sens mathématique d'un programme est une fonction qui prend une continuation (celle qui suit son exécution) et rend une continuation (celle qui correspond à son exécution).

Ainsi, si P est un programme, alors sa sémantique [[P]] est de type Continuation → Continuation, où le type Continuation est le type État → Observation.

Et si E est une expression (programme qui a une valeur dans le langage), [[E]] est de type E_Continuation → Continuation, où le type E_Continuation (ou continuation d'expression) est le type Valeur → Continuation.

Les continuations permettent de donner un contenu calculatoire à la logique classique dans le cadre de la correspondance de Curry-Howard.

Bibliographie

• Peter J. Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. août 1965. Reparu dans Higher-Order and Symbolic Computation (en), 11(2):125-143, 1998, avec une préface de Hayo Thielecke.
• Drew McDermott et Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259. mai 1972.
• Daniel G. Bobrow (en): A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
• Carl Hewitt (en), Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
• Christopher Strachey et Christopher P. Wadsworth. Continuations: a Mathematical semantics for handling full jumps Technical Monograph PRG-11. Oxford University Computing Laboratory. janvier 1974. Reparu dans Higher Order and Symbolic Computation, 13(1/2):135—152, 2000, avec une préface de Christopher P. Wadsworth.
• John C. Reynolds. Definitional Interpreters for Higher-Order Programming Languages Proceedings of 25th ACM National Conference, pp. 717–740, 1972. Reparu dans Higher-Order and Symbolic Computation 11(4):363-397, 1998, avec une préface.
• John C. Reynolds. On the Relation between Direct and Continuation Semantics Proceedings of Second Colloquium on Automata, Languages, and Programming. LNCS Vol. 14, pp. 141–156, 1974.
• John C. Reynolds, « The discoveries of continuations », Lisp and Symbolic Computation, vol. 6, n^os 3/4,‎ 1993, p. 233–248 (lire en ligne)
• Gerald Sussman et Guy Steele. SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, December 1975. Reprinted in Higher-Order and Symbolic Computation 11(4):405-439, 1998, with a foreword.
• Robert Hieb, R. Kent Dybvig (en), Carl Bruggeman. Representing Control in the Presence of First-Class Continuations Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 66–77.
• Will Clinger (en), Anne Hartheimer, Eric Ost. Implementation Strategies for Continuations Proceedings of the 1988 ACM conference on LISP and Functional Programming, pp. 124–131, 1988. Journal version: Higher-Order and Symbolic Computation, 12(1):7-45, 1999.
• Christian Queinnec. Inverting back the inversion of control or, Continuations versus page-centric programming SIGPLAN Notices 38(2), pp. 57–64, 2003.