StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In Algo & Data II we used these all the times to "exit" or "return" from a (long) function</p> <p>for example the BFS algorthm to traverse trees with was implemented like this:</p> <pre><code>(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))))))))) </code></pre> <p>As you can see the algorithm will exit when the node-discovered function returns true:</p> <pre><code> (if (node-discovered node) (exit node)) </code></pre> <p>the function will also give a "return value": 'node'</p> <p>why the function exits, is because of this statement:</p> <pre><code>(call-with-current-continuation (lambda (my-future) (set! exit my-future) </code></pre> <p>when we use exit, it will go back to the state before the execution, emptying the call-stack and return the value you gave it.</p> <p>So basically, call-cc is used (here) to jump out of a recursive function, instead of waiting for the entire recursion to end by itself (which can be quite expensive when doing lots of computational work)</p> <p>another smaller example doing the same with call-cc:</p> <pre><code>(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)))) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload