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.

Continuations de première classe

Dans certains langages de programmation comme en C ou en Scheme, on peut manipuler les continuations 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é. Cette utilisation des continuations a été critiquée pour conduire à du code difficile à lire et sous-performant[1].

En C

En C, l'instruction setjmp permet de capturer une continuation (en fait, cela stocke l'état interne du programme dans une variable, notamment la valeur du compteur ordinal et du registre de pile), et l'instruction longjmp permet de restaurer l'état précédent du programme en déroutant l'exécution vers une continuation enregistrée[2].

En Scheme

Dans certains langages de programmation fonctionnelle, une continuation peut être représentée par une fonction qui peut prendre divers arguments 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é). Voici un exemple en Scheme[3] :

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

Le programme ci-dessus commence 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. Le programme appelle donc la fonction f avec l'argument k qui est ce futur là. La fonction est une séquence de trois instructions. La première instruction est (display "toto\n") et affiche toto. La deuxième instruction appelle la continuation k passée en argument avec la valeur "titi". Ainsi, on sort de la fonction f 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.

Pour résumer, quand ce programme est exécuté, l'instruction (display "tata\n") a été ignorée. Le programme a pour sortie à l'écran :

toto
titi

La fonction call-with-current-continuation est souvent abrégée par son alias call/cc.

Exceptions

Les exceptions ont beaucoup de choses en commun avec les continuations de première classe, car les deux permettent de résoudre des problèmes similaires[4]. De plus, les exceptions permettent de manipuler la continuation courante implicitement.

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 qui traite l'exception) 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 dont on rattrape les exceptions, alors on appellera la continuation correspondante. Une fois le bloc d'exception exécuté, on restore le gestionnaire d'exception précédent. L'exemple suivant en OCaml [5]:

try 
  50/0 
with 
  Division_by_zero -> 42;;

retourne

- : int = 42

En effet, 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. Enfin, si une autre erreur est levée, elle est propagée au bloc parent.

Néanmoins, les continuations de première classe et les exceptions ne sont pas interchangeables. En effet, dans un langage sans mécanisme de mémoire mutable, les continuations ne peuvent pas simuler les exceptions, ni réciproquement. De plus, même combinées, les exceptions et les continuations ne peuvent pas simuler une mémoire mutable. Une façon de distinguer les deux est de dire que les exceptions ne peuvent pas faire qu'une fonction retourne deux fois, tandis que les continuations ne peuvent pas totalement ignorer le contexte appelant. En revanche, dans un langage avec mémoire mutable, les exceptions ne peuvent pas simuler les continuations, alors que les continuations peuvent simuler les exceptions[4].

Programmation par continuation

En programmation fonctionnelle, la programmation par continuation, en anglais : continuation-passing style (CPS), désigne une technique de programmation consistant à n'utiliser que de simples appels de fonctions 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. De plus, les appels imbriqués de la forme f(g(x)) sont proscrits. Ces fonctions se retrouvent en quelque sorte maîtresses de leur destin, et ne se contentent plus de subir le contexte[6].

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, comme l'illustre l'exemple suivant qui calcule la fonction factorielle en OCaml. Ceci se traduit par une moindre consommation de la pile, limitant les risques de débordement, ainsi que par flot de contrôle explicite, permettant de compiler facilement un programme fonctionnel vers une représentation plus bas niveau, par exemple vers un assembleur avec l'instruction goto[7].

Il est possible de transformer un programme quelconque en un programme équivalent en CPS. C'est une passe de compilation courante pour les langages fonctionnels[8], notamment effectuées par le compilateur OCaml.

Version directe :

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

Version par continuation :

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

On remarque que tous les appels de fonctions sont terminaux.

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_cont print_int 5 dans le second. Pour récupérer le résultat dans le second cas, on peut simplement passer comme continuation la fonction identité qui renvoie simplement son argument, et on peut redéfinir la première version avec :

let fact n = fact_cont (function r -> r) n

John C. Reynolds a notamment montré que l'utilisation de ce style de programmation permettait d'implémenter facilement un interpréteur pour un langage de programmation avec des fonctions d'ordre supérieur y compris si le langage dans lequel l'interpréteur est codé n'en dispose pas, et de choisir la stratégie d'évaluation indépendamment de celle du langage de base[9].

