The language Scheme [R4R] provides continuations as first class objects. Continuations are useful for implementing a wide variety of advanced control constructs, including non-local exits, backtracking, and coroutines.
Whenever an expression is evaluated there is a continuation which is waiting for the result of the expression. The continuation represents an entire (default) future for the computation and may be represented as a snapshot of the current state of the program. A language which provides continuations as first-class objects allows a continuation to be saved, and later re-invoked. This re-invocation puts the computation back to the point where the continuation was saved, and additionally passes a result back to the continuation, in place of the result of the original expression.
For dynamic evaluation, the points we would mark are equalities in splitting points. In this case there are two possible ways to continue the computation, one for each branch of the tree. We therefore save the continuation of the equality test in a global table, returning false as the result of the equality test. After execution of this side of the splitting tree has completed, we can invoke this continuation with a true argument to force execution along the other path of the splitting tree. This serialises the computation as a sequence of disjoint paths in the splitting tree -- there is no redundant execution of code when continuations are used.
The Scheme primitive which provides this snapshot is call-with-current-continuation, abbreviated to call/cc. This is a Scheme primitive which passes an object representing the continuation of the call/cc expression to the argument of the call/cc. The argument should be a function that takes one parameter. The following illustrates the use of call/cc:
(define *the-cont* nil) ;; continuation holder
(define *the-val* nil) ;; value for continuation
;; Equality. If either argument is a symbol, we save
;; the current continuation, and return false. If
;; neither is a symbol, we call = as usual. In Scheme
;; false is #f, true is #t.
(define (my-equal a b)
(if (or (symbol? a) (symbol? b))
(call/cc
(lambda (cont)
;; save the continuation,
(set! *the-cont* cont)
;; and a value for it
(set! *the-val* #t)
#f))
(= a b)))
;; if x is zero, then return good, bad otherwise.
(define (test x)
(if (my-equal x 0) "good" "bad"))
> (test 3) ;; simple case, 3 <> 0 value is: "bad" > (test 'x) ;; saves a continuation value is: "bad" ;; and returns as if false ;; restart the computation from my-equal with the ;; value it saved (#t in this case) > (*the-cont* *the-val*) value is: "good" ;; we get this result
The above example shows the basic idea behind continuations, as used in dynamic evaluation -- an equality test can (by definition) only return true or false, but we use a continuation in order to be able to back-track to the point of the test, so that we can follow both possible execution paths. However, we must identify cases which are provably true or provably false, which in the case of a constructible closure of a field is a significant task.
Note that a continuation saves dynamic information, but not global variables -- clearly some state has to be left alone when restoring a continuation, because without that a program would have no way of discovering whether it was continuing from a re-invoked continuation, or from normal execution.
For the purposes of dynamic evaluation, it is possible to simulate continuations in C using the fork function. This is available under UNIX-style operating systems -- in this case a continuation is really a whole separate process which is allowed to compute up to the end of the allCases function, and then return its result to its caller.