Basically, a continuation stores the state of your program. Some languages expose this to you (i.e, Scheme and C -- C via setjmp) and some do not. In Scheme, a call looks like (call/cc FUNC) where FUNC is passed in as its parameter the continuation. call/cc returns with whatever FUNC returns, but there's a catch. Any time the continuation (the parameter) is called, it's as if call/cc returned that value at that exact state and time (time?) in the execution that call/cc was originally called. You essentially store the entire state of your program at one given time, and you can revert back to it. It's basically time travel (or as close as we are to it).
This example shows it in a cool context. Ok, first let's show you how you can infinite loop without ever using recursion or loops and print 0 -> infinity:
#lang racket
(define (infinite-print)
(let* ((a (call/cc (lambda (k)
(cons 0 k))))
(b (car a))
(c (cdr a))
)
(printf "~a\n" b)
(c (cons (+ b 1) c))
)
)
(infinite-print)
Btw, this is using racket, an implementation (and extension -- though it also lacks some features) of Scheme.
Before getting into a slightly more complicated example, it is helpful to see *how* you actually can do this without using a loop or recursion, perhaps with a small venture into pseudo-assembly. Let's suppose %ip is the instruction pointer, the numbers on the left are addresses in memory, and %r1 holds 0 initially, then this would look something like:
1 print %r1
2 mov %r1 + 1 -> %r1
3 mov 1 -> %ip # if we want to be really pedantic. after the instruction executes (assuming fixed size), this should be 0, so then +1 to 1
Which is essentially what the continuation is doing (likely not this optimized though). One way to think of a continuation is storing a "ip/ep" pair (instruction ptr/environment ptr). Saving the environment and making sure it's still around when you "continue" is a different story. So it literally is restoring your instruction pointer, as opposed to using any sort of "jump" (like loops) or "call" (in recursion) that you might otherwise use.
Ok, moving on, here's a slightly more complicated example, where you can generate all the unique pairs in a list and output them (note, due to the way continuations work, it's more simple to just have a side effect than keep track of state, but you can see how I did keep track of state with an extra data structure in the 'remove-duplicates' method):
#lang racket
;; implementation 1
(define (output-unique-pairs og)
(define (give-pairs g full)
(let*
(
(context (call/cc (lambda (k) (cons k full))))
(k (car context))
(rem (cdr context))
) ;; note that this is a common paradigm
(if (null? rem)
'done
(let ((h (car rem)))
(if (< g h)
(printf "~a ~a\n" g h)
'nothing)
(k (cons k (cdr rem)))
)
)
)
)
(define (remove-dupes l)
(let*
(
(context (call/cc (lambda (k) (cons k (cons '() l)))))
(k (car context))
(cur (cadr context))
(later (cddr context))
)
;; cheating, since member and append probably use recursion
;; but that's enough...
(if (null? later)
cur
(if (member (car later) cur)
(k (cons k (cons cur (cdr later))))
(k (cons k (cons (append cur (list (car later))) (cdr later))))
)
)
)
)
(let* (
(og (remove-dupes og))
(context (call/cc (lambda (k) (cons k og))))
(k (car context))
(rem (cdr context))
)
(if (null? rem)
'done
(begin
(give-pairs (car rem) og)
(k (cons k (cdr rem)))
)
)
)
)
(output-unique-pairs '(1 1 2 3 3 4 5))
;; implementation 2
;; higher-order functional
;; FILL IN HERE ...
Hopefully somewhat educational, and also pretty cool.