Question

J'ai essayé à plusieurs reprises de saisir le concept des continuations et call / cc . Chaque tentative était un échec. Quelqu'un peut-il m'expliquer s'il vous plaît ces concepts, idéalement avec des exemples plus réalistes que ceux-ci sur Wikipedia ou dans d'autres publications SO.

J'ai de l'expérience en programmation Web et en POO. Je comprends aussi l’assemblage du 6502 et j’ai eu une petite promenade avec Erlang. Cependant, je ne peux toujours pas comprendre les appels / cc.

Était-ce utile?

La solution

Écoutez, j'ai trouvé cette style de passage en continu sur ce sujet.

Voici une copie dépouillée des détails de cet article:

  

Auteur: Marijn Haverbeke   Date: 24 juillet 2007

     

La fonction call-with-current-continuation de Scheme permet de capturer un calcul, un état de la pile d'appels pour ainsi dire, et de reprendre ce même état ultérieurement. En plus d’une telle primitive, diverses formes de gestion des exceptions et d’astuces longjmp similaires à celles du C peuvent être implémentées. 

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);
     

Ceci peut être transformé comme suit: Nous ajoutons un argument supplémentaire à chaque fonction, qui sera utilisé pour passer à la suite de la fonction. Cette continuation est une valeur de fonction représentant les actions à exécuter après le retour de la fonction. La pile (d'appels) devient obsolète dans le style de passage de continuation & # 8213; quand une fonction appelle une autre fonction, c'est la dernière chose qu'elle fait. Au lieu d'attendre le retour de la fonction appelée, il place le travail qu'il souhaite effectuer par la suite dans une continuation qu'il transfère à la fonction. 

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});
     

Imaginez que nous ayons un énorme document à capitaliser. Il suffit de cinq secondes pour la parcourir en une fois, et geler le navigateur pendant cinq secondes est plutôt mauvais. Considérez cette simple modification de capitaliseText (ne faites pas attention au mondial laid): 

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}
     

Maintenant, tous les vingt nœuds, le calcul est interrompu pendant une centaine de millisecondes pour donner à l’interface du navigateur un moment pour répondre aux commentaires de l’utilisateur. Une forme très primitive de threading & # 8213; vous pouvez même exécuter plusieurs calculs en même temps comme ceci.

     

Une application plus communément utile de ceci est liée à XMLHttpRequests, ou aux divers hacks de balises IFRAME et SCRIPT utilisés pour les simuler. Celles-ci nécessitent toujours de travailler avec un mécanisme de rappel pour gérer les données renvoyées par le serveur. Dans les cas simples, une fonction triviale fera l'affaire, ou quelques globales peuvent être utilisées pour stocker l'état du calcul qui doit être repris après le retour des données. Dans les cas complexes, par exemple lorsque les données sont utilisées par une fonction qui doit renvoyer une valeur à l'appelant, les continuations simplifient considérablement les choses. Vous n’enregistrez que la continuation en tant que rappel et votre calcul reprend lorsque la demande est terminée.

Autres conseils

Pour le comparer à C, la continuation actuelle ressemble à l’état actuel de la pile. Toutes les fonctions attendent que le résultat de la fonction en cours se termine afin qu'elles puissent reprendre l'exécution. La variable capturée en tant que continuation actuelle est utilisée comme une fonction, sauf qu'elle prend la valeur fournie et la renvoie à la pile en attente. Ce comportement est similaire à la fonction C longjmp où vous pouvez revenir immédiatement aux parties inférieures de la pile. . 

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

Une différence essentielle entre la pile C et la continuation est qu’une continuation peut être utilisée à n’importe quel point du programme, même si l’état de la pile a changé. Cela signifie que vous pouvez essentiellement restaurer des versions antérieures de la pile et les utiliser encore et encore, entraînant ainsi un flux de programme unique. 

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

La possibilité de sauvegarder et de restaurer l'état d'un programme a beaucoup en commun avec le multithreading. En fait, vous pouvez implémenter votre propre planificateur de thread à l'aide de continuations, comme j'ai tenté d'illustrer ici .

Un exemple trivial d'utilisation de la continuation serait de mettre en œuvre un gestionnaire de threads (fibre si vous le souhaitez) sur une machine à processeur unique. Le planificateur interromprait périodiquement le flux d’exécution (ou, dans le cas de fibres, serait invoqué à divers endroits stratégiques du code), enregistrerait le état de continuation (correspondant au thread actuel ), puis passez à un état de continuation différent (correspondant à un autre thread dont l'état a été enregistré précédemment.)

En vous référant à l'arrière-plan de votre assemblage, l'état de continuation capturera des détails tels que le pointeur d'instruction, les registres et le contexte de pile (pointeur) , à enregistrer et à restaurer à volonté.

Une autre façon d'utiliser la continuation serait de penser à remplacer les appels de méthode par plusieurs entités de type thread qui coexistent en parallèle (en cours d'exécution ou en suspension) en passant le contrôle l'une à l'autre en utilisant des contextes de continuation. du paradigme 'classique' appel . Ils opéreraient sur des données globales (partagées) au lieu de compter sur des paramètres. C’est dans une certaine mesure plus souple que appel dans le sens où la pile ne doit pas nécessairement être liquidée puis désactivée (les appels sont imbriqués ), mais le contrôle peut circuler arbitrairement.