Interprétation logique

L'opérateur call/cc et les divers opérateurs de contrôle équivalents, comme l'opérateur ${\displaystyle {\mathfrak {C}}}$ de Felleisen et al.[10], permettent de donner une interprétation calculatoire de la logique classique dans le cadre de la correspondance de Curry-Howard[11]. En effet, call/cc a pour type ${\displaystyle ((A\to B)\to A)\to A}$, qui correspond à la loi de Peirce, et ${\displaystyle {\mathfrak {C}}}$ a pour type ${\displaystyle \neg \neg A\to A}$, où ${\displaystyle \neg A=A\to \bot }$ désigne un programme qui prend un paramètre de type ${\displaystyle A}$ en entrée et ne termine pas.

En sémantique dénotationnelle

Il existe une sémantique dénotationnelle dite par passage de continuation[12]. 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 ${\displaystyle P}$ est un programme, sa sémantique ${\displaystyle [\![P]\!]}$ est de type ${\displaystyle \mathrm {Continuation} \to \mathrm {Continuation} }$, où ${\displaystyle \mathrm {Continuation} }$ correspond au type ${\displaystyle \mathrm {Etat\ du\ programme} \to \mathrm {Effet\ observable} }$.

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.
• (en) Andrew W. Appel, Compiling with Continuations, Cambridge, Cambridge University Press, 1991 (ISBN 978-0-521-03311-4, DOI 10.1017/CBO9780511609619 ).

Références

1. (en) Oleg Kiselyov, « An argument against call/cc », sur okmij.org (consulté le 5 octobre 2024)
2. (en) « setjmp(3) - Linux manual page » , sur man7.org (consulté le 5 octobre 2024)
3. (en) Free Software Foundation, « Continuations (Guile Reference Manual) », sur www.gnu.org (consulté le 5 octobre 2024)
4. (en) Hayo Thielecke, « On Exceptions Versus Continuations in the Presence of State », Programming Languages and Systems. ESOP 2000. Lecture Notes in Computer Science, Springer, vol. 1782,‎ 2000, p. 397–411 (ISBN 978-3-540-46425-9, DOI 10.1007/3-540-46425-5_26 ), version longue, accessible gratuitement : https://www.cs.bu.edu/~kfoury/CVS-Working-Files/CS520-Fall06/Handouts/contrasting-exceptions-and-continuations.pdf
5. (en) « Error Handling · OCaml Documentation » , sur OCaml.org (consulté le 7 novembre 2024)
6. Appel 1991, p. 11-22
7. Appel 1991, p. 4-6
8. Appel 1991, p. 55-65
9. (en) John C. Reynolds, « Definitional interpreters for higher-order programming languages », Proceedings of the 25th ACM annual conference, Association for Computing Machinery, vol. 2,‎ 1^er août 1972, p. 717–740 (ISBN 978-1-4503-7492-7, DOI 10.1145/800194.805852, lire en ligne [PDF], consulté le 5 octobre 2024)
10. (en) Matthias Felleisen, Daniel P. Friedman, Eugene Kohlbecker et Bruce Duba, « A syntactic theory of sequential control », Theoretical Computer Science, vol. 52, n^o 3,‎ 1^er janvier 1987, p. 205–237 (ISSN 0304-3975, DOI 10.1016/0304-3975(87)90109-5 )
11. (en) Timothy G. Griffin, « A formulae-as-type notion of control », POPL '90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Association for Computing Machinery,‎ 1^er décembre 1989, p. 47–58 (ISBN 978-0-89791-343-0, DOI 10.1145/96709.96714 , lire en ligne [PDF], consulté le 5 octobre 2024)
12. (en) John C. Reynolds, « On the Relation between Direct and Continuation Semantics », Automata, Languages and Programming, Springer,‎ 1974, p. 141–156 (ISBN 978-3-662-21545-6, DOI 10.1007/978-3-662-21545-6_10 , lire en ligne [PDF], consulté le 17 novembre 2024)