2008-08-29 23 views
21

Je suis en train de saisir le concept de continuations et j'ai trouvé plusieurs petits exemples d'enseignement comme celui-ci de la Wikipedia article:Vous cherchez des exemples de « réel » utilise des continuations

(define the-continuation #f) 

(define (test) 
    (let ((i 0)) 
    ; call/cc calls its first function argument, passing 
    ; a continuation variable representing this point in 
    ; the program as the argument to that function. 
    ; 
    ; In this case, the function argument assigns that 
    ; continuation to the variable the-continuation. 
    ; 
    (call/cc (lambda (k) (set! the-continuation k))) 
    ; 
    ; The next time the-continuation is called, we start here. 
    (set! i (+ i 1)) 
    i)) 

Je comprends ce que cette petite fonction fait, mais je ne peux pas voir une application évidente de celui-ci. Bien que je ne m'attends pas à utiliser des suites dans tout mon code de sitôt, je voudrais savoir quelques cas où ils peuvent être appropriés. Donc, je cherche des exemples de code plus explicite de ce que les continuations peuvent m'offrir en tant que programmeur.

À la votre!

Répondre

15

Dans Algo & données II nous avons utilisé ces tous les temps de « sortie » ou « retour » d'un (long) fonction

par exemple le algorthm BFS pour traverser les arbres avec a été mis en œuvre comme celui-ci:

(define (BFS graph root-discovered node-discovered edge-discovered edge-bumped . nodes) 
    (define visited (make-vector (graph.order graph) #f)) 
    (define q (queue.new)) 
    (define exit()) 
    (define (BFS-tree node) 
    (if (node-discovered node) 
     (exit node)) 
    (graph.map-edges 
    graph 
    node 
    (lambda (node2) 
     (cond ((not (vector-ref visited node2)) 
       (when (edge-discovered node node2) 
       (vector-set! visited node2 #t) 
       (queue.enqueue! q node2))) 
      (else 
       (edge-bumped node node2))))) 
    (if (not (queue.empty? q)) 
     (BFS-tree (queue.serve! q)))) 

    (call-with-current-continuation 
    (lambda (my-future) 
    (set! exit my-future) 
    (cond ((null? nodes) 
      (graph.map-nodes 
      graph 
      (lambda (node) 
       (when (not (vector-ref visited node)) 
       (vector-set! visited node #t) 
       (root-discovered node) 
       (BFS-tree node))))) 
      (else 
      (let loop-nodes 
       ((node-list (car nodes))) 
       (vector-set! visited (car node-list) #t) 
       (root-discovered (car node-list)) 
       (BFS-tree (car node-list)) 
       (if (not (null? (cdr node-list))) 
       (loop-nodes (cdr node-list))))))))) 

Comme vous pouvez le voir l'algorithme sortir lorsque le nœud découvert retourne true:

(if (node-discovered node) 
     (exit node)) 

la fonction donnera également un « retour valeur ": « noeud »

pourquoi les sorties de fonction, est à cause de cette déclaration:

(call-with-current-continuation 
     (lambda (my-future) 
     (set! exit my-future) 

lorsque nous utilisons la sortie, il va revenir à l'état avant l'exécution, vider la pile des appels et retourne la valeur que tu lui as donnée.

Donc, fondamentalement, appelez-cc est utilisé (ici) pour sauter d'une fonction récursive, au lieu d'attendre la récursion entière à la fin par lui-même (qui peut être assez cher quand faire beaucoup de travail de calcul)

un autre exemple plus petit faisant la même chose avec appel cc:

(define (connected? g node1 node2) 
    (define visited (make-vector (graph.order g) #f)) 
    (define return()) 
    (define (connected-rec x y) 
    (if (eq? x y) 
     (return #t)) 
    (vector-set! visited x #t) 
    (graph.map-edges g 
        x 
        (lambda (t) 
         (if (not (vector-ref visited t)) 
         (connected-rec t y))))) 
    (call-with-current-continuation 
    (lambda (future) 
    (set! return future) 
    (connected-rec node1 node2) 
    (return #f)))) 
3

Les continus peuvent être utilisés dans des exemples «réels» lorsque le flux du programme n'est pas linéaire ou même pas prédéterminé. Une situation familière est web applications.

+0

Oui! Je cherche des échantillons de code cependant. –

5

Les suites sont utilisées par certains serveurs Web et frameworks Web pour stocker des informations de session. Un objet de continuation est créé pour chaque session et ensuite utilisé par chaque requête dans la session.

There's an article about this approach here.

9
+1

Oui, Seaside est un bon exemple, je l'ai utilisé dans un projet de 6 mois! Je cherche des échantillons de code cependant. –

7

@Pat

Mer

Oui, Seaside est un bon exemple. J'ai parcouru son code rapidement et ai trouvé ce message illustrant le contrôle de passage entre les composants d'une manière apparemment statefull à travers le Web.

WAComponent >> call: aComponent 
    "Pass control from the receiver to aComponent. The receiver will be 
    temporarily replaced with aComponent. Code can return from here later 
    on by sending #answer: to aComponent." 

    ^AnswerContinuation currentDo: [ :cc | 
     self show: aComponent onAnswer: cc. 
     WARenderNotification raiseSignal ] 

Tellement sympa!

5

Je suis tombé sur une mise en œuvre de l'opérateur amb dans this post de http://www.randomhacks.net, en utilisant continuations.

Voici ce que l'amb opeerator fait:

# amb will (appear to) choose values 
# for x and y that prevent future 
# trouble. 
x = amb 1, 2, 3 
y = amb 4, 5, 6 

# Ooops! If x*y isn't 8, amb would 
# get angry. You wouldn't like 
# amb when it's angry. 
amb if x*y != 8 

# Sure enough, x is 2 and y is 4. 
puts x, y 

Et voici la mise en œuvre du poste:

# A list of places we can "rewind" to 
# if we encounter amb with no 
# arguments. 
$backtrack_points = [] 

# Rewind to our most recent backtrack 
# point. 
def backtrack 
    if $backtrack_points.empty? 
    raise "Can't backtrack" 
    else 
    $backtrack_points.pop.call 
    end 
end 

# Recursive implementation of the 
# amb operator. 
def amb *choices 
    # Fail if we have no arguments. 
    backtrack if choices.empty? 
    callcc {|cc| 
    # cc contains the "current 
    # continuation". When called, 
    # it will make the program 
    # rewind to the end of this block. 
    $backtrack_points.push cc 

    # Return our first argument. 
    return choices[0] 
    } 

    # We only get here if we backtrack 
    # using the stored value of cc, 
    # above. We call amb recursively 
    # with the arguments we didn't use. 
    amb *choices[1...choices.length] 
end 

# Backtracking beyond a call to cut 
# is strictly forbidden. 
def cut 
    $backtrack_points = [] 
end 

J'aime amb!

6

J'ai construit mon propre logiciel de test unitaire. Avant d'exécuter le test, je stocke la continuation avant d'exécuter le test, puis en cas d'échec, je dis (optionnellement) à l'interpréteur du schéma de passer en mode débogage, et je ré-invoque la continuation. De cette façon, je peux franchir le code problématique très facilement.

Si vos continuations sont sérialisables, vous pouvez également stocker puis en cas d'échec de l'application, puis les invoquer de nouveau pour obtenir des informations détaillées sur les valeurs variables, traces de pile, etc.

3

continuations sont une bonne alternative à thread- Dans ce modèle, au lieu de lancer un nouveau thread (lourd) chaque fois qu'une requête arrive, vous commencez simplement un travail dans une fonction. prêt à bloquer sur les E/S (c'est-à-dire en lisant depuis la base de données), vous passez une continuation dans le gestionnaire de réponse de mise en réseau.Lorsque la réponse revient, vous exécutez la continuation. cheme, vous pouvez traiter beaucoup de demandes avec juste quelques threads. Cela rend le flux de contrôle plus complexe que l'utilisation de threads de blocage, mais sous une charge importante, il est plus efficace (au moins sur le matériel actuel).

1

Que diriez-vous du Google Mapplets API? Il y a un tas de fonctions (toutes se terminant par Async) auxquelles vous passez un rappel. La fonction API fait une requête asynchrone, obtient son résultat, puis transmet ce résultat à votre callback (en tant que "prochaine chose à faire"). Cela ressemble beaucoup à continuation passing style pour moi. Ce numéro example montre un cas très simple.

map.getZoomAsync(function(zoom) { 
    alert("Current zoom level is " + zoom); // this is the continuation 
}); 
alert("This might happen before or after you see the zoom level message"); 

Comme cela est Javascript il n'y a pas tail call optimization, de sorte que la pile se développera à chaque appel dans une suite, et vous finirez par revenir le fil de contrôle du navigateur. Tout de même, je pense que c'est une belle abstraction.

0

Les suites peuvent être utilisées pour implémenter des exceptions, un débogueur.

1

Si vous devez invoquer une action asynchrone et suspendre l'exécution jusqu'à ce que vous obteniez le résultat, vous devez normalement interroger le résultat ou placer le reste de votre code dans un rappel à exécuter par l'action asynchrone à la fin.Avec les continuations, vous n'avez pas besoin de faire l'option inefficace de l'interrogation, et vous n'avez pas besoin d'emballer tout votre code pour être exécuté après l'événement asynch dans un rappel - vous venez de passer l'état actuel du code comme rappel - et le code est effectivement "réveillé" dès que l'action asynchrone est terminée.

2

L'opérateur amb est un bon exemple qui permet une programmation déclarative de type prologue. Au moment où on se parle, je suis en train de coder un logiciel de composition musicale dans Scheme (je suis un musicien avec presque aucune connaissance de la théorie derrière la musique et j'analyse juste mes propres morceaux pour voir comment les maths derrière cela fonctionne.)

En utilisant l'opérateur amb, je peux simplement remplir les contraintes qu'une mélodie doit satisfaire et laisser Scheme déterminer le résultat. Les suites sont probablement mises en Scheme à cause de la philosophie du langage, Scheme est un framework qui vous permet de réaliser n'importe quel paradigme de programmation trouvé dans un autre langage en définissant des bibliothèques dans Scheme lui-même. Les continuations servent à créer vos propres structures de contrôle abstraites telles que «retourner», «casser» ou activer la programmation déclarative. Le schéma est plus «généralisant» et demande que de telles constructions soient aussi capables d'être spécifiées par le programmeur.