Si vous essayez de visualiser ce concept dans un langage tel que le C, imaginez avoir une grande boucle avec une seule instruction switch (continuation_point) {case point1: ...} , où chaque observation correspond à un point de continuation-save, et où le code contenu dans chaque observation peut modifier la valeur de continuation_point et laisser le contrôle à celui-ci. continuation_point en séparez du commutateur et engagez la prochaine itération dans la boucle.

Quel est le contexte de votre question? Des scénarios particuliers vous intéressent? Un langage de programmation particulier? L’exemple fil / fibre ci-dessus est-il suffisant?

Ce qui m'a aidé, c'est l'idée que dans un langage traditionnel avec des appels de fonction, vous passez implicitement une continuation chaque fois que vous appelez une fonction.

Avant de passer au code d’une fonction, vous enregistrez un état sur la pile (c’est-à-dire que vous insérez votre adresse de retour et que la pile contient déjà vos sections locales). C'est essentiellement une continuation. Lorsque la fonction est terminée, elle doit déterminer où envoyer le flux d'exécution. Il utilise la suite stockée sur la pile, en sautant l’adresse de retour et en y sautant.

D'autres langues généralisent cette idée de suites vous permettant de spécifier explicitement où poursuivre l'exécution du code, plutôt que de continuer implicitement à partir de l'endroit où l'appel de fonction a été effectué.

EDIT sur la base du commentaire:

La suite correspond à l'état d'exécution complète. A tout moment de l'exécution, vous pouvez diviser le programme en deux parties (dans le temps et non dans l'espace): ce qui a fonctionné jusqu'ici et tout ce qui va se dérouler à partir de maintenant. La " suite actuelle " est le "tout ce qui va courir d'ici" (vous pouvez penser à cela comme une fonction qui fera tout ce que le reste de votre programme aurait fait). Ainsi, la fonction que vous fournissez à call / cc reçoit la continuation qui était en cours lorsque call / cc a été appelé. La fonction peut utiliser la continuation pour renvoyer l'exécution à l'instruction call / cc (plus probable si elle transmettra la continuation à autre chose, car si elle l'utilisait directement, elle pourrait faire un retour simple à la place. ).

Quand j’essayais de comprendre call / cc, j’ai trouvé ceci La page appelez avec la suite du programme pour les programmeurs C a été utile.

La meilleure explication que j'ai vue se trouve dans le livre de Paul Graham, Sur Lisp .

Imaginez que votre script soit une étape de jeu vidéo. Call / cc est comme une étape de bonus.

parallèle entre l'étape bonus et l'appel / cc

Dès que vous le touchez, vous êtes transféré vers l'étape bonus (c'est-à-dire la définition de la fonction transmise en tant qu'argument à call / cc [f dans ce cas]).

Les étapes bonus sont différentes des étapes ordinaires car elles comportent généralement un élément (c'est-à-dire que l'argument de la fonction transmise à call / cc) que vous perdez si vous le touchez. et sont ramenés au stade normal.

parallèle entre l'étape de bonus de sortie et les arguments de la fonction call / cc

Donc, peu importe s'il y a beaucoup de arguments , lorsque vous atteignez l'un d'eux, c'est terminé. Ainsi, notre exécution atteint (arg 42) et renvoie la somme (+ 42 10) .

Il y a également quelques remarques qui méritent d'être notées:

  • Toutes les fonctions ne peuvent pas être utilisées avec call / cc. Puisqu'il attend un suite (c'est une fonction), vous ne pouvez pas avoir un f comme ceci: (définir f (lambda (k) (+ k 42)) , car vous ne pouvez pas somme a une fonction.
  • De même, vous ne pouvez pas avoir (définir f (lambda (k) (f 42 10))) parce que la suite n'attend qu'un argument.
  • vous pouvez finir sans toucher aucune sortie, dans ce cas, la fonction se déroule comme suit: toute fonction ordinaire (par exemple, (définir f (lambda (k) 42) ) se termine et renvoie 42).

Il existe plusieurs niveaux pour comprendre call / cc. Vous devez d’abord comprendre les termes et le fonctionnement du mécanisme. Ensuite, une compréhension de quand et comment l'appel / cc est utilisé dans la "vraie vie" la programmation est nécessaire.

Le premier niveau peut être atteint en étudiant CPS, mais il existe alternatives.

Pour le deuxième niveau, je recommande le classique suivant de Friedman.

Daniel P. Friedman. "Applications of Continuations: Invited Tutorial". 1988 Principes des langages de programmation (POPL88). Janvier 1988.

Consultez la description et la mise en oeuvre de call / cc pour FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with -continuations.aspx

Le modèle que j’ai utilisé pour comprendre les suites d’un point de vue impératif est qu’il s’agit d’une copie de la pile d’appel combinée avec le pointeur sur l’instruction suivante.

Call / cc appelle une fonction (transmise en tant qu'argument) avec la continuation en tant qu'argument.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top