Qu'est-ce que call/cc?

Question

Qu'est-ce que call/cc?

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

j'ai une formation en programmation web et de la programmation orientée objet. Je comprends aussi 6502 assemblée et a eu un léger randez-vous avec Erlang. Cependant encore, je ne peut pas envelopper la tête autour de call / cc.

38

callcc continuations lambda lambda-calculus scheme

demandé sur Michał Rudnicki 2009-03-05 01:30:32

10 réponses

score 11 · Answer 1

Look, j'ai trouvé ce Continuation Passing Style meilleure description sur ce sujet.

Voici une copie dépouillée de 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 en quelque sorte, et de reprendre ce même état plus tard. Sur en plus d'une telle primitive, diverses formes de manipulation d'exception et des trucs C-like longjmp peuvent être mis en œuvre.
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);
cela peut être transformé comme suit: Nous ajoutons un argument supplémentaire à chaque fonction, qui sera utilisé pour passer la continuation de la fonction. Cette continuation est une valeur de fonction représentant les actions qui doivent se produire après la fonction 'retourne'. La pile (call) devient obsolète dans la continuation-passing style-quand une fonction appelle une autre la fonction, qui est la dernière chose qu'il fait. Au lieu d'attendre que la fonction appelée revienne, elle met tout travail qu'elle veut faire par la suite dans une continuation, qu'elle passe à 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 document huuuuge à capitaliser. Le traverser en une seule fois prend cinq secondes, et geler le navigateur pendant cinq secondes est plutôt de mauvais style. Considérez cette modification simple de capitaliseText (ne faites pas attention à l'laid global):
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 noeuds, le calcul est interrompu pendant cent millisecondes pour donner à l'interface du navigateur un moment pour répondre à l'entrée de l'utilisateur. Un très forme primitive de filetage ― vous pouvez même exécuter plusieurs calculs en même temps comme ça.

une application plus utile de ceci est liée à XMLHttpRequests, ou aux différents hacks IFRAME et SCRIPT tag utilisés pour les simuler. Ceux-ci exigent toujours un à travailler avec une sorte de mécanisme de rappel pour gérer les données que le serveur renvoie. Dans des cas simples, une fonction triviale fera l'affaire, ou quelques globals peuvent être utilisés 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 rendre une certaine valeur à son interlocuteur, les continuations simplifient considérablement les choses. Vous enregistrez juste la continuation comme le rappel, et votre calcul est repris quand la demande sera terminée.

score 22 · Answer 2

pour le comparer à C, la continuation courante est comme l'état courant de la pile. Il a toutes les fonctions en attente du résultat de la fonction courante pour finir afin qu'ils puissent reprendre l'exécution. La variable capturée comme continuation courante est utilisée comme une fonction, sauf qu'elle prend la valeur fournie et la renvoie à la pile d'attente. Ce comportement est similaire à la fonction C longjmp où vous pouvez retourner aux parties inférieures de la pile immédiatement.

(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 une suite n'est qu'une continuation peut être utilisée à tout moment dans le programme, même si l'état de la pile a changé. Cela signifie que vous pouvez essentiellement restaurer des versions plus anciennes de la pile et les utiliser encore et encore, conduisant à 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é d'enregistrer et de restaurer l'état d'un programme a beaucoup en commun avec le multithreading. En fait, vous pouvez implémenter votre propre ordonnanceur de thread en utilisant des continuations, comme j'ai essayé d'illustrer ici .

score 7 · Answer 3

un exemple trivial d'utilisation de la suite serait d'implémenter un gestionnaire de thread (fibre si vous le souhaitez) sur une machine monoprocesseur. L'ordonnanceur interrompt le flux d'exécution périodiquement (ou, dans le cas de fibres, est invoqué à divers points stratégiques du code), sauf le état de continuation (correspondant au fil courant ), puis passer à un autre suite état (correspondant à un fil différent dont l'état a été sauvegardé précédemment.)

se référant à votre arrière-plan d'assemblage, l'état de continuation capturerait des détails tels que le pointeur d'instruction, les registres, et le contexte de pile (pointeur) , pour être sauvé et restauré à 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 suspendu) passant le contrôle l'un à l'autre en utilisant des contextes de continuation au lieu du paradigme" classique call . Ils fonctionneraient sur des données globales (partagées) plutôt que sur des paramètres. Ceci est dans une certaine mesure plus flexible que call en ce sens que la pile n'a pas à remonter puis descendre ( calls sont emboîtés ), mais le contrôle peut se passer arbitrairement.

essayer de visualiser ce concept dans un langage tel que C, imaginez avoir une grande boucle avec une seule déclaration switch(continuation_point) { case point1: ... } , où chaque case correspond à une suite-savepoint, et où le code à l'intérieur de chaque case peut modifier la valeur de continuation_point et céder le contrôle à celui continuation_point par break ing à partir du switch et engager la prochaine itération dans la boucle.

Quel est le contexte de votre question? Tout les scénarios particuliers, vous êtes intéressé? Tout langage de programmation particulier? L'exemple fil/fibre ci-dessus est-il suffisant?

score 5 · Answer 4

la chose qui m'a aidé est l'idée que dans un langage traditionnel avec des appels de fonction vous passez implicitement une suite chaque fois que vous faites un appel de fonction.

avant de passer au code d'une fonction, vous enregistrez un État sur la pile (c'est-à-dire que vous appuyez sur votre adresse de retour et que la pile contient déjà vos locaux). Il s'agit essentiellement d'une continuation. Lorsque la fonction est terminée, elle doit déterminer où envoyer le flux d'exécution. Il utilise le la suite stockée sur la pile, en sautant l'adresse de retour et en sautant vers elle.

D'autres langues généralisent cette idée de continuations 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é fait.

modifier sur la base du commentaire:

la suite est l'état d'exécution complète. À tout moment de l'exécution, vous pouvez diviser le programme en deux parties (dans le temps, pas dans l'espace) - ce qui a couru jusqu'à présent, et tout ce qui va courir à partir d'ici. L'actuel "suite" est "tout ce qui va exécuter à partir d'ici" (vous pouvez voir ça comme une sorte de fonction qui va faire tout le reste de votre programme aurais fait). Ainsi, la fonction que vous fournissez à call/cc passe la suite qui était courante lorsque call/cc a été invoquée. La fonction peut utiliser la suite pour retourner l'exécution à la call/cc déclaration (plus probable bien qu'il va passer la suite autour de quelque chose d'autre, parce que si elle l'a utilisé directement, il pourrait faire un simple retour à la place).

score 4 · Answer 5

quand j'ai essayé de comprendre call/cc, j'ai trouvé cette page appel-avec-courant-continuation-for-C-programmers utile.

score 3 · Answer 6

Imaginez que votre scénario est une scène de jeu vidéo. Call / cc est comme une étape bonus.

dès que vous le touchez, vous êtes transféré à l'étape bonus (i.e. la définition de la fonction transmise comme argument à call/cc [f dans ce cas]).

les étapes Bonus sont différentes des étapes ordinaires parce que d'habitude ils ont un élément (i.e. l'argument de la fonction passée à call/cc) que si vous la touchez vous perdez et sont transportés de nouveau à l'étape normale.

