Voir la source de Continuation (informatique)

{{Ébauche|informatique}}
{{Autres projets|wiktionary = continuation}}

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 [[langage de programmation|langages de programmation]] comme en [[C (langage)|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 (informatique)|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<ref>{{Lien web |langue=en |auteur=Oleg Kiselyov |titre=An argument against call/cc |url=https://okmij.org/ftp/continuations/against-callcc.html |site=okmij.org |consulté le=2024-10-05}}</ref>.

=== En C ===
En [[C (langage)|C]], l'instruction <code>setjmp</code> 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 <code>longjmp</code> permet de restaurer l'état précédent du programme en déroutant l'exécution vers une continuation enregistrée<ref>{{Lien web |langue=en |titre=setjmp(3) - Linux manual page |url=https://man7.org/linux/man-pages/man3/setjmp.3.html |accès url=libre |site=man7.org |consulté le=2024-10-05}}</ref>.

=== 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]]<ref>{{Lien web |langue=en |auteur=[[Free Software Foundation]] |titre=Continuations (Guile Reference Manual) |url=https://www.gnu.org/software/guile/manual/html_node/Continuations.html |site=www.gnu.org |consulté le=2024-10-05}}</ref> :
<syntaxhighlight lang="scheme">
(define (f k)
  (display "toto\n")
  (k "titi\n")
  (display "tata\n"))
(display (call-with-current-continuation f))
</syntaxhighlight>Le programme ci-dessus commence par définir une fonction <code>f</code>. Puis, nous demandons d'afficher le résultat (<code>display</code>) de <code>(call-with-current-continuation f)</code>. L'instruction <code>(call-with-current-continuation f)</code> a pour effet de ''capturer'' la continuation courante (qui est d'afficher la valeur de retour grâce à la commande <code>display</code>, puis de terminer le programme) et de la passer en argument à la fonction <code>f</code>. Le programme appelle donc la fonction <code>f</code> avec l'argument <code>k</code> qui est ce futur là. La fonction est une séquence de trois instructions. La première instruction est <code>(display "toto\n")</code> et affiche <code>toto</code>. La deuxième instruction appelle la continuation <code>k</code>  passée en argument avec la valeur <code>"titi"</code>. Ainsi, on sort de la fonction <code>f</code> puisque la continuation a été capturée à l'extérieur. Après cela, la continuation s'exécute normalement : <code>display</code> s'exécute avec la valeur de retour <code>"titi"</code> de <code>(call-with-current-continuation f)</code> et le programme termine.

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

 toto
 titi
La fonction <code>call-with-current-continuation</code> est souvent abrégée par son alias <code>call/cc</code>.

== Exceptions ==
Les [[Système de gestion d'exceptions|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<ref name=":0">{{Article|langue=en|prénom1=Hayo|nom1=Thielecke|titre=''On Exceptions Versus Continuations in the Presence of State''|périodique=Programming Languages and Systems. ESOP 2000. Lecture Notes in Computer Science|volume=1782|pages=397–411|éditeur=Springer|date=2000|isbn=978-3-540-46425-9|doi=10.1007/3-540-46425-5_26|accès doi=payant|consulté le=2024-11-07|format=pdf}}, version longue, accessible gratuitement : https://www.cs.bu.edu/~kfoury/CVS-Working-Files/CS520-Fall06/Handouts/contrasting-exceptions-and-continuations.pdf</ref>. De plus, les exceptions permettent de manipuler la continuation courante implicitement. 

En effet, le bloc d'exception n'est qu'une [[syntaxe|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]] <ref>{{Lien web |langue=en |titre=Error Handling · OCaml Documentation |url=https://ocaml.org/docs/error-handling |accès url=libre |site=OCaml.org |consulté le=2024-11-07}}</ref>:<syntaxhighlight lang="ocaml">try 
  50/0 
with 
  Division_by_zero -> 42;;</syntaxhighlight>
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 <code>Division_by_zero</code>. 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<ref name=":0" />.

== 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 <code>f(g(x))</code> sont proscrits. Ces fonctions se retrouvent en quelque sorte maîtresses de leur destin, et ne se contentent plus de subir le contexte<ref>{{Référence Harvard sans parenthèses|Appel|1991|p=11-22}}</ref>.

Un des enjeux de la programmation par continuation est d'obtenir un programme [[Récursion terminale|récursif terminal]], qui après [[Compilateur|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épassement de pile|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 (informatique)|goto]]<ref>{{Référence Harvard sans parenthèses|Appel|1991|p=4-6}}</ref>.

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<ref>{{Référence Harvard sans parenthèses|Appel|1991|p=55-65}}</ref>, notamment effectuées par le compilateur [[OCaml]].

Version directe :
<syntaxhighlight lang="ocaml">
let rec fact = function 
  | 0 -> 1
  | n -> n * (fact (n - 1))
</syntaxhighlight>

Version par continuation :
<syntaxhighlight lang="ocaml">
let rec fact_cont k = function
  | 0 -> k 1
  | n -> fact_cont (function x -> k (n * x)) (n - 1)
</syntaxhighlight>
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 <code>print_int (fact 5)</code> dans le premier cas et <code>fact_cont print_int 5</code> dans le second. Pour récupérer le résultat dans le second cas, on peut simplement passer comme continuation la [[Application identité|fonction identité]] qui renvoie simplement son argument, et on peut redéfinir la première version avec :<syntaxhighlight lang="ocaml">
let fact n = fact_cont (function r -> r) n
</syntaxhighlight>[[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 (informatique)|stratégie d'évaluation]] indépendamment de celle du langage de base<ref>{{Article|langue=en|auteur1=[[John C. Reynolds]]|titre=''Definitional interpreters for higher-order programming languages''|périodique=Proceedings of the 25th ACM annual conference|série=|volume=2|numéro=|pages=717–740|éditeur=Association for Computing Machinery|date=1972-08-01|isbn=978-1-4503-7492-7|doi=10.1145/800194.805852|lire en ligne=https://dl.acm.org/doi/10.1145/800194.805852|consulté le=2024-10-05|accès url=libre|format=pdf}}</ref>.

== Interprétation logique ==
L'opérateur <code>call/cc</code> et les divers [[Structure de contrôle|opérateurs de contrôle]] équivalents, comme l'opérateur <math>\mathfrak{C}</math> de Felleisen {{Et al.}}<ref>{{Article|langue=en|auteur1=[[Matthias Felleisen]]|auteur2=Daniel P. Friedman|auteur3=Eugene Kohlbecker|auteur4=Bruce Duba|titre=''A syntactic theory of sequential control''|périodique=Theoretical Computer Science|volume=52|numéro=3|pages=205–237|date=1987-01-01|issn=0304-3975|doi=10.1016/0304-3975(87)90109-5|accès doi=libre|consulté le=2024-10-05}}</ref>, permettent de donner une interprétation calculatoire de la [[logique classique]] dans le cadre de la [[correspondance de Curry-Howard]]<ref>{{Article|langue=en|auteur1=Timothy G. Griffin|titre=''A formulae-as-type notion of control''|périodique=POPL '90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages|série=|numéro=|pages=47–58|éditeur=Association for Computing Machinery|date=1989-12-01|isbn=978-0-89791-343-0|doi=10.1145/96709.96714|accès doi=libre|lire en ligne=https://www.cl.cam.ac.uk/~tgg22/publications/popl90.pdf|consulté le=2024-10-05|accès url=libre|format=pdf}}</ref>. En effet, <code>call/cc</code> a pour type <math>((A \to B) \to A) \to A</math>, qui correspond à la [[loi de Peirce]], et <math>\mathfrak{C}</math> a pour type <math>\neg\neg A \to A</math>, où <math>\neg A = A \to \bot</math> désigne un programme qui prend un paramètre de type <math>A</math> en entrée et ne termine pas.

== En sémantique dénotationnelle ==
Il existe une [[sémantique dénotationnelle]] dite ''par passage de continuation''<ref>{{Article|langue=en|auteur1=[[John C. Reynolds]]|titre=''On the Relation between Direct and Continuation Semantics''|périodique=Automata, Languages and Programming|pages=141–156|éditeur=Springer|date=1974|isbn=978-3-662-21545-6|doi=10.1007/978-3-662-21545-6_10|accès doi=payant|lire en ligne=http://www.cs.cmu.edu/afs/cs/user/jcr/ftp/reldircont.pdf|consulté le=2024-11-17|accès url=libre|format=pdf}}</ref>. Dans cette [[sémantique des langages de programmation|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 <math>P</math> est un programme, sa sémantique <math>[\![P]\!]</math> est de type <math>\mathrm{Continuation} \to \mathrm{Continuation}</math>, où <math>\mathrm{Continuation}</math> correspond au type <math>\mathrm{Etat\ du\ programme} \to \mathrm{Effet\ observable}</math>.

== Bibliographie ==
* [[Peter J. Landin]]. ''A Generalization of Jumps and Labels'' Report. UNIVAC Systems Programming Research. {{date-|août 1965}}. Reparu dans {{Lien|langue=en|fr=Higher-Order and Symbolic Computation}}, 11(2):125-143, 1998, avec une préface de Hayo Thielecke.
* [[Drew McDermott]] et [[Gerald Jay Sussman|Gerry Sussman]]. ''The Conniver Reference Manual'' MIT AI Memo 259. {{date-|mai 1972}}.
* {{Lien|langue=en|fr=Daniel G. Bobrow}}: ''A Model for Control Structures for Artificial Intelligence Programming Languages'' IJCAI 1973.
* {{Lien|langue=en|fr=Carl Hewitt}}, [[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. {{date-|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.&nbsp;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.&nbsp;141–156, 1974.
* {{Article|prénom=John C.|nom=Reynolds|url=http://www.cs.ru.nl/~freek/courses/tt-2011/papers/cps/histcont.pdf|titre=The discoveries of continuations|journal=Lisp and Symbolic Computation|volume=6|numéro=3/4|année=1993|pages=233–248}}
* [[Gerald Jay Sussman|Gerald Sussman]] et [[Guy Lewis Steele, Jr.|Guy Steele]]. ''SCHEME: An Interpreter for Extended Lambda Calculus'' AI Memo 349, MIT Artificial Intelligence Laboratory, [[Cambridge (Massachusetts)|Cambridge, Massachusetts]], December 1975. Reprinted in Higher-Order and Symbolic Computation 11(4):405-439, 1998, with a foreword.
* [[Robert Hieb]], {{Lien|langue=en|fr=R. Kent Dybvig}}, [[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.&nbsp;66–77.
* {{Lien|William Clinger (computer scientist)|texte=Will Clinger}}, [[Anne Hartheimer]], [[Eric Ost]]. ''Implementation Strategies for Continuations'' Proceedings of the 1988 ACM conference on LISP and Functional Programming, pp.&nbsp;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.&nbsp;57–64, 2003.
* {{Ouvrage|langue=en|auteur1=Andrew W. Appel|titre=Compiling with Continuations|lieu=Cambridge|éditeur=[[Cambridge University Press]]|année=1991|isbn=978-0-521-03311-4|doi=10.1017/CBO9780511609619|accès doi=payant|consulté le=8 novembre 2024}}.

== Références ==
[[Catégorie:Informatique théorique]]
[[Catégorie:Programmation informatique]]
[[Catégorie:Structure de contrôle]]
[[Catégorie:Calculabilité]]
[[Catégorie:Logique mathématique]]
[[Catégorie:Théorie de la démonstration]]
[[Catégorie:Théorie des types]]
<references />
{{Portail|informatique|logique}}