edu.rice.cs.plt.recur
Interface Continuation<T>

All Superinterfaces:

ResolvingThunk<T>, Thunk<T>

All Known Implementing Classes:

ArgContinuation, BinaryArgContinuation, ComposedContinuation, PendingContinuation, ValueContinuation

public interface Continuation<T>
extends ResolvingThunk<T>

A thunk enabling iterative evaluation of a recursive function. If a function with a continuation return type can immediately produce the result value, it wraps the value in a simple continuation; otherwise, it wraps a recursive computation in a continuation that, when resolved, will produce the result. To produce a value from a continuation, clients may either invoke value() or iteratively invoke step() until isResolved() on the result is true.

Traditionally, continuations are functions that are threaded through all recursive invocations of some function. Such an approach allows continuation-based functions to be defined exclusively in terms of tail recursion, and to immediately return a result. Here, in contrast, we use continuations to solve two problems: first, as traditionally, they allow us to represent calling contexts without relying on the stack; and second, they delay the evaluation of recursion so that even tail recursion is prevented from filling up the stack (since Java does not perform tail-call optimization). Continuation-based methods thus must return, where T is the original return type, a Continuation<T> rather than a T. To prevent unnecessary clutter, these methods are not required to accept a continuation as a parameter; instead, they may assume that there is nothing more to be done with the result, and where this is not the case, the continuation classes' implementation of step() will handle the result appropriately.

As an example, here are two recursive functions translated to use Continuations. First, a tail-recursive method:

 boolean isEven(int x) {
   if (x == 0) { return true; }
   if (x == 1) { return false; }
   else { return isEven(x - 2); }
 }
 

This can be written using continuations as follows:

 Continuation<Boolean> isEven(int x) {
   if (x == 0) { return ValueContinuation.make(true); }
   if (x == 1) { return ValueContinuation.make(false); }
   else {
     return new PendingContinuation<Boolean>() {
       public Continuation<? extends Boolean> step() {
         return isEven(x - 2);
       }
     };
   }
 }
 

Second, a recursive method that requires on calling context:

 long sum(int n) {
   if (n == 0) { return 0l; }
   else { return sum(n-1) + n; }
 }
 

This is written with continuations thus:

 Continuation<Long> sum(final int n) {
   if (n == 0l) { return ValueContinuation.make(0l); }
   else {
     return new ArgContinuation<Long, Long>() {
       public Continuation<Long> arg() { return sum(n-1); }
       public Continuation<Long> apply(Long arg) {
         return ValueContinuation.make(arg + n);
       }
     };
   }
 }
 

In both cases, evaluation of the original function with large inputs will lead to a stack overflow, while the stack size in the continuation-based versions is bounded by a small constant.

As an illustration, an invocation of sum(3), as defined above, results in the following evaluation (using informal abbreviations to represent the continuations and lambdas involved):

 sum(3)
 = Arg(sum(2), \x.Val(x+3))
 [STEP]
 Comp(Arg(sum(1), \x.Val(x+2)), \x.Val(x+3))
 [STEP]
 Comp(Arg(sum(0), \x.Val(x+1)), \x.Val(x+2)).compose(\x.Val(x+3))
 = Comp(Arg(sum(0), \x.Val(x+1)), \y.(\x.Val(x+2))(y).compose(\x.Val(x+3)) )
 [STEP]
 Comp(Val(0), \x.Val(x+1)).compose( \y.(\x.Val(x+2))(y).compose(\x.Val(x+3)) )
 = Comp(Val(0), \z.(\x.Val(x+1))(z).compose( \y.(\x.Val(x+2))(y).compose(\x.Val(x+3)) ) )
 [STEP]
 (\x.Val(x+1))(0).compose( \y.(\x.Val(x+2))(y).compose(\x.Val(x+3)) )
 = Val(1).compose( \y.(\x.Val(x+2))(y).compose(\x.Val(x+3)) )
 = Comp(Val(1), \y.(\x.Val(x+2))(y).compose(\x.Val(x+3)) )
 [STEP]
 \x.Val(x+2))(1).compose(\x.Val(x+3))
 = Val(3).compose(\x.Val(x+3))
 = Comp(Val(3), \x.Val(x+3))
 [STEP]
 Val(6)
 

There are 6 steps: three to expand the recursion to the base case, and three to perform the necessary computation after a recursive result has been determined.

Method Summary

<R> Continuation<? extends R>	compose(Lambda<? super T,? extends Continuation<? extends R>> c) Produce a continuation that will invoke c with this object's result.
boolean	isResolved() Return true iff the continuation has been resolved to a value.
Continuation<? extends T>	step() Produce a continuation representing the next step of computation.
T	value() Iteratively resolve the continuation to a value.

Method Detail

value

T value()

Iteratively resolve the continuation to a value.

Specified by:

value in interface Thunk<T>

isResolved

boolean isResolved()

Return true iff the continuation has been resolved to a value.

Specified by:

isResolved in interface ResolvingThunk<T>

step

Continuation<? extends T> step()

Produce a continuation representing the next step of computation.

Throws:

java.lang.IllegalStateException - If isResolved() is true

compose

<R> Continuation<? extends R> compose(Lambda<? super T,? extends Continuation<? extends R>> c)

Produce a continuation that will invoke c with this object's result.