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))))
Oui! Je cherche des échantillons de code cependant. –