ainsi il n'importe pas s'il y a beaucoup de args , quand vous atteignez l'un d'eux son plus. Ainsi notre exécution atteint (arg 42) et la renvoie à la somme (+ 42 10) .

il y a aussi quelques remarques qui valent noticing:

toutes les fonctions ne peuvent pas être utilisées avec call/cc. Depuis elle s'attend à une poursuite (qui est une fonction), vous ne pouvez pas avoir un f comme ceci: (define f (lambda (k) (+ k 42)) , parce que vous ne pouvez pas sum a fonction.
vous ne pouvez pas non plus avoir (define f (lambda (k) (f 42 10))) parce que la suite n'attend qu'un seul argument.
vous pouvez finir sans touching aucune sortie, dans ce cas la fonction procède comme toute fonction ordinaire (par exemple (define f (lambda (k) 42) finitions et retourne 42).

score 2 · Answer 7

la meilleure explication que j'ai vue est dans le livre de Paul Graham, On Lisp .

2

répondu Jacob Gabrielson 2009-03-04 22:42:58

score 2 · Answer 8

il y a plusieurs niveaux pour comprendre call/cc. D'abord, vous devez comprendre les termes et la façon dont le mécanisme fonctionne. Ensuite, une compréhension de comment et quand call/cc est utilisé dans la vie réelle" programmation n'est nécessaire.

le premier niveau peut être atteint en étudiant CPS, mais il ya alternative.

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

Daniel P. Friedman. "Les Applications de Continuations: Tutoriel Invité". 1988 principes des langages de programmation (POPL88). Janvier 1988.

score 2 · Answer 9

le modèle que j'ai utilisé pour comprendre les continuations d'un point de vue impératif est qu'il s'agit d'une copie de la pile d'appels combinée avec un pointeur vers l'instruction suivante.

Call / cc appelle une fonction (transmise comme argument) avec la suite comme argument.

score 1 · Answer 10

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

Las etiquetas más populares

Qu'est-ce que call/cc?

10 réponses